Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion

Ashok CutkoskyHarsh MehtaFrancesco Orabona

article2023ICML72 citations

Establishes a reduction from non-smooth, non-convex stochastic optimization to online learning that achieves the optimal $O(\epsilon^{-3}\delta^{-1})$ gradient complexity for finding $(\delta,\epsilon)$ -stationary points while unifying and recovering state-of-the-art rates across smooth and deterministic settings.

Listen

Training modern deep neural networks requires optimizing non-convex objective functions over massive datasets, making training time a primary bottleneck for deploying larger and more capable models. While theoretical convergence guarantees have historically depended on assuming mathematical smoothness, modern machine learning architectures regularly incorporate non-smooth components such as rectified linear units and pooling layers. Consequently, standard optimization theories fail to guarantee convergence in realistic non-smooth, noisy environments, creating a gap between empirical practice and theoretical guarantees.

The article establishes optimal computational complexity bounds for non-smooth, non-convex stochastic optimization by introducing a novel algorithmic reduction to online learning. It demonstrates how to identify an approximate stationary point—a location where the expected gradient in a small surrounding ball is near zero—using fewer noisy gradient evaluations than previous methods.

To achieve this, the article transforms the non-convex optimization problem into an online linear learning framework. The proposed algorithm chooses parameter updates by feeding gradient evaluations taken at slightly randomized points into an online learning procedure with shifting regret guarantees. When combined with periodically reset online gradient descent, the algorithm determines the direction of updates while strictly controlling error across iterations, requiring only standard first-order noisy gradient queries without demanding exact differentiability.

The investigation yields several key theoretical findings. First, it reduces the sample complexity required to find an approximate stationary point from the prior best-known rate to an optimal rate, improving efficiency by a factor proportional to the target accuracy. Second, it proves a matching theoretical lower bound, confirming that this convergence rate cannot be fundamentally improved in the stochastic setting. Third, when applied to smooth and second-order smooth functions, the framework immediately recovers all existing optimal convergence rates for standard stochastic gradient methods. Fourth, for deterministic functions with second-order smoothness, incorporating optimistic online learning with predictive hints achieves a state-of-the-art complexity rate.

These results establish that non-smooth, non-convex optimization can achieve convergence guarantees comparable to smooth optimization without needing global smoothness assumptions. In real-world engineering terms, the findings provide a rigorous foundation for step-clipping and momentum-style updates in neural network training, confirming that non-smooth architectures can be trained with guaranteed efficiency and minimal computational overhead.

Organizations developing large-scale machine learning training pipelines should leverage these insights by adopting update rules that incorporate slight gradient perturbations alongside bounded step sizes to enhance stability. Researchers and practitioners should focus next on developing fully adaptive algorithms that automatically tune internal block sizes and step parameters without requiring advance knowledge of function properties.

The primary theoretical limitation is that the proposed framework currently assumes ideal parameter tuning and relies on expected bounds rather than high-probability guarantees. Nonetheless, because the mathematical bounds are backed by matching optimality proofs, confidence in the theoretical foundations remains exceptionally high.

Boston University Google nonconvex optimization stochastic stochastic non-smooth non-convex optimization online-to-non-convex conversion stochastic gradient descent

arXiv: 2302.03775

Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). Provides the foundational theory of online convex optimization, regret minimization, and online-to-batch reductions that form the direct mathematical basis for the source's online-to-non-convex conversion framework.
Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). Introduces online convex programming and standard online gradient descent with regret analysis upon which the source's periodically reset online learning procedures build.
Paper: Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming, Saeed Ghadimi et al. (2013). Establishes baseline complexity bounds and randomized iteration selection for non-convex stochastic optimization and randomized smoothing techniques, which the source directly improves upon to optimal rates.
Paper: Logarithmic regret algorithms for online convex optimization, Elad Hazan et al. (2006). Develops fast-rate and specialized regret minimization algorithms for online convex optimization that underpin advanced online-learning reduction strategies.
Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). Surveys the core theoretical complexities, trade-offs, and convergence principles of stochastic gradient methods in non-convex machine learning regimes.
Book: Convex Optimization: Algorithms and Complexity, Sébastien Bubeck (2015). Supplies comprehensive oracle complexity lower and upper bounds for first-order optimization, establishing the theoretical benchmark that the source paper targets in non-smooth settings.

No sufficiently relevant recommendations were found.

Cover for Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion

