Optimal Deterministic Oracle Complexity for Weakly Convex Optimization

Jiajin Li; Siyu Pan

Optimal Deterministic Oracle Complexity for Weakly Convex Optimization

T0 review · 0 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Every deterministic first-order method needs Ω(ρG²Δ/ε⁴) oracle queries to reach an ε-stationary point of a weakly convex nonsmooth function, matching all known upper bounds and pinning the ε⁻⁴ cost on nonsmooth geometry itself.

desk verdict Tight deterministic lower bound for weakly convex optimization, with a genuinely new hard-instance construction; the proof looks sound and deserves peer review. read the letter →

arxiv 2608.03246 v1 pith:UBFDMIBD submitted 2026-08-04 math.OC

Jiajin Li , Siyu Pan This is my paper

classification math.OC MSC 90C2690C3049J5290C60

keywords weaklyconvexoptimizationoraclecomplexityMoreauenvelopedeterministiclowerboundzero-chainconstructionnonsmoothnonconvexfullsubdifferentialepsilon-stationarypoint

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a tight lower bound on how many queries a deterministic first-order optimization method must make to find an approximate stationary point of a weakly convex, nonsmooth function. It shows that, in the small-gap regime $\Delta \le G^2/\rho$, every method using function values and full subdifferentials requires at least $\Omega(\rho G^2\Delta/\epsilon^4)$ queries, where $\rho$ is the weak-convexity modulus, $G$ is the Lipschitz constant, and $\Delta$ is the initial gap. This matches the best known deterministic and stochastic upper bounds up to universal constants, so the bound is optimal for the class. The result implies that the extra $\epsilon^{-2}$ factor over smooth nonconvex optimization is an intrinsic cost of nonsmooth geometry, not an artifact of stochastic noise or subgradient selection.

What carries the argument

The load-bearing object is a generalized zero-chain with a diagonal coordinate filtration: nested coordinate subspaces $V_t$ with $\dim(V_{t+1}/V_t) \le 6$. The hard instance satisfies the setwise zero-chain property $\partial \bar{f}(x) \subseteq V_{t+1}$ whenever $x \in V_t$, so every oracle query reveals at most a constant number of previously hidden coordinates. The construction pairs a tilted max-affine convex block $\phi(u) = \max\{0, \max_j (c_j - (N/8)u_j)\}$ with strictly decreasing intercepts — which enforces the one-step locality of the subdifferential — with a smooth progress function $\psi$ that couples $M$ copies of the block into an overlapping relay. This converts a within-bl

What would settle it

Implement the unscaled hard instance for small admissible $(M,N)$ (e.g., $N=60$, $M=2$) and compute $\|\nabla \bar{f}_{1/2}(y)\|$ for $y \in V_{H-1}$; if any reachable point has Moreau gradient at most $1/(8\sqrt{N})$, the certificate (C3) fails. Equivalently, a deterministic first-order algorithm that provably returns an $\epsilon$-stationary point on every $f \in F(G,\rho,\Delta)$ in $o(\rho G^2\Delta/\epsilon^4)$ queries would falsify Theorem 3.2.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.2: there exist numerical constants $c_0, c_1 > 0$ such that for any $G, \rho, \Delta > 0$ and $\epsilon$ with $\epsilon^2 \le c_0 \min\{G^2, \rho\Delta\}$, every deterministic first-order algorithm requires at least $c_1 G^2 \min\{\rho\Delta, G^2\}/\epsilon^4$ oracle queries to find a point with $\|\nabla f_{1/(2\rho)}(x)\| \le \epsilon$ for some $f$ in the class of $G$-Lipschitz, $\rho$-weakly convex functions with initial gap $\Delta$. The oracle returns both the function value and the full subdifferential, so the difficulty cannot be blamed on subgradient selection. The proof constructs an explicit hard instance by coupling $M = \Theta(\rho\$\Delta$/\$epsilon^{2}$)

Load-bearing premise

The bound holds under the definition of stationarity as $\|\nabla f_{1/(2\rho)}(x)\| \le \epsilon$; if the problem class were judged by a different stationarity criterion, such as the norm of a subgradient, the $\epsilon^{-4}$ complexity could be different.

