{"id":"f1fac96b-4b00-4b40-ac5e-f3a54b0d5f9f","arxiv_id":"2607.07249","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":4,"one_line_summary":"The minimax optimal rate for minimizing the k-th derivative of a Hölder function from noisy zero-order queries is N^{-(β-1)/(β+k)}, achieved by a kernel-based projected stochastic gradient algorithm.","lead":"This paper proves matching upper and lower bounds on how fast you can minimize the k-th derivative of an unknown function when you can only observe noisy values of the function itself. It matters because it establishes the fundamental statistical limits of optimizing derivatives from indirect, noisy observations.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. Proofs are detailed, self-contained, and follow established techniques correctly.","rationale":"The reader's verdict of ACCEPT with HIGH confidence is appropriate. The paper establishes matching minimax bounds for a genuinely novel problem (optimizing k-th derivatives from zero-order queries of the original function). Both proofs are carried out in full detail with careful verification of all regularity conditions. The upper bound uses a clean two-kernel construction and a well-controlled Chung-type recursion. The lower bound uses a standard but carefully executed two-hypothesis construction with explicit verification that g± ∈ F'_{α,β,k}. The reader correctly identifies strong convexity as the load-bearing assumption; it is standard, transparently used, and its relaxation is acknowledged as open. The three acknowledged limitations (dimension gap, Gaussian noise in lower bound, strong convexity) are genuine but do not affect the correctness of the central claim. No adjustment to the verdict is warranted.","tokens_in":23422,"tokens_out":5724,"duration_ms":254860,"concrete_test":"Independently re-derive the bias bound in Lemma 5.1 by expanding g(x_t + hue_j ± hve_l) to order ℓ* = ⌊β+k⌋ and applying kernel moment conditions (7)-(8); verify that the only surviving term in the double sum (13) is (a,b) = (k,1), giving ∂_j^k ∂_l g(x_t) = ∂_l f(x_t), and that the remainder is O(h^{β-1}). If any other term survives or the remainder bound fails, the bias-variance trade-off in Theorem 5.1 would be affected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After tracing both the upper and lower bound proofs in detail, I do not find a load-bearing concern that lands. The upper bound chain is sound: Lemma 5.1's bias bound correctly exploits the kernel moment conditions (7)-(8) and the differencing trick that cancels even powers of v; Lemma 5.2's second moment bound correctly uses the Lipschitz property of ∇g on Θ⁺; the Chung-type recursion (Lemma 6.1) correctly handles the two forcing terms (bias A-term non-decaying in T for fixed h, variance B-term decaying as 1/T), and the choice h = κT^{-1/(2(β+k))} balances them to rate T^{-(β-1)/(β+k)}. The conversion N = 2dT then yields the stated d^{(2β+k-1)/(β+k)} N^{-(β-1)/(β+k)} bound. The lower bound construction is also correct: g± = q ± rh^{β+k}Φ(x₁/h) with f± = α‖x‖² ± rh^β Φ^{(k)}(x₁/h) is verified to lie in F'_{α,β,k} for all properties (a)-(g); the KL divergence is made constant by the choice r_N = c* N^{-1/2} h_N^{-(β+k)}; the minimizer separation ∥x₊* - x₋*∥ ≥ c₀ r h^{β-1} follows from the implicit function theorem argument; and the squared separation gives the N^{-(β-1)/(β+k)} rate. The reader's identified weakest assumption (strong convexity of f) is indeed load-bearing — it drives the α/2 factor in (28), the Chung recursion, and the optimization-error-to-distance conversion (67) — but it is a standard assumption in zero-order optimization, is transparently used, and its relaxation is acknowledged as open in Section 7. The dimension gap, the Gaussian-noise restriction in the lower bound, and the strong convexity assumption are all acknowledged limitations, not correctness issues.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies the problem of minimizing the k-th order partial derivative f = ∂_j^k g of an unknown function g over a compact convex set Θ, given a budget of N noisy zero-order queries of g at sequentially chosen points. The authors assume g has Hölder regularity β+k (β≥2), f is α-strongly convex, and standard boundedness/Lipschitz conditions hold. They propose a kernel-based gradient estimator using paired queries along the j-th coordinate (kernel K_k) and each gradient direction (kernel K_1), and analyze a projected stochastic gradient algorithm. The main results are: (1) Theorem 5.1, an upper bound on the expected optimization error of order d^{(2β+k-1)/(β+k)} N^{-(β-1)/(β+k)}; and (2) Theorem 5.2, a matching minimax lower bound of order N^{-(β-1)/(β+k)} over all sequential algorithms, establishing optimality in N. The gap between upper and lower bounds is a dimension-dependent polynomial factor, which is left as an open question.","tokens_in":23727,"tokens_out":1856,"duration_ms":247830,"significance":"The paper addresses a novel problem at the interface of zero-order optimization and nonparametric statistics: optimizing a derivative of an unknown function observed only through noisy function values. This 'indirect observation' setting is a natural generalization of standard zero-order optimization (k=0) and connects to deconvolution and linear inverse problems. The matching minimax rates in N are the central contribution and are established via a clean, self-contained proof chain. The upper bound uses a two-kernel construction with explicit moment conditions (Eqs. 7-8), a Chung-type recursion handling two forcing terms (Lemma 6.1), and an explicit bias-variance tradeoff (Remark 5.1). The lower bound constructs explicit adversarial functions g± = q ± r h^{β+k} Φ(x₁/h), verifies all class properties (a)-(g), and uses a KL-divergence reduction with a parameter choice (Eq. 59) that makes the KL divergence constant. The rate N^{-(β-1)/(β+k)} transparently reflects the loss of k units of smoothness from indirect observation. The dimension gap is honestly acknowledged.","major_comments":[{"comment":"Section 5.2, Theorem 5.2: The lower bound is stated under the assumption that the noise variables ξ_t are i.i.d. Gaussian (line: 'assume the oracle model (1), where ξ_t's are i.i.d. Gaussian with mean 0 and variance σ²'). The upper bound (Theorem 5.1) only requires E[ξ_t²] ≤ σ² with no independence or zero-mean assumption. This asymmetry is not highlighted in the abstract or introduction, where the results are presented as 'matching.' While the Gaussian restriction for lower bounds is standard practice, a brief remark explaining that the lower bound uses Gaussian noise (and thus the matching applies under this noise model) would improve transparency. This is a presentation issue rather than a correctness concern, as the upper bound is valid under weaker conditions.","section":null},{"comment":"Section 6.2, proof of Theorem 5.2, verification of property (a) for β=2: The Hölder regularity of q is verified by bounding the Taylor remainder of order ℓ* = k+1, yielding |R_q(x,z)| ≤ C_q α ‖z-x‖^{k+2} (Eq. 46 and surrounding text). This is correct since β+k = k+2 when β=2. However, the case β>2 is handled by noting that q is a polynomial of degree k+2 and its Taylor expansion of order ℓ* ≥ k+2 is exact, so q ∈ F^{β+k}(0). This is fine, but the text should clarify that when β>2 is not an integer, ℓ* = ⌊β+k⌋ could still equal k+2 (e.g., β=2.5 gives ℓ*=k+2), in which case the exactness argument applies, but when β≥3, ℓ*≥k+3 and the degree-k+2 polynomial is also exactly represented. The current phrasing 'Since β+k > k+2 so ℓ* ≥ k+2' is slightly imprecise: for 2<β<3, ℓ*=k+2 exactly, not strictly greater. This does not affect the conclusion but the inequality should be ℓ* ≥ k+2.","section":null}],"minor_comments":[{"comment":"Section 1, definition of class F'_{α,β,k}: The condition (g) states 'f attains its minimum on Θ at a point x* ∈ int(Θ).' This is used in the lower bound proof (Section 6.2) to ensure x*± ∈ int(Θ) via the inclusion [-2h₀, 2h₀]^d ⊂ int(Θ) (Eq. 41). The proof correctly verifies this, but the main text could note that condition (g) is essential for the lower bound construction, not just convenience.","section":null},{"comment":"Section 4.2, Eq. (6): The query points are written as x_t + hU_{t,l}e_j ± hV_{t,l}e_l. When l=j, both perturbations are along the same coordinate. The estimator (Eq. 9) still applies, but the analysis of Lemma 5.1 for l=j uses the bound |u±v| ≤ |u|+|v|, which is noted in the proof. This is handled correctly but a brief remark in Section 4.2 that the l=j case is non-degenerate would help the reader.","section":null},{"comment":"Section 6.1, proof of Lemma 5.2, Eq. (18): The bound (g(x+s)-g(x-s))² ≤ 3L̄²h⁴/32 + 3G_g²h² uses ‖s‖ ≤ h/2. The factor 3/32 comes from 3·(L̄²/2)·(h/2)⁴·2 = 3L̄²h⁴/32. The intermediate step showing this substitution explicitly would aid verification, though the arithmetic is correct.","section":null},{"comment":"Section 6.1, Lemma 6.1: The shift inequality (t+1+t₀)^q ≤ 2(t+t₀)^q is stated to follow from t₀ ≥ 2q. The proof uses (1+1/(2q))^q ≤ e^{1/2} ≤ 2. This is correct, but the bound e^{1/2} ≈ 1.649 < 2 is loose; this is fine for the result but could be tightened if sharper dimension dependence were sought.","section":null},{"comment":"Section 7 (Discussion): The open question about the dimension exponent (2β+k-1)/(β+k) is well-motivated. The remark that 'standard Assouad-type constructions are not directly available' due to the interaction between Hölder regularity of g and strong convexity of ∂_j^k g is insightful and correctly identifies the technical obstacle.","section":null},{"comment":"References: The paper by Wieczorek [2010] is cited as the only prior work on mode estimation under indirect observations. The connection to this paper is clearly delineated (sequential vs. i.i.d. observations). The reference list is appropriate and comprehensive.","section":null},{"comment":"Notation: In Section 4.1, the Hölder class F_β(L) is defined with ℓ = ⌊β⌋ as 'the largest integer strictly less than β.' This is the standard convention (floor for non-integer β, β-1 for integer β). This should perhaps be stated more explicitly to avoid confusion with the convention ⌊β⌋ = β for integer β.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a solid contribution with matching minimax rates. The proofs are detailed and correct upon careful reading. The two major comments are presentation-level: the Gaussian noise restriction in the lower bound should be more prominently flagged relative to the upper bound's weaker noise assumption, and a minor imprecision in the β>2 case of the lower bound proof should be corrected. Neither affects the central claims. The dimension gap is honestly acknowledged as open. The paper fits well in a statistics/optimization journal. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper solves a genuinely new problem: minimax-optimal rates for minimizing the k-th partial derivative of an unknown function g, given only noisy zero-order queries of g itself. The main result is that the optimal rate in the query budget N is N^{-(β-1)/(β+k)}, achieved by a kernel-based projected stochastic gradient method and matched by a lower bound over all sequential algorithms. No prior work covers k≥1 in this sequential setting; the only related result (Wieczorek 2010) handles 1D deconvolution mode estimation with i.i.d. data, which is a different and harder regime. The k=0 case recovers known results from Polyak-Tsybakov and others, which is a good sanity check. What is actually new and well-executed: the two-kernel gradient estimator (Section 4.2) that extracts the k-th derivative along coordinate j and the first derivative along coordinate l simultaneously, using paired queries with Legendre-polynomial-based kernels satisfying moment cancellation conditions. The upper bound chain is clean and transparent: bias bound (Lemma 5.1) exploiting kernel moment conditions, second moment bound (Lemma 5.2) using Lipschitz properties of ∇g on the enlarged set, a Chung-type recursion (Lemma 6.1) handling two forcing terms of different polynomial orders, and standard conversion to optimization error. The lower bound constructs explicit adversarial functions g± = q ± r·h^{β+k}·Φ(x₁/h), verifies all seven regularity properties of the function class, controls the KL divergence to a constant via the choice r_N = c*·N^{-1/2}·h_N^{-(β+k)}, and uses the implicit function theorem to separate the minimizers. The proofs are detailed and self-contained. Soft spots, in proportion: (1) The dimension gap is real — the upper bound carries d^{(2β+k-1)/(β+k)} while the lower bound is dimension-free. The authors acknowledge this honestly but do not resolve it. Standard Assouad constructions do not transfer cleanly because perturbing g along multiple coordinates must preserve both Hölder regularity of g and strong convexity of ∂_j^k g. (2) The lower bound requires Gaussian noise while the upper bound allows general finite-variance noise. Minor mismatch, standard in the literature. (3) Strong convexity of f is load-bearing throughout — it drives the α/2 factor in the recursion, the Chung lemma application, and the distance-to-optimization-error conversion. Relaxation to mere convexity is acknowledged as open and would require substantially different techniques. None of these are correctness issues. The stress-test note traced both proofs in detail and found no load-bearing gaps. I agree with that assessment. This is for researchers at the intersection of zero-order optimization and nonparametric statistics. It deserves a serious referee.","headline":"First minimax analysis for optimizing higher-order derivatives from sequential zero-order queries; matching bounds in N, open dimension gap.","tokens_in":24318,"tokens_out":678,"would_cite":true,"duration_ms":115260,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","90C56","62G05"],"pacs":[],"model":"glm-5.2","headline":"Optimal rate found for minimizing derivatives from noisy queries","keywords":["zero-order optimization","stochastic optimization","minimax lower bounds","kernel estimation","Hölder smoothness","derivative estimation","strong convexity","projected stochastic gradient"],"falsifier":"If one could exhibit a sequential algorithm achieving optimization error o(N^{−(β−1)/(β+k)}) uniformly over the class F'_{α,β,k}, Theorem 5.2 would be falsified. Conversely, if the lower-bound construction's two hypotheses g_± failed to satisfy all seven properties (a)–(g) of the class F'_{α,β,k} simultaneously for the chosen parameters, the lower bound would not apply.","tokens_in":23658,"feed_emoji":"📉","tokens_out":1457,"duration_ms":322825,"temperature":0.7,"pith_summary":"The paper solves the problem of finding the minimizer of the k-th partial derivative f = ∂_j^k g of an unknown function g, when the learner can only query g at sequentially chosen points and receives noisy values. The main result is that the minimax optimal rate of the optimization error E[f(x̂_N) − f*] is exactly N^{−(β−1)/(β+k)} in the total number of queries N, where β ≥ 2 is the Hölder smoothness of f and k ≥ 0 is the order of differentiation. The upper bound is achieved by a kernel-based projected stochastic gradient algorithm using 2d paired queries per iteration with a carefully tuned smoothing parameter h ∝ T^{−1/(2(β+k))}, and the matching lower bound holds over all sequential algorithms, establishing that each additional order of differentiation costs exactly one unit of smoothness in the convergence rate exponent.","feed_headline":"Optimal rate found for minimizing derivatives from noisy queries","feed_subtitle":"Each order of differentiation costs one unit of smoothness: the minimax rate is N^{−(β−1)/(β+k)}, matched above and below.","key_machinery":"The proof of the upper bound combines: (i) a kernel-based gradient estimator (equation 9) using two bounded kernels K_k and K_1 with specific moment-cancellation properties (7)–(8), paired perturbations along e_j and e_l, and h^{−(k+1)} scaling; (ii) a bias bound of order h^{β−1} (Lemma 5.1) exploiting Hölder regularity and kernel moment cancellation; (iii) a second-moment bound of order G^2 + d h^{2(β−1)} + d h^{−2(k+1)} (Lemma 5.2) capturing noise, smoothness of g, and the h^{−(k+1)} amplification; (iv) a Chung-type recursion (Lemma 6.1) for the sequence Δ_t = E[||x_t − x*||^2] with two forcing terms A/(t+t_0) and B/(t+t_0)^2, where the A-term encodes squared bias and the B-term encodesvar","core_discovery":"The central discovery is the exact minimax rate N^{−(β−1)/(β+k)} for zero-order optimization of a k-th order derivative under Hölder smoothness β+k and strong convexity of f. The rate is achieved by a two-kernel gradient estimator: one kernel K_k extracts the k-th derivative along the perturbation coordinate j (using moment-cancellation conditions (7)), and a second kernel K_1 extracts the first-order derivative along each gradient coordinate l (using moment-cancellation conditions (8)). The paired perturbations hUe_j ± hVe_l and the scaling h^{−(k+1)} recover ∂_l ∂_j^k g(x_t) = ∂_l f(x_t) up to a bias of order h^{β−1} and a variance of order h^{−2(k+1)}. The optimal bias-variance trade-off,","pith_inferences":["The smoothness cost of k derivatives being exactly k units in the rate exponent suggests a general principle: for zero-order optimization of any linear functional L[g] that costs s units of smoothness to estimate, the optimal rate should be N^{−(β−1−s)/(β+s)} under analogous assumptions, though this extrapolation is not established in the paper.","The lower-bound construction via two hypotheses g_± = q ± r h^{β+k} Φ(x_1/h) that are indistinguishable under KL divergence ≤ 1/8 yet have k-th derivatives with well-separated minimizers could potentially extend to mixed partial derivatives, though the authors note the two-kernel construction is tailored to a single coordinate direction.","Relaxing strong convexity to mere convexity would likely change the achievable rate, since the α/2 factor in the recursion (30) and the lower-bound reduction (67) both depend on strong convexity to relate optimization error to squared distance from the minimizer."],"forward_implications":["The rate N^{−(β−1)/(β+k)} quantifies precisely how much harder it is to optimize a derivative than the function itself: each order of differentiation k shifts the exponent down by 1/(β+k) relative to the direct case, establishing a smoothness cost calculus for indirect zero-order optimization.","The two-kernel construction (K_k for the derivative direction, K_1 for the gradient direction) provides a template for estimating gradients of composite functionals from zero-order data, potentially extending to mixed partial derivatives and other linear functionals of g.","The gap between the upper bound's dimension factor d^{(2β+k−1)/(β+k)} and the dimension-free lower bound identifies the sharp dimension dependence as the main open problem, analogous to the direct case (k=0) where the exponent 2−1/β is known to be reducible to 1 for β=2,3.","The sequential query structure allows rates depending on d only polynomially, in contrast to passive (i.i.d.) observation where rates depend exponentially on d—a separation between active and passive regimes that extends to derivative optimization."],"fun_headline_variants":["Minimax rate for gradient-free optimization of derivatives under strong convexity","Optimal zero-order optimization of k-th order derivatives from noisy function queries","Each derivative order costs one smoothness unit: minimax rate N^{−(β−1)/(β+k)}","Two-kernel estimator achieves optimal rate for minimizing derivatives without gradients","Matching upper and lower bounds for zero-order derivative optimization under Hölder regula"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The entire argument relies on f = ∂_j^k g being α-strongly convex on Θ, which ensures the minimizer is unique and well-separated, drives the linear convergence factor α/2 in the recursion, and allows the lower bound to convert squared distance into optimization error. Without strong convexity, the minimizer need not be unique and neither the upper-bound recursion nor the lower-bound construction would go through.","fun_headline_variants_meta":{"raw":{"variants":["Minimax rate for gradient-free optimization of derivatives under strong convexity","Optimal zero-order optimization of k-th order derivatives from noisy function queries","Each derivative order costs one smoothness unit: minimax rate N^{−(β−1)/(β+k)}","Two-kernel estimator achieves optimal rate for minimizing derivatives without gradients","Matching upper and lower bounds for zero-order derivative optimization under Hölder regularity"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":731,"prompt_tokens":629,"completion_tokens":102,"prompt_tokens_details":null},"tokens_in":629,"tokens_out":102,"duration_ms":37928,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T16:07:23.701282+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"If one could exhibit a sequential algorithm achieving optimization error o(N^{−(β−1)/(β+k)}) uniformly over the class F'_{α,β,k}, Theorem 5.2 would be falsified. Conversely, if the lower-bound construction's two hypotheses g_± failed to satisfy all seven properties (a)–(g) of the class F'_{α,β,k} simultaneously for the chosen parameters, the lower bound would not apply.","supporting_citations":[],"review_version":1}