Abstract

We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for finding a (δ, ε)-stationary point from O(ε^{-4}δ^{-1}) stochastic gradient queries to O(ε^{-3}δ^{-1}), which we also show to be optimal. Our primary technique is a reduction from non-smooth non-convex optimization to online learning, after which our results follow from standard regret bounds in online learning. For deterministic and second-order smooth objectives, applying more advanced optimistic online learning techniques enables a new complexity of O(ε^{-1.5}δ^{-0.5}). Our improved non-smooth analysis also immediately recovers all optimal or best-known results for finding ε stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings.

Topics

nonconvex optimization stochastic

Keywords

stochastic non-smooth non-convex optimization online-to-non-convex conversion stochastic gradient descent optimistic mirror descent directional derivative oracle variance reduction dynamic regret stationary points iteration complexity

1. Introduction
1.1. Related Work
2. Definitions and Setup
2.1. (δ, ε)-Stationary Points
2.2. Online Learning
3. Online-to-Non-Convex Conversion
3.1. Guarantees for Non-Smooth Non-Convex Functions
4. Bounds for the L1 Norm
5. From Non-smooth to Smooth Guarantees
6. Deterministic and Smooth Case
6.1. Better Results with Second-Order Smoothness
7. Lower Bounds
8. Conclusion
Acknowledgements
References
A. Proof of Proposition 2
B. Analysis of (Optimistic) Online Gradient Descent
C. Algorithm 2 and Regret Guarantee
D. Proof of Theorem 17
E. Proofs for Section 5
F. Lower Bounds
F.1. Definitions and Results from Arjevani et al. (2019)
F.2. Defining the 'Hard' Instance
F.3. Definition and Properties of qB
G. Proof of Theorem 13
H. Directional Derivative Setting

Knowls

Knowl 1 — Optimization and stochastic-oracle setting
assumption
The objective is a differentiable function $F:\mathcal H\to\mathbb R$ on a real Hilbert space, with finite lower bound $F^*:=\inf_{x\in\mathcal H}F(x)>-\infty$ . No smoothness assumption is imposed. The function is required to be well-behaved, meaning that for every $x,y\in\mathcal H$ ,
$F(y)-F(x)=\int_0^1\left\langle \nabla F\bigl(x+t(y-x)\bigr),y-x\right\rangle\,dt.$
The algorithm accesses $F$ through an unbiased stochastic gradient oracle $g=\operatorname{GRAD}(x,z)$ , where $z$ is freshly sampled randomness, $\mathbb E[g\mid x]=\nabla F(x)$ , and the conditional variance satisfies $\operatorname{Var}(g\mid x)\le \sigma^2$ . The paper’s results are stated primarily for this setting; locally Lipschitz, possibly nondifferentiable objectives are handled through randomized smoothing.
Knowl 2 — Finite-support approximate stationarity
definition
For an almost-everywhere differentiable function $F$ and a point $x$ , radius $\delta>0$ , and tolerance $\varepsilon>0$ , $x$ is called a $(\delta,\varepsilon)$ -stationary point if there is a finite set $S\subseteq B(x,\delta)$ such that a uniformly sampled $y\in S$ satisfies
$\mathbb E[y]=x, \qquad \left\|\mathbb E[\nabla F(y)]\right\|\le \varepsilon.$
Equivalently, the paper measures stationarity by
$\|\nabla F(x)\|_\delta := \inf_{\substack{S\subseteq B(x,\delta)\\ |S|<\infty,\;\frac1{|S|}\sum_{y\in S}y=x}} \left\|\frac1{|S|}\sum_{y\in S}\nabla F(y)\right\|.$
Thus, the goal is not necessarily to make the gradient at $x$ itself small, but to find a centered finite distribution of nearby points whose average gradient is small.
Knowl 3 — Online-to-non-convex conversion procedure
algorithm
The method converts an online linear-learning algorithm into a first-order non-convex optimizer. Let $x_0$ be the initial point, let $K,T\in\mathbb N$ , set $M=KT$ , and let an online learner output an update $\Delta_n$ before observing the current gradient. The learner receives linear losses $\ell_n(\Delta)=\langle g_n,\Delta\rangle$ .
Input: initial point $x_0$ , integers $K,T$ , online learner A
Set $M=K T$
for $n=1,\ldots,M$ do
    Obtain update $\Delta_n$ from A
    Set $x_n=x_{n-1}+\Delta_n$
    Sample $s_n$ uniformly from $[0,1]$
    Set $w_n=x_{n-1}+s_n\Delta_n$
    Sample fresh oracle randomness $z_n$
    Query $g_n=\operatorname{GRAD}(w_n,z_n)$
    Send linear loss vector $g_n$ to A