Editorial extensions

If this is right

No deterministic first-order method can beat the existing O(ε⁻⁴) algorithms on this function class; the ε⁻⁴ rate is optimal.
The Θ(ε⁻²) complexity of smooth nonconvex optimization cannot be achieved for nonsmooth weakly convex problems; the extra ε⁻² factor is intrinsic to nonsmooth geometry.
Because the oracle returns the full subdifferential, the lower bound is independent of how subgradients are selected; any algorithm that only sees a single subgradient is no better off.
The bound applies to deterministic outputs and query points alike, so termination rules and post-processing cannot reduce the query cost.
The Moreau-envelope stationarity measure is the right lens for this class: under it, stochastic and deterministic methods both hit the same optimal complexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the diagonal-zero-chain construction can be made robust to small random projections, the lower bound may extend to randomized algorithms through a minimax argument, resolving the randomized case the authors leave open.
The strong dependence on the stationarity measure suggests that switching to, say, subgradient-norm stationarity might change the complexity; one testable direction is to compute the analogous lower bound under that measure.
The constant-width diagonal filtration could generalize to other composite problems where multiple information barriers overlap, potentially yielding lower bounds for convex-composite or difference-of-convex optimization.
The paper's machine-checked formalization offers a way to verify the four certificates on concrete instances, which could serve as a template for certifying future lower-bound constructions.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

This paper closes a real gap: it gives the Ω(ρG²Δ/ε⁴) deterministic oracle lower bound for nonsmooth weakly convex optimization under the full subdifferential oracle, matching the known upper bounds up to constants. That was not a routine extension of Carmon et al. The hard instance is the contribution: the tilted max-affine block plus the relay coupling across blocks, with the constant-width diagonal filtration handling the overlapping information flow. On close reading, the setwise zero-chain property (Proposition 5.2) does the load-bearing work, and it appears to hold even in the delicate cases—unreached blocks have strictly negative scores, partially revealed blocks expose at most one next coordinate. The finite-horizon resisting oracle argument in Section 6 is a clean adaptation, and the dimension counting is sufficient even with linear dependencies.

The paper is honest about its structure and gives explicit constants throughout. The proofs are self-contained except for standard references. I share the reader's verdict: no internal contradiction found, no circularity. The stationarity measure—gradient of the Moreau envelope—is a stated premise, not a hidden assumption, and it is the standard notion in this literature. The full subdifferential oracle makes the lower bound stronger, not weaker.

Soft spots, in proportion: the AI Disclosure cites a Lean formalization but does not include the code or pin a commit hash. That is a verification gap rather than a mathematical one, but it means the delicate subdifferential calculus in Lemma 5.3 and Proposition 5.2 is not independently machine-checked. The authors should be asked to supply the exact repository state. Also, the result covers deterministic algorithms only; the stochastic case is left open, which is fine for this paper but worth noting in the conclusion.

Who is this for? Anyone working on complexity of nonsmooth nonconvex optimization. It separates smooth nonconvex from nonsmooth weakly convex cleanly, and it gives the optimization theory community a new construction technique that may transfer to randomized lower bounds.

My take: accept for peer review. The core argument is novel, detailed, and reads as correct. The referee should focus on the zero-chain verification and ask for the pinned Lean artifact, but this is not a desk-reject and not a "needs major revision" in substance. I would cite it, and I would bring it to a reading group if anyone in the group cares about oracle complexity.

Recommendation: send to referees.

Referee Report

0 major / 4 minor

Summary. The paper proves a deterministic oracle lower bound for finding ε-stationary points of ρ-weakly convex, G-Lipschitz nonsmooth functions, where stationarity is measured by the norm of the Moreau-envelope gradient. The main result (Theorem 3.2) states that, for ε² ≤ c0 min{G², ρΔ}, every deterministic first-order algorithm requires Ω(G² min{ρΔ, G²}/ε⁴) oracle queries, which is Ω(ρG²Δ/ε⁴) in the small-gap regime Δ ≤ G²/ρ. The proof constructs a hard instance from M tilted max-affine convex blocks coupled by smooth progress functions, and verifies a constant-width diagonal zero-chain property. A lower bound for generalized zero-respecting algorithms (Theorem 3.1) is derived from four certificates (Condition 3.1), then extended to arbitrary deterministic algorithms by a finite-horizon resisting-oracle argument and rotation invariance (Section 6). The lower bound matches the known deterministic and stochastic upper bounds.

