pith. sign in

arxiv: 2606.28641 · v1 · pith:ODFJTIMKnew · submitted 2026-06-26 · 🧮 math.ST · stat.TH

Revisiting local regression: shape regularity, uniform rates, and the limits of random splits

J\'er\'emy Bettinger , Fran\c{c}ois Portier , Adrien Saumard This is my paper

Pith reviewed 2026-06-30 00:21 UTC · model grok-4.3

classification 🧮 math.ST stat.TH
keywords local regressionshape regularityLipschitz functionsk-nearest neighborsdecision treesuniform ratesVC classesnon-asymptotic analysis
0
0 comments X

The pith

Shape regularity of localizing sets is necessary and sufficient for local averaging estimators to reach optimal rates for Lipschitz regression, up to logarithmic factors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that local averaging estimators for Lipschitz regression functions achieve their best possible pointwise and uniform rates precisely when the sets over which they average have nearly isotropic shape. This necessity and sufficiency is proved non-asymptotically, including an explicit counter-example where anisotropic sets produce slower rates. The same condition explains why the k-nearest-neighbor rule succeeds even on unbounded domains, while standard random-split tree constructions fail because cell aspect ratios grow exponentially. A modified tree rule that simply rejects splits violating shape regularity restores the optimal rate and is accompanied by a uniform deviation bound.

Core claim

Shape regularity is both necessary and sufficient to attain optimal rates, up to logarithmic factors. Necessity is established non-asymptotically through an explicit anisotropic example. The k-nearest neighbor rule is shape-regular by construction and attains the optimal rate even on unbounded supports. The popular random-split condition for trees does not guarantee optimal rates because the cell aspect ratio diverges exponentially with depth. A tree construction that enforces shape regularity through a constraint on admissible splits restores the optimal rate for Lipschitz functions.

What carries the argument

shape-regular local maps, where averaging is performed over sets with an almost isotropic geometry

If this is right

  • The k-nearest neighbor estimator attains the optimal uniform rate without requiring bounded support.
  • Random-split trees produce cells whose aspect ratios diverge exponentially, so shape regularity fails with positive probability.
  • Enforcing a simple geometric constraint on splits in trees yields a uniform deviation inequality and the optimal rate.
  • The characterization holds for both pointwise and sup-norm estimation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Methods that adaptively choose local sets may need an explicit isotropy check or correction to reach optimal rates.
  • The same shape-regularity requirement likely applies to other local averaging schemes such as kernel or partitioning estimators.
  • In practice, monitoring the maximum aspect ratio of chosen neighborhoods could serve as a diagnostic for rate optimality.

Load-bearing premise

The localizing sets form a VC family, allowing a general deviation bound to be applied to the estimators.

What would settle it

An explicit anisotropic localizing set for which the local averaging estimator fails to achieve the optimal rate (up to logs) on a Lipschitz function, even in finite samples.

read the original abstract

Considering pointwise and sup-norm estimation, we analyze the non-asymptotic behavior of local averaging estimators for Lipschitz regression functions. Building on a general deviation bound for estimators based on a VC family of localizing sets, we introduce the notion of shape-regular local maps, where averaging is performed over sets with an almost isotropic geometry. Our main message is a characterization: shape regularity is both necessary and sufficient to attain optimal rates, up to logarithmic factors. Necessity is established non-asymptotically through an explicit anisotropic example, sharpening a phenomenon previously understood only heuristically in asymptotic theory. We then draw two consequences. First, the simple $k$-nearest neighbor rule is shape-regular by construction and attains the optimal rate, even on unbounded supports. Second, and perhaps surprisingly, the popular random-split condition for trees -- known to ensure consistency and vanishing cell diameters -- does not guarantee optimal rates: for blind tree constructions, the cell aspect ratio diverges exponentially with depth, so that shape regularity fails with positive probability. This identifies the absence of a geometric correction mechanism, rather than a slowly shrinking diameter, as the obstruction to optimality. Motivated by this gap, we propose a tree construction that enforces shape regularity through a simple constraint on admissible splits, and prove a uniform deviation inequality showing that it restores the optimal rate for Lipschitz functions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper analyzes the non-asymptotic behavior of local averaging estimators for Lipschitz regression functions under pointwise and sup-norm estimation. It introduces the notion of shape-regular local maps (with almost isotropic geometry) and establishes a characterization that shape regularity is both necessary and sufficient to attain optimal rates up to logarithmic factors. Necessity is shown via an explicit anisotropic example; sufficiency builds on a general deviation bound for VC families of localizing sets. Consequences include that k-NN is shape-regular and attains the rate even on unbounded supports, while random-split trees fail to guarantee shape regularity (cell aspect ratios diverge exponentially), and a constrained tree construction is proposed to restore optimality via a uniform deviation inequality.