end for
For $k=1,\ldots,K$ and $t=1,\ldots,T$ , set $w_t^k=w_{(k-1)T+t}$
For $k=1,\ldots,K$ , set $w^k=\frac1T\sum_{t=1}^T w_t^k$
Return $w^1,\ldots,w^K$
For any comparison vectors $u_1,\ldots,u_M$ , define the cumulative linear regret $\sum_{n=1}^M\langle g_n,\Delta_n-u_n\rangle$ . If $\bar g_n:=\int_0^1\nabla F(x_{n-1}+s\Delta_n)\,ds$ , well-behavedness gives the exact decomposition
$F(x_M)=F(x_0)+\sum_{n=1}^M\langle g_n,\Delta_n-u_n\rangle +\sum_{n=1}^M\langle \bar g_n-g_n,\Delta_n\rangle +\sum_{n=1}^M\langle g_n,u_n\rangle.$
Because $s_n$ is uniform and the oracle is unbiased, $\mathbb E[g_n\mid x_{n-1},\Delta_n]=\bar g_n$ , so the second sum vanishes in expectation. Consequently, online regret directly controls the decrease of the non-convex objective, while the comparison vectors are chosen from blockwise average gradients.
Knowl 4 — Master reduction from shifting regret to averaged gradients
theoretical result
Run the online-to-non-convex conversion for $M=KT$ rounds, with $s_n$ sampled uniformly from $[0,1]$ . For each block $k$ , define $w_t^k=w_{(k-1)T+t}$ and choose the comparison vector
$u^k=-D\,\frac{\sum_{t=1}^T\nabla F(w_t^k)}{\left\|\sum_{t=1}^T\nabla F(w_t^k)\right\|},$
where $D>0$ and $u^k=0$ when the numerator is zero. Let $u_n=u^k$ throughout block $k$ , and let the stochastic gradient variance satisfy $\operatorname{Var}(g_n)\le\sigma^2$ . Define the $K$ -shifting regret
$R_T(u^1,\ldots,u^K) :=\sum_{k=1}^K\sum_{t=1}^T \left\langle g_{(k-1)T+t},\Delta_{(k-1)T+t}-u^k\right\rangle.$
Then
$\mathbb E\left[\frac1K\sum_{k=1}^K \left\|\frac1T\sum_{t=1}^T\nabla F(w_t^k)\right\|\right] \le \frac{F(x_0)-F^*}{DM} +\frac{\mathbb E[R_T(u^1,\ldots,u^K)]}{DM} +\frac{\sigma}{\sqrt T}.$
This is the central reduction: any online learner with a small shifting-regret bound yields a non-convex optimization guarantee, even though the objective need not be smooth or convex.
Knowl 5 — Optimal stochastic complexity for nonsmooth non-convex objectives
empirical result
Suppose the stochastic gradients satisfy $\mathbb E\|g_n\|^2\le G^2$ , and the online learner guarantees $\|\Delta_n\|\le D$ together with
$\mathbb E[R_T(u^1,\ldots,u^K)]\le DGK\sqrt T$
for every sequence of comparison vectors with $\|u^k\|\le D$ . Online gradient descent restarted every $T$ rounds has this guarantee. Given a budget of $N$ oracle queries and target radius $\delta>0$ , choose
$D=\frac{\delta}{T}, \qquad T=\min\left\{\left\lceil\left(\frac{GN\delta}{F(x_0)-F^*}\right)^{2/3}\right\rceil,\frac N2\right\}, \qquad K=\left\lfloor\frac NT\right\rfloor.$
The block average $w^k=T^{-1}\sum_{t=1}^T w_t^k$ then satisfies $\|w_t^k-w^k\|\le\delta$ for every $k,t$ , and
$\mathbb E\left[\frac1K\sum_{k=1}^K\|\nabla F(w^k)\|_\delta\right] \le \frac{2(F(x_0)-F^*)}{\delta N} + \max\left\{ \frac{5G^{2/3}(F(x_0)-F^*)^{1/3}}{(N\delta)^{1/3}}, \frac{6G}{\sqrt N} \right\}.$
Selecting one block average uniformly at random therefore produces a $(\delta,\varepsilon)$ -stationary point using $O\!\left(G(F(x_0)-F^*)\varepsilon^{-3}\delta^{-1}\right)$ stochastic gradient evaluations, up to constants and the lower-order $N^{-1/2}$ term. This improves the previous $O(\varepsilon^{-4}\delta^{-1})$ dependence to $O(\varepsilon^{-3}\delta^{-1})$ .
Knowl 6 — Matching stochastic lower bound
theoretical result
For any radius $\delta>0$ , tolerance $\varepsilon>0$ , objective gap $\gamma>0$ , and gradient second-moment scale $G$ satisfying
$G\ge \frac{3\sqrt{2\varepsilon\gamma}}{\sqrt\delta},$
there exists a distribution over $G$ -Lipschitz, infinitely differentiable functions $F:\mathbb R^d\to\mathbb R$ with $F(0)-\inf_xF(x)\le\gamma$ and stochastic first-order oracles satisfying $\mathbb E\|\operatorname{GRAD}(x,z)\|^2\le G^2$ such that every randomized first-order algorithm requires
$\Omega\left(\frac{G^2\gamma}{\delta\varepsilon^3}\right)$
stochastic oracle queries to produce an $x$ with $\mathbb E[\|\nabla F(x)\|_\delta]\le\varepsilon$ . Hence the $O(\varepsilon^{-3}\delta^{-1})$ dependence achieved by the online-to-non-convex conversion is optimal in this parameter regime, even for smooth Lipschitz hard instances.
Knowl 7 — Recovery of optimal stochastic smooth-objective rates
theoretical result
The paper relates its neighborhood stationarity measure to ordinary stationarity. If $F$ is $H$ -smooth, meaning $\nabla F$ is $H$ -Lipschitz, then every point satisfying $\|\nabla F(x)\|_\delta\le\varepsilon$ also satisfies
$\|\nabla F(x)\|\le\varepsilon+H\delta.$
If $F$ is $J$ -second-order-smooth, meaning $\|\nabla^2F(x)-\nabla^2F(y)\|_{\mathrm{op}}\le J\|x-y\|$ , then
$\|\nabla F(x)\|\le\varepsilon+\frac J2\delta^2.$
Combining these relations with the $O(\varepsilon^{-3}\delta^{-1})$ stochastic nonsmooth guarantee gives an $O(\varepsilon^{-4})$ stochastic-gradient complexity for an ordinary $(0,\varepsilon)$ -stationary point of an $H$ -smooth objective by setting $\delta=\varepsilon/H$ . For a $J$ -second-order-smooth objective, setting $\delta=\sqrt{\varepsilon/J}$ gives $O(\varepsilon^{-7/2})$ , matching the paper’s stated optimal rate for that setting.
Knowl 8 — Deterministic smooth optimization via optimistic online learning
theoretical result
For a deterministic oracle $g_n=\nabla F(w_n)$ and an $H$ -smooth objective, the conversion can use an optimistic online learner whose updates obey $\|\Delta_n\|\le D$ and whose static regret satisfies
$R_T(u)\le C D\sqrt{\sum_{t=1}^T\|g_t-h_t\|^2}$
for hints $h_t$ and constant $C$ . Taking the standard hints $h_t=g_{t-1}$ and restarting the learner every $T$ rounds makes the regret depend on the variation of consecutive gradients rather than their absolute magnitudes. With $D=\delta/T$ and
$T=\min\left\{\left\lceil\left(\frac{C\delta^2\sqrt{HN}}{F(x_0)-F^*}\right)^{2/5}\right\rceil,\frac N2\right\},$
the resulting method finds a $(\delta,\varepsilon)$ -stationary point in $O(\varepsilon^{-5/3}\delta^{-1/3})$ deterministic gradient evaluations, up to problem-dependent constants and lower-order terms. Using $\delta=\varepsilon/H$ and the smoothness transfer bound yields an $O(\varepsilon^{-2})$ complexity for an ordinary stationary point, matching the standard deterministic first-order rate.
Knowl 9 — Second-order-smooth deterministic acceleration with careful hints
algorithm
For an $H$ -smooth and $J$ -second-order-smooth objective, the paper uses midpoint queries and recursively refined optimistic hints. Let $\Pi_D$ denote projection onto the radius- $D$ Euclidean ball. The optimistic learner is:
Input: learning rate $\eta$ , horizon $T$ , radius $D$ , integer $Q$
Set $\Delta^0_1=0$
for $t=1,\ldots,T$ do
    Set $h^0_t=\nabla F(x_{t-1})$
    for $i=1,\ldots,Q$ do
        Set $h^i_t=\nabla F\left(x_{t-1}+\frac12\Pi_D(\Delta^0_t-\eta h^{i-1}_t)\right)$
    end for
    Set $h_t=h^Q_t$
    Set $\Delta_t=\Pi_D(\Delta^0_t-\eta h_t)$
    Query the actual gradient $g_t=\nabla F\left(x_{t-1}+\frac12\Delta_t\right)$
    Set $\Delta^0_{t+1}=\Pi_D(\Delta^0_t-\eta g_t)$
