{"id":"4813e487-8990-4e26-b41a-83c5bc4051c2","arxiv_id":"2412.02797","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimal nonlinear sampling recovery of mixed-smoothness classes H^r_q is at least c m^{-r+1/q-1/p} (log m)^{(d-1)/p}, a logarithmic factor not captured by previous lower-bound techniques.","lead":"This paper proves new lower bounds on how accurately functions with mixed smoothness can be reconstructed from finitely many point values, even when arbitrary nonlinear reconstruction rules are allowed. The bounds reveal a logarithmic penalty that earlier lower-bound techniques missed, and they show how a simple two-function argument yields these limits.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified to Theorem 1.3; the transfer via Theorem 2.1 and the separation of the u(s) blocks are terse but valid, so the logarithmic lower bound survives scrutiny.","rationale":"I read the central argument in good faith and could not find a load-bearing flaw. The two-function trick, the separated-block construction, and the final scaling all work. The reader's weakest assumption identifies the transfer from H(Q_n)_q to H^r_q and the distinctness of the u(s) blocks as the riskiest point. In fact, the distinctness is automatic from the divisibility-by-3 construction: the possible block index boxes B_s are pairwise disjoint, so no two selected blocks can collide. The existence of u(s) with large L_∞ norm follows immediately from the support being contained in at most 3^d Littlewood-Paley blocks. The embedding into H^r_q is handled by the standard block-decay characterization in Theorem 2.1 with constants independent of n; one only needs to scale by 2^{-r(n+3d)} so that the block bound holds uniformly for all s. The logarithmic factor (log m)^((d-1)/p) is exactly the number of separated blocks n^(d-1) to the power 1/p, and the power in m comes from the exponential scaling, matching the theorem. The secondary issues the reader mentions in Section 4 and Section 5 are real but minor: some constants and quasi-norm estimates are asserted rather than derived, and they should be cleaned up in revision. They do not undermine Theorem 1.3, which is the main claim. I therefore recommend keeping the verdict unchanged while asking the authors to expand the terse parts of the proof.","tokens_in":13313,"tokens_out":38145,"duration_ms":399352,"concrete_test":"Add to the proof of Lemma 3.2 a one-paragraph derivation of (3.4) and the disjointness claim: set B_s = ∏_{j=1}^d {s_j-1, s_j, s_j+1}; observe that t_s = Σ_{u∈B_s} δ_u(t_s) and hence max ||δ_u(t_s)||_∞ >= 3^{-d} ||t_s||_∞. Then check that for distinct s, s' in Y_{n,3}, the boxes B_s are pairwise disjoint because one coordinate differs by a multiple of 3, hence by at least 3, making the corresponding one-dimensional index intervals disjoint. Also verify the embedding constant by writing out the scaling: for h_scaled = c 2^{-r(n+3d)} h, one has ||A_s(h_scaled)||_q <= C 2^{-r||s||_1} for every s, with C and c independent of n; this closes the transfer to H^r_q.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main claimed lower bound, Theorem 1.3, rests on Lemma 3.2. The potential weak points are (i) the use of Theorem 2.1 to pass from the model class H(Q_n)_q to H^r_q with constants independent of n, and (ii) the assertion that the selected blocks u(s) are distinct so that the estimate (3.6) sees all n^(d-1) blocks. Both points are terse in the paper, but they are valid. For (ii), the Fourier support of t_s is contained in the union of the 3^d blocks B_s := {s_j-1, s_j, s_j+1}^d, so the triangle inequality gives max_{u in B_s} ||δ_u(t_s)||_∞ >= 3^{-d} ||t_s||_∞, which is exactly (3.4). Moreover, for distinct s, s' in Y_{n,3}, some coordinate differs by a multiple of 3 and hence by at least 3; the corresponding intervals {s_j-1, s_j, s_j+1} and {s'_j-1, s'_j, s'_j+1} are disjoint, so B_s and B_{s'} are disjoint. Thus δ_{u(s)}(f) = δ_{u(s)}(t_s) without cancellation. For (i), after scaling h by 2^{-r(n+3d)}, the block decay ||A_s(h_scaled)||_q <= C 2^{-r||s||_1} holds for all s (with A_s = 0 beyond the support), so Theorem 2.1 applies with constants independent of n. The secondary gaps noted by the reader in Sections 4 and 5 are presentation-level and do not affect the central Theorem 1.3.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies lower bounds for the optimal nonlinear sampling recovery characteristic rho^o_m(W,L_p) on classes of multivariate periodic functions with mixed smoothness. The main result (Theorem 1.3) states that for 1 ≤ q ≤ p < ∞, p > 1, r > 1/q, one has rho^o_m(H^r_q,L_p) ≥ c(d) m^{-r+1/q-1/p} (log m)^{(d-1)/p}. The proof constructs, for an arbitrary set of m sample points, a trigonometric polynomial f that vanishes at all sample points, has small dyadic-block norms ||A_s(f)||_q (so that a scaled version belongs to a model class H(Q_n)_q), and has large L_p norm by virtue of a Littlewood-Paley-type lower bound. The model-class lower bound is then transferred to H^r_q via the known equivalence between the mixed-difference definition and the dyadic-block decay condition (Theorem 2.1). Additional results include a lower bound rho^o_m(H^r_infty,L_1) ≥ c m^{-r} (log m)^{d-1} (Proposition 1.2), lower bounds for classes with structural coefficient conditions in Section 5, and consequences for Gelfand widths.","tokens_in":13603,"tokens_out":34014,"duration_ms":297995,"significance":"If the result is correct, Theorem 1.3 provides a new lower bound with a logarithmic factor (log m)^{(d-1)/p} for nonlinear sampling recovery on the H^r_q classes, improving on the previously known m^{-r+1/q-1/p} bound that follows from trigonometric-width techniques. The argument is elementary and self-contained once the cited tools (Theorem 2.1, Theorem 2.2, Lemma 3.1 from [21], and the quadrature example from [15]) are accepted; these are published results with independent proofs, and no circularity is apparent. The paper also demonstrates the usefulness of a simple two-function comparison principle (Proposition 6.1) and gives lower bounds for related structural classes and Gelfand widths. The proofs are constructive and checkable, though some deductions are terse.","major_comments":[],"minor_comments":[{"comment":"The constant in the lower bound is written as c(d), but the proof passes through Theorem 2.2 with u = p, whose constants depend on p, and through Theorem 2.1, whose constants depend on r,d,q,l. The deduction also introduces a factor depending on r through the scaling 2^{-rn}. Please rephrase the statements to make the parameter dependence of the constant explicit (e.g., c(r,d,p,q)), or explain why the constant can be chosen independent of these parameters.","section":"Section 3, Lemma 3.2 and Theorem 1.3"},{"comment":"The statement that Theorem 1.3 is a direct corollary of Lemma 3.2 is not accompanied by the derivation. Since the transition from the model class H(Q_{n+b})_q to H^r_q and the change of variables from n to m is a key step, please add a short paragraph showing that choosing n with m ≤ S_n/2 and S_n ≍ 2^n yields 2^{-n} ≍ m^{-1} and n^{(d-1)/p} ≍ (log m)^{(d-1)/p}.","section":"Section 3, after Lemma 3.2"},{"comment":"The claim 'It is easy to derive from here that for each s ... there exists u(s) ...' is correct but terse. Please add one or two sentences explaining that t_s has frequency support contained in the union of the 3^d blocks {s_j-1, s_j, s_j+1}^d and that the sup norm of t_s is bounded by the sum of the sup norms of its block projections, so that one block must contain at least a fixed fraction of the norm.","section":"Section 3, display (3.4)"},{"comment":"The lower bound for p = 1 is derived by saying 'in the same way as we derived Theorem 5.1 from the example built in the proof of Lemma 3.2', but the analogous block-norm estimates for the functions from Section 4 are not shown. Since (5.15) is a new result, please provide the key estimates for |δ_s(t)|_{A_β} and ||t||_1 that lead to the stated exponent.","section":"Section 5, bound (5.15)"},{"comment":"In the proof of (1.4), the step from (2.8) to (2.9) implicitly uses that the number of indices s with ||s||_1 = j is O(j^{d-1}); stating this explicitly would help the reader follow the bookkeeping.","section":"Section 1, Proposition 1.1"},{"comment":"There are several spacing and typographical errors (e.g., 'M ostly', 'boun ds', 'pro blem') in the abstract and first paragraphs; these should be corrected in the final version.","section":"Abstract and Introduction"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript's main technical claim appears sound. The central construction in Lemma 3.2 is valid: the separation of the blocks via 3-divisible coordinates ensures that distinct s give disjoint frequency supports, and the transfer through Theorem 2.1 has constants independent of n as required. The paper relies substantially on earlier results by the same main author ([21], [15]), but these are published and used as tools rather than restated conclusions, so I see no circularity. The main revision need is precision about constants and a few expanded derivations; the mathematical contribution is appropriate for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: Theorem 1.3 is real. The new log factor (log m)^{(d-1)/p} for nonlinear sampling recovery on H^r_q is a genuine advance, and the proof is basically correct. I read the stress-test note and agree with it: the two terse points in Lemma 3.2—getting constants independent of n from Theorem 2.1 and the disjointness of the blocks u(s)—do hold, so the main bound survives scrutiny.\n\nWhat's actually new: the log factor itself. As Remark 3.1 records, the prior lower bound was m^{-r+1/q-1/p} without a log, so this sharpens the H-class result and separates H from W in this regime. The technique is simple, as the authors admit: a separated-block trigonometric construction plus the two-function trick. That simplicity is a virtue; they don't oversell it. Proposition 1.2 for H^r_∞, L1 with (log m)^{d-1} and the Section 5 structural-class bounds are also new applications of existing tools.\n\nThe soft spots are real but minor. In Section 4, the chain ‖Au(t)‖∞ ≪ ... ≪ 2^{r(n-‖u‖1)} needs an absorbed constant depending on r,d when n-‖u‖1 is small; as written the displayed inequality is not literally true for all n,u. It's fixable with a constant. Section 5's Theorem 5.1 skips the bookkeeping that identifies the q=2 norm estimate and the support sizes before applying Corollary 5.1; again routine, but it should be spelled out. Neither issue touches Theorem 1.3.\n\nThe citation pattern is fine. The paper leans on the same author's earlier lemmas, but those are independently published and the paper says so; that's not a defect for a paper that is explicitly a follow-up.\n\nWho this is for: people working on sampling recovery, hyperbolic cross approximation, and widths. They'll want to know Theorem 1.3. The paper deserves a serious referee. There's no data or code, so review is about the math, and the main math checks out. I'd accept it with minor revisions.","headline":"A genuine new lower bound with a log factor for sampling recovery on H^r_q; the main proof is correct, with only routine fixable gaps in the secondary sections.","tokens_in":14301,"tokens_out":2334,"would_cite":true,"duration_ms":23309,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A46","41A63","42B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Nonlinear sampling recovery of mixed-smoothness classes cannot beat $m^{-r+1/q-1/p}(\\log m)^{(d-1)/p}$ in $L_p$, for $1\\le q\\le p<\\infty$, $p>1$, $r>1/q$.","keywords":["optimal sampling recovery","nonlinear recovery","lower bounds","mixed smoothness","H^r_q classes","hyperbolic cross","Littlewood-Paley blocks","trigonometric polynomials"],"falsifier":"Compute the $L_p$ norm of the test function $f=\\sum_{s\\in Y_{n,3}} t_s$ from Lemma 3.2 for, say, $d=2$, $q=p=2$, and increasing $n$; if $\\|f\\|_2$ grows slower than $2^{n/2}n^{1/2}$, the claimed lower bound fails. Alternatively, exhibit any nonlinear recovery rule for $H^r_q$ in $L_p$ with error $o\\bigl(m^{-r+1/q-1/p}(\\log m)^{(d-1)/p}\\bigr)$ along some subsequence $m\\to\\infty$.","tokens_in":13036,"feed_emoji":"📉","tokens_out":9665,"duration_ms":92083,"temperature":0.7,"pith_summary":"This paper proves that no nonlinear rule using $m$ point evaluations can recover every function in the mixed-smoothness class $H^r_q$ (periodic functions with bounded mixed differences in $L_q$) with $L_p$ error better than a constant multiple of $m^{-r+1/q-1/p}(\\log m)^{(d-1)/p}$, in the range $1\\le q\\le p<\\infty$, $p>1$, $r>1/q$. The logarithmic factor is the new content: earlier arguments gave only $m^{-r+1/q-1/p}$. The result matters because nonlinear sampling recovery is much harder to lower-bound than linear recovery, since Kolmogorov-width theory does not apply, and the authors show that two simple observations, block separation and symmetry of the class, are enough to force the log factor. A companion result gives an $m^{-r}(\\log m)^{d-1}$ lower bound for recovering $H^r_\\infty$ in $L_1$. If correct, the main bound matches the known linear-recovery upper bounds in the relevant range and shows the log penalty is an intrinsic feature of the problem.","feed_headline":"Sampling mixed-smoothness functions must pay a log factor","feed_subtitle":"New lower bound forces a (log m)^((d-1)/p) penalty on every nonlinear method for H^r_q.","key_machinery":"The load-bearing object is the dyadic block decomposition of a periodic function: for a multi-index $s$ with nonnegative integer coordinates, $\\rho(s)$ is the set of frequencies $k$ with $2^{s_j-1}\\le |k_j|<2^{s_j}$, and $A_s(f)$ is the projection of $f$ onto those frequencies. The paper works with the model class $H(Q_n)_q=\\{f\\in T(Q_n): \\|A_s(f)\\|_q\\le 1\\}$, which by Theorem 2.1 embeds into $H^r_q$ with constants independent of $n$. The proof then fixes any set of $m$ sample points, chooses the separated index family $Y_{n,3}$ (multi-indices with all coordinates divisible by 3 and $\\|s\\|_1=n$), and builds $f=\\sum_{s\\in Y_{n,3}} g_{\\xi,s}K_{2^{s-2}}(x-x^*_s)$, a sum of localized trigonometric blocks each vanishing at the sample points. Separation ensures the blocks do not merge, and a Littlewood-Paley-type norm inequality (Theorem 2.2) gives $\\|f\\|_p\\ge c\\,2^{n(1-1/p)}n^{(d-1)/p}$. Finally, the symmetry observation of Proposition 6.1 converts a large-norm function vanishing on the samples into a lower bound for the recovery error.","core_discovery":"The central claim is Theorem 1.3: for $1\\le q\\le p<\\infty$, $p>1$, $r>1/q$, the optimal nonlinear sampling recovery error satisfies $\\rho^o_m(H^r_q,L_p) \\ge c(d)\\, m^{-r+1/q-1/p}(\\log m)^{(d-1)/p}$. Here $H^r_q$ is the class of multivariate periodic functions whose mixed differences satisfy $\\|\\Delta^l_{t(e)} f\\|_q \\le B \\prod_{j\\in e}|t_j|^r$, and $\\rho^o_m$ is the infimum, over all choices of $m$ sample points and all mappings from sample values to functions, of the worst-case $L_p$ error. The proof constructs, for any proposed sampling scheme, a function in a closely related dyadic-block class $H(Q_n)_q$ that vanishes at all $m$ sample points and yet has $L_p$ norm at least $c\\,2^{n(1-1/p)}n^{(d-1)/p}$; because the class is symmetric, both this function and its negative are admissible, so any recovery map must err by at least this norm. The new logarithmic factor $n^{(d-1)/p}$, equivalently $(\\log m)^{(d-1)/p}$, comes from the number of separated frequency blocks available at level $n$.","pith_inferences":["The construction is insensitive to how the recovery map processes the samples, so this style of lower bound should also apply to adaptive sampling designs, provided the eventually chosen sample set is among the sets considered.","The matching log exponents between this lower bound and known linear upper bounds suggest that, for $H^r_q$ classes in the range $1<q\\le 2\\le p<\\infty$, nonlinear methods may not improve the rate of sampling recovery over linear ones, in contrast to the known situation for $W^r_q$ classes in $L_2$.","A natural next test is whether the same block-separation idea transfers to non-periodic or stochastic sampling settings, where the vanishing-at-sample trick would need a different localization argument.","The dyadic-block norm comparison used here could be sharpened to give matching constants in the log exponent for the structural classes $H^{a,b}_{A_\\beta}$, complementing the upper bounds already known for those classes."],"forward_implications":["No nonlinear algorithm, however adaptive, can recover all of $H^r_q$ from $m$ point values in $L_p$ at a rate better than $m^{-r+1/q-1/p}(\\log m)^{(d-1)/p}$ in the range $1\\le q\\le p<\\infty$, $p>1$.","The logarithmic factor is necessary for every dimension $d>1$ and every finite $p$, not an artifact of particular algorithms.","In the range where the known linear-recovery upper bound carries the same $(\\log m)^{(d-1)/p}$ factor, the optimal nonlinear recovery rate is now pinned down up to constants.","For recovery of $H^r_\\infty$ in $L_1$, the full $(\\log m)^{d-1}$ factor is forced, matching the known upper bound.","Because the sampling functionals in the construction can be replaced by arbitrary linear functionals, the same bounds hold for Gelfand widths of these classes."],"supporting_citations":[{"why":"Proves Lemma 3.1, the base lower bound for unit $L_q$-balls of trigonometric subspaces that the block construction extends.","marker":"[21]"},{"why":"Provides Theorem 2.1, the equivalence between mixed-difference smoothness and dyadic-block decay used to embed $H(Q_n)_q$ into $H^r_q$, and the Fej\\'er-kernel norm bound used in (3.2).","marker":"[18]"},{"why":"Supplies Theorem 2.2, the Littlewood-Paley-type norm comparison that yields the $L_p$ lower bound (3.6).","marker":"[14]"},{"why":"Proves the matching upper bound for $W^r_q$ classes and the embedding results that locate the new lower bound in the optimal-recovery picture.","marker":"[7]"},{"why":"Constructs trigonometric functions vanishing at prescribed points with large integral, the engine for Proposition 1.2 and the Gelfand-width comments.","marker":"[15]"},{"why":"Introduces the structural classes $W^{a,b}_{A_\\beta}$ and supplies the upper bound (5.14) that Section 5 compares against.","marker":"[12]"}],"fun_headline_variants":["Log penalty proven for nonlinear sampling recovery","Mixed-smoothness sampling recovery faces log factor","Nonlinear recovery lower bound: log factor unavoidable","Optimal sampling recovery incurs log penalty","Sampling mixed-smoothness functions: log factor required"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof needs the equivalence between the mixed-difference definition of $H^r_q$ and the dyadic-block condition to hold with a constant that does not grow with the level $n$, and it needs the frequency blocks $u(s)$ produced by the construction to stay pairwise distinct; the paper asserts the second point with 'it is easy to derive' and does not give the constant bookkeeping.","fun_headline_variants_meta":{"raw":{"variants":["Log penalty proven for nonlinear sampling recovery","Mixed-smoothness sampling recovery faces log factor","Nonlinear recovery lower bound: log factor unavoidable","Optimal sampling recovery incurs log penalty","Sampling mixed-smoothness functions: log factor required"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000254,"raw_usage":{"total_tokens":1572,"prompt_tokens":954,"completion_tokens":618,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":548}},"tokens_in":570,"tokens_out":618,"duration_ms":6556,"temperature":1.0,"reasoning_tokens":548,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:07:20.533852+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the $L_p$ norm of the test function $f=\\sum_{s\\in Y_{n,3}} t_s$ from Lemma 3.2 for, say, $d=2$, $q=p=2$, and increasing $n$; if $\\|f\\|_2$ grows slower than $2^{n/2}n^{1/2}$, the claimed lower bound fails. Alternatively, exhibit any nonlinear recovery rule for $H^r_q$ in $L_p$ with error $o\\bigl(m^{-r+1/q-1/p}(\\log m)^{(d-1)/p}\\bigr)$ along some subsequence $m\\to\\infty$.","supporting_citations":[{"cited_title":"Sparse sampling recovery in integral norms on some function classes","cited_arxiv_id":"2401.14670","evidence_quote":"Proves Lemma 3.1, the base lower bound for unit $L_q$-balls of trigonometric subspaces that the block construction extends."},{"cited_title":"Temlyakov, Multivariate Approximation , Cambridge University Press, 2018","cited_arxiv_id":null,"evidence_quote":"Provides Theorem 2.1, the equivalence between mixed-difference smoothness and dyadic-block decay used to embed $H(Q_n)_q$ into $H^r_q$, and the Fej\\'er-kernel norm bound used in (3.2)."},{"cited_title":"Temlyakov, Approximation of functions with bounded mixed derivative, Trudy MIAN, 178 (1986), 1–112","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 2.2, the Littlewood-Paley-type norm comparison that yields the $L_p$ lower bound (3.6)."},{"cited_title":"Bounds for the sampling discretization error and their applications to the universal sampling discretization","cited_arxiv_id":"2312.05670","evidence_quote":"Proves the matching upper bound for $W^r_q$ classes and the embedding results that locate the new lower bound in the optimal-recovery picture."},{"cited_title":"Temlyakov, On a way of obtaining lower estimates for the er- rors of quadrature formulas, Matem","cited_arxiv_id":null,"evidence_quote":"Constructs trigonometric functions vanishing at prescribed points with large integral, the engine for Proposition 1.2 and the Gelfand-width comments."},{"cited_title":"Sampling recovery on function classes with a structural condition","cited_arxiv_id":"2404.07210","evidence_quote":"Introduces the structural classes $W^{a,b}_{A_\\beta}$ and supplies the upper bound (5.14) that Section 5 compares against."}],"review_version":1}