Significance. If the results hold, the work sharpens the geometric conditions required for optimal nonparametric rates in local averaging, moving beyond heuristic asymptotic understanding to non-asymptotic necessity via an explicit example. The constructive proposal for shape-regular trees addresses a practical gap in tree-based methods. Strengths include the explicit necessity construction and the identification that vanishing diameters alone are insufficient without geometric control.

major comments (2)
  1. [Abstract (paragraph on the deviation bound) and the section defining shape-regular local maps and proving the uniform de] The sufficiency claim (shape regularity sufficient for optimal rates up to logs) rests on invoking the general deviation bound for estimators based on a VC family of localizing sets. The manuscript must explicitly establish that the family of shape-regular local maps (or the admissible splits in the constrained tree) forms a VC class whose dimension is bounded independently of n (and other parameters) in a manner that does not inflate the claimed rates; without this verification the deviation bound cannot be applied at the stated precision.
  2. [Section on the proposed tree construction and its uniform deviation inequality] In the analysis of the constrained tree construction, the proof that shape regularity is enforced with high probability and yields the optimal rate must confirm that the resulting localizing sets remain within a VC family of controlled dimension; the exponential divergence shown for unconstrained random splits suggests that any constraint mechanism needs a quantitative VC-dimension bound to close the argument.
minor comments (1)
  1. Notation for the local maps and aspect ratios should be introduced with explicit definitions before their use in the main theorems to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for explicit VC-dimension verification in the sufficiency arguments. We agree these points require clarification and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract (paragraph on the deviation bound) and the section defining shape-regular local maps and proving the uniform de] The sufficiency claim (shape regularity sufficient for optimal rates up to logs) rests on invoking the general deviation bound for estimators based on a VC family of localizing sets. The manuscript must explicitly establish that the family of shape-regular local maps (or the admissible splits in the constrained tree) forms a VC class whose dimension is bounded independently of n (and other parameters) in a manner that does not inflate the claimed rates; without this verification the deviation bound cannot be applied at the stated precision.

    Authors: We agree that the manuscript invokes the general deviation bound without an explicit verification that the family of shape-regular local maps has VC dimension bounded independently of n. This is a substantive gap. In the revision we will add a new lemma establishing that the collection of all shape-regular local sets (defined via the almost-isotropic geometry condition) forms a VC class whose dimension is bounded by a constant depending only on the ambient dimension d; the bound is independent of n and of the localization radius, so that the logarithmic factors in the stated rates remain unaffected. revision: yes

  2. Referee: [Section on the proposed tree construction and its uniform deviation inequality] In the analysis of the constrained tree construction, the proof that shape regularity is enforced with high probability and yields the optimal rate must confirm that the resulting localizing sets remain within a VC family of controlled dimension; the exponential divergence shown for unconstrained random splits suggests that any constraint mechanism needs a quantitative VC-dimension bound to close the argument.

    Authors: We concur that the constrained-tree analysis must include a quantitative VC-dimension bound. The revision will augment the uniform deviation inequality proof with an explicit argument showing that the admissible splits under the shape-regularity constraint generate localizing sets belonging to a VC class whose dimension is at most C(d), a constant independent of sample size, tree depth, and the constraint parameter. This closes the argument without altering the claimed rates. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations rely on external VC theory

full rationale

The paper's necessity direction uses an explicit non-asymptotic anisotropic counterexample independent of any fitted quantities or self-citations. The sufficiency direction invokes a general deviation bound for VC families of localizing sets (standard external theory) applied after introducing shape-regular maps; no equation or claim reduces by construction to its own inputs, no self-citation chain is load-bearing for the central characterization, and no ansatz or uniqueness result is smuggled via prior author work. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard VC theory for deviation bounds and introduces the new concept of shape-regular local maps; no free parameters or data-fitted quantities appear in the abstract description.

axioms (1)
  • domain assumption Estimators are based on a VC family of localizing sets
    Invoked to apply a general deviation bound (abstract opening sentence).
invented entities (1)
  • shape-regular local maps no independent evidence
    purpose: Averaging sets with almost isotropic geometry that achieve optimal rates
    New notion introduced to characterize when local averaging attains optimal rates; no independent evidence outside the paper.