end for
With $\eta=1/(2H)$ and $Q=\left\lceil\log_2\sqrt{NG/(HD)}\right\rceil$ , where $G$ is a Lipschitz bound on $F$ , the learner uses $O(\log N)$ gradient queries per outer iteration and achieves hints whose error from the actual midpoint gradient is $O(N^{-1/2})$ . In the outer conversion, set the sampling location to the midpoint $s_n=1/2$ , restart this learner every $T$ rounds, and choose $D=\delta/T$ . The resulting guarantee is
$\frac1K\sum_{k=1}^K\|\nabla F(w^k)\|_\delta \le \frac{4G}{N}+\frac{2(F(x_0)-F^*)}{N\delta} +\frac{3(H+J\delta)^{1/3}(F(x_0)-F^*)^{2/3}}{\delta^{1/3}N^{2/3}} +\frac{10\delta(H+J\delta)}{N^2}.$
Choosing $\delta=H^{1/7}(F(x_0)-F^*)^{2/7}/(J^{3/7}N^{2/7})$ gives
$\frac1K\sum_{k=1}^K\|\nabla F(w^k)\| =O\left(\frac{J^{1/7}H^{2/7}(F(x_0)-F^*)^{4/7}}{N^{4/7}}\right),$
while the total number of gradient queries is $O(N\log N)$ . Equivalently, the method obtains a $(0,\varepsilon)$ -stationary point in $\widetilde O(\varepsilon^{-7/4})$ queries, improving the $O(\varepsilon^{-2})$ deterministic smooth rate up to logarithmic factors.
Knowl 10 — Extension to locally Lipschitz and nondifferentiable objectives
theoretical result
The framework extends beyond everywhere-differentiable objectives. If a locally Lipschitz function $F:\mathbb R^d\to\mathbb R$ is differentiable everywhere, it automatically satisfies the well-behaved line-integral condition. If $F$ is nondifferentiable, choose any smoothing radius $p>0$ , let $u$ be uniform on the unit Euclidean ball, and define
$\widehat F(x):=\mathbb E_u[F(x+pu)].$
Then $\widehat F$ is differentiable and well-behaved, and the oracle
$\widehat{\operatorname{GRAD}}(x,(z,u)):=\operatorname{GRAD}(x+pu,z)$
is an unbiased stochastic gradient oracle for $\widehat F$ . The queried point $x+pu$ is a differentiability point with probability one. If $F$ is $G$ -Lipschitz, then the smoothing perturbation is uniformly bounded by
$|\widehat F(x)-F(x)|\le pG.$
Moreover, if $p\le\delta$ and $\|\nabla\widehat F(x)\|_\delta\le\varepsilon$ , then
$\|\nabla F(x)\|_{2\delta}\le\varepsilon.$
Thus the stochastic nonsmooth guarantees apply to locally Lipschitz objectives after arbitrarily small randomized smoothing, with only a constant-factor enlargement of the stationarity radius.

