The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
math.OC · cs.LG
Quick verdict
Proves deterministic methods need (1/ε)^Ω(d) queries for Goldstein stationarity, closing the poly-vs-exp gap; core proof checks out, extensions partly terse.
Summary
This paper resolves an open problem posed by Jordan et al. (2023): whether deterministic first-order algorithms can find (δ,ε)-Goldstein stationary points of Lipschitz nonsmooth nonconvex functions with oracle complexity polynomial in d, 1/δ, and 1/ε. The answer is negative. Building on prior Ω(d) lower bounds, the author proves (Theorem 3.1) that any deterministic local algorithm requires more than (L/32ε)^(d/2) oracle calls — i.e., (1/ε)^Ω(d) — closing the exponential gap to the known randomized dimension-free upper bounds. The proof uses a resisting oracle that answers with local linear functions, fixing the deterministic algorithm's iterates; a spherical-cap union bound (Lemma 4.1) finds a direction w weakly correlated with all pairwise iterate differences; and a support-function construction F (Lemma 4.3) keeps every Goldstein subgradient in a cap bounded away from zero while matching the prescribed affine pieces near each iterate. Extensions show the hard instance can be taken C¹ (§5.1), that a single Goldstein descent step is equally hard (§5.2), that the relaxed (λ,ε)-stationarity of Zhang–Cutkosky inherits the bound (§5.3), and that meaningful deterministic smoothing costs exp(Ω(d)) (§5.4). Limitations: the exponent d/2 is not proven tight against grid-search-type upper bounds; justifications for Corollary 5.2 and parts of §5.3 are terse; the bound holds only above a dimension threshold and for ε < L/32. No code or experiments — a pure theory contribution.
Review complete
Assessment at a glance
2
risk flags identified
● high 0
● medium 1
● low 1
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Any deterministic local algorithm requires more than (L/32ε)^(d/2) oracle calls to guarantee a (δ,ε)-Goldstein stationary point of an L-Lipschitz function (Theorem 3.1).
- Consequently, no deterministic first-order algorithm with poly(d, δ⁻¹, ε⁻¹) oracle complexity exists for this task, answering Jordan et al. [2023]'s open question in the negative.
- The hard instance can be taken continuously differentiable (§5.1), and the same exponential lower bound applies to a single Goldstein descent step (§5.2), (λ,ε)-stationarity (§5.3), and meaningful deterministic smoothing (§5.4).
- Randomization thus offers an exponential — not merely linear — oracle-complexity advantage in nonsmooth nonconvex optimization.
Strengths
Resolves a stated open problem with an exponential improvement
Answers Jordan et al. [2023]'s question negatively: Theorem 3.1 improves the prior Ω(d) deterministic lower bounds (Jordan et al. 2023; Tian & So 2024) to T > (L/32ε)^(d/2), ruling out any poly(d, δ⁻¹, ε⁻¹) deterministic first-order algorithm.
Short, independently checkable proof
The core argument spans ~3 pages; I re-derived the main-line algebra: cap radius ‖z−uv‖² ≤ 2α² < 4ε′², union-bound total ≤ 1/(16ε′²4^d) < 1 for d > log₂(1/(4ε′)) (consistent with the theorem's dimension threshold), and Lemma 4.3's Eq. (5) via σ_Kw(x−z) ≥ D−2r > 2r with r ≤ D/8.
Strong oracle model strengthens the impossibility
One construction yields many corollaries, with transparent AI disclosure
Weaknesses
Corollary 5.2 lacks a formal task definition and full proof
A step in the §5.3 proof is unjustified as written
The exponent is not tight and tightness is not discussed
Restrictive parameter regime
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper resolves, negatively, the open question of Jordan et al. [COLT 2023]: can a deterministic first-order algorithm return a (δ,ε)-Goldstein stationary point of an L-Lipschitz function using poly(d, δ⁻¹, ε⁻¹) oracle calls? The main result (Theorem 3.1) states that for any δ < Δ/L, ε < L/32 and d ≥ ⌈2log₂(L/8ε)⌉, no deterministic local algorithm can guarantee that one of its T iterates is (δ,ε)-Goldstein stationary unless T > (L/32ε)^(d/2). Since randomized algorithms achieve dimension-free complexity [Zhang et al., 2020], this establishes an exponential — not merely linear — advantage of randomization and closes the gap between the prior Ω(d) lower bounds and exhaustive-search upper bounds. Sections 5.1–5.4 extend the result to C¹ objectives, single Goldstein descent steps, (λ,ε)-stationarity [Zhang–Cutkosky 2024], and deterministic smoothing.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 2 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a (δ,ε)-Goldstein stationary point?
For a nonsmooth (Lipschitz) function, it is a point where some convex combination of gradients (or Clarke subgradients) taken from within a δ-ball around the point has norm at most ε. It is the standard tractable surrogate for 'gradient norm ≈ 0' in nonsmooth nonconvex optimization, because true subgradient norms can be uninformative there.
What problem did this paper solve?
Jordan et al. (2023) and Tian–So (2024) showed deterministic algorithms need Ω(d) queries, while randomized algorithms need none dimension-wise, leaving open whether deterministic algorithms could still succeed in poly(d, 1/δ, 1/ε) queries. This paper proves they need (1/ε)^Ω(d) queries, so no polynomial deterministic algorithm exists — randomization helps exponentially.
Does this prove randomization is necessary for training neural networks?
Not directly. The theorem is a worst-case oracle-complexity separation: deterministic local algorithms cannot reliably find (δ,ε)-Goldstein stationary points of Lipschitz functions without exponentially many queries, while randomized ones can. It says nothing definitive about practical deep-learning training dynamics, but it gives the first exponential justification for randomized methods in this setting.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Novelty and concurrent-work status could not be verified offline (no network access); the 'resolves an open problem' assessment relies on the paper's own literature account.
- Figure 1 is available only as extracted text; the visual geometry of the construction was not independently checked.
- PDF text extraction garbles some display equations; proofs were verified at the level of the extracted content, with main-line algebra re-derived.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.