pith-pipeline@v0.9.1-grok · 5778 in / 1217 out tokens · 34284 ms · 2026-06-30T00:21:25.840010+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

228 extracted references · 9 canonical work pages · 3 internal anchors

  1. [1]

    Test , volume=

    A random forest guided tour , author=. Test , volume=. 2016 , publisher=

    2016

  2. [2]

    Electronic Journal of Statistics , number =

    Luc Devroye and L. Electronic Journal of Statistics , number =. 2018 , publisher =

    2018

  3. [3]

    Local Rademacher complexities , author=. Ann. Statist. , volume=. 2005 , publisher=

    2005

  4. [4]

    Asymptotic Theory for Random Forests

    Asymptotic theory for random forests , author=. arXiv preprint arXiv:1405.0352 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    Journal of the American Statistical Association , volume=

    Estimation and inference of heterogeneous treatment effects using random forests , author=. Journal of the American Statistical Association , volume=. 2018 , publisher=

    2018

  6. [6]

    Journal of artificial intelligence research , volume=

    SMOTE: synthetic minority over-sampling technique , author=. Journal of artificial intelligence research , volume=

  7. [7]

    1996 , publisher=

    A probabilistic theory of pattern recognition , author=. 1996 , publisher=

    1996

  8. [8]

    Advances in neural information processing systems , volume=

    Mondrian forests: Efficient online random forests , author=. Advances in neural information processing systems , volume=

  9. [9]

    2006 , publisher=

    A distribution-free theory of nonparametric regression , author=. 2006 , publisher=

    2006

  10. [10]

    The annals of statistics , pages=

    Optimal global rates of convergence for nonparametric regression , author=. The annals of statistics , pages=. 1982 , publisher=

    1982

  11. [11]

    BAGAN: Data Augmentation with Balancing GAN

    Bagan: Data augmentation with balancing gan , author=. arXiv preprint arXiv:1803.09655 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    Exploratory Undersampling for Class-Imbalance Learning , year=

    Liu, Xu-Ying and Wu, Jianxin and Zhou, Zhi-Hua , journal=. Exploratory Undersampling for Class-Imbalance Learning , year=

  13. [13]

    and Galar, M

    Triguero, I. and Galar, M. and Vluymans, S. and Cornelis, C. and Bustince, H. and Herrera, F. and Saeys, Y. , booktitle=. Evolutionary undersampling for imbalanced big data classification , year=

  14. [14]

    Electronic Journal of Statistics , number =

    Clayton Scott , title =. Electronic Journal of Statistics , number =. 2012 , doi =

    2012

  15. [15]

    Proceedings of the 30th International Conference on Machine Learning , pages =

    On the Statistical Consistency of Algorithms for Binary Classification under Class Imbalance , author =. Proceedings of the 30th International Conference on Machine Learning , pages =. 2013 , editor =

    2013

  16. [16]

    International Conference on Machine Learning , pages=

    Class-weighted classification: Trade-offs and robust approaches , author=. International Conference on Machine Learning , pages=. 2020 , organization=

    2020

  17. [17]

    Introduction to Statistical Learning Theory , author =

  18. [18]

    Classification in general finite dimensional spaces with the

    Gadat, S\'. Classification in general finite dimensional spaces with the. Ann. Statist. , FJOURNAL =. 2016 , NUMBER =

    2016

  19. [19]

    , title =

    Tsybakov, Alexandre B. , title =. 2008 , publisher =

    2008

  20. [20]

    Choice of neighbor order in nearest-neighbor classification , author=. Ann. Statist. , volume=

  21. [21]

    2021 , publisher=

    Mathematical foundations of infinite-dimensional statistical models , author=. 2021 , publisher=

    2021

  22. [22]

    An exponential inequality for the distribution function of the kernel density estimator, with applications to adaptive estimation , JOURNAL =

    Gin\'. An exponential inequality for the distribution function of the kernel density estimator, with applications to adaptive estimation , JOURNAL =. 2009 , NUMBER =

    2009

  23. [23]

    Nonparametric discrimination: Consistency properties , author=

    Discriminatory analysis. Nonparametric discrimination: Consistency properties , author=. Int. Stat. Rev. , volume=. 1951 , publisher=

    1951

  24. [24]

    Local nearest neighbour classification with applications to semi-supervised learning , author=. Ann. Statist. , volume=. 2020 , publisher=

    2020

  25. [25]

    Theory of classification: a survey of some recent advances , JOURNAL =

    Boucheron, St\'. Theory of classification: a survey of some recent advances , JOURNAL =. 2005 , PAGES =

    2005

  26. [26]

    Dudley, R. M. , TITLE =. J. Funct. Anal. , FJOURNAL =. 1967 , PAGES =

    1967

  27. [27]

    Hierarchical nearest-neighbor Gaussian process models for large geostatistical datasets , author=. J. Amer. Statist. Assoc. , volume=. 2016 , publisher=

    2016

  28. [28]

    Bousquet, Olivier , TITLE =. C. R. Math. Acad. Sci. Paris , FJOURNAL =. 2002 , NUMBER =

    2002

  29. [29]

    The Annals of Statistics , pages=

    Risk Bounds for Statistical Learning , author=. The Annals of Statistics , pages=. 2006 , publisher=

    2006

  30. [30]

    Journal of Combinatorial Theory, Series A , volume=

    Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension , author=. Journal of Combinatorial Theory, Series A , volume=. 1995 , publisher=

    1995

  31. [31]

    The Annals of Probability , volume=

    About the constants in Talagrand's concentration inequalities for empirical processes , author=. The Annals of Probability , volume=. 2000 , publisher=

    2000

  32. [32]

    2023 , publisher=

    Mathematical analysis of machine learning algorithms , author=. 2023 , publisher=

    2023

  33. [33]

    Lecture Notes (Princeton University) , year=

    Probability in high dimension , author=. Lecture Notes (Princeton University) , year=

  34. [34]

    1991 , publisher=

    Probability in Banach Spaces: isoperimetry and processes , author=. 1991 , publisher=

    1991

  35. [35]

    Consistency of a recursive nearest neighbor regression function estimate , author=. J. Multivariate Anal. , volume=. 1980 , publisher=

    1980

  36. [36]

    The strong uniform consistency of nearest neighbor density estimates , author=. Ann. Statist. , pages=. 1977 , publisher=

    1977

  37. [37]

    Empirical Risk Minimization under Random Censorship , author=. J. Mach. Learn. Res. , volume=

  38. [38]

    Smooth regression analysis , author=. Sankhy. 1964 , publisher=

    1964

  39. [39]

    Theory Probab

    On estimating regression , author=. Theory Probab. Appl. , volume=. 1964 , publisher=

    1964

  40. [40]

    Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test , author=. Ann. Probab. , pages=. 1983 , publisher=

    1983

  41. [41]

    On the measure of Voronoi cells , author=. J. Appl. Probab. , FJOURNAL =. 2017 , publisher=

    2017

  42. [42]

    Bernoulli , volume=

    Integral approximation by kernel smoothing , author=. Bernoulli , volume=. 2016 , publisher=

    2016

  43. [43]

    Statistics & Probability Letters , volume=

    Consistent estimation of residual variance with random forest Out-Of-Bag errors , author=. Statistics & Probability Letters , volume=. 2019 , publisher=

    2019

  44. [44]

    AISTATS proceedings , pages=

    Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic Bounds and Applications , author=. AISTATS proceedings , pages=. 2021 , organization=

    2021

  45. [45]

    On the strong universal consistency of nearest neighbor regression function estimates , author=. Ann. Statist. , pages=. 1994 , publisher=

    1994

  46. [46]

    Rate of convergence of k -nearest-neighbor classification rule , author=. J. Mach. Learn. Res. , volume=. 2017 , publisher=

    2017

  47. [47]

    Electron

    A nearest neighbor estimate of the residual variance , author=. Electron. J. Stat. , volume=. 2018 , publisher=

    2018

  48. [48]

    1966 , PAGES =

    Royall, Richard Miles , TITLE =. 1966 , PAGES =

    1966

  49. [49]

    Principles of nonparametric learning , pages=

    Pattern classification and learning theory , author=. Principles of nonparametric learning , pages=. 2002 , publisher=

    2002

  50. [50]

    Statistics & Probability Letters , volume=

    Uniform concentration bounds for frequencies of rare events , author=. Statistics & Probability Letters , volume=. 2022 , publisher=

    2022

  51. [51]

    Estimation of a conditional copula and association measures , author=. Scand. J. Stat. , volume=. 2011 , publisher=

    2011

  52. [52]

    1981 , journal=

    Nonparametric regression with randomly censored survival data , author=. 1981 , journal=

    1981

  53. [53]

    IEEE Trans

    Estimation by the nearest neighbor rule , author=. IEEE Trans. Inform. Theory , volume=. 1968 , publisher=

    1968

  54. [54]

    Robust nonparametric regression with simultaneous scale curve estimation , author=. Ann. Statist. , pages=. 1988 , publisher=

    1988

  55. [55]

    The rate of convergence of k_n -

    Gy. The rate of convergence of k_n -. IEEE Trans. Inform. Theory , volume=. 1981 , publisher=

    1981

  56. [56]

    Asymptotic normality of multivariate k -

    Mack, YP , journal=. Asymptotic normality of multivariate k -. 1980 , number =

    1980

  57. [57]

    Statistical Decision Theory and Related Topics , pages=

    Large sample properties of nearest neighbor density function estimators , author=. Statistical Decision Theory and Related Topics , pages=. 1977 , publisher=

    1977

  58. [58]

    IEEE Trans

    The uniform convergence of nearest neighbor regression function estimators and their application in optimization , author=. IEEE Trans. Inform. Theory , volume=. 1978 , publisher=

    1978

  59. [59]

    arXiv preprint arXiv:2110.15083 , year=

    Nearest neighbor process: weak convergence and non-asymptotic bound , author=. arXiv preprint arXiv:2110.15083 , year=

    work page arXiv

  60. [60]

    Pattern Classification and Learning Theory

    Lugosi, G. Pattern Classification and Learning Theory. Principles of Nonparametric Learning. 2002

    2002

  61. [61]

    1990 , publisher=

    Applied nonparametric regression , author=. 1990 , publisher=

    1990

  62. [62]

    Conference on Learning Theory , pages=

    Learning the dependence structure of rare events: a non-asymptotic study , author=. Conference on Learning Theory , pages=. 2015 , organization=

    2015

  63. [63]

    A result of

    Anthony, Martin and Shawe-Taylor, John , journal=. A result of. 1993 , publisher=

    1993

  64. [64]

    Sharper bounds for Gaussian and empirical processes , author=. Ann. Probab. , pages=. 1994 , publisher=

    1994

  65. [65]

    Plassier, Vincent and Portier, Francois and Segers, Johan , TITLE =. Ann. Inst. Henri Poincar\'. 2023 , NUMBER =

    2023

  66. [66]

    Electron

    Partial and average copulas and association measures , author=. Electron. J. Stat. , volume=. 2015 , publisher=

    2015

  67. [67]

    Computational Statistics & Data Analysis , volume=

    Nonparametric estimation of pair-copula constructions with the empirical pair-copula , author=. Computational Statistics & Data Analysis , volume=. 2015 , publisher=

    2015

  68. [68]

    simplifying

    About tests of the “simplifying” assumption for conditional copulas , author=. Dependence Modeling , volume=. 2017 , publisher=

    2017

  69. [69]

    Asymptotics of conditional empirical processes , author=. J. Multivariate Anal. , volume=. 1988 , publisher=

    1988

  70. [70]

    Local properties of k -

    Mack, Yue-Pok , journal=. Local properties of k -. 1981 , publisher=

    1981

  71. [71]

    NeurIPS proceedings , pages=

    Distance metric learning for large margin nearest neighbor classification , author=. NeurIPS proceedings , pages=

  72. [72]

    Conditional Empirical Processes , author=. Ann. Statist. , volume=. 1986 , publisher=

    1986

  73. [73]

    Strong uniform consistency rates for estimators of conditional functionals , author=. Ann. Statist. , pages=. 1988 , publisher=

    1988

  74. [74]

    NeurIPS proceedings , volume=

    Rates of Convergence for Large-scale Nearest Neighbor Classification , author=. NeurIPS proceedings , volume=

  75. [75]

    Kpotufe, Samory , booktitle=. k-

  76. [76]

    Journal of Multivariate Analysis , volume=

    On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification , author=. Journal of Multivariate Analysis , volume=. 2010 , publisher=

    2010

  77. [77]

    , author=

    On the Rate of Convergence of the Bagged Nearest Neighbor Estimate. , author=. J. Mach. Learn. Res. , volume=

  78. [78]

    Test , volume=

    Test of independence and randomness based on the empirical copula process , author=. Test , volume=. 2004 , publisher=

    2004

  79. [79]

    Lectures on the nearest neighbor method , SERIES =

    Biau, G\'. Lectures on the nearest neighbor method , SERIES =. 2015 , PAGES =

    2015

  80. [80]

    Non-asymptotic uniform rates of consistency for k -

    Jiang, Heinrich , booktitle=. Non-asymptotic uniform rates of consistency for k -

Showing first 80 references.