{"id":"848e69c9-9c56-488e-92af-8dd03a709369","arxiv_id":"2508.13496","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For functions satisfying an (α,β) subgradient growth condition, the paper's variance-reduced randomized smoothing method reaches a (δ,ε)-Goldstein stationary point in Õ(d^{3/2}δ^{-1}ε^{-3}) function evaluations with high probability.","lead":"Randomized smoothing is a standard trick for minimizing rough functions by averaging randomly perturbed values. This paper weakens the usual global smoothness assumption, proving new convergence rates for three derivative-free algorithms, with a near-optimal query count when variance reduction is added.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's rate is conditional on exact oracle access to α,β,σ,ℓ, which the main theorems never assume and the algorithms never compute.","rationale":"The Reader's weakest_assumption identifies the same concern: the main theorems do not list exact knowledge of α(x_t), β(x_t,r), σ(x_t), and ℓ(x_t,r) as an assumption, yet the step-size and batch-size formulas require these quantities at every iterate. This is the single most load-bearing issue for the central claim because, without it, the stated Õ(d^{3/2}δ^{-1}ε^{-3}) complexity is not the complexity of a well-defined zeroth-order algorithm. The paper's own Conclusion admits reliance on knowing α and β, which is an in-scope limitation statement that should be weighed. I did not find a deeper mathematical contradiction: under the additional assumption that these quantities are supplied exactly, the proof structure for Theorem 3 appears coherent, including the variance-reduction argument and the high-probability boundedness argument. The level-boundedness assumption is explicit and restricts the function class, but it is a stated condition rather than a hidden gap; I therefore treat it as secondary. The experiments tune hyperparameters and do not implement the theorem formulas, so they do not resolve the implementability concern. The verdict should remain CONDITIONAL: acceptance should require either an explicit assumption that α,β,σ,ℓ are available exactly, or a parameter-free variant that estimates them from function values without changing the rate.","tokens_in":26777,"tokens_out":16715,"duration_ms":171647,"concrete_test":"Implement Algorithm 3 exactly as specified in Theorem 3 on a one-dimensional toy f(x)=x^4+|x|, using closed-form α,β,σ,ℓ and the theorem's own formulas: η_t from (4.3), B_{s0}=⌈72σ²(x_{s0})Tδ/√d⌉, b_s=⌈72qd⌉, q=⌈ε^{-1}⌉, with no grid tuning of step sizes or batch sizes. Count function evaluations needed to reach min_t∥∇fδ(x_t)∥≤ε for ε=10^{-1},10^{-2},10^{-3} and check whether the empirical scaling is ε^{-3}. In a companion run, estimate α,β,σ,ℓ by finite differences from function values only; if the two implementations differ in rate by more than logarithmic factors, the missing-oracle assumption is confirmed as load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing claim is Theorem 3 (Appendix D): with high probability, RS-NVRGF finds a (δ,ε)-Goldstein stationary point with Õ(d^{3/2}δ^{-1}ε^{-3}) zeroth-order oracle calls. For this to be a theorem about an implementable zeroth-order method, the algorithm must be able to set its step sizes and batch sizes. The formulas (4.1)-(4.3), and their formal versions in Appendix D, define η_t, B_{s0}, and b_s in terms of α(x_t), β(x_t,δ), σ(x_t), and ℓ(x_t,r). None of these quantities is an output of the zeroth-order oracle (which returns only function values), and no procedure is given for estimating or computing them. The formal Theorems 1-3 list Assumption 1 (level-boundedness of fδ) as the substantive assumption; exact knowledge of α,β,σ,ℓ is not stated as an assumption. The paper itself concedes this in the Conclusion: 'our result relies on the assumption of knowing α and β. A possible direction is to design a parameter-free method.' The experimental section does not close the gap: step sizes are tuned from a grid and batch sizes are selected from a small set, rather than set by the theorem formulas. Thus, as stated, the high-probability ε^{-3} rate is a conditional statement about a parameter-idealized algorithm, not about a fully specified zeroth-order procedure. I did not find an internal contradiction in the proof under the additional assumption that these quantities are available; the missing assumption is the soft spot.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an (α,β) subgradient growth condition as a replacement for the global Lipschitz assumption in nonsmooth nonconvex optimization, and shows that spherical randomized smoothing of such functions yields a locally smooth surrogate. It then introduces three zeroth-order algorithms—RS-GF, RS-NGF, and RS-NVRGF—and claims high-probability convergence to (δ,ε)-Goldstein stationary points with sample complexities Õ(d^{5/2}δ^{-1}ε^{-4}), Õ(d^{3/2}δ^{-1}ε^{-4}), and Õ(d^{3/2}δ^{-1}ε^{-3}), respectively. The last rate is advertised as matching the optimal ε-dependence previously known only for globally Lipschitz functions. The paper includes detailed appendix proofs, examples of the new function class, and numerical experiments on a sensor-network-like problem and on black-box CIFAR attacks.","tokens_in":27122,"tokens_out":15287,"duration_ms":156457,"significance":"If the central theorems were valid for an implementable zeroth-order procedure, the paper would make a useful extension of randomized-smoothing theory to locally Lipschitz, possibly non-globally-Lipschitz objectives. The local smoothness proposition for fδ and the high-probability machinery are nontrivial and are supported by detailed derivations. The main limitation is that the algorithms' step sizes and batch sizes depend on exact values of α(x_t), β(x_t,·), σ(x_t), and ℓ(x_t,·), which are not outputs of a zeroth-order oracle and are not stated as assumptions in the formal theorems. The paper's own conclusion concedes this, but the abstract and theorem statements overclaim by presenting the rates as unconditional zeroth-order oracle complexities. Because the mathematical core appears sound under an explicit idealized oracle, the contribution is salvageable with a substantial revision.","major_comments":[{"comment":"The step-size and batch-size formulas (4.1)–(4.3) and their formal versions in Appendix D require exact evaluation at every iterate of α(x_t), β(x_t,δ), β(x_t,r), σ(x_t), and ℓ(x_t,r). These quantities are not produced by the stated zeroth-order oracle, which returns only function values, and no estimation procedure or oracle model for them is provided. The formal theorems list only Assumption 1 (level-boundedness of fδ) as the substantive assumption. The Conclusion states that 'our result relies on the assumption of knowing α and β,' but this limitation is not incorporated into the theorem statements or the abstract. The experiments do not close the gap because step sizes are tuned on a grid and batch sizes are selected from a small set rather than set by the theorem's formulas. As stated, the high-probability ε^{-3} rate is a conditional statement about a parameter-idealized algorithm, not a guarantee for a fully specified zeroth-order method.","section":"Section 4, Theorems 1–3, Algorithms 1–3; Conclusion, Section 6"},{"comment":"The proof asserts that C_t = O(Δ d^{-1/4}δ^{1/2}) and uses this to conclude the iteration complexity T = Õ(d^{1/2}δ^{-1}ε^{-2}). This is not a valid derivation as written: with ℓ(x,r) = c√d(2α(x)+β(x,δ)+β(x,r+δ))/(2δ), the term √(Δ/(3ℓ(x,·))) is at least of order √(Δδ/(√d M)), where M = sup_{x∈Q}(2α(x)+β(x,·)+β(x,·)) over the level set Q. The displayed bound omits M and also conflates an upper bound with the lower bound actually needed to control 1/C_path. The claimed d-, δ-, and ε-scaling may still be correct after absorbing problem-dependent constants, but the proof as written is incomplete and should explicitly introduce and track such constants.","section":"Appendix D, proof of Theorem 2, around Eq. (D.23)"}],"minor_comments":[{"comment":"The informal step-size formula (4.1) uses c_{t,δ} = α(x_t)+β(x_t,3δ) consistently, while the formal version of Theorem 1 uses β(x_t,δ) in the second term of C_t and β(x_t,3δ) in the others; the notation should be aligned.","section":"Section 4.1 and Appendix D, Theorem 1"},{"comment":"The normalized update x_{t+1} = x_t - η_t m_t/‖m_t‖ is undefined when m_t = 0; a convention for that zero-probability or degenerate event should be stated for completeness.","section":"Algorithm 3 and Theorem 3"},{"comment":"The paper states early that f is lower bounded by f* and that a Δ > fδ(x1)-f* is available, but these requirements are not listed in the formal theorem hypotheses alongside Assumption 1; they should be made explicit.","section":"Notation and Assumption 1"},{"comment":"In the Bernstein argument the text uses both log(2/p) and log(2T/p) in the step-size bound and in the definition of c; these should be made consistent because the final probability p/T depends on the T-dependent logarithmic factor.","section":"Appendix D, proof of Theorem 1"},{"comment":"The displayed expression for the recursion of m_t contains a sign ambiguity in the terms involving g(x_{t-1},S) and g(x_t,S); the intended centered random variable should be written explicitly to avoid confusion.","section":"Appendix C, Lemma 11 proof"}],"recommendation":"major_revision","confidential_remarks":"The missing-oracle issue is acknowledged by the authors themselves in the Conclusion, so a revision that adds an explicit exact-oracle assumption or an adaptive estimation scheme is feasible. Without such a change, the abstract and theorem statements materially overclaim what is proven for a true zeroth-order method."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper genuinely extends randomized smoothing beyond global Lipschitz continuity. The (α,β) subgradient growth condition is a real generalization, covering L-smooth gradients, generalized smoothness, polynomial growth, and even exponential growth. The local smoothing analysis is careful, and the variance-reduced algorithm hits the near-optimal O~(d^{3/2}δ^{-1}ε^{-3}) high-probability Goldstein-stationarity rate. I read the appendix proofs and found no internal contradiction in the conditional claims. That is a substantive contribution.\n\nThe soft spot is load-bearing: the step sizes and batch sizes in Theorems 1–3 are defined in terms of α(x_t), β(x_t,·), σ(x_t), and ℓ(x_t,·). None of these quantities is available from the zeroth-order oracle, and the theorems never list their exact knowledge as an assumption. The paper admits this in the conclusion — \"our result relies on the assumption of knowing α and β\" — but the formal statements still describe Algorithms 1–3 as implementable procedures. As stated, the rates hold for an idealized algorithm with a parameter oracle, not for the algorithm as written. The experiments tune these quantities from grids, which confirms the gap rather than closing it. This does not invalidate the mathematics, but it changes what the paper actually proves.\n\nA few smaller issues: there is a minor inconsistency in the Theorem 2 proof where the batch-size term appears as B_s in one line and √B_s in the bound, and the informal main-text statements of the batch sizes differ from the formal appendix versions. These are fixable.\n\nWho should read this: researchers in nonsmooth nonconvex zeroth-order optimization, especially those working on relaxed Lipschitz frameworks. The conditional rates and the (α,β) class itself are worth knowing. The paper deserves a serious referee: the missing assumption can be stated, and the authors either need to provide an estimation procedure for the local parameters or develop a parameter-free variant. I would engage with it, but I would ask for that gap to be closed before accepting the algorithmic claims as stated.","headline":"A real extension of randomized smoothing rates to a locally Lipschitz class, but the main theorems silently assume exact knowledge of α,β,σ,ℓ, which a zeroth-order algorithm cannot have.","tokens_in":27648,"tokens_out":2659,"would_cite":true,"duration_ms":30659,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C56","49J52"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomized smoothing provably works when the objective has no global Lipschitz constant.","keywords":["randomized smoothing","nonsmooth nonconvex optimization","Goldstein stationarity","subgradient growth condition","zeroth-order oracle","variance reduction","gradient-free optimization","generalized smoothness"],"falsifier":"Take $f(x)=\\exp(|x|)-x^3$ in $d=1$ with $\\alpha(x)=\\exp(|x|)+3x^2$ and run RS-NVRGF with finite-difference estimates of $\\alpha$ and $\\beta$ replacing the exact values in the step-size formulas: if no such implementable variant reaches a $(10^{-4},\\epsilon)$-Goldstein point with $O(\\epsilon^{-3})$ oracle calls, the hidden-exactness premise is doing the work; conversely, a concrete trajectory where the exact-schedule theorem fails to hold would refute the claimed bound.","tokens_in":26550,"feed_emoji":"🎲","tokens_out":6753,"duration_ms":68917,"temperature":0.7,"pith_summary":"The paper asks whether randomized smoothing can be analyzed when the objective is not globally Lipschitz, which has been the standard assumption in this area. It introduces an $(\\alpha,\\beta)$ subgradient growth condition that bounds local subgradient norms by $\\alpha(x)$ and controls how that bound varies between nearby points, strictly generalizing global Lipschitz continuity and covering polynomial and exponential local growth. Under this condition, spherical smoothing produces a differentiable function with a point-dependent smoothness constant, and the paper develops three gradient-free algorithms whose best variant reaches a $(\\delta,\\epsilon)$-Goldstein stationary point with high probability using $\\tilde{\\mathcal{O}}(d^{3/2}\\delta^{-1}\\epsilon^{-3})$ function evaluations. This matches the best previously known $\\epsilon$-dependence for globally Lipschitz problems, up to logarithmic factors. The practical caveat, acknowledged in the conclusion, is that the step-size rules require exact knowledge of the local growth quantities at every iterate.","feed_headline":"Randomized smoothing reaches near-optimal rates beyond Lipschitz","feed_subtitle":"A local growth condition and variance reduction match the best known oracle cost, down to epsilon^-3, without a global Lipschitz bound.","key_machinery":"The load-bearing object is the $(\\alpha,\\beta)$ subgradient growth condition and its propagation through spherical smoothing. It converts an unbounded local Lipschitz constant into a point-dependent smoothness constant of $f_\\delta$, which then feeds directly into the step-size formulas (4.1)--(4.3). The variance-reduced loop of Algorithm 3 uses periodic large batches to reduce gradient-estimator variance, which is what lowers the $\\epsilon$-exponent from $-4$ to $-3$.","core_discovery":"The central claim is that the global Lipschitz assumption can be replaced by a strictly weaker local growth condition without losing the convergence rates of randomized smoothing. A function $f$ satisfies the $(\\alpha,\\beta)$ subgradient growth condition if every Clarke subgradient at $x$ has norm at most $\\alpha(x)$, and $|\\alpha(x)-\\alpha(y)| \\le \\beta(x,\\|x-y\\|)$ with $\\beta$ non-decreasing in the radius. Spherical smoothing $f_\\delta(x)=\\mathbb{E}_{w\\sim U(B_1(0))} f(x+\\delta w)$ then gives a continuously differentiable function whose gradient lies in the Goldstein $\\delta$-subdifferential, and the paper proves a local descent inequality with smoothness constant $\\ell(x,r)=c\\sqrt{d}(2\\alpha(x)+\\beta(x,\\delta)+\\beta(x,r+\\delta))/(2\\delta)$. Under level-boundedness of $f_\\delta$ and with step sizes that adapt to $\\alpha(x_t)$, $\\beta(x_t,\\cdot)$, $\\sigma(x_t)$, and $\\ell(x_t,\\cdot)$, the paper proves high-probability convergence to a $(\\delta,\\epsilon)$-Goldstein stationary point for three algorithms; the variance-reduced RS-NVRGF attains the $\\epsilon^{-3}$ sample complexity previously tied to global Lipschitz assumptions.","pith_inferences":["A natural next step is a parameter-free variant that estimates $\\alpha$ and $\\beta$ online from function-value queries; the step-size logic suggests that conservative estimates keeping iterates inside the level set would be enough to preserve the rates.","The analysis suggests the real barrier is not global Lipschitzness itself but control of subgradient growth over the bounded level set, so other function classes with such local control may inherit the same rates.","For composite objectives that arise in adversarial attacks and sensor-network localization, replacing exact growth quantities with finite-difference estimates would make the variance-reduced rate testable in practice, although the paper does not supply that analysis."],"forward_implications":["If the central claim is correct, any level-bounded objective satisfying the $(\\alpha,\\beta)$ growth condition can be optimized by zeroth-order randomized smoothing at essentially the same $\\epsilon$-rate as globally Lipschitz objectives.","The three rates are $\\tilde{\\mathcal{O}}(d^{5/2}\\delta^{-1}\\epsilon^{-4})$ for RS-GF, $\\tilde{\\mathcal{O}}(d^{3/2}\\delta^{-1}\\epsilon^{-4})$ for RS-NGF, and $\\tilde{\\mathcal{O}}(d^{3/2}\\delta^{-1}\\epsilon^{-3})$ for RS-NVRGF, showing that normalization improves the dimension dependence and variance reduction improves the $\\epsilon$-dependence.","The stationarity guarantee is a $(\\delta,\\epsilon)$-Goldstein stationary point, the standard tractable surrogate for Clarke stationarity in nonsmooth nonconvex problems.","The non-polynomial example $f(x)=\\exp(|x|)-x^3$ shows the function class is not limited to polynomial subgradient bounds, so the analysis covers objectives that previously fell outside the known randomized-smoothing theory.","The high-probability rates depend on exact evaluation of $\\alpha(x_t)$, $\\beta(x_t,\\cdot)$, $\\sigma(x_t)$, and $\\ell(x_t,\\cdot)$ at every iterate; without that access, the stated complexity bounds are not tied to an implementable procedure."],"supporting_citations":[{"why":"supplies the spherical-smoothing gradient estimator and the Goldstein-stationarity convergence template this paper extends.","marker":"Lin et al. [2022]"},{"why":"supplies the variance-reduced gradient-free algorithm and the optimal $\\epsilon^{-3}$ complexity benchmark for the globally Lipschitz case.","marker":"Chen et al. [2023a]"},{"why":"establishes randomized smoothing as a derivative-free method whose convolution gradient is unbiased.","marker":"Nesterov and Spokoiny [2017]"},{"why":"provides the sub-Gaussian concentration inequality used to control the function-value estimator variance.","marker":"Wainwright [2019]"},{"why":"provides the martingale Bernstein inequality used in the high-probability bounded-iterates argument.","marker":"Chezhegov et al. [2024]"},{"why":"provides the normalized-gradient inequality used to analyze the normalized step-size methods.","marker":"Hübler et al. [2024]"},{"why":"provides the SPIDER variance-reduction mechanism that Algorithm 3 adapts.","marker":"Fang et al. [2018]"}],"fun_headline_variants":["Randomized smoothing drops global Lipschitz, keeps near-optimal rates","Local growth condition unlocks optimal smoothing without Lipschitz","Smoothing beyond Lipschitz: optimal rates via local growth","Variance-reduced smoothing matches optimal complexity without Lipschitz","Relaxed Lipschitz assumption yields near-optimal randomized smoothing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the algorithm can be handed exact values, at each step, of the local constants that describe how steep the function is and how smooth its smoothed version is near the current point; the theorems assume these values are available to set step sizes, and the paper only notes at the end that a parameter-free method is left for future work.","fun_headline_variants_meta":{"raw":{"variants":["Randomized smoothing drops global Lipschitz, keeps near-optimal rates","Local growth condition unlocks optimal smoothing without Lipschitz","Smoothing beyond Lipschitz: optimal rates via local growth","Variance-reduced smoothing matches optimal complexity without Lipschitz","Relaxed Lipschitz assumption yields near-optimal randomized smoothing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000282,"raw_usage":{"total_tokens":1708,"prompt_tokens":1026,"completion_tokens":682,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":642,"completion_tokens_details":{"reasoning_tokens":594}},"tokens_in":642,"tokens_out":682,"duration_ms":6846,"temperature":1.0,"reasoning_tokens":594,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:14:45.500245+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $f(x)=\\exp(|x|)-x^3$ in $d=1$ with $\\alpha(x)=\\exp(|x|)+3x^2$ and run RS-NVRGF with finite-difference estimates of $\\alpha$ and $\\beta$ replacing the exact values in the step-size formulas: if no such implementable variant reaches a $(10^{-4},\\epsilon)$-Goldstein point with $O(\\epsilon^{-3})$ oracle calls, the hidden-exactness premise is doing the work; conversely, a concrete trajectory where the exact-schedule theorem fails to hold would refute the claimed bound.","supporting_citations":[{"cited_title":"Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization","cited_arxiv_id":null,"evidence_quote":"supplies the spherical-smoothing gradient estimator and the Goldstein-stationarity convergence template this paper extends."},{"cited_title":"Random gradient-free minimization of convex functions","cited_arxiv_id":null,"evidence_quote":"establishes randomized smoothing as a derivative-free method whose convolution gradient is unbiased."}],"review_version":1}