Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

arXiv:2610.13787v1 [math.OC] 9 Oct 2026

Gon Buzaglo Princeton University

Guy Kornowski Institute for Advanced Study Abstract

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 (δ, ε)-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 e −1 ε−3 ) rate using stochastic gradients, projection-based and projection-free algorithms that achieve a O(δ −1 −3 e which we show to be optimal, and a O(dδ ε ) 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

We consider stochastic optimization problems of the form min f (x) := Eξ∼Ξ [F (x; ξ)] ,

x∈X

(1)

where the objective f : Rd → R is neither smooth nor convex, subject to a closed convex constraint set X ⊆ Rd . Such problems arise naturally in machine learning applications, including in adversarial attacks and robust training [Szegedy et al., 2014, Madry et al., 2018, Wang et al., 2019, Qi et al., 2024], norm-constrained training of deep neural networks [Goodfellow et al., 2013, Srivastava et al., 2014], and sharpness-aware training [Foret et al., 2021, Chen et al., 2023, Mordido et al., 2024]. Nonetheless, despite its prevalence, constrained nonsmooth nonconvex optimization is rather challenging to analyze, with most existing work guaranteeing either only asymptotic convergence without explicit finite-time rates, or only applying to deterministic objectives, or both [Curtis and Overton, 2012, Hare et al., 2016, Ruszczyński, 2020, Davis et al., 2020, Ermol’ev and Norkin, 1998, Hoseini Monjezi and Nobakhtian, 2021, Grimmer and Jia, 2025]. Recently, Liu et al. [2024] provided the first non-asymptotic convergence rates for algorithms solving problem (1). To do so, the authors defined two novel stationarity measures suitable for constrained nonsmooth optimization, which generalize the classic gradient mapping norm and the Frank-Wolfe gap, both of which are common measures for smooth constrained optimization, by replacing classical gradients with the Goldstein subdifferential. The Goldstein subdifferential, which is the convex hull of nearby Clarke subdifferentials [Goldstein, 1977, Clarke, 1990], has played a key role in non-asymptotic analyses of (unconstrained) nonsmooth nonconvex optimization problems in recent years following Zhang et al. [2020], since the norm of individual gradients cannot be minimized efficiently in general [Kornowski and Shamir, 2022]. While Liu et al. [2024] established convergence rates for several zeroth-order methods, it is notable that these rates are strictly worse than those achievable for unconstrained optimization when X = Rd . In 1

particular, the complexities of the algorithms therein all scale as O(d3/2 ) where d is the problem’s dimension, whereas in the analogous unconstrained problem, the optimal complexity is known to be O(d) [Kornowski and Shamir, 2024]. This raises the natural question, asked by Liu et al. [2024], of whether the complexity achieved in their work can be further improved. In particular, it remained unclear whether incorporating constraints necessarily makes nonsmooth nonconvex optimization harder to solve.

1.1

Our Contributions

In our work, we design and analyze both first-order and zeroth-order algorithms for constrained nonsmooth nonconvex stochastic optimization, extending as well as strictly improving the complexities obtained by Liu et al. [2024]. We establish optimal convergence rates for our algorithms with matching lower bounds, which in particular prove that constrained nonsmooth optimization is as easy as unconstrained smooth optimization in terms of query complexity for nonconvex stochastic problems, namely neither constraints nor nonsmoothness degrade the convergence rates. Our contributions can be summarized as follows: • Reduction from Constrained Optimization to Online Learning (Theorem 3.1): As our main proof technique, we extend the online-to-nonconvex framework of Cutkosky et al. [2023] to optimization over a closed convex constraint set. Our reduction converts any online learning algorithm that is “local” in the sense that its predictions remain close to one another, into a constrained optimization algorithm, and translates the online learner’s regret into a local constrained-stationarity guarantee. • First-Order Algorithms (Theorem 4.1 and Theorem 5.1): We use our generic reduction to design stochastic first-order algorithms with optimal gradient oracle complexity for problem (1). In particular, by using classic online learning algorithms such as online gradient descent (OGD) [Zinkevich, 2003] or follow the regularized leader (FTRL) [Shalev-Shwartz and Singer, 2007] and applying our reduction, we obtain e −1 ε−3 ) stochastic graprojection-based and projection-free algorithms which, in both cases, require O(δ dients to converge to a constrained approximate-stationary point (formally defined in Section 2). These are the first gradient-based algorithms for this problem class that are equipped with dimension-free complexity, which as we will further show, is optimal. • Zeroth-Order Algorithms (Theorems 6.1 and 6.2): We further discuss zeroth-order algorithms that only query noisy function values, and obtain projection-based and projection-free algorithms which, in both e −1 ε−3 ) function-value queries to converge to a constrained approximate-stationary cases, require O(dδ √ point. This improves over the complexities obtained by Liu et al. [2024] by a Ω( d) factor in both projection-based and projection-free settings, and has optimal dependence on both the dimension and the accuracy parameters, with the recent joint lower bound of Zhang et al. [2026] matching our rate for the Goldstein residual. • Matching Lower Bounds (Section 7): Finally, we adapt the lower bound technique of Arjevani et al. [2023] to the discussed setting. In particular, we prove an Ω(ε−4 ) lower bound on the first-order complexity of minimizing the Frank-Wolfe gap in stochastic nonconvex optimization. Our lower bound holds even for smooth objectives and matches the rates of existing smooth algorithms [Reddi et al., 2016]. As we show, this result further yields matching lower bounds for both the Goldstein Frank-Wolfe gap and the Goldstein residual (to be defined in Section 2), establishing the optimality of our convergence rates.

2

Preliminaries

Notation. We use bold-faced letters for vectors, e.g., x ∈ Rd , and ∥ · ∥ denotes the Euclidean norm. We denote [n] := {1, . . . , n}, B(x, r) := {y : ∥y − x∥ ≤ r}, and dist(x, A) := inf a∈A ∥x − a∥, and denote by conv (·) the convex hull operator and by Unif(A) the uniform measure over a set A. The projection of a point y ∈ Rd onto a closed convex set X is denoted by ΠX (y) := arg minx∈X ∥x − y∥. We say that a function f : Rd → R is L-Lipschitz if |f (x) − f (y)| ≤ L∥x − y∥ for all x, y ∈ Rd , and H-smooth if it is 2

differentiable and ∥∇f (x) − ∇f (y)∥ ≤ H∥x − y∥. We follow standard big-O notation with O (·) , Ω (·) , Θ (·) hiding constants that do not depend on problem parameters and Õ (·) , Ω̃ (·) , Θ̃ (·) suppressing logarithmic factors. Nonsmooth analysis. By Rademacher’s theorem, Lipschitz functions are differentiable almost everywhere. Therefore, for a Lipschitz function f : Rd → R and point x ∈ Rd the Clarke subdifferential [Clarke, 1990] is well-defined as the convex hull of all limit points of ∇f (xn ) over all sequences of differentiable points which converge to x, formally defined as ∂f (x) := conv{g : g = limn→∞ ∇f (xn ), xn → x} . The Clarke subdifferential becomes the subdifferential for a convex f , or the gradient if f is continuously differentiable. Constrained nonsmooth optimization. Throughout the paper, we let the constraint set X ⊆ Rd be a nonempty closed convex set. For x ∈ X , g ∈ Rd , and η > 0, we define the mapping Gη,X (x, g) := η1 x −
ΠX (x − ηg) , which coincides with the gradient mapping when g = ∇f (x), whose norm is a standard stationarity criterion for constrained smooth optimization [Ghadimi and Lan, 2016, Ghadimi et al., 2016]. In this paper, following Liu et al. [2024], we let δ ≥
0 and consider the generalized gradient mapping with g ∈ ∂δ f (x), where ∂δ f (x) := conv ∪y∈B(x,δ) ∂f (y) is the Goldstein δ-subdifferential [Goldstein, 1977, Zhang et al., 2020]. We define the δ-Goldstein residual of f at x ∈ X as Rf,X δ (x) :=

min

sup ∥Gη,X (x, g)∥ =

g∈∂δ f (x) η>0

min g∈∂δ f (x)

dist −g, NX (x) ,



where NX (x) := n ∈ Rd : ⟨n, y − x⟩ ≤ 0 for every y ∈ X denotes the normal cone of X at x ∈ X , and the equality above is proved in Lemma 8.2. The Goldstein residual above will serve as a stationarity measure. Note that this definition reduces to a standard gradient norm bound in the smooth unconstrained setting, since NRd (x) = {0} and ∂0 f (x) = {∇f (x)}. Moreover, the δ-Goldstein residual relaxes the standard optimality condition 0 ∈ ∂f (x) + NX (x) for constrained Lipschitz optimization (see Borwein and Lewis, 2006, Corollary 6.3.9). Remark 2.1. Liu et al. [2024] considered stationarity with respect to a fixed parameter η > 0, as opposed to taking the supremum over η as we do. Thus, it is notable that our results not only provide improved complexities, but also guarantee a stronger stationarity condition. If X is compact with some finite diameter D, the Frank-Wolfe gap maxu∈X ⟨∇f (x), x − u⟩ is yet another standard optimality criterion, prevalent in the smooth projection-free optimization literature [LacosteJulien, 2016]. For nonsmooth problems, Liu et al. [2024] introduced the δ-Frank-Wolfe gap as FWf,X δ (x) :=

min

max ⟨g, x − u⟩ .

g∈∂δ f (x) u∈X

f,X We show that FWf,X δ (x) ≤ D · Rδ (x) in Lemma 8.3, namely the two notions differ by at most a diameter factor, and therefore bounding the residual over a compact set implies a bound on the gap. Section 8.1 further contains some useful results related to the discussed stationarity measures.

Online linear optimization. Online linear optimization (OLO) is a standard framework for sequential decision-making without stochastic assumptions [Cesa-Bianchi et al., 2006, Hazan, 2016, Orabona, 2019], which proceeds as follows: Over M ∈ N rounds, an adversary chooses loss vectors ℓm ∈ Rd ; at each round, the learner chooses ym ∈ C from a compact convex set C ⊆ Rd before observing ℓm , and incurs loss ⟨ℓm , ym ⟩. We use the following local class of OLO algorithms. Definition 2.2. Let X be nonempty, closed, and convex, and let r > 0. An r-local OLO algorithm A associates with every initialization x ∈ X a nonempty compact convex set CA (x) ⊆ X ∩ B(x, r), depending only on x and with x ∈ CA (x), so that all predictions of A initialized at x lie in CA (x). 3

Algorithm 1: Online-to-nonconvex conversion(x0 , K, M, r, A) Input: initialization x0 ∈ X , r-local online learner A, epoch budget K, epoch length M . 1 for k = 0, 1, . . . , K − 1 do 2 initialize a fresh copy Ak of A at xk ; 3 for m = 1, . . . , M do 4 obtain prediction yk,m from Ak ; 5 sample sk,m ∼ Unif([0, 1]); 6 zk,m ← xk + sk,m (yk,m − xk ); 7 sample ξk,m ∼ Ξ; 8 query gk,m ← ∇F (zk,m ; ξk,m ); 9 send gk,m to Ak ; 10

sample Jk ∼ Unif([M ]) and xk+1 ← yk,Jk ;

sample I ∼ Unif({0, . . . , K − 1});
PM 1 M 12 return xI , (zI,m )m=1 , M m=1 gI,m ; 11

In Sections 4 and 5, we obtain such local learners from standard OLO algorithms with a small computational modification. Their regret when initialized at x is defined as RegretA (x; ℓ1 , . . . , ℓM ) :=

max y∈CA (x)

M X

⟨ℓm , ym − y⟩ .

m=1

Problem setting. We consider a stochastic optimization problem associated to an objective f : Rd → R of the form f (x) = Eξ∼Ξ [F (x; ξ)], subject to a nonempty closed convex set X ⊆ Rd . For simplicity, we assume that f and the stochastic components F (·; ξ) are differentiable, but do not assume that f is smooth.1 We assume access to stochastic component gradients: Given any point x ∈ X , the oracle samples ξ ∼ Ξ independently and returns ∇F (x; ξ), satisfying Eξ [∥∇F (x; ξ)∥2 ] ≤ G2 .

Eξ [∇F (x; ξ)] = ∇f (x),

3

Constrained Online-to-Nonconvex Conversion

We present a reduction from constrained nonconvex optimization to online learning in Algorithm 1. While some earlier online-to-nonconvex results assumed smoothness [Agarwal et al., 2019, Hallak et al., 2021], we rely on the nonsmooth conversion of Cutkosky et al. [2023], with subsequent works extending this approach in various directions [Zhang and Cutkosky, 2024, Ahn et al., 2024, Ahn and Cutkosky, 2024, Ahn et al., 2025]. These results focus on unconstrained optimization,2 whereas Algorithm 1 allows general closed convex constraints. The next result summarizes its guarantee: Theorem 3.1. Assume x0 ∈ X satisfies f (x0 ) − inf x∈X f (x) ≤ ∆ < ∞, and let A be an r-local online learner. The output of Algorithm 1 satisfies  E h i D 1 XM f,CA (xI ) ∇f (zI,m ), xI − y E FWr (xI ) ≤ E maxy∈CA (xI ) m=1 M 1 The differentiability assumption can be relaxed using standard randomized smoothing (over an arbitrarily small ball), yielding a differentiable objective; see [Cutkosky et al., 2023, Davis et al., 2022]. We choose to avoid this slight technicality altogether in our work. 2 A notable exception is the work of Sahinoglu et al. [2025], which extended the online-to-nonconvex framework to Riemannian manifolds. However, their setting is incomparable to ours as it excludes boundaries and therefore does not require incorporating the constraints into the stationarity notion.

4

Algorithm 2: Online gradient descent with an anchor(x0 , r, α) Input: anchor x0 ∈ X , radius r > 0, step size α > 0. 1 y1 ← x0 ; 2 for m = 1, . . . , M do 3 predict ym ; 4 receive loss vector ℓm ; 5 vm ← ΠX (ym − αℓm ); 6 if ∥vm − x0 ∥ ≤ r then 7 ym+1 ← vm ; 8 else −x0 ; 9 ym+1 ← x0 + r ∥vvm m −x0 ∥ 10

return yM +1 ;

≤

∆ 1 XK−1 rG + E [RegretA (xk ; gk,1 , . . . , gk,M )] + √ . k=0 K KM M

(2)

The guarantee in Theorem 3.1 is stated in terms of the local Frank-Wolfe gap over CA (xI ) ⊆ X ∩ B(xI , r), which contains the output xI . In Sections 4 and 5, respectively, we relate this local gap to the √ Goldstein residual and the global Goldstein Frank-Wolfe gap. We further remark that the additive rG/ M term in Eq. (2) can be relaxed to depend on the variance of the stochastic gradients instead of the√second moment. In particular, whenever supx∈X Eξ [∥∇F (x; ξ) − ∇f (x)∥2 ] ≤ σ 2 , it can be replaced by rσ/ M , which yields a slightly stronger result in low-noise regimes.

4

Projection-based Algorithm

In this section, we instantiate Algorithm 1 with a variant of online gradient descent [Zinkevich, 2003] as the online learner. Starting from x0 , Algorithm 2 projects each gradient step onto X , and, if necessary, moves the projected point toward x0 so that it remains in B(x0 , r), which ensures the r-local OLO property. To analyze Algorithm 2, we build on the simple observation that OGD does not need projections onto X ∩ B(x0 , r) but rather only that for any point y ∈ X ∩ B(x0 , r), the update satisfies ∥ym+1 − y∥ ≤ ∥ym − αℓm − y∥. Hence the standard regret bound holds over X ∩ B(x0 , r), as we show in Lemmas 8.5 and 8.6. Plugged into Theorem 3.1, this yields a local Frank-Wolfe gap guarantee. However, this alone is insufficient to control the Goldstein residual. Indeed, Theorem 3.1 controls the local quantity maxy∈X ∩B(x,r) ⟨g, x − y⟩, where g is the average gradient returned by the conversion. This quantity is at least min{η∥Gη,X (x, g)∥2 , r∥Gη,X (x, g)∥} (as we show in Lemma 8.4), thus OGD can achieve ∥Gη,X (x, g)∥ ≤ ε only for η ≳ r/ε, and since the mapping norm is non-increasing in η by Lemma 8.2, this does not control the smaller η parameters needed for the Goldstein residual. The key observation is that ∥x − ΠX (x − ηg)∥ = η∥Gη,X (x, g)∥ ≲ r, thus taking r ≈ δ ensures that g ∈ ∂δ f (ΠX (x − ηg)), rather than g ∈ ∂δ f (x). This displacement introduces an additional error term which is controlled in expectation, so Algorithm 3 repeats this process O(log(1/ε))-many times to ensure the final residual bound, resulting in the following: Theorem 4.1. lLet ε, δ > 0. Assume x0 ∈ X satisfies f (x0 ) − inf x∈X f (x) ≤ ∆ < ∞.  Run  Algorithm 3 with
m  48∆  
 2 r 4G ∆G 96G 2 e r = δ/5, M = , α = G√M , K = rε , N = 2 log ε . Then, using O δε3 stochastic-gradient ε out queries, it returns xout ∈ X satisfying E[Rf,X )] ≤ ε. δ (x

The gradient oracle complexity of Theorem 4.1 is optimal (up to a logarithmic factor). Indeed, in the unconstrained setting as a particular case, the lower bounds of Arjevani et al. [2023], Cutkosky et al. [2023] already imply an Ω(∆G2 /(δε3 )) rate for the Goldstein residual, since for X = Rd the residual reduces to the 5

Algorithm 3: Projection-based wrapper algorithm(x0 , r, ε, K, M, N, α) Input: initialization x0 , parameters r, ε, K, M, N, α. 1 n⋆ ← N ; 2 A := Algorithm 2(·, r, α); 3 for n = 1, . . . , N do bn ) ← Algorithm 1(x0 , K, M, r, A); 4 (xn , (zn,m )M m=1 , g
b 5 pn ← ΠX xn − 6r ε gn ; 6 if ∥xn − pn ∥ ≤ 4r then 7 n⋆ ← n; 8 break; 9

return xout = pn⋆ ;

Algorithm 4: Projection-free follow-the-regularized-leader(x0 , δ, α, M, N ) Input: Initialization x0 , radius δ, step size α, budgets M, N . 1 for m = 1, . . . , M do 2 w0 ← x0 ; 3 for n = 0, . . . , N  − 1 do  Pm−1 −1 4 vn ← LMOX (wn − x0 ) ; j=1 ℓj + α 
 2 δ δ n wn + n+2 1− D x0 + D vn ; 5 wn+1 ← n+2 6

predict ym ← wN and obtain loss vector ℓm ;

standard Goldstein stationarity measure. Complementarily, Corollary 8.23 derives the same lower bound on a bounded constrained domain. Moreover, as recently shown by Kornowski [2026], this rate cannot be improved even if the gradients are deterministic.

5

Projection-Free Algorithm

In this section, we additionally assume that X is compact with diameter D := maxx,y∈X ∥x − y∥ < ∞, and replace projections by access to a linear minimization oracle LMOX (y) ∈ arg min ⟨y, x⟩ , x∈X

which, in many applications, is substantially cheaper to evaluate [Jaggi et al., 2010, Lacoste-Julien et al., 2013, Jaggi, 2013, Combettes and Pokutta, 2021]. A natural projection-free choice for the OLO algorithm is Follow-the-Perturbed-Leader (FTPL) [Kalai and Vempala, 2005, Hazan and Minasyan, 2020]. However, in our conversion, the linear loss depends on the learner’s current prediction, which invalidates the standard FTPL analysis. Another natural candidate is Online Frank-Wolfe (OFW) [Hazan √ and Kale, 2012], which uses only one LMO call per round but has regret much larger than the O(δG M ) needed for our optimal rates. As observed by Kretzu and Garber [2021], OFW can be viewed as approximately implementing Follow-theRegularized-Leader (FTRL) [Shalev-Shwartz and Singer, 2007] by taking a single Frank-Wolfe step toward the minimizer of the current FTRL objective. We instead use N iterations of the Frank-Wolfe algorithm [Frank and Wolfe, 1956, Jaggi, 2013]√to approximate each quadratic FTRL subproblem in Algorithm 4. Taking N = 4M preserves the O(δG M ) regret (Proposition 8.10) and hence the optimal gradient oracle complexity of Theorem 5.1:

6

Algorithm 5: Two-point gradient estimator(z, ρ, ξ) Input: query point z ∈ Rd , smoothing radius ρ > 0, stochastic sample ξ. d−1 1 sample u ∼ Unif(S ); 2 query F (z + ρu; ξ) and F (z − ρu; ξ);
d 3 return F (z + ρu; ξ) − F (z − ρu; ξ) u; 2ρ

Theorem 5.1. Let εl > 0 andm 0 < δ < D. Assume x0 ∈ X satisfies f (x0 ) − inf x∈X f (x) ≤ ∆ < ∞. Set  
2 K = 2∆D , M = 6DG , N = 4M, α = G√δ M . Run Algorithm 1 with r = δ and Algorithm 4 as A. Then, δε ε  3 2 G out using O ∆D stochastic-gradient queries, it returns xout ∈ X satisfying E[FWf,X )] ≤ ε. δ (x δε3 We later provide in Theorem 8.20 a lower bound for the Frank-Wolfe gap even for smooth objectives, while Corollary 8.22 yields the matching Ω(∆D3 G2 /(δε3 )) lower bound for the Goldstein Frank-Wolfe gap. Thus, the gradient oracle complexity of Theorem 5.1 is optimal up to universal constants. Notably, the analysis described above introduces an additional cost in terms of LMO calls. Faster Frank-Wolfe variants can improve this complexity under stronger geometric assumptions on X [Garber and Hazan, 2015, 2016], while other projection-free online methods use different oracle models [Mhammedi, 2022, 2025]. Extending our approach in these directions is left for future work.

6

Zeroth-Order Optimization

In this section, instead of access to a stochastic-gradient oracle, we assume access to stochastic component values F (x; ξ). We assume that each stochastic component F ( · ; ξ) : Rd → R is L(ξ)-Lipschitz, with Eξ∼Ξ [L(ξ)2 ] ≤ G2 . As is standard in this setting, we will make use of a two-point gradient estimator of the randomized smoothing. To that end, the uniform smoothing over a ball of a function f is defined as fρ (x) := Ez∼Unif(B(0,ρ)) [f (x + z)] . √ It is well known (see Yousefian et al., 2012, Duchi et al., 2012) that fρ is G-Lipschitz, is O( dGρ−1 )-smooth, and satisfies |f (x) − fρ (x)| ≤ ρG for every x ∈ Rd . To obtain zeroth-order results, we simply apply Algorithm 1 to fρ , by replacing its stochastic-gradient query by a call to the gradient estimator of Algorithm 5 with inputs zk,m , ρ, ξk,m . The formal analysis, which is deferred to Section 8.5, yields the following results: Theorem 6.1. Let ε, δ > 0. Assume x0 ∈ X satisfies f (x0 ) − inf x∈X f (x) ≤ ∆, and set ρ := min{δ/2, ∆/(2G)}. Run Algorithm 3 on fρ using Algorithm 5, with  parameters  chosen as in Theorem 4.1, with (G, δ, ∆) there re√ ∆G2 d 1/4 e placed by (4(2π) function-value queries, it returns xout ∈ X satisfying dG, δ/2, 2∆). Then, using O 3 δε

out E[Rf,X )] ≤ ε. δ (x

Theorem 6.2. Let ε > 0. Suppose X is compact with diameter D, and let 0 < δ < D. Assume x0 ∈ X satisfies f (x0 ) − inf x∈X f (x) ≤ ∆, and set ρ := min{δ/2, ∆/(2G)}. Run Algorithm 1 on fρ using Algorithm √ 5 and Algo1/4 rithm 4 as A, with chosen as in Theorem 5.1, with (G, δ, ∆) there replaced by (4(2π) dG, δ/2, 2∆).  parameters  Then, using O

∆D 3 G2 d δε3

out function-value queries, it returns xout ∈ X satisfying E[FWf,X )] ≤ ε. δ (x

As previously mentioned, both of the results above improve over the query complexities of Liu et al. √ [2024] by a factor of Ω( d).

7

Remark 6.3 (Overall complexity and parallel computation). Although our zeroth-order algorithms attain the optimal dependence of the query complexity on the dimension and stationarity parameters discussed above, it is not clear whether their computational complexity is optimal in terms of the number of projections or LMO calls. Note that as 2 e stated, Theorems 6.1 and 6.2 require O(∆G d/(δε3 )) projections and O(∆D5 G4 d2 /(δε5 )) LMO calls, respectively. However, as in Kornowski and Shamir [2024], these computational costs can be reduced by averaging independent zeroth-order gradient estimators, a standard approach for trading query complexity for parallel computation [Duchi et al., 2018, Bubeck et al., 2019]: At each gradient query, we can average b independent two-point estimators, thus reducing their second moment from order dG2 to G2 (1+d/b), while using b times as many samples per round. Taking b = d preserves the query complexity up to constants, while making the projection/LMO complexity dimension-free, 2 e with O(∆G /(δε3 )) projections or O(∆D5 G4 /(δε5 )) LMO calls. In contrast, the guarantees of Liu et al. [2024] retain an explicit dependence on d in their computational complexity, although with a better dependence on ε. Determining the optimal tradeoff between query and projection/LMO-oracle complexity remains open.

7

Lower Bounds

We further show that the convergence rates obtained in this work are essentially optimal. For simplicity, we prove lower bounds for (possibly-)randomized zero-respecting first-order algorithms, a class of algorithms which includes all algorithms of interest in this setting (including our first-order algorithms). Extending such a lower bound to any randomized algorithm is by now standard in the literature [Carmon et al., 2020, Arjevani et al., 2023, Cutkosky et al., 2023], while still being rather technical. As this is not the main result in our paper but rather complementary to demonstrate the optimality of our algorithms, we chose to focus here on zero-respecting algorithms for the sake of conciseness. We state the lower bounds informally here and defer their formal statements and proofs to Section 8.6, where we also define the class of zero-respecting algorithms. We start by providing a lower bound in terms of the Frank-Wolfe gap. Although the Frank-Wolfe gap is a standard stationarity measure for constrained nonconvex optimization and is widely used to analyze projection-free methods [Jaggi, 2013, Lacoste-Julien, 2016], to our knowledge, no complexity lower bound for the Frank-Wolfe gap was previously known in the stochastic setting, even for smooth objectives. Our first result provides such a lower bound. Theorem 7.1 (Theorem 8.20, informal). Under mild parameter conditions, there is a dimension d = O(H∆D2 /ε2 ) such that for any zero-respecting first-order algorithm there is an H-smooth stochastic  objectivef satisfying f (0) −

inf x∈X f (x) ≤ ∆ for which achieving expected Frank-Wolfe gap at most ε requires Ω queries.

∆HG2 D 4 ε4

stochastic-gradient

Theorem 8.20 gives a tight lower bound, as the standard minibatched stochastic Frank-Wolfe method [Reddi et al., 2016] achieves the same stochastic-gradient complexity under our stochastic first-order oracle. As a consequence of the theorem above, we obtain lower bounds for the nonsmooth Goldstein FrankWolfe gap and for the Goldstein residual which match our upper bounds. Corollary 7.2 (Corollaries 8.22  informal). Under the same setting as above, achieving expected δ-Frank and 8.23, 3

2

G stochastic-gradient queries, and achieving expected δ-Goldstein residual at Wolfe gap at most ε requires Ω ∆D δε3  2 most ε requires Ω ∆G stochastic-gradient queries. δε3

For the Goldstein residual, the resulting rate recovers the known lower bounds from unconstrained nonsmooth nonconvex optimization [Arjevani et al., 2023, Cutkosky et al., 2023]. Moreover, Kornowski [2026] recently showed that the same lower bound holds even in the deterministic-gradient setting. In the zeroth-order setting, the dependence on the dimension and on the stationarity parameters δ, ε is optimal separately [Duchi et al., 2015, Cutkosky et al., 2023, Kornowski and Shamir, 2024]. Moreover, Zhang et al. [2026] recently established the joint Ω(dG2 ∆/(δε3 )) lower bound for the Goldstein residual, matching Theorem 6.1 up to logarithmic factors. Their lower bound restricts queries to a bounded ball, a restriction 8

that appears removable by the standard soft-projection construction [Carmon et al., 2020]. Extending their construction to the Goldstein Frank-Wolfe gap appears possible and is left for future work.

8

Analysis

8.1

Basic Geometric Properties

We collect a few simple facts about Euclidean projection and the stationarity measures we use. We first record two elementary properties of Euclidean projection. Fact 8.1. Let X ⊆ Rd be nonempty, closed, and convex. For z ∈ Rd and p ∈ X , we have p = ΠX (z) if and only if z − p ∈ NX (p). Moreover, ΠX is nonexpansive, namely ∥ΠX (z) − ΠX (w)∥ ≤ ∥z − w∥ for every z, w ∈ Rd . Lemma 8.2. For every x ∈ X and g ∈ Rd , the map η 7→ ∥Gη,X (x, g)∥ is non-increasing, and
sup ∥Gη,X (x, g)∥ = dist −g, NX (x) . η>0

Proof. The monotonicity follows from Gafni and Bertsekas [1982, Lemma 3]. For any n ∈ NX (x), Fact 8.1 gives x = ΠX (x + ηn). Hence, by nonexpansiveness, ∥Gη,X (x, g)∥ =

1 ∥ΠX (x − ηg) − ΠX (x + ηn)∥ ≤ ∥g + n∥. η

Minimizing over n ∈ NX (x) and then taking the supremum over η > 0 gives
sup ∥Gη,X (x, g)∥ ≤ dist −g, NX (x) . η>0

To prove the opposite inequality and thus equality, it holds by monotonicity that L := lim ∥Gη,X (x, g)∥ = sup ∥Gη,X (x, g)∥. η↓0

η>0

The preceding bound shows that Gη,X (x, g) is bounded as η ↓ 0. Hence, by Bolzano–Weierstrass, there exist a sequence ηj ↓ 0 and v ∈ Rd such that Gηj ,X (x, g) → v. Denote pj := ΠX (x − ηj g). Then pj → x, and by Fact 8.1, x − η j g − pj Gηj ,X (x, g) − g = ∈ NX (pj ), ηj since the normal cone is a cone. Thus, for every y ∈ X , we have Gηj ,X (x, g) − g, y − pj j → ∞ gives ⟨v − g, y − x⟩ ≤ 0 for every y ∈ X , and hence v − g ∈ NX (x). Therefore
dist −g, NX (x) ≤ ∥v∥ = L.

≤ 0. Taking

Lemma 8.3. For every x ∈ X , g, h ∈ Rd , and η > 0, ∥Gη,X (x, g) − Gη,X (x, h)∥ ≤ ∥g − h∥.

(3)

If X is compact with diameter D, then max ⟨g, x − u⟩ − max ⟨h, x − u⟩ ≤ D∥g − h∥, u∈X

u∈X

9

max ⟨g, x − u⟩ ≤ Ddist −g, NX (x) . u∈X

(4)

Proof. Lipschitzness of the mapping appears in Ghadimi and Lan [2016, Lemma 4]. For the gap bounds, |⟨g − h, x − u⟩| ≤ D∥g − h∥, and, for every n ∈ NX (x) and u ∈ X , ⟨g, x − u⟩ ≤ ⟨g + n, x − u⟩ ≤ D∥g + n∥. Taking the appropriate maximum and infimum proves Eq. (4). Lemma 8.4. For every x ∈ X , g ∈ Rd , r > 0, and η > 0,  max ⟨g, x − y⟩ ≥ min η∥Gη,X (x, g)∥2 , r∥Gη,X (x, g)∥ . y∈X ∩B(x,r)

Proof. Let p := ΠX (x − ηg). By Fact 8.1, x − ηg − p ∈ NX (p). Since x ∈ X , the definition of the normal cone gives ⟨x − ηg − p, x − p⟩ ≤ 0, and hence ⟨g, x − p⟩ ≥

1 ∥x − p∥2 = η∥Gη,X (x, g)∥2 . η

If ∥x − p∥ ≤ r, then p ∈ X ∩ B(x, r), so max

y∈X ∩B(x,r)

⟨g, x − y⟩ ≥ η∥Gη,X (x, g)∥2 .

r Otherwise, by convexity, x + ∥p−x∥ (p − x) ∈ X ∩ B(x, r). Thus

max

y∈X ∩B(x,r)

⟨g, x − y⟩ ≥

r r ⟨g, x − p⟩ ≥ ∥p − x∥ = r∥Gη,X (x, g)∥. ∥p − x∥ η

The result follows.

8.2

Proof of Theorem 3.1: Constrained OLO-to-Nonconvex Conversion

Fix an epoch k and denote ∇k,m := ∇f (zk,m ). Since for every m ∈ [M ] we have zk,m ∈ B(xk , r), it PM 1 follows that M m=1 ∇k,m ∈ ∂r f (xk ) , and thus the first inequality in Eq. (2) follows from the definition of A (xI ) (x ). Since CA (xk ) ⊆ B(xk , r), we have by Cauchy–Schwarz FWf,C I r max y∈CA (xk )

≤

M X m=1

M X

⟨∇k,m , xk − y⟩

m=1

⟨gk,m , xk − yk,m ⟩ +

max y∈CA (xk )

M X

⟨gk,m , yk,m − y⟩ + r

m=1

M X

∇k,m − gk,m

.

m=1

By unbiasedness and the second-moment bound,     E ∥∇k,m − gk,m ∥2 zk,m = E ∥gk,m ∥2 zk,m − ∥∇k,m ∥2 ≤ G2 . Moreover, since each oracle call uses a fresh independent sample, the errors ∇k,m − gk,m have conditional
2 PM mean zero, and hence their cross terms vanish. Therefore E ≤ M G2 , and Jensen’s m=1 ∇k,m − gk,m √
PM inequality gives E ≤ G M. m=1 ∇k,m − gk,m

10

By conditional unbiasedness of the oracle, the uniform choice of sk,m , and the line-integral identity,  Z 1 ⟨∇f (xk + s(yk,m − xk )) , xk − yk,m ⟩ ds E ⟨gk,m , xk − yk,m ⟩ = E  0  = E f (xk ) − f (yk,m ) . Since xk+1 = yk,Jk with Jk ∼ Unif([M ]), E

" M X

#   ⟨gk,m , xk − yk,m ⟩ = M E f (xk ) − f (xk+1 ) .

m=1

Taking expectations in the first display and dividing by M therefore gives " E

* max

y∈CA (xk )

M

1 X ∇k,m , xk − y M m=1

+#

  rG 1 E [RegretA (xk ; gk,1 , . . . , gk,M )] + √ . ≤ E f (xk ) − f (xk+1 ) + M M Finally, summing over k = 0, . . . , K − 1 and dividing by K gives K−1

1 X E K k=0

"

* max

y∈CA (xk )

M

1 X ∇k,m , xk − y M m=1

+#

K−1

≤

1 X rG E[f (x0 ) − f (xK )] + E [RegretA (xk ; gk,1 , . . . , gk,M )] + √ K KM M k=0

≤

∆ 1 + K KM

K−1 X

rG E [RegretA (xk ; gk,1 , . . . , gk,M )] + √ , M k=0

where the second inequality uses f (xK ) ≥ inf x∈X f (x). Since I ∼ Unif({0, . . . , K − 1}), this proves the second inequality in Eq. (2).

8.3

Projection-Based Application

Lemma 8.5. For a point x ∈ X and radius r > 0, define the clipped projection Φx,r : Rd → Rd as   r (ΠX (v) − x) . Φx,r (v) = x + min 1, ∥ΠX (v) − x∥ Then for any v ∈ Rd we have Φx,r (v) ∈ X ∩ B(x, r), and for any y ∈ X ∩ B(x, r), ∥Φx,r (v) − y∥ ≤ ∥v − y∥. Proof. Let v ∈ Rd and w := ΠX (v) ∈ X . If ∥w − x∥ ≤ r, then Φx,r (v) = w ∈ X ∩ B(x, r). Otherwise it holds r r that Φx,r (v) = (1 − ∥w−x∥ )x + ∥w−x∥ w, and since X is convex and x, w ∈ X , it holds that Φx,r (v) ∈ X . By construction Φx,r (v) ∈ B(x, r), so overall Φx,r (v) ∈ X ∩ B(x, r), proving the first claim. Furthermore, let y ∈ X ∩ B(x, r) and note that Φx,r (v) = ΠB(x,r) (ΠX (v)), so nonexpansiveness of the projections proves the second claim. Lemma 8.6 is simply the regret guarantee of online gradient descent (see, e.g., Hazan [2016]) instantiated over X ∩ B(x, r), which we give here for completeness.

11

Lemma 8.6. For any sequence of loss vectors ℓ1 , . . . , ℓM , Algorithm 2 satisfies, for every y ∈ X ∩ B(x0 , r), M X

⟨ℓm , ym − y⟩ ≤

m=1

M α X r2 ∥ℓm ∥2 . + 2α 2 m=1

Proof. The update in Algorithm 2 is exactly Φx0 ,r (ym − αℓm ). Thus, by Lemma 8.5, ∥ym+1 − y∥2 ≤ ∥ym − αℓm − y∥2 . Expanding, rearranging, and summing over m gives M X

⟨ℓm , ym − y⟩ ≤

m=1

M ∥y1 − y∥2 α X + ∥ℓm ∥2 . 2α 2 m=1

Since y1 = x0 and y ∈ X ∩ B(x0 , r), ∥y1 − y∥ ≤ r. 2  8∆ , K ≥ rε and A given by Proposition 8.7. Let r > 0 and ε0 > 0. Run Algorithm 1 with M ≥ 16G ε0 0 √ Algorithm 2 with step size α = r/(G M ). Its outputs satisfy " # M 1 X E ∥Gr/ϵ0 ,X (xI , ∇f (zI,m ))∥ ≤ ε0 . (5) M m=1 Proof. For each epoch k, condition on the anchor xk and apply Lemma 8.6 with x = xk and ℓm = gk,m . Taking expectations and using E∥gk,m ∥2 ≤ G2 gives " E

M X

max

y∈X ∩B(xk ,r)

# ⟨gk,m , yk,m − y⟩ ≤

m=1

αM G2 r2 + . 2α 2

√ √ PM 1 With α = r/(G M ), the RHS is rG M . Write ∇I := M m=1 ∇f (zI,m ), then Theorem 3.1 gives   2rG rε0 ∆ +√ ≤ , E max ⟨∇I , xI − y⟩ ≤ K 4 y∈X ∩B(xI ,r) M where the last inequality uses the choices of K and M . Let p := ΠX (xI − εr0 ∇I ). By Fact 8.1,

r xI − ∇I − p, xI − p ε0

and therefore ⟨∇I , xI − p⟩ ≥

≤ 0,

ε0 r ∥xI − p∥2 = ∥Gr/ε0 ,X (xI , ∇I )∥2 . r ε0

If ∥xI − p∥ ≤ r, then p ∈ X ∩ B(xI , r) and thus max

y∈X ∩B(xI ,r)

⟨∇I , xI − y⟩ ≥

Otherwise, y := xI + r

r ∥Gr/ε0 ,X (xI , ∇I )∥2 . ε0

p − xI ∈ X ∩ B(xI , r), ∥p − xI ∥

since p, xI ∈ X and r/∥p − xI ∥ ∈ (0, 1). Therefore max

y∈X ∩B(xI ,r)

⟨∇I , xI − y⟩ ≥

r ⟨∇I , xI − p⟩ ≥ r∥Gr/ε0 ,X (xI , ∇I )∥. ∥p − xI ∥

12

So in either case, ∥Gr/ε0 ,X (xI , ∇I )∥ ≤

r

ε0 1 max ⟨∇I , xI − y⟩ + max ⟨∇I , xI − y⟩ . r y∈X ∩B(xI ,r) r y∈X ∩B(xI ,r)

Taking expectations and applying Jensen’s inequality gives r ε0 rε0 1 rε0 3 E∥Gr/ε0 ,X (xI , ∇I )∥ ≤ + = ε0 ≤ ε0 . r 4 r 4 4

Lemma 8.8. Let X be a nonempty closed convex set and let x ∈ X , g ∈ ∂r f (x), v ∈ Rd . Denote p := ΠX (x − ηv). Then
g ∈ ∂r+∥p−x∥ f (p), dist −g, NX (p) ≤ ∥Gη,X (x, v)∥ + ∥g − v∥. Proof. Since g ∈ ∂r f (x) and
B(x, r) ⊆ B p, r + ∥p − x∥ , the first claim follows. By Fact 8.1, x − ηv − p ∈ NX (p). Since NX (p) is a cone, Gη,X (x, v) − v =

x−p − v ∈ NX (p). η

Therefore,

dist −g, NX (p) ≤ ∥ − g − Gη,X (x, v) − v ∥ ≤ ∥Gη,X (x, v)∥ + ∥g − v∥. PM 1 Proof of Theorem 4.1. For each trial n, denote ∇n := M m=1 ∇f (zn,m ). By unbiasedness, independence, G2 ε 2 bn ∥ ≤ M , so E∥∇n − g bn ∥ ≤ √GM ≤ 96 and the second-moment bound, E∥∇n − g . By Proposition 8.7 with ε0 = ε/6 and Lemma 8.3 we have bn )∥ ≤ E∥G6r/ε,X (xn , ∇n )∥ + E∥∇n − g bn ∥ ≤ E∥G6r/ε,X (xn , g

ε , 3

so Markov’s inequality gives   2ε 1 bn )∥ ≤ P ∥G6r/ε,X (xn , g ≥ . 3 2 By definition of G6r/ε,X , 6r bn )∥, ∥G6r/ε,X (xn , g ε so each trial is accepted with probability at least 1/2. Let E denote the event that at least one trial is accepted. Since the trials are i.i.d., ε P(E c ) ≤ 2−N ≤ . 4G On E, n⋆ is the first accepted trial. As zn⋆ ,1 , . . . , zn⋆ ,M ∈ B(xn⋆ , r), we have ∇n⋆ ∈ ∂r f (xn⋆ ). Since the trial is accepted, ∥xout − xn⋆ ∥ ≤ 4r, and hence ∇n⋆ ∈ ∂5r f (xout ) = ∂δ f (xout ) by the choice of r. Therefore, Lemma 8.8 gives ∥pn − xn ∥ =

out bn⋆ )∥ + ∥∇n⋆ − g b n⋆ ∥ ≤ Rf,X ) ≤ dist(−∇n⋆ , NX (xout )) ≤ ∥G6r/ε,X (xn⋆ , g δ (x

2ε bn⋆ ∥. + ∥∇n⋆ − g 3

Moreover, bn⋆ ∥ | E] = E[∥∇n − g bn ∥ | ∥pn − xn ∥ ≤ 4r] ≤ E[∥∇n⋆ − g 13

bn ∥ E∥∇n − g ε ≤ . P(∥pn − xn ∥ ≤ 4r) 48

Thus out E[Rf,X ) | E] ≤ δ (x

2ε ε 11ε + = . 3 48 16

out On E c , xout = pN ∈ X , and Rf,X ) ≤ G. Therefore δ (x out ERf,X )≤ δ (x

8.4

11ε ε 11ε + GP(E c ) ≤ + ≤ ε. 16 16 4

Projection-Free Application

Lemma 8.9. For any 0 < δ ≤ D and x ∈ X ,   δ δ 1− x + X ⊆ X ∩ B(x, δ). D D Moreover, for every g ∈ Rd , ⟨g, x − y⟩ =

max y∈(1−δ/D)x+(δ/D)X

and thus f,(1−δ/D)x+(δ/D)X

FWδ

(x) =

δ max ⟨g, x − u⟩ D u∈X δ FWf,X δ (x). D

δ δ Proof. Write y = 1 − D x+ D u for some u ∈ X . By convexity, y ∈ X , and ∥y − x∥ =

δ ∥u − x∥ ≤ δ. D

δ Also, x − y = D (x − u), which gives the second claim. Taking the minimum over g ∈ ∂δ f (x) gives the last claim. √ Proposition 8.10. Let AF be Algorithm 4 with input x0 and α = δ/(G M ), N = 4M, and suppose E∥ℓm ∥2 ≤ G2 for every m ∈ [M ]. Then √ E[RegretAF (x0 ; ℓ1 , . . . , ℓM )] ≤ 2δG M .

Proof. The proof combines the Frank-Wolfe convergence rate [Jaggi, 2013] with the standard quadratic FTRL regret bound [Orabona, 2019], as we detail below. Write *m−1 +   X δ δ 1 C := 1 − x0 + X , Qm (y) := ℓj , y + ∥y − x0 ∥2 , D D 2α j=1 ⋆ and let ym ∈ arg miny∈C Qm (y). By Lemma 8.9,

  δ δ 1− x0 + vn ∈ arg min ⟨∇Qm (wn ), s⟩ , D D s∈C and therefore wn are the iterates of Frank-Wolfe (see, e.g., [Jaggi, 2013, Algorithm 1]) on Qm over C. Since Qm is α−1 -smooth and C has diameter at most δ, the standard Frank-Wolfe guarantee [Jaggi, 2013, Theorem 1] gives 2δ 2 ⋆ Qm (ym ) − Qm (ym )≤ . α(N + 2)

14

1 ⋆ 2 Moreover, Qm is α−1 -strongly convex so the LHS is lower bounded by 2α ∥ym − ym ∥ , and thus ⋆ ∥ym − ym ∥≤ √

2δ . N +2

⋆ The points ym are the FTRL iterates for the linear losses y 7→ ⟨ℓm , y⟩ with regularizer ψ(y) = 21 ∥y − x0 ∥2 and constant regularization coefficient α. Since ψ is 1-strongly convex and miny∈C ψ(y) = 0, the standard FTRL bound [Orabona, 2019, Corollary 7.6] gives, for every y ∈ C, M X

⋆ ⟨ℓm , ym − y⟩ ≤

m=1

M α X ∥y − x0 ∥2 + ∥ℓm ∥2 . 2α 2 m=1

For every y ∈ C, by using Cauchy–Schwarz, the fact that ∥y − x0 ∥ ≤ δ and the guarantees above we arrive at M M M X X X ⋆ ⋆ ⟨ℓm , ym − y⟩ = ⟨ℓm , ym − y⟩ + ⟨ℓm , ym − ym ⟩ m=1

m=1

≤

m=1

M X 2δ δ ∥ℓm ∥, + ∥ℓm ∥2 + √ 2α 2 m=1 N + 2 m=1 2

M α X

Taking the maximum over y ∈ C gives a bound on RegretAF (x0 ; ℓ1 , . . . , ℓM ), and then taking expectations and using E∥ℓm ∥ ≤ (E∥ℓm ∥2 )1/2 ≤ G, E[RegretAF (x0 ; ℓ1 , . . . , ℓM )] ≤

√ δ2 αM G2 2δM G + +√ ≤ 2δG M , 2α 2 N +2

√ where the last inequality uses α = δ/(G M ) and N = 4M . Proof of Theorem 5.1. Let xout denote the first component returned by Algorithm 1. Then, by Theorem 3.1 and proposition 8.10, h i ∆ 3δG f,(1−δ/D)xout +(δ/D)X E FWδ (xout ) ≤ +√ . K M We use Lemma 8.9 to see that Algorithm 4 is a δ-local learner over (1 − δ/D)xout + (δ/D)X , and use Lemma 8.9 again to write δ δε ∆ 3δG out E[FWf,X )] ≤ +√ ≤ , δ (x D K D M which proves the claim.

8.5

Zeroth-Order Optimization

Our zeroth-order results rely on the following: Lemma 8.11 (Kornowski and Shamir, 2024). For every ρ, ν ≥ 0, we have ∂ν fρ (x) ⊆ ∂ρ+ν f (x). Consequently, if ρ + ν ≤ δ, then every g ∈ ∂ν fρ (x) is also in ∂δ f (x). The following standard two-point estimator follows from Shamir [2017], with the explicit constant in the second-moment bound from Lin et al. [2022]. b is the Lemma 8.12. For every ρ > 0 and every possibly adaptive query point z, if ξ ∼ Ξ is a fresh sample and g output of Algorithm 5, then √ E[b g | z] = ∇fρ (z), E[∥b g∥2 | z] ≤ 16 2π dG2 .

15

In this section, when applying Algorithm 1 to fρ , we replace its stochastic-gradient query by a call to Algorithm 5 with inputs zk,m , ρ, ξk,m . Proof of Theorem 6.1. Since |f (x) − fρ (x)| ≤ ρG for every x, fρ (x0 ) − inf x∈X fρ (x) ≤ ∆ + 2Gρ √ ≤ 2∆. By
Lemma 8.12, applying Theorem 4.1 to fρ with (G, δ, ∆) replaced by the parameters 4(2π)1/4 d G, δ/2, 2∆ fρ ,X (xout ) ≤ ε. By Lemma 8.11, ∂δ/2 fρ (xout ) ⊆ ∂δ/2+ρ f (xout ) ⊆ ∂δ f (xout ), and therefore we have gives ERδ/2 out ERf,X ) ≤ ε. The claimed complexity follows from Theorem 4.1. δ (x

Proof of Theorem 6.2. Since |f (x) − fρ (x)| ≤ ρG for every x, fρ (x0 ) − inf x∈X fρ (x) ≤ ∆ + 2Gρ √ ≤ 2∆. By
Lemma 8.12, applying Theorem 5.1 to fρ with (G, δ, ∆) replaced by the parameters 4(2π)1/4 d G, δ/2, 2∆ fρ ,X gives E FWδ/2 (xout ) ≤ ε. By Lemma 8.11, ∂δ/2 fρ (xout ) ⊆ ∂δ/2+ρ f (xout ) ⊆ ∂δ f (xout ), and therefore we out have E FWf,X ) ≤ ε. The claimed complexity follows from Theorem 5.1. δ (x

8.6

Lower Bounds

As previously discussed, we formally prove our lower bounds for (possibly-)randomized zero-respecting first-order algorithms, which are defined as follows: Definition 8.13 (Arjevani et al., 2023, Definition 1). A stochastic first-order algorithm is zero-respecting if, for any oracle and any realization of its randomness, its queries xt satisfy, for every t ≥ 1, [ supp(xt ) ⊆ supp(gi ) , i<t

where gi is the stochastic gradient returned at xi and supp(x) := {j : xj ̸= 0}. For a ≥ 0 and y ∈ Rd , we denote
proga (y) := max {i ∈ [d] : |yi | > a} ∪ {0} . Next, we define a probability-p zero-chain, and restate a few technical results from Arjevani et al. [2023]. Definition 8.14 (Arjevani et al., 2023, Definition 2). A stochastic gradient function g : Rd × Ξ → Rd is a probability-p zero-chain if   Pr ∃ y ∈ Rd : prog0 (g(y, ξ)) = prog1/4 (y) + 1 ≤ p ξ

and

  Pr ∃ y ∈ Rd : prog0 (g(y, ξ)) > prog1/4 (y) + 1 = 0 . ξ

Lemma 8.15 (Arjevani et al., 2023, Lemma 2). There are universal constants ∆0 , ℓ1 , γ∞ > 0 such that, for every d ∈ N, there is a differentiable function f¯d : Rd → R satisfying: 1. f¯d (0) − inf y f¯d (y) ≤ ∆0 d. 2. The gradient of f¯d is ℓ1 -Lipschitz, i.e., ∥∇f¯d (y) − ∇f¯d (y′ )∥ ≤ ℓ1 ∥y − y′ ∥ for every y, y′ ∈ Rd . 3. For every y ∈ Rd , ∥∇f¯d (y)∥∞ ≤ γ∞ . 4. For every y ∈ Rd with prog1 (y) < d, ∥∇f¯d (y)∥ ≥ [∇f¯d (y)]prog1 (y)+1 > 1. Lemma 8.16 (Arjevani et al., 2023, Lemma 8). Let d ∈ N, let f¯d be as in Lemma 8.15, and let p ∈ (0, 1]. There is a universal constant ς > 0 and a differentiable stochastic function F̄d,p (·; ξ) such that: 1. For every y ∈ Rd , Eξ [F̄d,p (y; ξ)] = f¯d (y) and Eξ [∇F̄d,p (y; ξ)] = ∇f¯d (y). 16

2. For every y ∈ Rd , Eξ ∥∇F̄d,p (y; ξ) − ∇f¯d (y)∥2 ≤ ς 2 /p. 3. The stochastic gradient ∇F̄d,p is a probability-p zero-chain. Lemma 8.17 (Arjevani et al., 2023, Lemma 1). Let g(y, ξ) be a probability-p zero-chain gradient estimator for f¯ : Rd → R, and let the oracle return (f¯(y), g(y, ξ)). If y1 , y2 , . . . ∈ Rd are the queries of a zero-respecting algorithm applied to this oracle, then, with probability at least 1 − δ, prog0 (yt ) < d

for every t ≤

d − log(1/δ) . 2p

We first rescale these results to the parameters used in our lower bound. Lemma 8.18. √There are universal constants c, C > 0 such that the following holds. Let L, ∆, σ, η > 0 satisfy η ≤ c min{σ, L∆}. Then there exists a dimension d ≤ CL∆/η 2 for which there is a stochastic function F0 : Rd × Ξ → R, differentiable in its first argument, with mean f√ 0 (x) := Eξ [F0 (x; ξ)], such that f0 is L-smooth, f0 (0) − inf x∈Rd f0 (x) ≤ ∆, and, for every x ∈ Rd , ∥∇f0 (x)∥ ≤ C L∆, Eξ [∇F0 (x; ξ)] = ∇f0 (x), and Eξ ∥∇F0 (x; ξ) − 2 4 ∇f0 (x)∥2 ≤ σ 2 . Moreover, S any randomized zero-respecting algorithm making T ≤ cL∆σ /η queries and returning out out x with supp(x ) ⊆ t≤T supp(∇F0 (xt ; ξt )) satisfies  1 |[∇f0 (xout )]j | ≥ η ≥ . 2

 η Pr ∃j ∈ [d] : |xout j |≤C , L

Proof. Let ∆0 , ℓ1 , γ∞ , ς be as in Lemmas 8.15 and 8.16, and set   ℓ1 η L∆ λ := , d := , L 2∆0 ℓ1 η 2

p :=

ς 2 η2 . σ2

For sufficiently small c and large C, 2 ≤ d ≤ CL∆/η 2 and p ≤ 1. Define, using the functions from Lemmas 8.15 and 8.16, Lλ2 ¯ Lλ2 f0 (x) := fd (x/λ), F0 (x; ξ) := F̄d,p (x/λ; ξ) . ℓ1 ℓ1 2 By Lemma 8.15 ∆, and ∥∇f0 (x)∥ ≤ √ √ and Lλ/ℓ1 = η, f0 is L-smooth, f0 (0) − inf x∈Rd f0 (x) ≤ (Lλ /ℓ21 )∆0 2d ≤ ηγ∞ d ≤ C L∆. By Lemma 8.16, F0 is unbiased and Eξ ∥∇F0 (x; ξ)−∇f0 (x)∥ ≤ η ς 2 /p = σ 2 . Appending xout /λ as query T + 1, and decreasing c if necessary,

T +1≤c

L∆σ 2 d − log 2 +1≤ . η4 2p

Hence Lemma 8.17 gives prog0 (xout /λ) < d with probability at least 1/2. Now for this event, define j := prog1 (xout /λ) + 1. Since prog1 (xout /λ) < d, we have j ∈ [d], and by the definition of prog1 , |xout j |≤λ=

ℓ1 η η ≤C . L L

Moreover, by Lemma 8.15 and Lλ/ℓ1 = η, |[∇f0 (xout )]j | = η|[∇f¯d (xout /λ)]j | > η .

To convert the hard coordinate in Lemma 8.18 into a Frank-Wolfe lower bound, we add a quadratic radial term to the hard function. Lemma 8.18 yields the desired gap near the origin, while the radial term ensures a large gap away from the origin.

17

Lemma 8.19. Let D > 0, let f0 : Rd → R be differentiable with ∥∇f0 (x)∥ ≤ M for every x ∈ Rd , and let 0 < η ≤ M . Define f (x) := f0 (x) + (4M/D)∥x∥2 and X := B(0, D/2). If x ∈ X has a coordinate j such that |xj | ≤ Dη/(16M ) and |[∇f0 (x)]j | ≥ η, then FWf,X (x) ≥ Dη/8. ∇f (x) Proof. If ∥x∥ ≤ D/4, then by choosing − D 2 ∥∇f (x)∥ ∈ X we have

D ∇f (x) 2 ∥∇f (x)∥ D = ⟨∇f (x), x⟩ + ∥∇f (x)∥ 2 D ≥ −∥∇f (x)∥∥x∥ + ∥∇f (x)∥ 2 D ≥ ∥∇f (x)∥ 4 D ≥ |[∇f (x)]j | 4   D 8M ≥ |[∇f0 (x)]j | − |xj | 4 D   D 8M Dη Dη ≥ . η− = 4 D 16M 8

FWf,X (x) ≥

∇f (x), x +

Otherwise, choose −Dx/(2∥x∥) ∈ X to get   x FWf,X (x) ≥ ∇f (x), x + D 2∥x∥    x D + ∥x∥ ∇f (x), ≥ 2 ∥x∥      x D 8M + ∥x∥ ∇f0 (x), ∥x∥ = + 2 ∥x∥ D    D 8M ≥ + ∥x∥ ∥x∥ − M 2 D DM ≥ 2 Dη ≥ . 8

Theorem 8.20. There are universal constants c, C, Cd > 0 such that the following holds. Let H, ∆, G, D, ε > 0 satisfy √ √ ∆ ≤ cHD2 , ε ≤ cD H∆, G ≥ C H∆ . Then there exists a dimension d ≤ Cd H∆D2 /ε2 for which there are differentiable stochastic components F (·; ξ) whose mean f : Rd → R is H-smooth and, for X := B(0, D/2), we have, for every x ∈ X , f (0) − inf f (x) ≤ ∆, x∈X

Eξ [∇F (x; ξ)] = ∇f (x),

Eξ ∥∇F (x; ξ)∥2 ≤ G2 .

Moreover, any randomized zero-respecting first-order algorithm making queries x1 , . . . , xT ∈ X and returning xout ∈ X satisfying [
supp(xout ) ⊆ supp ∇F (xt ; ξt ) , E[FWf,X (xout )] ≤ ε, t≤T

18

must have

∆HG2 D4 T =Ω ε4 

 .

Proof. Set η := 32ε/D and √ apply Lemma 8.18 with L = H/2 and σ = G/2. Let Czc denote its universal constant C, set M := Czc H∆, and define F (x; ξ) := F0 (x; ξ) +

4M ∥x∥2 . D

For sufficiently small c and large C, Cd , the assumptions of Lemma 8.18 hold, and its dimension satisfies the claimed bound. Thus f is H-smooth and we have that f (0) − inf f (x) ≤ f0 (0) − inf f0 ≤ ∆ x∈X

and Eξ ∥∇F (x; ξ)∥2 = ∥∇f (x)∥2 + Eξ ∥∇F0 (x; ξ) − ∇f0 (x)∥2 ≤ G2 . Given a zero-respecting algorithm for F , subtracting 8M x/D from each oracle response simulates the F0 oracle. Inductively, for every t, [

[
supp(xt ) ⊆ supp ∇F0 (xs ; ξs ) , supp ∇F (xt ; ξt ) ⊆ supp ∇F0 (xs ; ξs ) . s<t

s≤t

Thus the simulated algorithm is zero-respecting with supp(xout ) ⊆ sufficiently small universal constant c0 > 0, if T ≤ c0

S

t≤T supp(∇F0 (xt ; ξt )).

Hence, for a

∆HG2 D4 , ε4

then Lemmas 8.18 and 8.19 give E[FWf,X (xout )] ≥

1 Dη · = 2ε . 2 8

Lemma 8.21. Let f be H-smooth and let X be compact with diameter D. Then, for every x ∈ X and δ ≥ 0, f,X FWf,X (x) − HDδ ≤ FWf,X δ (x) ≤ DRδ (x) . P Proof. For every g ∈ ∂δ f (x), writing g = i αi ∇f (yi ) with yi ∈ B(x, δ) gives X ∥g − ∇f (x)∥ ≤ αi ∥∇f (yi ) − ∇f (x)∥ ≤ Hδ . i

Then by Lemma 8.3, 

FWf,X (x) − HDδ ≤

min g∈∂δ f (x)

≤

min

 max ⟨g, x − u⟩ + D∥g − ∇f (x)∥ − HDδ u∈X

max ⟨g, x − u⟩

g∈∂δ f (x) u∈X

= FWf,X δ (x) ≤D

min g∈∂δ f (x)

dist(−g, NX (x))

= DRf,X δ (x) .

19

The smooth Frank-Wolfe lower bound immediately yields the corresponding lower bound for the Goldstein Frank-Wolfe gap, as we formalize in the corollary below. Corollary 8.22. There are universal constants c, C, Cd > 0 such that the following holds. Let ∆, G, D, ε > 0 and 0 < δ < D satisfy εD εδ ε∆ ≤∆≤c , G2 ≥ C . C D δ Dδ Then there exists a dimension d ≤ Cd ∆D/(δε) for which there are differentiable stochastic components F (·; ξ) with mean f such that, for X := B(0, D/2), f is ε/(Dδ)-smooth and the initial-suboptimality and stochastic-gradient bounds in Theorem 8.20 hold. Every randomized zero-respecting first-order algorithm satisfying the output-support condition of Theorem 8.20 requires   ∆D3 G2 Ω δε3 out stochastic-gradient queries to return xout ∈ X with E[FWf,X )] ≤ ε. δ (x

Proof. Apply Theorem 8.20 with H = ε/(Dδ) and ordinary Frank-Wolfe target 2ε. By Lemma 8.21, f,X FWf,X (x) − ε . δ (x) ≥ FW

Finally, the Goldstein Frank-Wolfe lower bound in turn yields the corresponding lower bound for the Goldstein residual. Corollary 8.23. There are universal constants c, C, Cd > 0 such that the following holds. Let ∆, G, D, ε > 0 and 0 < δ < D satisfy εD2 ε∆ Cεδ ≤ ∆ ≤ c , G2 ≥ C . δ δ Then there exists a dimension d ≤ Cd ∆/(δε) for which there are differentiable stochastic components F (·; ξ) with mean f such that, for X := B(0, D/2), f is ε/δ-smooth and the initial-suboptimality and stochastic-gradient bounds in Theorem 8.20 hold. Every randomized zero-respecting first-order algorithm satisfying the output-support condition of Theorem 8.20 requires   ∆G2 Ω δε3 out stochastic-gradient queries to return xout ∈ X with E[Rf,X )] ≤ ε. δ (x f,X Proof. Apply Corollary 8.22 with target Dε. By Lemma 8.21, FWf,X δ (x) ≤ DRδ (x).

9

Discussion

In this paper, we provided the first dimension-free algorithms for first-order constrained optimization of arbitrary stochastic Lipschitz functions, without smoothness or convexity assumptions, and showed that their rates are optimal for (possibly-)randomized zero-respecting algorithms. Our approach also extends to the zeroth-order setting in Section 6 and closes the upper-bound gap left open by Liu et al. [2024]. As discussed in Section 7, the recent joint lower bound of Zhang et al. [2026] shows the optimality of our zeroth-order rate for the Goldstein residual already in the unconstrained case. We leave several directions open for future work. A natural direction is to further assess the overall computational complexity of this setting (see Remark 6.3), and to extend the framework in this work more generally to composite optimization problems as in Chen et al. [2025]. Finally, similarly to Liu et al. [2024], our guarantees control the expectation of a stationarity measure (in our case, a stronger one, as discussed in Remark 2.1), whereas obtaining analogous high-probability guarantees should be possible using standard 20

amplification techniques, which we do not pursue here. We also leave open formally extending the lower bounds in Section 8.6 from randomized zero-respecting algorithms to arbitrary randomized algorithms, which seems possible using known reduction techniques [Carmon et al., 2020]. Lastly, we note that there exist practical drawbacks to our algorithms. Most notably, as is common in nonsmooth nonconvex optimization, our guarantees require several parameters to be tuned at different scales, making the methods less attractive from a practical standpoint. It would therefore be interesting to find simpler algorithms that retain the same guarantees. One possible route is through a reduction of nonsmooth nonconvex optimization to static regret of the type proposed by Chen and Hazan [2024], which could potentially lead to a substantially simpler algorithmic framework.

Statement on use of AI The results in this paper were developed through a highly interactive process involving AI models, specifically, GPT Sol 5.6 and GPT Astra. The authors began with a roadmap of the results, and formalized and generalized them with the help of AI. Every mathematical argument appearing in the paper was independently re-derived, rewritten and simplified by the authors. The authors take full responsibility for the correctness and presentation of all material in this manuscript.

21

References Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. Efficient full-matrix adaptive regularization. In International Conference on Machine Learning, pages 102–110. PMLR, 2019. Kwangjun Ahn and Ashok Cutkosky. Adam with model exponential moving average is effective for nonconvex optimization. Advances in Neural Information Processing Systems, 37:94909–94933, 2024. Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, and Yan Dai. Understanding adam optimizer via online learning of updates: Adam is ftrl in disguise. In Proceedings of the 41st International Conference on Machine Learning. JMLR.org, 2024. Kwangjun Ahn, Gagik Magakyan, and Ashok Cutkosky. General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 772–795. PMLR, 13–19 Jul 2025. Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165–214, 2023. Jonathan Borwein and Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, 2006. Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Advances in neural information processing systems, 32, 2019. Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184:71–120, 2020. doi: 10.1007/s10107-019-01406-y. Nicolo Cesa-Bianchi, Gábor Lugosi, et al. Prediction, learning, and games, volume 1. Cambridge university press Cambridge, 2006. Xinyi Chen and Elad Hazan. Open problem: Black-box reductions and adaptive gradient methods for nonconvex optimization. In The Thirty Seventh Annual Conference on Learning Theory, pages 5317–5324. PMLR, 2024. Zixiang Chen, Junkai Zhang, Yiwen Kou, Xiangning Chen, Cho-Jui Hsieh, and Quanquan Gu. Why does sharpness-aware minimization generalize better than sgd? In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 72325–72376. Curran Associates, Inc., 2023. doi: 10.52202/075280-3165. Ziyi Chen, Peiran Yu, and Heng Huang. Zeroth-order methods for stochastic nonconvex nonsmooth composite optimization. arXiv preprint arXiv:2510.04446, 2025. Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990. Cyrille W Combettes and Sebastian Pokutta. Complexity of linear minimization and projection on some sets. Operations Research Letters, 49(4):565–571, 2021. Frank E Curtis and Michael L Overton. A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization. SIAM Journal on Optimization, 22(2):474–500, 2012. Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. In International Conference on Machine Learning, pages 6643–6670. PMLR, 2023. 22

Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 20(1):119–154, 2020. Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. A gradient sampling method with complexity guarantees for lipschitz functions in high and low dimensions. Advances in neural information processing systems, 35:6692–6703, 2022. John Duchi, Feng Ruan, and Chulhee Yun. Minimax bounds on stochastic batched convex optimization. In Conference On Learning Theory, pages 3065–3162. PMLR, 2018. John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674–701, 2012. John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61 (5):2788–2806, 2015. Yu M Ermol’ev and VI Norkin. Stochastic generalized gradient method for nonconvex nonsmooth stochastic optimization. Cybernetics and Systems Analysis, 34(2):196–215, 1998. Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In ICLR Spotlight, 2021. Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95–110, 1956. Eli M Gafni and Dimitri P Bertsekas. Convergence of a gradient projection method. Laboratory for Information and Decision Systems, 1982. Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets. In International Conference on Machine Learning, pages 541–549. PMLR, 2015. Dan Garber and Elad Hazan. A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3):1493–1528, 2016. Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59–99, 2016. Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155:267–305, 2016. Allen A Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13(1):14–22, 1977. Ian Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio. Maxout networks. In International conference on machine learning, pages 1319–1327. PMLR, 2013. Benjamin Grimmer and Zhichao Jia. Goldstein stationarity in lipschitz constrained optimization. Optimization Letters, 19(2):425–435, 2025. Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher. Regret minimization in stochastic non-convex learning via a proximal-gradient approach. In International Conference on Machine Learning, pages 4008– 4017. PMLR, 2021. Warren Hare, Claudia Sagastizábal, and Mikhail Solodov. A proximal bundle method for nonsmooth nonconvex functions with inexact information. Computational Optimization and Applications, 63(1):1–28, 2016.

23

Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2:157–325, 2016. Elad Hazan and Satyen Kale. Projection-free online learning. arXiv preprint arXiv:1206.4657, 2012. Elad Hazan and Edgar Minasyan. Faster projection-free online learning. In Conference on Learning Theory, pages 1877–1893. PMLR, 2020. Najmeh Hoseini Monjezi and S Nobakhtian. A filter proximal bundle method for nonsmooth nonconvex constrained optimization. Journal of Global Optimization, 79(1):1–37, 2021. Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning, pages 427–435. PMLR, 2013. Martin Jaggi, Marek Sulovsk, et al. A simple algorithm for nuclear norm regularized problems. In Proceedings of the 27th international conference on machine learning (ICML-10), pages 471–478, 2010. Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, 2005. Guy Kornowski. The complexity of finding stationary points in nonsmooth nonconvex optimization. arXiv preprint arXiv:2609.17780, 2026. Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Journal of Machine Learning Research, 23:1–44, 2022. Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25(122):1–14, 2024. Ben Kretzu and Dan Garber. Revisiting projection-free online learning: the strongly convex case. In International Conference on Artificial Intelligence and Statistics, pages 3592–3600. PMLR, 2021. Simon Lacoste-Julien. Convergence rate of frank-wolfe for non-convex objectives. arXiv:1607.00345, 2016.

arXiv preprint

Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate frank-wolfe optimization for structural svms. In International Conference on Machine Learning, pages 53–61. PMLR, 2013. Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160–26175, 2022. Zhuanghua Liu, Cheng Chen, Luo Luo, and Bryan Kian Hsiang Low. Zeroth-order methods for constrained nonconvex nonsmooth stochastic optimization. In Forty-first International Conference on Machine Learning, 2024. Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Conference on Learning Theory, pages 5314–5390. PMLR, 2022. Zakaria Mhammedi. Online convex optimization with a separation oracle. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 4033–4077. PMLR, 30 Jun–04 Jul 2025.

24

Goncalo Mordido, Pranshu Malviya, Aristide Baratin, and Sarath Chandar. Lookbehind-SAM: k steps back, 1 step forward. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 36229–36248. PMLR, 21–27 Jul 2024. Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019. Xiangyu Qi, Kaixuan Huang, Ashwinee Panda, Peter Henderson, Mengdi Wang, and Prateek Mittal. Visual adversarial examples jailbreak aligned large language models. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pages 21527–21536, 2024. Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic frank-wolfe methods for nonconvex optimization. In 2016 54th annual Allerton conference on communication, control, and computing (Allerton), pages 1244–1251. IEEE, 2016. Andrzej Ruszczyński. Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization. Optimization Letters, 14(7):1615–1625, 2020. Emre Sahinoglu, Youbang Sun, and Shahin Shahrampour. Finite-time analysis of stochastic nonconvex nonsmooth optimization on the riemannian manifolds. In D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen, editors, Advances in Neural Information Processing Systems, volume 38, Main Conference, pages 134166–134186. Curran Associates, Inc., 2025. doi: 10.52202/085713-4473. Shai Shalev-Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms. Machine Learning, 69(2):115–142, 2007. Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18:1–11, 2017. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1): 1929–1958, 2014. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2019. Farzad Yousefian, Angelia Nedić, and Uday V Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56–67, 2012. Haihan Zhang, Wendao Wu, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouchen Lin. Joint lower bounds for zeroth-order nonconvex optimization on euclidean balls, 2026. Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International conference on machine learning, pages 11173–11182. PMLR, 2020. Qinzi Zhang and Ashok Cutkosky. Random scaling and momentum for non-smooth non-convex optimization. In Proceedings of the 41st International Conference on Machine Learning. JMLR.org, 2024. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003. 25

Related documents

• Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints#1298283
• An Inexact Trust-Region Method for Structured Nonsmooth Optimization with Application to Risk-Averse Stochastic Programming#999770
• The Complexity of Convex Optimization with Mismatched Geometry#1117622
• Linear convergence rate analysis of Proximal-Tracking for nonsmooth distributed optimization#1063611
• Bayesian optimization with Gaussian processes to accelerate stationary point searches#644964