Coverage note — The coordinatewise $L_1$-stationarity refinement and the appendix extension to stochastic directional-derivative oracles were omitted because they are secondary norm/oracle variants of the main conversion and do not change its central complexity results.

References

1.Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E., and Ma, T. Finding approximate local minima for nonconvex optimization in linear time. arXiv preprint arXiv:1611.01146, 2016.
2.Allen-Zhu, Z. Natasha 2: Faster non-convex optimization than SGD. In Advances in neural information processing systems, pp. 2675–2686, 2018.
3.Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365, 2019.
4.Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Sekhari, A., and Sridharan, K. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pp. 242–299, 2020.
5.Baby, D. and Wang, Y.-X. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In International Conference on Artificial Intelligence and Statistics, pp. 1805–1845. PMLR, 2022.
6.Bertsekas, D. P. Stochastic optimization problems with nondifferentiable cost functionals. Journal of Optimization Theory and Applications, 12(2):218–231, 1973.
7.Bianchi, P., Hachem, W., and Schechtman, S. Convergence of constant step stochastic gradient descent for non-smooth non-convex functions. Set-Valued and Variational Analysis, 30(3):1117–1147, 2022.
8.Bubeck, S. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
9.Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. “convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions. In International Conference on Machine Learning, pp. 654–663. PMLR, 2017.
10.Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):1751–1772, 2018.
11.Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points I. Mathematical Programming, pp. 1–50, 2019.
12.Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming, 185(1-2), 2021.
13.Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge University Press, 2006.
14.Cesa-Bianchi, N., Conconi, A., and Gentile, C. On the generalization ability of on-line learning algorithms. Information Theory, IEEE Transactions on, 50(9):2050–2057, 2004.
15.Chen, L., Luo, H., and Wei, C.-Y. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory, pp. 1216–1259. PMLR, 2021.
16.Clarke, F. H. Optimization and nonsmooth analysis. SIAM, 1990.
17.Cutkosky, A. Combining online learning guarantees. In Proceedings of the Thirty-Second Conference on Learning Theory, pp. 895–913, 2019.
18.Cutkosky, A. Parameter-free, dynamic, and strongly-adaptive online learning. In International Conference on Machine Learning, volume 2, 2020.
19.Cutkosky, A. and Mehta, H. Momentum improves normalized SGD. In International Conference on Machine Learning, 2020.
20.Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in Banach spaces. In Conference On Learning Theory, pp. 1493–1529, 2018.
21.Cutkosky, A. and Orabona, F. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems, pp. 15210–15219, 2019.
22.Daniely, A., Gonen, A., and Shalev-Shwartz, S. Strongly adaptive online learning. In International Conference on Machine Learning, pp. 1405–1411. PMLR, 2015.
23.Davis, D., Drusvyatskiy, D., Lee, Y. T., Padmanabhan, S., and Ye, G. A gradient sampling method with complexity guarantees for lipschitz functions in high and low dimensions. arXiv preprint arXiv:2112.06969, 2021.
24.Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. In Conference on Learning Theory (COLT), pp. 257–269, 2010.
25.Duchi, J. C., Bartlett, P. L., and Wainwright, M. J. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674–701, 2012.
26.Fang, C., Li, C. J., Lin, Z., and Zhang, T. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 689–699, 2018.
27.Fang, C., Lin, Z., and Zhang, T. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory, pp. 1192–1234, 2019.
28.Faw, M., Tziotis, I., Caramanis, C., Mokhtari, A., Shakkottai, S., and Ward, R. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pp. 313–355. PMLR, 2022.
29.Flaxman, A. D., Kalai, A. T., and McMahan, H. B. Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 385–394, 2005.
30.Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.
31.Ghai, U., Lu, Z., and Hazan, E. Non-convex online learning via algorithmic equivalence. arXiv preprint arXiv:2205.15235, 2022.
32.Goyal, P., Dollar, P., Girshick, R., Noordhuis, P., ´Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K. Accurate, large minibatch SGD: Training ImageNet in 1 hour. arXiv preprint arXiv:1706.02677, 2017.
33.Hazan, E. Introduction to online convex optimization. arXiv preprint arXiv:1909.05207, 2019.
34.Hazan, E. and Kale, S. Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine learning, 80(2-3):165–188, 2010.
35.Hazan, E., Singh, K., and Zhang, C. Efficient regret minimization in non-convex games. In International Conference on Machine Learning, pp. 1433–1441. PMLR, 2017.
36.Herbster, M. and Warmuth, M. K. Tracking the best regressor. In Proceedings of the eleventh annual conference on Computational learning theory, pp. 24–31, 1998.
37.Hoeven, D., Erven, T., and Kotłowski, W. The many faces of exponential weights in online learning. In Conference On Learning Theory, pp. 2067–2092. PMLR, 2018.
38.Jacobsen, A. and Cutkosky, A. Parameter-free mirror descent. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 4160–4211. PMLR, 2022.
39.Jordan, M. I., Lin, T., and Zampetakis, M. On the complexity of deterministic nonsmooth and nonconvex optimization. arXiv preprint arXiv:2209.12463, 2022.
40.Jun, K.-S., Orabona, F., Wright, S., and Willett, R. Improved strongly adaptive online learning using coin betting. In Artificial Intelligence and Statistics, pp. 943–951. PMLR, 2017.
41.Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03606, 2020.
42.Kingma, D. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
43.Kornowski, G. and Shamir, O. On the complexity of finding small subgradients in nonsmooth optimization. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022a.
44.Kornowski, G. and Shamir, O. Oracle complexity in nonsmooth nonconvex optimization. Journal of Machine Learning Research, 23(314):1–44, 2022b.
45.Levy, K., Kavis, A., and Cevher, V. Storm+: Fully adaptive SGD with recursive momentum for nonconvex optimization. Advances in Neural Information Processing Systems, 34:20571–20582, 2021.
46.Li, H. and Lin, Z. Restarted nonconvex accelerated gradient descent: No more polylogarithmic factor in the o(ε−7/4) complexity. In International Conference on Machine Learning. PMLR, 2022.
47.Li, X. and Orabona, F. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 983–992. PMLR, 2019.
48.Li, X., Zhuang, Z., and Orabona, F. A second look at exponential and cosine step sizes: Simplicity, adaptivity, and performance. In International Conference on Machine Learning, pp. 6553–6564. PMLR, 2021.
49.Lin, T., Zheng, Z., and Jordan, M. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160–26175, 2022.
50.Liu, Z., Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. L. META-STORM: Generalized fully-adaptive variance reduced SGD for unbounded functions. arXiv preprint arXiv:2209.14853, 2022.
51.Loshchilov, I. and Hutter, F. SGDR: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.03983, 2016.
52.Loshchilov, I. and Hutter, F. Decoupled weight decay regularization. In International Conference on Learning Representations, 2018.
53.Lu, Z., Xia, W., Arora, S., and Hazan, E. Adaptive gradient methods with local guarantees. arXiv preprint arXiv:2203.01400, 2022.
54.Luo, H., Zhang, M., Zhao, P., and Zhou, Z.-H. Corralling a larger band of bandits: A case study on switching regret for linear bandits. In Conference on Learning Theory, 2022.
55.McMahan, H. B. and Streeter, M. Adaptive bound optimization for online convex optimization. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), pp. 244–256, 2010.
56.Mhammedi, Z. and Koolen, W. M. Lipschitz and comparator-norm adaptivity in online learning. Conference on Learning Theory, pp. 2858–2887, 2020.
57.Orabona, F. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019.
58.Orabona, F. and Pal, D. Scale-free algorithms for online linear optimization. In Chaudhuri, K., Gentile, C., and Zilles, S. (eds.), Algorithmic Learning Theory, pp. 287–301. Springer International Publishing, 2015.
59.Patel, V. and Berahas, A. S. Gradient descent in the absence of global lipschitz continuity of the gradients: Convergence, divergence and limitations of its continuous approximation. arXiv preprint arXiv:2210.02418, 2022.
60.Rakhlin, A. and Sridharan, K. Online learning with predictable sequences. In Conference on Learning Theory (COLT), pp. 993–1019, 2013.
61.Sachs, S., Hadiji, H., van Erven, T., and Guzmán, C. Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. arXiv preprint arXiv:2202.07554, 2022.
62.Stein, E. M. and Shakarchi, R. Real analysis: measure theory, integration, and Hilbert spaces. Princeton University Press, 2009.
63.Tian, L. and So, A. M.-C. No dimension-free deterministic algorithm computes approximate stationarities of lipschitzians. arXiv preprint arXiv:2210.06907, 2022.
64.Tian, L., Zhou, K., and So, A. M.-C. On the finite-time complexity and practical computation of approximate stationarity concepts of lipschitz functions. In International Conference on Machine Learning, pp. 21360–21379. PMLR, 2022.
65.Tripuraneni, N., Stern, M., Jin, C., Regier, J., and Jordan, M. I. Stochastic cubic regularization for fast nonconvex optimization. In Advances in neural information processing systems, pp. 2899–2908, 2018.
66.Wang, G., Hu, Z., Muthukumar, V., and Abernethy, J. Adaptive oracle-efficient online learning. arXiv preprint arXiv:2210.09385, 2022.
67.You, Y., Li, J., Reddi, S., Hseu, J., Kumar, S., Bhojanapalli, S., Song, X., Demmel, J., Keutzer, K., and Hsieh, C.-J. Large batch optimization for deep learning: Training BERT in 76 minutes. arXiv preprint arXiv:1904.00962, 2019.
68.Zhang, J. and Cutkosky, A. Parameter-free regret in high probability with heavy tails. In Advances in Neural Information Processing Systems, 2022.
69.Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383–15393, 2020a.
70.Zhang, J., Lin, H., Jegelka, S., Sra, S., and Jadbabaie, A. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, 2020b.
71.Zhang, L., Lu, S., and Zhou, Z.-H. Adaptive online learning in dynamic environments. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 1330–1340, 2018.
72.Zhang, L., Wang, G., Tu, W.-W., Jiang, W., and Zhou, Z.-H. Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. Advances in Neural Information Processing Systems, 34:24968–24980, 2021.
73.Zhang, Z., Cutkosky, A., and Paschalidis, I. Adversarial tracking control via strongly adaptive online learning with memory. In International Conference on Artificial Intelligence and Statistics, pp. 8458–8492. PMLR, 2022.
74.Zhou, D., Xu, P., and Gu, Q. Stochastic nested variance reduction for nonconvex optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 3925–3936, 2018.
75.Zhuang, Z., Cutkosky, A., and Orabona, F. Surrogate losses for online learning of stepsizes in stochastic non-convex optimization. In International Conference on Machine Learning, pp. 7664–7672, 2019.
76.Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928–936, 2003.

