REVIEW 2 major objections 6 minor 25 references
Entropy and Learning of Lipschitz Functions under Log-Concave Measures
T0 review · 2 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read For 1-Lipschitz regression under log-concave measures, this paper proves that two polynomial-based estimators—one knowing the measure's orthogonal polynomial basis, one knowing nothing—both reach the minimax L2 risk, of order $\log d /…
desk verdict Strong entropy and projection-estimator results, but the least-squares analysis has a real small-ball net gap that needs repair before the advertised range is fully proven. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Three pieces carry the argument. First, polynomial truncation: every 1-Lipschitz function has $L^2(\mu)$-distance at most $\Psi_\mu(m)$ from the space of degree-$m$ polynomials, and for Gaussian-like measures $\Psi_\mu(m)^2 \lesssim 1/m$. Second, empirical risk control: log-concave moment growth for polynomials and exponential concentration inequalities bound the coefficient errors of the projection estimator; for the least-squares estimator, the same concentration plus a matrix deviation bound for the empirical Gram matrix and a small-ball estimate for its smallest eigenvalue produce the $D/n$ variance terms. Third, the entropy construction: random multilinear polynomials with Gaussian coefficients stay bounded in fourth moment under product isotropic log-concave measures, and the Markov (Langevin) semigroup smooths their truncations into Lipschitz functions while preserving $L^2$ separation; a quantitative Gaussian approximation of low-dimensional marginals transfers the construction to general isotropic log-concave measures. A standard information-theoretic reduction then converts the entropy lower bound into the minimax lower bound.
What would settle it
Compute the metric entropy $H_\mu^L(\epsilon)$ for the standard Gaussian in dimension $d=100$ at $\epsilon = 0.32$, just above $d^{-1/4}$: the theorems predict $\log H$ is of order $\epsilon^{-2}\log d$, with lower bound $\log\binom{d}{\lfloor c/\epsilon\rfloor^2}$ and upper bound $\log\binom{d}{\lceil 4/\epsilon\rceil^2}$; a packing count whose logarithm grows only polynomially in $d$ would refute the lower bound, and one growing faster than $d^{O(\epsilon^{-2})}$ would refute the upper bound. Alternatively, find an isotropic log-concave measure with the Gaussian approximation rate $\Psi_\mu(m)^2 \lesssim 1/m$ but with a Lipschitz Poincare constant growing with $d$; if its minimax rate in the subexponential regime is not $\log d / \log n$, the claimed universal rate fails outside the stated normalization.
Extended reading notes
Core claim
The paper's central claim is that the metric entropy of the class of 1-Lipschitz functions—the logarithm of the largest number of functions that are pairwise $\epsilon$-separated in $L^2(\mu)$—is the right measure of statistical difficulty in this setting, and that it is far smaller than distribution-free bounds suggest. In the Gaussian case and more generally for isotropic log-concave measures with polynomial approximation rate $\Psi_\mu(m)^2 \lesssim 1/m$, the paper proves that for $\epsilon > d^{-1/4}$ the entropy satisfies $\log\binom{d}{\lfloor c/\epsilon\rfloor^2} \lesssim H_\mu^L(\epsilon) \lesssim \log\binom{d}{\lceil 4/\epsilon\rceil^2}$, so in the relevant range the entropy is of order $\epsilon^{-2}\log d$. With Gaussian noise of variance $\sigma^2 \in [n^{-\kappa}, n]$, this entropy controls the minimax lower bound $R^\ast_{n,d} \gtrsim (1+\kappa)\log n / \log d$, and the projection estimator and the least-squares estimator both match that rate up to constants in the stated subexponential range. The two estimators differ in what they require: the projection estimator must know an orthogonal polynomial basis of $\mu$, while the least-squares estimator is distribution-free, and both have risk governed by the polynomial approximation error $\Psi_\mu(m)^2$ plus a variance term of order $(m^2+\sigma^2)D/n$, up to logarithmic factors for the least-squares estimator.
Load-bearing premise
The load-bearing premise is that the measure's Lipschitz Poincare constant is bounded by a universal constant (the normalization $\Psi_\mu(0)=1$); if that constant grows with dimension, the estimator variance terms grow and the matching with the minimax lower bound breaks.
Editorial extensions
If this is right
- For Gaussian inputs, learning a 1-Lipschitz function to $L^2$ accuracy $\epsilon$ needs only $n \simeq d^{c/\epsilon}$ samples, so fixed-accuracy learning is polynomial in the dimension rather than exponential.
- The least-squares estimator attains the minimax rate without knowing $\mu$ over the stated ranges, so distribution-free polynomial regression is information-theoretically optimal there.
- In the subexponential range $n \le \exp(c d^{2\eta}\log d/\kappa)$, no estimator can beat the polynomial estimators: the minimax lower bound is $(1+\kappa)\log n / \log d$.
- For product measures the same conclusions hold up to $n \le \exp(c\sqrt{d}\log d/\kappa)$, almost the entire subexponential window.
- The entropy bounds $H_\mu^L(\epsilon) \asymp \epsilon^{-2}\log d$ for $\epsilon > d^{-1/4}$ stand alone as a quantitative statement about the metric size of Lipschitz balls under log-concave measures.
Reading between the lines
- A natural extension not pursued in the paper: the same entropy estimate should control rates in other $L^2$-based statistical problems over Lipschitz classes, such as nonparametric testing or density estimation, where the effective dimension $\log(d)/\epsilon^2$ determines sample complexity.
- If the bounded-Poincare normalization is weakened to a slowly growing Lipschitz Poincare constant, the proof pattern suggests risk bounds multiplied by that constant; whether the $\log d / \log n$ minimax rate survives is a testable open question.
- The construction via random multilinear polynomials plus semigroup smoothing is a reusable device: it should yield entropy bounds for other function classes defined by smoothness rather than Lipschitzness, such as Holder or Sobolev balls, under log-concave measures.
- The degree choice $m_0-4$ in the least-squares analysis leaves room for the conjecture that a more delicate matrix concentration could let $m=m_0$ be used, extending the range of $n$ without changing the risk; this is not claimed by the paper.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies nonparametric regression of 1-Lipschitz functions under log-concave measures in high dimension, with Gaussian additive noise. It analyzes two polynomial estimators: a projection estimator that uses an orthogonal polynomial basis of the underlying measure, and a least-squares estimator over low-degree polynomials that is measure-blind. Under the normalization Psi_mu(0)=1 and a polynomial approximation rate Psi_mu(m), the paper proves upper bounds on the L2(mu) risk for both estimators (Theorems 1.2 and 1.4). When Psi_mu^2(m) is of order 1/m, as for the Gaussian measure or the uniform measure on the hypercube, these bounds match the minimax lower bounds up to universal constants in a subexponential sample-size regime, giving risk of order log d / log n. The core new ingredient is Theorem 4.1/Corollary 4.2: metric entropy estimates for the unit ball of 1-Lipschitz functions in L2(mu), stated as new even for the Gaussian measure. The lower-bound construction uses random multilinear polynomials, truncation, and the Langevin semigroup, and the minimax lower bound follows from a Yang-Barron argument.
Significance. If the proofs are completed, this is a substantial contribution. The entropy estimates for Lipschitz classes under log-concave measures are new and are the key to matching minimax rates in a high-dimensional regime where the sample size is only subexponential in the dimension. The projection-estimator analysis is clean and the lower-bound construction via random multilinear polynomials and semigroup smoothing is elegant and appears sound. The paper also gives credit-worthy explicit quantitative statements: the constants are universal, the approximation-vs-estimation decomposition is transparent, and the entropy upper and lower bounds match up to constants. The main weakness is that the least-squares upper bound, which is half of the central claim, rests on an incomplete small-ball net argument in Lemma 3.10; this needs to be repaired before the results on the least-squares estimator are fully supported.
major comments (2)
- [§3.2.3, Lemma 3.10] The second small-ball estimate for lambda_min(C_n) is not justified as written. The line P((1/n)S_n <= 2t) <= P(S_n <= 2 sqrt(t))^n conflates the sum S_n with a single variable V; the intended step should be P((1/n) sum V_i <= 2t) <= P(V <= 2 sqrt(t))^n, which implicitly uses t <= 1/n^2. More importantly, the union bound over a t-net of the sphere does not control the anisotropic term (theta - theta')^T C_n (theta - theta'), which is bounded by ||theta - theta'||^2 ||C_n||_op; the proof gives no bound on ||C_n||_op or on max_i ||Z_i||^2 inside that union bound. Since Lemma 3.3 integrates the resulting tail bound over event C, and Theorem 3.2 and the least-squares half of Corollary 1.7 depend on Lemma 3.3, this gap is load-bearing. The argument is likely repairable by adding a high-probability event controlling max_i ||Z_i||^2 and using a finer net, but the proof as written is incomplete.
- [§3.2.3, Lemma 3.10, first statement] The same net issue affects the first tail estimate P(lambda_min(C_n) <= e^{-c0 m}) <= exp(- n / e^{c1 m}). To pass from a vector theta with (1/n) sum (Z_i . theta)^2 <= e^{-c0 m} to a point theta' in the stated net, one needs to control the extra term involving ||Z_i||^2; the proof instead merely states that a union bound over a net 'concludes the proof'. The phrase 'at 1/2-net' is also unclear: the net radius should be a small multiple of e^{-c0 m}, and the necessary control on the norms of the Z_i is absent. This must be rewritten, together with the second statement, before Lemma 3.3 can be accepted.
minor comments (6)
- [Abstract and Section 1.2] The abstract states the results for 'a log-concave measure' without the normalization Psi_mu(0)=1 and the polynomial approximation condition (10); the reader should be told in the abstract that the claims are conditional on a bounded Lipschitz Poincare constant and the stated approximation rate.
- [Corollary 1.7] There is a grammar error in the first bullet: 'The projection estimator and the least squares estimators achieves' should be 'achieve'.
- [Section 1, after Theorem 1.5] The sentence 'Note that it is more conventional to define entropy via covering numbers rather than packing numbers' is duplicated verbatim.
- [Lemma 3.10, proof] The displayed inequality P((1/n)S_n <= 2t) <= P(S_n <= 2 sqrt(t))^n appears to be a typo for P(V <= 2 sqrt(t))^n once S_n is the sum of the n variables; this should be corrected for readability even after the net argument is repaired.
- [Section 4.1] In the definition after equation (82), the notation P|_lambda for the truncation is not defined formally; it would help to write P|_lambda(x) = P(x) 1_{|P(x)| <= lambda} explicitly in the main text.
- [Theorem 1.4 proof, second regime] In the second regime of the proof of Theorem 1.4, the term (C log n)^{2m0+1-p} (m0/d)^p is not explicitly bounded after p is chosen; the argument can be completed using alpha < 1/2, but this step should be written out for the reader.
Circularity Check
No circular reduction in the core derivation; self-citations are background or external, not load-bearing.
full rationale
The paper's central claims do not reduce to their own inputs by construction. The upper risk bounds (Theorems 3.1 and 3.2) are stated in terms of the approximation function Psi_mu(m), which is an assumption about mu and is not manufactured as a prediction; the minimax matching is explicitly conditional on (24). The entropy lower bound (Theorems 4.1 and 4.4) is built from random multilinear polynomials, the Langevin semigroup, Carbery-Wright anti-concentration, and Rudelson's covariance estimate, rather than from the target entropy value, so it is not self-definitional. The general isotropic case invokes the Eldan-Klartag marginal approximation theorem [EK08]; this is a published, parameter-free external result, and the author overlap does not make the argument circular. The other self-citations ([BK25], [KL25], [Kla23], [Biz23]) are used for background facts, standard semigroup smoothing, or illustrative examples (e.g., the hypercube rate), and none is the load-bearing step that forces the minimax conclusion. A technical gap in the small-ball estimate of Lemma 3.10 (noted by the skeptic) would be a correctness issue rather than a circularity, and it does not change this verdict. Accordingly, no circular step is identified; the score of 2 reflects only the presence of minor, non-load-bearing self-citations.
Assumptions & free parameters
assumptions (8)
- domain assumption The measure mu is log-concave and isotropic (covariance identity).
- domain assumption Normalization Psi_mu(0)=1, i.e., the Poincare constant for 1-Lipschitz functions satisfies C_P^Lip(mu) <~ 1.
- domain assumption The polynomial approximation property (10), with Psi_mu(m) decreasing to 0; for the main matching results, Psi_mu^2(m) <~ 1/m as in (24).
- standard math Carbery-Wright anti-concentration for polynomials under log-concave measures (Theorem 2.5).
- standard math Bourgain-NSV moment bounds for polynomials under log-concave measures (Proposition 2.3).
- standard math Eldan-Klartag pointwise marginal estimate (Theorem 4.6): every isotropic log-concave measure has a low-dimensional marginal whose density is close to Gaussian on a large ball.
- standard math Langevin semigroup smoothing and gradient estimates for log-concave measures (Lemmas 2.6 and 2.7).
- standard math Log-concave fourth moment bound E X^4 <= 9 for centered unit-variance coordinates (Eit24).
Cite this review
Pith. "Pith review of Entropy and Learning of Lipschitz Functions under Log-Concave Measures." pith.science (2026). https://pith.science/paper/AWA64TUE
@misc{pith2026250910355,
author = {Pith},
title = {Pith review of: Entropy and Learning of Lipschitz Functions under Log-Concave Measures},
year = {2026},
howpublished = {\url{https://pith.science/paper/AWA64TUE}},
note = {Machine review of arXiv:2509.10355}
}
abstract
We study regression of $1$-Lipschitz functions under a log-concave measure $\mu$ on $\mathbb{R}^d$. We focus on the high-dimensional regime where the sample size $n$ is subexponential in $d$, in which distribution-free estimators are ineffective. We analyze two polynomial-based procedures: the projection estimator, which relies on knowledge of an orthogonal polynomial basis of $\mu$, and the least-squares estimator over low-degree polynomials, which requires no knowledge of $\mu$ whatsoever. Their risk is governed by the rate of polynomial approximation of Lipschitz functions in $L^2(\mu)$. When this rate matches the Gaussian one, we show that both estimators achieve minimax bounds over a wide range of parameters. A key ingredient is sharp entropy estimates for the class of $1$-Lipschitz functions in $L^2(\mu)$, which are new even in the Gaussian setting.
Reference graph
Works this paper leans on
-
[1]
Alice and Bob meet Banach , volume 223
Guillaume Aubrun and Stanis aw J Szarek. Alice and Bob meet Banach , volume 223. American Mathematical Soc., 2017
2017
-
[2]
Analysis and geometry of Markov diffusion operators , volume 348
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators , volume 348. Springer Science & Business Media, 2013
work page 2013
-
[3]
On the log-sobolev constant of log-concave measures
Pierre Bizeul. On the log-sobolev constant of log-concave measures. arXiv preprint arXiv:2306.12997 , 2023
arXiv 2023
-
[4]
Polynomial Approximation in $ L^2 $ of the Double Exponential via Complex Analysis
Pierre Bizeul and Boaz Klartag. Polynomial approximation in l^2 of the double exponential via complex analysis. arXiv preprint arXiv:2502.07448 , 2025
work page Pith review arXiv 2025
-
[5]
On concentration of distributions of random weighted sums
Sergey G Bobkov. On concentration of distributions of random weighted sums. Annals of probability , pages 195--215, 2003
work page 2003
-
[6]
On the distribution of polynomials on high-dimensional convex sets
Jean Bourgain. On the distribution of polynomials on high-dimensional convex sets. In Geometric aspects of functional analysis (1989--90) , volume 1469 of Lecture Notes in Math. , pages 127--137. Springer, Berlin, 1991
work page 1989
-
[7]
Distributional and lq norm inequalities for polynomials over convex bodies in rn
Anthony Carbery and James Wright. Distributional and lq norm inequalities for polynomials over convex bodies in rn. Mathematical research letters , 8(3):233--248, 2001
work page 2001
-
[8]
Learning low-degree functions from a logarithmic number of random queries
Alexandros Eskenazis and Paata Ivanisvili. Learning low-degree functions from a logarithmic number of random queries. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 203--207, 2022
work page 2022
Show all 25 references
-
[9]
Low-degree learning and the metric entropy of polynomials
Alexandros Eskenazis, Paata Ivanisvili, and Lauritz Streck. Low-degree learning and the metric entropy of polynomials. arXiv preprint arXiv:2203.09659 , 2022
2022 arXiv
-
[10]
The centered convex body whose marginals have the heaviest tails
Yam Eitan. The centered convex body whose marginals have the heaviest tails. Studia Math. , 274(3):201--215, 2024
2024
-
[11]
Pointwise estimates for marginals of convex bodies
Ronon Eldan and Boaz Klartag. Pointwise estimates for marginals of convex bodies. J. Funct. Anal. , 254(8):2275--2293, 2008
2008
-
[12]
On markov-bernstein-type inequalities and their applications
G \'e za Freud. On markov-bernstein-type inequalities and their applications. Journal of Approximation Theory , 19(1):22--37, 1977
1977
-
[13]
A topological application of the isoperimetric inequality
Mikhael Gromov and Vitali D Milman. A topological application of the isoperimetric inequality. American Journal of Mathematics , 105(4):843--854, 1983
1983
-
[14]
Probability inequalities for sums of bounded random variables
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association , 58(301):13--30, 1963
1963
-
[15]
Isoperimetric inequalities in high dimensional convex sets
Boaz Klartag and Jospeh Lehec. Isoperimetric inequalities in high dimensional convex sets. Bulletin of the Amer. Math. Soc. , 2025+
2025
-
[16]
Logarithmic bounds for isoperimetry and slices of convex sets
Boaz Klartag. Logarithmic bounds for isoperimetry and slices of convex sets. arXiv preprint arXiv:2303.14938 , 2023
2023 arXiv
-
[17]
Isoperimetric problems for convex bodies and a localization lemma
Ravi Kannan, L \'a szl \'o Lov \'a sz, and Mikl \'o s Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry , 13:541--559, 1995
1995
-
[18]
Levin and D
A.L. Levin and D. S. Lubinsky. Canonical products and the weights (-x^ ) \ ( > 1) with applications. Journal of approximation theory , 49(2):149--169, 1987
1987
-
[19]
A survey of weighted approximation for exponential weights
Doron S Lubinsky. A survey of weighted approximation for exponential weights. arXiv preprint math/0701099 , 2007
2007 arXiv
-
[20]
On the role of convexity in isoperimetry, spectral gap and concentration
Emanuel Milman. On the role of convexity in isoperimetry, spectral gap and concentration. Inventiones mathematicae , 177(1):1--43, 2009
2009
-
[21]
Fedor Nazarov, Mikhail Sodin, and Alexander Volberg. The geometric K annan- L ov\'asz- S imonovits lemma, dimension-free estimates for the distribution of the values of polynomials, and the distribution of the zeros of random analytic functions. Algebra i Analiz , 14(2):214--234, 2002
2002
-
[22]
Introduction to operator space theory
Gilles Pisier. Introduction to operator space theory . Number 294. Cambridge University Press, 2003
2003
-
[23]
Random vectors in the isotropic position
Mark Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis , 164(1):60--72, 1999
1999
-
[24]
High-dimensional probability: An introduction with applications in data science , volume 47
Roman Vershynin. High-dimensional probability: An introduction with applications in data science , volume 47. Cambridge university press, 2018
2018
-
[25]
High-dimensional statistics: A non-asymptotic viewpoint , volume 48
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint , volume 48. Cambridge university press, 2019
2019
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.