Source-linked AI summary
Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
Gon Buzaglo, Guy Kornowski
TL;DR
Constrained stochastic optimization with nonsmooth, nonconvex objectives has lacked strong finite-time guarantees. The paper uses a generic reduction to design first-order algorithms, achieving a dimension-free ˜O(δ^-1ε^-3) gradient complexity that it shows is optimal.
Problem
Constrained nonsmooth nonconvex optimization is challenging to analyze, and much existing work lacks explicit finite-time rates or applies only to deterministic objectives.
Source: §1 · p. 1Method
A generic online-to-nonconvex reduction is used to design projection-based and projection-free stochastic first-order algorithms.
Source: §1.1 · p. 2Results
˜O(δ^-1ε^-3) stochastic-gradient complexity is achieved, and the paper reports this rate as optimal.
Source: §1.1 · p. 2, §4 · p. 5Takeaways & Limitations
The discussion states that the first-order algorithms are dimension-free and that the zeroth-order rate is optimal for the Goldstein residual even in the unconstrained case.
Source: §9 · p. 20The guarantees control the expectation of a stationarity measure; analogous high-probability guarantees are left as a direction for future work.
Source: §9 · p. 20
Abstract
from arXiv · showhide
We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a $(\delta,\varepsilon)$-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities, and are the first to achieve optimal convergence rates for this task in several settings. In particular, we design projection-based and projection-free algorithms that achieve a $\widetilde O(\delta^{-1}\varepsilon^{-3})$ rate using stochastic gradients, which we show to be optimal, and a $\widetilde O(d\delta^{-1}\varepsilon^{-3})$ rate using zeroth-order queries, which is also optimal in its dependence on the dimension $d$ and improves over prior work. Notably, our lower bound is given in terms of the Frank-Wolfe gap and holds even for smooth problems, which is of independent interest. These results show that in nonconvex stochastic optimization, the convergence rate is degraded neither by the presence of constraints nor by nonsmoothness. Our analysis is based on a reduction to online linear optimization, extending a related technique from unconstrained optimization.
1 Introduction
The paper addresses stochastic optimization with nonsmooth, nonconvex objectives and convex constraints, where existing guarantees often lack finite-time rates or apply only to deterministic objectives. It introduces an online-learning reduction and first-order, zeroth-order, and lower-bound results for this setting.
1 Introduction
- Existing work often gives only asymptotic guarantees without finite-time rates, or applies only to deterministic objectives, for constrained nonsmooth nonconvex optimization.These problems arise in adversarial and robust training, norm-constrained neural-network training, and sharpness-aware training.Source: §1 · p. 1
- Liu et al. [2024] established the first non-asymptotic rates, but their zeroth-order complexities scale as O(d^3/2), versus the O(d) optimal complexity known for the analogous unconstrained problem.Whether constraints necessarily make nonsmooth nonconvex optimization harder remained unclear.Source: §1 · pp. 1–2
1.1 Our Contributions
- The proof framework extends Cutkosky et al. [2023] by converting local online learning into constrained optimization and translating online regret into a local stationarity guarantee.The learner's predictions must remain close to one another.Source: §1.1 · p. 2
- Projection-based and projection-free stochastic first-order algorithms achieve ˜O(δ^-1ε^-3) gradient complexity, the first dimension-free rate for this problem class.The paper states that this complexity is optimal.Source: §1.1 · p. 2
- Projection-based and projection-free zeroth-order algorithms achieve ˜O(dδ^-1ε^-3) function-value-query complexity, with optimal dependence on dimension and accuracy parameters.The rate improves over Liu et al. [2024] by a Ω(d) factor in both settings.Source: §1.1 · p. 2
- An Ω(ε^-4) lower bound for stochastic first-order minimization of the Frank-Wolfe gap holds even for smooth objectives and yields matching bounds for Goldstein stationarity measures.The lower bound matches rates of existing smooth algorithms.Source: §1.1 · p. 2
2 Preliminaries
The preliminaries specify the stochastic constrained problem, its stationarity measures, and the local online-learning framework used in the paper. They also relate Goldstein stationarity to standard constrained criteria.
2 Preliminaries
- The Goldstein δ-subdifferential uses nearby Clarke subdifferentials, and the δ-Goldstein residual serves as a stationarity measure that relaxes constrained Lipschitz optimality.In the smooth unconstrained setting, the residual reduces to a standard gradient norm bound.Source: §2 · p. 3
- Unlike Liu et al. [2024], the paper takes a supremum over η rather than fixing η, and states that this guarantees a stronger stationarity condition.The generalized gradient mapping coincides with the standard gradient mapping when g = ∇f(x).Source: §2 · p. 3
- For nonsmooth problems, the δ-Frank-Wolfe gap is introduced; on a compact set, bounding the residual implies a gap bound up to a diameter factor.The Frank-Wolfe gap is a standard optimality criterion in smooth projection-free optimization.Source: §2 · p. 3
- Online linear optimization proceeds over rounds with predictions in a compact convex set; an r-local learner keeps its predictions in a set contained in X ∩ B(x, r).The paper also defines regret for local learners initialized at x.Source: §2 · pp. 3–4
- The problem uses a nonempty closed convex constraint set and a stochastic objective; the paper assumes differentiable stochastic components but does not assume the objective is smooth.Stochastic component gradients are sampled independently at queried points.Source: §2 · p. 4
3 Constrained Online-to-Nonconvex Conversion
The paper extends an online-to-nonconvex conversion to general closed convex constraints. Its guarantee is expressed through a local Frank-Wolfe gap, which later sections relate to global stationarity measures.
3 Constrained Online-to-Nonconvex Conversion
- The conversion extends the nonsmooth online-to-nonconvex framework of Cutkosky et al. [2023] from unconstrained settings to general closed convex constraints.The cited Riemannian-manifold exception of Sahinoglu et al. [2025] excludes boundaries and does not incorporate constraints into stationarity.Source: §3 · p. 4
- Theorem 3.1 assumes a finite initial objective gap and an r-local online learner; its guarantee is stated using a local Frank-Wolfe gap.The local set contains the output and lies within the radius-r neighborhood; later sections relate the gap to Goldstein stationarity measures.Source: §3 · pp. 4–5
- The setup assumes differentiability, but the footnote says randomized smoothing over an arbitrarily small ball can relax that assumption.The authors avoid this technicality in their analysis.Source: §3 · p. 4
- The stochastic-gradient error term can use the noise variance instead of the second moment when the variance is uniformly bounded, yielding a stronger result in low-noise regimes.The passage specifies a uniform variance bound over x ∈ X.Source: §3 · p. 5
4 Projection-based Algorithm
The projection-based method instantiates the conversion with anchored online gradient descent, then addresses why its local gap guarantee alone does not control the Goldstein residual. Repeated projected updates yield the stated residual guarantee, with a matching complexity lower bound.
4 Projection-based Algorithm
- Anchored online gradient descent projects gradient steps onto X and, if needed, moves the result toward the anchor to keep it within radius r, giving a local Frank-Wolfe gap guarantee.Its regret bound applies over X ∩ B(x0, r) without requiring projections onto that intersection.Source: §4 · p. 5
- A local Frank-Wolfe gap alone does not control the Goldstein residual at the smaller η values required by the residual.The controlled quantity is at least min{η∥Gη,X(x,g)∥^2, r∥Gη,X(x,g)∥}, so the stated argument only ensures a small mapping norm for η ≳ r/ε.Source: §4 · p. 5
- Choosing r ≈ δ makes the projected point close enough for g to belong to its Goldstein δ-subdifferential; repeating the process O(log(1/ε)) times controls the displacement error in expectation.The resulting algorithm has the residual guarantee stated in Theorem 4.1.Source: §4 · p. 5
- The first-order complexity lower bound is Ω(∆G^2/(δε^3)) for Goldstein-residual minimization, and the paper reports the same lower bound on a bounded constrained domain.The rate cannot be improved even with deterministic gradients, as shown by Kornowski [2026].Source: §4 · pp. 5–6
5 Projection-Free Algorithm
The projection-free algorithm uses repeated Frank-Wolfe steps to approximate FTRL subproblems, attaining the gradient-oracle complexity of Theorem 5.1 up to universal constants. Its analysis adds LMO calls, with possible improvements under stronger geometric assumptions left for future work.
5 Projection-Free Algorithm
- N=4M Frank-Wolfe iterations approximate each quadratic FTRL subproblem while preserving the regret needed for Theorem 5.1.The method avoids the single-step Online Frank-Wolfe approach, whose regret is too large for the target rates.Source: §5 · p. 6
- The projection-free algorithm achieves the optimal gradient-oracle complexity of Theorem 5.1 up to universal constants.The result is stated for a compact constraint set and uses a linear minimization oracle.Source: §5 · pp. 6–7
- The analysis incurs additional LMO calls; faster Frank-Wolfe variants may help under stronger geometric assumptions, and improving the tradeoff remains future work.The standard FTPL analysis also does not apply because the linear loss depends on the learner’s current prediction.Source: §5 · pp. 6–7
6 Zeroth-Order Optimization
The zeroth-order results use randomized smoothing and a two-point estimator in projection-based and projection-free algorithms. Their query guarantees come with computational costs whose optimal tradeoff with query complexity remains open.
6 Zeroth-Order Optimization
- The method applies Algorithm 1 to the smoothed objective fρ, replacing stochastic-gradient queries with a two-point gradient estimator.The smoothing radius is set to min{δ/2, ∆/(2G)} in both stated theorems.Source: §6 · p. 7
- The zeroth-order algorithms use function-value queries to produce constrained stationarity guarantees in both projection-based and projection-free settings.Theorem 6.1 applies Algorithm 3, while Theorem 6.2 uses Algorithm 1 with Algorithm 4 as its online learner.Source: §6 · p. 7
- Averaging d independent estimators preserves query complexity up to constants while making projection and LMO complexity dimension-free.The resulting costs are eO(∆G^2/(δε^3)) projections or O(∆D^5G^4/(δε^5)) LMO calls.Source: §6 · p. 8
- The optimal tradeoff between query complexity and projection or LMO complexity remains open.As stated, Theorems 6.1 and 6.2 require eO(∆G^2d/(δε^3)) projections and O(∆D^5G^4d^2/(δε^5)) LMO calls, respectively.Source: §6 · p. 8
7 Lower Bounds
The paper establishes a stochastic Frank-Wolfe-gap lower bound even for smooth objectives, then derives lower bounds matching its upper bounds for nonsmooth Goldstein measures. The lower-bound arguments focus on zero-respecting first-order algorithms for concision.
7 Lower Bounds
- A stochastic Frank-Wolfe-gap lower bound was previously unknown, even for smooth objectives, and the paper establishes one.The resulting lower bound is tight: standard minibatched stochastic Frank-Wolfe achieves the same stochastic-gradient complexity under the stated oracle.Source: §7 · p. 8
- The lower bounds for the nonsmooth Goldstein Frank-Wolfe gap and Goldstein residual match the paper’s upper bounds.The authors focus on zero-respecting first-order algorithms for concision, noting that extending the lower bound to any randomized algorithm is standard but technical.Source: §7 · p. 8
- Zhang et al. [2026] established a joint Ω(dG^2∆/(δε^3)) lower bound for the Goldstein residual, matching Theorem 6.1 up to logarithmic factors.That lower bound restricts queries to a bounded ball.Source: §7 · p. 8
- Extending the lower-bound construction to the Goldstein Frank-Wolfe gap is left for future work.The authors state that such an extension appears possible.Source: §7 · p. 9
8 Analysis
The analysis develops tools for constrained OLO-to-nonconvex methods and lower bounds, including smooth stochastic hard instances whose bounds transfer to Goldstein stationarity measures.
8.1 Basic Geometric Properties
- Projection characterization and nonexpansiveness, together with monotonicity of the gradient-mapping norm in its stepsize, provide basic tools for the analysis.Source: §8.1 · p. 9
8.2 Proof of Theorem 3.1: Constrained OLO-to-Nonconvex Conversion
- The constrained OLO-to-nonconvex proof combines local generalized-subgradient membership with unbiased, independent oracle errors and an online-regret bound.It aggregates these ingredients across epochs to establish the conversion guarantee.Source: §8.2 · pp. 10–11
8.3 Projection-Based Application
- The map Φx,r sends every input into X ∩ B(x, r); each trial is accepted with probability at least 1/2, and on acceptance ∇n⋆ belongs to ∂δf(xout).Conditioned on E, the expected norm error between ∇n⋆ and bgn⋆ is at most ε.Source: §8.3 · pp. 11, 13
8.4 Projection-Free Application
- The projection-free proof combines Frank-Wolfe convergence with a quadratic FTRL regret bound to establish the algorithm's guarantee.Source: §8.4 · pp. 14–15
8.5 Zeroth-Order Optimization
- For zeroth-order optimization, a two-point estimator is applied to a smoothed objective, and smoothing-subgradient inclusion transfers its stationarity guarantee to the original objective.The inclusion ensures ∂νfρ(x) ⊆ ∂ρ+νf(x), so ρ + ν ≤ δ yields δ-stationarity membership.Source: §8.5 · pp. 15–16
8.6 Lower Bounds
- The lower-bound construction gives an L-smooth stochastic objective in dimension d ≤ CLΔ/η² with initial gap at most Δ, bounded gradient, and oracle variance at most σ².The associated result considers randomized zero-respecting algorithms making T ≤ cLΔσ²/η⁴ queries.Source: §8.6 · p. 17
- A quadratic radial term converts the hard-coordinate result into a Frank–Wolfe gap lower bound, controlling points near and far from the origin.Under Lemma 8.19’s coordinate conditions, FWf,X(x) ≥ Dη/8.Source: §8.6 · p. 18
- d ≤ CdHΔD²/ε² suffices for Theorem 8.20’s smooth stochastic hard instances on X = B(0, D/2), which impose a query lower bound on randomized zero-respecting first-order algorithms.The mean is H-smooth, with initial suboptimality at most Δ and second moment of stochastic gradients at most G²; the theorem also imposes an output-support condition.Source: §8.6 · p. 18
- d ≤ CdΔD/(δε) yields a Goldstein Frank–Wolfe lower bound via the smooth Frank–Wolfe lower bound and a comparison lemma.Corollary 8.22 uses instances with smoothness ε/(Dδ) and the initial-suboptimality and stochastic-gradient bounds of Theorem 8.20.Source: §8.6 · p. 20
- For X := B(0, D/2), some dimension d ≤ Cd∆/(δε) admits differentiable stochastic components with mean f, where f is ε/δ-smooth and the initial-suboptimality and stochastic-gradient bounds in Theorem 8.20 hold.Source: §8.6 · p. 20
9 Discussion
The discussion summarizes dimension-free first-order guarantees and their optimality, while identifying open extensions and practical burdens. It also describes the authors’ use of AI in developing the paper.
9 Discussion
- The paper gives the first dimension-free first-order algorithms for constrained stochastic Lipschitz objectives without smoothness or convexity assumptions, with optimal rates for randomized zero-respecting algorithms.The discussion also notes that a later lower bound establishes the zeroth-order rate’s optimality for the Goldstein residual in the unconstrained case.Source: §9 · p. 20
- The authors leave overall computational complexity, composite optimization, and analogous high-probability guarantees for future work.They note their guarantees control the expectation of a stronger stationarity measure and say high-probability guarantees should be possible using standard amplification techniques.Source: §9 · p. 20
- The lower bounds are not formally extended from randomized zero-respecting algorithms to arbitrary randomized algorithms, though known reduction techniques may enable that extension.The authors describe the extension as technically involved.Source: §9 · p. 21
- The algorithms require tuning several parameters at different scales, making them less attractive practically and motivating a search for simpler methods with the same guarantees.The authors suggest a reduction to static regret as one possible route.Source: §9 · p. 21
Statement on use of AI
- The authors developed the results interactively with AI models, then independently re-derived, rewrote, and simplified every mathematical argument and take responsibility for the manuscript.Source: Statement on use of AI · p. 21