Citation

MLA

Cutkosky, A., et al. “Optimal Stochastic Non-smooth Non-convex Optimization Through Online-to-Non-convex Conversion”. International Conference on Machine Learning, vol. 202, 2023, pp. 6643–70, https://proceedings.mlr.press/v202/cutkosky23a.html.

APA

Cutkosky, A., Mehta, H., & Orabona, F. (2023). Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion. International Conference on Machine Learning, 202, 6643–6670. https://proceedings.mlr.press/v202/cutkosky23a.html

Chicago

Cutkosky, A., H. Mehta, and F. Orabona. 2023. “Optimal Stochastic Non-smooth Non-convex Optimization Through Online-to-Non-convex Conversion”. International Conference on Machine Learning 202: 6643–70. https://proceedings.mlr.press/v202/cutkosky23a.html.

Harvard

Cutkosky, A., Mehta, H. and Orabona, F. (2023) “Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion”, International Conference on Machine Learning. PMLR, pp. 6643–6670. Available at: https://proceedings.mlr.press/v202/cutkosky23a.html.

Vancouver

1. Cutkosky A, Mehta H, Orabona F (2023) Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion. In: International Conference on Machine Learning. PMLR, pp 6643–6670

BibTeX

@InProceedings{pmlr-v202-cutkosky23a,
  title = 	 {Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion},
  author =       {Cutkosky, Ashok and Mehta, Harsh and Orabona, Francesco},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {6643--6670},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/cutkosky23a/cutkosky23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/cutkosky23a.html},
  abstract = 	 {We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for finding a $(\delta,\epsilon)$-stationary point from $O(\epsilon^{-4}\delta^{-1})$ stochastic gradient queries to $O(\epsilon^{-3}\delta^{-1})$, which we also show to be optimal. Our primary technique is a reduction from non-smooth non-convex optimization to online learning, after which our results follow from standard regret bounds in online learning. For deterministic and second-order smooth objectives, applying more advanced optimistic online learning techniques enables a new complexity of $O(\epsilon^{-1.5}\delta^{-0.5})$. Our improved non-smooth analysis also immediately recovers all optimal or best-known results for finding $\epsilon$ stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Optimization and stochastic-oracle setting

Knowl 2 — Finite-support approximate stationarity

Knowl 3 — Online-to-non-convex conversion procedure

Knowl 4 — Master reduction from shifting regret to averaged gradients

Knowl 5 — Optimal stochastic complexity for nonsmooth non-convex objectives

Knowl 6 — Matching stochastic lower bound

Knowl 7 — Recovery of optimal stochastic smooth-objective rates

Knowl 8 — Deterministic smooth optimization via optimistic online learning

Knowl 9 — Second-order-smooth deterministic acceleration with careful hints

Knowl 10 — Extension to locally Lipschitz and nondifferentiable objectives

References

Citation

BibTeX

Access the Paper