Significance. If correct, the result settles the deterministic oracle complexity of weakly convex nonsmooth optimization and shows that the extra ε^{-2} factor relative to smooth nonconvex optimization is intrinsic to nonsmooth geometry rather than stochasticity. The paper is unusually explicit: numerical constants c0 and c1 are stated, the hard instance is given in closed form, and the four certificates are verified in Sections 5.1–5.4. The construction addresses the stronger full-subdifferential oracle through a setwise zero-chain property (Proposition 5.2), and the rotation argument (Lemma 6.2) properly handles set-valued oracle responses. I found no circularity: the lower bound is constructed from scratch, and upper bounds are cited only for context. The principal caveat is that the claimed Lean formalization is not included or pinned, so the verification claim could not be independently checked.

minor comments (4)

[Section 7 / AI Disclosure] The paper states that an accompanying Lean formalization is available at a GitHub URL and 'provides a formal verification of the deterministic first-order oracle lower bound', but no commit hash, archive, or extracted proof is included. Since the mathematical proof is self-contained, this does not affect the correctness assessment, but the verification claim should be made checkable (e.g., by providing a pinned artifact/DOI) or softened.
[Definition 2.2] The notation f_{1/(2ρ)} for the Moreau envelope with parameter 1/(2ρ) is slightly nonstandard. The definition min_z f(z)+ρ‖x−z‖² disambiguates it, but a one-sentence pointer to the standard convention (e.g., Davis and Drusvyatskiy [2019]) would help readers.
[Section 5.3, Proposition 5.3] In the estimate for ψ(z^M), the inequality q(t) ≤ 3t_+² is used without proof. It follows directly from the definition of q, but stating it explicitly would make the verification of the terminal-layer bound easier to follow.
[Section 3.1, Proposition 3.1] The line 'N ≥ G²/(128ε²)' uses the rounding bound floor(u) ≥ u/2 for u ≥ 2 silently. Adding a parenthetical would improve readability, since this is part of the parameter accounting.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; lower bound is derived from an explicit hard instance and verified certificates.

full rationale

The paper's central claim is a deterministic oracle lower bound, and its derivation chain is self-contained. Theorem 3.1 is reduced by Proposition 3.1 to four certificate conditions (C1)-(C4) on an explicit unscaled hard instance, which is defined in Eq. (1) from tilted max-affine blocks and a smooth progress function. The certificates are then proved directly: Proposition 5.1 establishes 1-Lipschitz and 1-weak convexity, Proposition 5.2 establishes the full-subdifferential zero-chain property, Proposition 5.3 establishes the Moreau-gradient lower bound before the terminal layer, and Proposition 5.4 bounds the initial gap. The stationarity measure—the gradient of the Moreau envelope—is a stated assumption (Definition 2.2), not a hidden input smuggled into the construction; the lower bound is conditional on that standard measure. The hard instance is not fitted to any algorithm or to the target complexity; it is a single explicit function used adversarially. Theorem 3.2 extends the zero-respecting bound to arbitrary deterministic algorithms through the classical finite-horizon rotation/resisting-oracle argument (Lemma 6.2), with rotation invariance proved in Lemma 6.1 and Appendix Lemma A.1. No load-bearing step invokes a self-citation or assumes the theorem being proved. The only residual caveat is the AI Disclosure's claim of an accompanying Lean formalization, which is not machine-checked within the submission; this is a verification risk, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 3 invented entities

The paper introduces three new mathematical constructs; none has independent empirical evidence, but they are part of a proof, not hypothesized physical entities. No free parameters are fitted; all constants in the construction are set analytically.

assumptions (4)

