{"id":"b48cc62f-e99b-4b43-bc18-e8586dbf370d","arxiv_id":"2509.10355","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For regression of 1-Lipschitz functions under log-concave measures with Gaussian-like polynomial approximation, low-degree polynomial estimators achieve the minimax L2 risk of order log d / log n when n is subexponential in d.","lead":"This paper studies how many noisy samples are needed to learn a 1-Lipschitz function in high dimensions when the input distribution is Gaussian or log-concave. It proves that low-degree polynomial estimators reach the information-theoretically optimal error rate using a sample size that only grows polynomially with dimension, and it computes the metric entropy of the class of Lipschitz functions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.10's small-ball net argument is incomplete: the t-net union bound for lambda_min(C_n) does not control ||C_n||_op, so the least-squares upper bound in Theorem 3.2/Corollary 1.7 is not yet fully proven.","rationale":"The reader's weakest assumption, the bounded-Poincare normalization, is a genuine restriction, but it is explicitly stated in Section 1.2 and the theorems are formulated with it; it does not make the argument internally inconsistent. The more immediate threat to the central claim is the small-ball/net step in Lemma 3.10, which is load-bearing for the least-squares estimator in Theorem 3.2 and Corollary 1.7. The reader did flag the net argument in Lemma 3.10 as a technical gap, which is why my assessment partially agrees, but I regard it as more central than the bounded-Poincare qualifier. The entropy estimates, the projection estimator, and the minimax lower bounds appear coherent and well-supported; if Lemma 3.10 can be repaired, the paper's conclusions should stand. Because the gap is localized and plausibly fixable, the appropriate verdict is CONDITIONAL rather than REJECT or UNVERDICTED.","tokens_in":979,"tokens_out":921,"duration_ms":482001,"concrete_test":"Re-derive the second estimate of Lemma 3.10 with a complete net argument. Condition on the high-probability event {||C_n - I||_op <= 1/2} available from Lemma 3.4, and check whether lambda_min(C_n) <= t forces some net point theta' to satisfy theta'^T C_n theta' <= C t. Then compute the union-bound tail using the Carbery-Wright bound of Theorem 2.5, and redo the integral in Lemma 3.3. If the additional factor involving ||C_n||_op changes the exponent from t^{n/16m} to a worse exponent, verify whether the final bound (55) still holds for the advertised range d^5 <= n <= exp(d^beta/C).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The least-squares half of the paper's central claim rests on Theorem 3.2, whose proof depends on Lemma 3.3, and Lemma 3.3 in turn depends on the tail estimates of Lemma 3.10. The second estimate in Lemma 3.10 is not justified as written. To pass from an eigenvector theta with theta^T C_n theta <= t to a point theta' in a t-net of the sphere, one must 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 inside that union bound, and ||C_n||_op is governed by the same random polynomial values that are being controlled only through Lemma 3.4 on a separate high-probability event. Moreover, the displayed line P((1/n)S_n <= 2t) <= P(S_n <= 2sqrt(t))^n appears to conflate the sum S_n with a single variable V; the intended implication would need a factor n: the event (1/n) sum V_i <= 2t implies each V_i <= 2nt, not V_i <= 2sqrt(t) unless one uses t <= 1/n^2 and inserts the n. A rigorous rewrite of this small-ball estimate, with the missing factor and a genuine net argument, is required. Without it, the variance term in the least-squares risk bound (55), and hence the advertised range n <= exp(d^beta/C), is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":29182,"tokens_out":14592,"duration_ms":130499,"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":[{"comment":"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.","section":"§3.2.3, Lemma 3.10"},{"comment":"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.","section":"§3.2.3, Lemma 3.10, first statement"}],"minor_comments":[{"comment":"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.","section":"Abstract and Section 1.2"},{"comment":"There is a grammar error in the first bullet: 'The projection estimator and the least squares estimators achieves' should be 'achieve'.","section":"Corollary 1.7"},{"comment":"The sentence 'Note that it is more conventional to define entropy via covering numbers rather than packing numbers' is duplicated verbatim.","section":"Section 1, after Theorem 1.5"},{"comment":"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":"Lemma 3.10, proof"},{"comment":"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.","section":"Section 4.1"},{"comment":"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.","section":"Theorem 1.4 proof, second regime"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for the journal and the core ideas are strong. The self-citation [BK25] is used only as background and for the tensorization principle in examples, not in the proofs of Theorems 1.2, 1.4, or 1.5. The main risk is the incomplete small-ball net argument in Lemma 3.10, which affects the proof of the least-squares upper bound; I expect this can be repaired with an additional norm-control event and a finer net. I do not see a need for a novelty disclosure beyond the authors' own citation of [BK25]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a strong paper with one genuine proof gap. The entropy lower bounds for the unit ball of 1-Lipschitz functions in L2(mu), new already for Gaussian, are the real contribution; the construction with random multilinear polynomials and the Langevin semigroup is clever and, as far as I can tell, correct. The projection-estimator half (Theorems 1.2/3.1) is also clean, and the minimax consequences follow from the entropy estimates in a standard way.\n\nThe soft spot is the least-squares estimator. Theorem 3.2 depends on Lemma 3.3, which depends on Lemma 3.10's small-ball estimates for lambda_min(C_n). The second estimate in Lemma 3.10 has a line that looks wrong at first: P(S_n/n <= 2t) <= P(S_n <= 2sqrt(t))^n. But that specific step is actually fine: under t <= 1/n^2, the event S_n/n <= 2t implies S_n <= 2sqrt(t), hence each of the n independent V_i is <= 2sqrt(t). The stress-test's factor-n complaint does not land.\n\nWhat does land is the net argument. Neither part of Lemma 3.10 controls ||C_n||_op, so passing from lambda_min <= t to existence of a net point with small quadratic form lacks an anisotropic bound. You need something like the high-probability event from Lemma 3.4 (||C_n - I||_op small) or an explicit truncation; then the net step works with radius t and an extra factor 2. As written, the proof is incomplete, and since Lemma 3.3 feeds directly into the variance term (55), the least-squares range for n is not fully established.\n\nI do not think this sinks the paper: the gap looks repairable with standard tools, and the projection-estimator and entropy results stand independently. The abstract is also a bit stronger than the theorems: the rate matching is conditional on Psi_mu^2(m) ~ 1/m and bounded Poincare, not true for all isotropic log-concave measures. The paper states this, but the headline does not.\n\nThis deserves a serious referee, with a request to fix Lemma 3.10. I would bring it to a reading group and would cite the entropy results.","headline":"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.","tokens_in":29758,"tokens_out":9805,"would_cite":true,"duration_ms":83976,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G08","60E15","41A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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 /…","keywords":["minimax regression","1-Lipschitz functions","log-concave measures","polynomial approximation","metric entropy","projection estimator","least-squares estimator","high-dimensional statistics"],"falsifier":"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.","tokens_in":28643,"feed_emoji":"📉","tokens_out":13618,"duration_ms":119427,"temperature":0.7,"pith_summary":"The paper asks a high-dimensional regression question: how many samples are needed to learn a 1-Lipschitz function from noisy values, when the input distribution is a log-concave measure and the sample size $n$ is only subexponential in the dimension $d$. Its answer is that two polynomial-based procedures—the projection estimator and the empirical least-squares estimate over low-degree polynomials—achieve the minimax risk (the smallest worst-case expected error any estimator can guarantee) up to universal constants, provided the measure approximates Lipschitz functions by polynomials at the Gaussian rate of $1/\\text{degree}$ and has a bounded Lipschitz Poincare constant. The optimal risk is of order $\\log d / \\log n$ in the range $d^5 \\le n \\le \\exp(c d^{2\\eta}\\log d)$, and up to $\\exp(c\\sqrt{d}\\log d)$ for product measures. The engine behind the matching lower bound is a sharp metric entropy estimate for the unit ball of 1-Lipschitz functions in $L^2(\\mu)$, which is stated as new even for the Gaussian measure.","feed_headline":"Minimax rate reached by polynomial estimators for Lipschitz regression","feed_subtitle":"With subexponential samples, projection and least-squares estimators match the log d / log n lower bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the log-concave moment growth for degree-$m$ polynomials used to bound coefficient-estimator variance.","marker":"[Bou91]"},{"why":"Provides an alternative proof source for the same polynomial moment inequality in log-concave spaces.","marker":"[NSV02]"},{"why":"Establishes that Lipschitz functions essentially attain the Poincare constant, tying the normalization $\\Psi_\\mu(0)=1$ to the standard Poincare inequality.","marker":"[Mil09]"},{"why":"Provides the anti-concentration (small-ball) bound for polynomials used to control the smallest eigenvalue of the empirical Gram matrix.","marker":"[CW01]"},{"why":"Provides the deviation bound for the empirical covariance matrix that controls the least-squares matrix inverse.","marker":"[Rud99]"},{"why":"Supplies the Gaussian approximation of low-dimensional marginals of isotropic log-concave measures, extending the entropy lower bound from product to general measures.","marker":"[EK08]"},{"why":"Gives the stochastic domination used to bound the fourth moment of random multilinear polynomials in the entropy construction.","marker":"[Hoe63]"},{"why":"Supplies the information-theoretic (Yang-Barron) method used to convert entropy lower bounds into minimax lower bounds.","marker":"[Wai19]"}],"fun_headline_variants":["Polynomial estimators match minimax bound for Lipschitz regression","Entropy controls minimax rate for Lipschitz regression","Low-degree polynomials achieve minimax Lipschitz learning","Subexponential samples suffice for optimal Lipschitz regression","Sharp entropy for Lipschitz functions drives minimax regression"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial estimators match minimax bound for Lipschitz regression","Entropy controls minimax rate for Lipschitz regression","Low-degree polynomials achieve minimax Lipschitz learning","Subexponential samples suffice for optimal Lipschitz regression","Sharp entropy for Lipschitz functions drives minimax regression"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000738,"raw_usage":{"total_tokens":3345,"prompt_tokens":1039,"completion_tokens":2306,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":655,"completion_tokens_details":{"reasoning_tokens":2225}},"tokens_in":655,"tokens_out":2306,"duration_ms":13825,"temperature":1.0,"reasoning_tokens":2225,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:58:45.401202+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}