standard math Subdifferential calculus for weakly convex functions (chain rule and max rule)
Used in Lemma 5.3 to characterize ∂f from the variational representation, citing Rockafellar and Wets 2009.
standard math Moreau envelope gradient identity: ∇f_{1/(2ρ)}(x) = 2ρ(x - prox_{1/(2ρ)} f (x))
Used throughout to connect stationarity with proximal operator, citing Davis and Drusvyatskiy 2019 Lemma 2.2.
standard math Weak convexity is preserved under pointwise max with common modulus
Used in Proposition 5.1 to show f is 3/4-weakly convex from the max representation.
domain assumption The full subdifferential oracle model returns all active subgradients, including convex combinations
This is the oracle model in Definition 2.3; the hardness result is stated for this strong oracle, and the construction must defeat it.

invented entities (3)

Tilted max-affine block
purpose: A convex hard block satisfying the setwise zero-chain property for the full subdifferential oracle
Introduced in Section 4.1; its entire subdifferential shifts by at most one coordinate. It is a proof construct, not a physical entity.
Constant-width diagonal filtration
purpose: Tracks interleaved propagation of oracle information across overlapping blocks
Defined in Section 5.2; each layer contains at most 6 coordinates, enabling the Θ(MN) horizon. It is an analytic device.
Weakly convex relay coupling
purpose: Couples M blocks so that progress in block m-1 is needed to activate block m
Defined in Section 4.2 via ψ and σ_m; produces the overlapping relay. It is a construction device.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal Deterministic Oracle Complexity for Weakly Convex Optimization." pith.science (2026). https://pith.science/paper/UBFDMIBD

@misc{pith2026260803246,
  author       = {Pith},
  title        = {Pith review of: Optimal Deterministic Oracle Complexity for Weakly Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UBFDMIBD}},
  note         = {Machine review of arXiv:2608.03246}
}

abstract

We study the oracle complexity of finding $\epsilon$-stationary points of $\rho$-weakly convex and $G$-Lipschitz functions, where stationarity is measured by the gradient of the Moreau envelope. We consider a first-order oracle that returns both the function value and the full subdifferential at every query point. We prove that every deterministic first-order algorithm requires $ \Omega({\rho G^2\Delta}/{\epsilon^4})$ oracle queries whenever $\Delta \leq {G^2}/{\rho}$, where $f(\bz)-\inf f \leq \Delta$. This lower bound matches the best known deterministic and stochastic first-order upper bounds, up to universal constants, and establishes the optimal deterministic oracle complexity. The result reveals a fundamental complexity separation between smooth nonconvex and nonsmooth weakly convex optimization. While smooth nonconvex minimization admits a $\Theta(\epsilon^{-2})$ oracle complexity, nonsmooth weakly convex optimization incurs an intrinsic additional $\epsilon^{-2}$ factor arising from nonsmooth geometry rather than stochasticity.

Figures

Figures reproduced from arXiv: 2608.03246 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 16 canonical work pages

[1]

Mathematics of Operations Research , volume=

The cost of nonconvexity in deterministic nonsmooth optimization , author=. Mathematics of Operations Research , volume=. 2024 , publisher=

work page 2024
[2]

Mathematics of Operations Research , volume=

Strong and weak convexity of sets and functions , author=. Mathematics of Operations Research , volume=. 1983 , publisher=

1983
[3]

2004 , publisher=

Fundamentals of Convex Analysis , author=. 2004 , publisher=

work page 2004
[4]

Mathematical Programming , volume=

Efficiency of minimizing compositions of convex functions and smooth maps , author=. Mathematical Programming , volume=. 2019 , publisher=

2019
[5]

Proximit

Moreau, Jean-Jacques , journal=. Proximit
[6]

Stochastic subgradient method converges at the rate

Davis, Damek and Drusvyatskiy, Dmitriy , journal=. Stochastic subgradient method converges at the rate

work page
[7]

SIAM journal on optimization , volume=

Stochastic first-and zeroth-order methods for nonconvex stochastic programming , author=. SIAM journal on optimization , volume=. 2013 , publisher=

2013
[8]

ICML Workshop on Beyond First-Order Methods in ML Systems , pages=

On the hardness of computing near-approximate stationary points of Clarke regular nonsmooth nonconvex problems and certain DC programs , author=. ICML Workshop on Beyond First-Order Methods in ML Systems , pages=

work page

Show all 25 references

[9]

arXiv preprint arXiv:2509.02804 , year=

A proximal descent method for minimizing weakly convex optimization , author=. arXiv preprint arXiv:2509.02804 , year=

arXiv
[10]

SIAM Journal on Optimization , volume=

Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems , author=. SIAM Journal on Optimization , volume=. 2019 , publisher=

2019
[11]

SIAM Journal on Optimization , volume=

Stochastic methods for composite and weakly convex optimization problems , author=. SIAM Journal on Optimization , volume=. 2018 , publisher=

2018
[12]

Mathematical Programming , volume=

Lower bounds for non-convex stochastic optimization , author=. Mathematical Programming , volume=. 2023 , publisher=

2023
[13]

2009 , publisher=

Variational Analysis , author=. 2009 , publisher=

2009
[14]

Journal of Complexity , volume=

Information-based complexity of linear operator equations , author=. Journal of Complexity , volume=. 1992 , publisher=

1992
[15]

Advances in Neural Information Processing Systems , volume=

Tight complexity bounds for optimizing composite objectives , author=. Advances in Neural Information Processing Systems , volume=
[16]

and Hinder, Oliver and Sidford, Aaron , journal=

Carmon, Yair and Duchi, John C. and Hinder, Oliver and Sidford, Aaron , journal=. Lower bounds for finding stationary points. 2020 , publisher=

2020
[17]

and Hinder, Oliver and Sidford, Aaron , title =

Carmon, Yair and Duchi, John C. and Hinder, Oliver and Sidford, Aaron , title =. Mathematical Programming , year =
[18]

SIAM Journal on Optimization , year =

Davis, Damek and Drusvyatskiy, Dmitriy , title =. SIAM Journal on Optimization , year =
[19]

Lower bounds for parallel and randomized convex optimization , journal =

Diakonikolas, Jelena and Guzm. Lower bounds for parallel and randomized convex optimization , journal =. 2020 , volume =

2020
[20]

Journal of Machine Learning Research , year =

Kornowski, Guy and Shamir, Ohad , title =. Journal of Machine Learning Research , year =
[21]

Nemirovski, A. S. and Yudin, D. B. , title =. 1983 , note =

1983
[22]

Nesterov, Yurii , title =
[23]

Mathematical Programming , year =

Tian, Lai and So, Anthony Man-Cho , title =. Mathematical Programming , year =
[24]

2017 , eprint =

Woodworth, Blake and Srebro, Nathan , title =. 2017 , eprint =

2017
[25]

Proceedings of the 37th International Conference on Machine Learning , editor =

Zhang, Jingzhao and Lin, Hongzhou and Jegelka, Stefanie and Sra, Suvrit and Jadbabaie, Ali , title =. Proceedings of the 37th International Conference on Machine Learning , editor =

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

Mathematics of Operations Research , volume=

The cost of nonconvexity in deterministic nonsmooth optimization , author=. Mathematics of Operations Research , volume=. 2024 , publisher=

work page 2024

[2] [2]

Mathematics of Operations Research , volume=

Strong and weak convexity of sets and functions , author=. Mathematics of Operations Research , volume=. 1983 , publisher=

1983

[3] [3]

2004 , publisher=

Fundamentals of Convex Analysis , author=. 2004 , publisher=

work page 2004

[4] [4]

Mathematical Programming , volume=

Efficiency of minimizing compositions of convex functions and smooth maps , author=. Mathematical Programming , volume=. 2019 , publisher=

2019

[5] [5]

Proximit

Moreau, Jean-Jacques , journal=. Proximit

[6] [6]

Stochastic subgradient method converges at the rate

Davis, Damek and Drusvyatskiy, Dmitriy , journal=. Stochastic subgradient method converges at the rate

work page

[7] [7]

SIAM journal on optimization , volume=

Stochastic first-and zeroth-order methods for nonconvex stochastic programming , author=. SIAM journal on optimization , volume=. 2013 , publisher=

2013

[8] [8]

ICML Workshop on Beyond First-Order Methods in ML Systems , pages=

On the hardness of computing near-approximate stationary points of Clarke regular nonsmooth nonconvex problems and certain DC programs , author=. ICML Workshop on Beyond First-Order Methods in ML Systems , pages=

work page