PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ashok Cutkosky, Harsh Mehta, Francesco Orabona

arXiv:2302.03775v3cs.LGmath.OCstat.ML

TL;DR

The paper studies how to find approximate stationary points for stochastic non-smooth non-convex objectives, where standard smoothness-based analyses are insufficient. It reduces optimization to online learning through linear losses formed from stochastic gradients, obtaining an optimal O(ε^-3δ^-1) rate and stronger rates in deterministic and second-order smooth settings.

  • Problem

    Non-smooth non-convex stochastic optimization lacks the smoothness-based guarantees available for standard neural-network optimization, motivating tractable stationarity criteria and sharper complexity bounds.

  • Method

    The paper reduces non-smooth non-convex stochastic optimization to online learning by using shifting-regret algorithms to choose updates from stochastic-gradient linear losses.

  • Results

    O(ε^-3δ^-1) stochastic gradient evaluations find a (δ, ε)-stationary point, improving the previous O(ε^-4δ^-1) rate and achieving optimality when ε ≤ O(δ).

  • Takeaways & Limitations

    Online-learning regret bounds provide an optimal route to stationarity for non-smooth non-convex stochastic optimization and recover established smooth-objective rates.

  • Takeaways & Limitations

    The main analysis uses a stochastic gradient oracle, while directional-gradient-oracle results require separate appendix modifications; deterministic improvement remains an open question in one setting.

Abstract

from arXiv · show

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 techniques also recover all optimal or best-known results for finding $ε$ stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings.

1 Introduction

The paper addresses stochastic non-smooth non-convex optimization, where standard smoothness-based guarantees do not apply, by reducing the problem to online learning. This yields improved and optimal stationarity complexities, alongside corollaries for smooth and second-order smooth objectives.

  • Motivation: Non-smooth objectives matter because neural-network architectures using ReLUs or max-pooling can violate the smoothness assumptions underlying standard SGD analyses.For smooth objectives, SGD has optimal O(ε^-4) complexity, while second-order smoothness gives optimal O(ε^-3.5) complexity.
  • Problem setting: The (δ, ε)-stationarity notion requires a nearby random point whose expected gradient norm is at most ε, with the current prior complexity O(ε^-4δ^-1).It generalizes ordinary (0, ε)-stationarity to settings where exact pointwise gradients may be unsuitable.
  • Contributions: O(ε^-3δ^-1) stochastic gradient evaluations identify a (δ, ε)-stationary point, improving the previous O(ε^-4δ^-1) rate.The paper establishes that this rate is optimal when ε ≤ O(δ).
  • Contributions: The online-to-non-convex reduction uses shifting-regret online algorithms to choose updates from linear losses built from stochastic gradients.This connects non-convex stochastic optimization with established online-learning regret bounds.
  • Corollaries: For deterministic and second-order smooth objectives, the method achieves O(ε^-3/2δ^-1/2), implying O(ε^-7/4) complexity for ordinary stationarity.The same framework also recovers O(ε^-4) and O(ε^-3.5) complexities for smooth and second-order smooth objectives, respectively.

2 Definitions and Setup

The paper studies differentiable, potentially non-smooth objectives accessed through stochastic gradients and defines stationarity using averaged gradients within a radius-δ neighborhood. Its framework relies on a mild well-behavedness condition that extends to locally Lipschitz objectives through arbitrarily small random smoothing.

  • Definitions and assumptions: The objective F is differentiable and bounded below, but no smoothness assumption is imposed.The formal setting is a real Hilbert space, typically R^d, with stochastic-gradient access in the motivating expectation-over-data formulation.
  • Definitions and assumptions: A stochastic gradient oracle returns an unbiased gradient estimate with bounded variance.The oracle samples an independent data variable and satisfies E[Grad(x,z)] = ∇F(x), with variance at most σ^2.
  • Definitions and assumptions: Well-behavedness is the regularity condition used to analyze nonsmooth objectives, and locally Lipschitz functions can satisfy it after arbitrarily small perturbation.Everywhere-differentiable locally Lipschitz functions are well-behaved; otherwise, uniform ball smoothing produces a differentiable, well-behaved surrogate.
  • Stationarity: A (δ, ϵ)-stationary point permits averaging gradients at finitely many points within distance δ while requiring their mean location to equal x.This definition generalizes ordinary ϵ-stationarity, which is recovered when δ = 0.
  • Online-learning setup: The paper reduces optimization to online linear learning with shifting competitors, where lower shifting regret yields stronger non-convex guarantees.The online learner chooses update directions against sequential linear losses, and resetting it supports comparison with changing competitors.

3 Online-to-Non-Convex Conversion

The online-to-non-convex conversion replaces direct optimization updates with online-learned directions and uses randomized intermediate gradients to handle nonsmoothness. Shifting-regret guarantees then yield the optimal stochastic complexity for finding (δ, ϵ)-stationary points, though the basic bound does not improve for deterministic gradients.

  • Online-to-non-convex conversion: The conversion lets an online learner choose each update direction, turning non-convex optimization into minimizing shifting regret over linear losses.The iterate update is x_n = x_{n−1} + Δ_n, while the learner receives losses based on stochastic gradients.
  • Online-to-non-convex conversion: Randomly sampling the gradient along each update segment separates nonsmooth approximation error from the need to predict the unrevealed gradient.This replaces the smooth-objective Taylor argument with randomized scaling and an online-learning prediction step.
  • Algorithm 1: The algorithm performs M = K·T updates, periodically resets the online learner, averages iterates within each block, and returns the block averages.Gradients are evaluated at randomized intermediate points w_n and sent to the online learner.
  • Guarantees for non-smooth non-convex functions: O(ϵ^-3δ^-1) stochastic gradient evaluations suffice to find a (δ, ϵ)-stationary point, and a matching lower bound makes this rate optimal in the stated regime.The guarantee assumes bounded gradient second moment and initial suboptimality γ, giving N = O(Gγϵ^-3δ^-1), with optimality essentially when δG^2 ≥ ϵγ.
  • Guarantees for non-smooth non-convex functions: The resulting rate does not appear to improve when gradients become deterministic because OGD regret remains governed by the gradient-magnitude parameter G.Whether deterministic nonsmooth optimization admits a better rate is left as an open question.

4 Bounds for the L1 Norm

Coordinate-wise online learning extends the conversion to L1-norm stationarity by using regret bounds tailored to coordinatewise gradient magnitudes. This can improve the dimension dependence relative to the Euclidean guarantee under matching moment assumptions.

  • Coordinate-wise online learning: Coordinate-wise online gradient descent yields regret controlled by the sum of coordinatewise gradient bounds, enabling L1-norm stationarity guarantees.Separate learning rates and coordinate projections produce bounds with respect to L1 costs.
  • L1 stationarity: The L1 stationarity notion averages gradients over an L∞ ball of radius δ while requiring mean gradient L1 norm at most ϵ.The sampled finite support must have mean x, paralleling the Euclidean stationarity definition.
  • L1 guarantees: Theorem 13 applies the same conversion with coordinatewise second-moment bounds and updates constrained in the L∞ norm.Its assumptions combine coordinatewise gradient control with a K-shifting regret bound.
  • Comparison with Euclidean bounds: Under matched aggregate moment assumptions, the coordinate-wise guarantee is better than the Euclidean Corollary 9 bound.The comparison is obtained by substituting the aggregate coordinate scale into the respective rates.

5 From Non-smooth to Smooth Guarantees

For smooth objectives, neighborhood stationarity converts directly into ordinary stationarity with an error determined by the smoothness order. Applying the nonsmooth conversion therefore recovers the optimal stochastic rates for first-order and second-order smooth objectives.

  • Smooth objectives: For H-smooth F, a (δ, ϵ)-stationary point is an ordinary (0, ϵ + Hδ)-stationary point.Choosing δ = ϵ/H converts the nonsmooth guarantee into O(ϵ^-4) iterations, matching optimal SGD.
  • Second-order smooth objectives: For J-second-order-smooth F, a (δ, ϵ)-stationary point is an ordinary (0, ϵ + Jδ^2)-stationary point.Choosing δ proportional to ϵ^1/2/J^1/2 yields O(ϵ^-3.5) iterations.
  • Implications: The conversion recovers optimal results for smooth stochastic losses, including the tight second-order-smooth rate.The first-order rate matches standard SGD, while the second-order rate matches refined SGD variants and known lower bounds.

6 Deterministic and Smooth Case

Optimistic online learning improves deterministic smooth optimization rates, with stronger hints yielding the best-known second-order smooth guarantee up to logarithmic factors.

  • 6 Deterministic and Smooth Case: Optimistic online algorithms exploit deterministic gradients and smoothness to obtain rates matching optimal deterministic results.The method uses static regret and carefully constructed hints within an online-to-non-convex conversion.
  • 6 Deterministic and Smooth Case: O(ϵ−5/3δ−1/3) iterations suffice for deterministic smooth objectives, implying O(ϵ−2) iterations for (0, ϵ)-stationarity when δ = ϵ/H.The latter matches the standard optimal rate.
  • 6.1 Better Results with Second-Order Smoothness: More informative hints approximate current gradients using O(log(N)) gradient queries, reducing regret and improving the convergence guarantee.The second-order smooth setting uses a fixed interpolation parameter and an optimistic mirror-descent update.
  • 6.1 Better Results with Second-Order Smoothness: The refined algorithm consumes NQ = O(N log(N)) total gradient queries.This logarithmic overhead accompanies the improved optimistic online-learning procedure.
  • 6.1 Better Results with Second-Order Smoothness: ˜O(ϵ−3/2δ−1/2) iterations find a (δ, ϵ)-stationary point for deterministic, second-order smooth objectives, translating to ˜O(ϵ−7/4) for (0, ϵ)-stationarity.This matches the best-known rate up to a logarithmic factor, though the lower bound remains weaker.

7 Lower Bounds

The paper proves that its O(ϵ−3δ−1) stochastic complexity is tight by extending a lower-bound construction for stochastic smooth non-convex optimization.

  • 7 Lower Bounds: The lower bound matches the paper’s O(ϵ−3δ−1) upper bound, establishing optimality for stochastic non-smooth stationarity.The reduction uses smooth hard instances whose (δ, ϵ)-stationarity would imply ordinary gradient stationarity at a comparable tolerance.
  • 7 Lower Bounds: Ω(G2γ/δϵ3) stochastic oracle queries are necessary for some G-Lipschitz, C∞ objectives under the stated gradient-moment conditions.The lower bound applies to any first-order algorithm seeking a point with E[∥∇F(x)∥δ] ≤ ϵ.
  • 7 Lower Bounds: The construction extends Arjevani et al. (2019) by setting H = ϵδ and scaling the oracle variance to obtain the δ-dependent lower bound.The resulting objective remains smooth and the oracle has bounded second moment.

8 Conclusion

The paper’s online-to-non-convex conversion yields an optimal stochastic rate for non-smooth objectives and opens questions about sharper online-learning tools and deterministic non-smooth limits.

  • 8 Conclusion: Online gradient descent achieves the optimal ϵ−3δ−1 complexity for finding (δ, ϵ)-stationary points.The result follows from converting shifting-regret guarantees into non-convex optimization guarantees.
  • 8 Conclusion: The analysis uses switching regret and suggests that strongly adaptive or dynamic regret may yield more refined non-convex optimization results.The authors also identify adaptation to unknown parameters as an open direction because the analysis assumes perfectly tuned constants.
  • 8 Conclusion: Deterministic non-smooth optimization remains unresolved: the best-known complexity is O(ϵ−3δ−1), and it is unknown whether the smoother-setting O(ϵ−3/2δ−1/2) rate extends to this case.Prior work indicates that randomization can be necessary even with deterministic gradient oracles.

A Proof of Proposition 2

The proof establishes regularity properties for locally Lipschitz objectives, including almost-everywhere differentiability and the behavior of their perturbed, smoothed versions.

  • A Proof of Proposition 2: The operator defined by integrating directional derivatives is linear and represented by a unique vector in finite-dimensional space.Its coordinates are determined by inner products with the standard basis vectors.
  • A Proof of Proposition 2: Locally Lipschitz functions are differentiable almost everywhere and Lipschitz on every compact set.The proof uses a countable cover by neighborhoods around rational-coordinate points and Rademacher’s theorem.
  • A Proof of Proposition 2: The line-segment restriction k(t) = F(x + t(y − x)) is absolutely continuous, enabling the Fundamental Theorem of Calculus representation of F(y) − F(x).This supplies the integral relation between function differences and gradients used in the proposition.
  • A Proof of Proposition 2: The perturbed function remains well-behaved, and an arbitrarily small perturbation preserves proximity to the original G-Lipschitz objective within pG.The perturbed stochastic oracle evaluates the original oracle at x + pu.
  • A Proof of Proposition 2: For the perturbed objective, gx = E_u[∇F(x + pu)] exists and equals the gradient of the perturbed function.Bounded convergence justifies the limiting argument, while compact-set Lipschitzness provides domination.

B Analysis of (Optimistic) Online Gradient Descent

This section analyzes online gradient methods, including optimistic variants, and connects their regret guarantees to the optimization algorithm’s gradient-evaluation complexity.

  • Online Gradient Descent: Optimistic Mirror Descent is analyzed on an L2 ball of radius D in a real Hilbert space, with a regret guarantee stated for every comparator u.The analysis specializes the domain to V = {x : ∥x∥≤D}.
  • Online Gradient Descent: Algorithm 3 reduces to online gradient descent when hints are absent, under a bounded expected squared-gradient assumption and an appropriate stepsize.The no-hint case is identified explicitly as online gradient descent.
  • Online-to-Non-convex Conversion: Theorem 21 analyzes the resulting multiscale procedure for H-smooth and G-Lipschitz objectives, with Q logarithmic stages and a total gradient-evaluation count proportional to T⌈log2(·)⌉.The supplied passages state the smoothness and Lipschitz conditions and the logarithmic evaluation structure, but the displayed expressions are incomplete.
  • Online-to-Non-convex Conversion: The optimization procedure implements the online update by choosing ∆t values corresponding to Algorithm 3 with a squared-Euclidean regularizer.This identifies the algorithmic equivalence used to transfer the regret analysis.

D Proof of Theorem 17

Theorem 17 converts a blockwise online-learning guarantee into an optimization result by repeating comparator choices across T iterations and controlling the resulting displacement and evaluation cost.

  • Proof of Theorem 17: The proof assigns each comparator uk to a consecutive block of T iterations, creating a piecewise-constant sequence for the online-to-optimization reduction.The sequence is defined by repeating u1, u2, and so on across blocks.
  • Proof of Theorem 17: The block construction ensures M = KT is at least N/2, and setting D = δ/T yields the required displacement control in the final bound.The proof explicitly uses M ≥ N/2 and substitutes D = δ/T.
  • Proof of Theorem 17: The proof combines the regret bound with the blockwise construction and then counts gradient evaluations directly to obtain the theorem’s complexity statement.The supplied conclusion states that the evaluation count follows by direct calculation.

E Proofs for Section 5

These proofs relate approximate stationarity to ordinary gradient norms, construct lower bounds through zero-chain instances, and establish the stochastic-oracle properties needed for the hardness argument.

  • Stationarity Relations: For H-smooth functions, (δ, ϵ)-stationarity implies ordinary gradient norm at most ϵ + Hδ.The result follows by bounding gradient variation within the δ-ball.
  • Stationarity Relations: For J-second-order-smooth functions, (δ, ϵ)-stationarity implies ordinary gradient norm at most ϵ + Jδ^2/2.The second-order smoothness relation yields a quadratic dependence on δ.
  • Lower-Bound Strategy: The lower-bound construction modifies the smooth-stationarity lower bound by using the implication from (δ, ϵ)-stationarity to (0, Hδ+ϵ)-stationarity.This transfers a lower bound for ordinary stationarity to the smoothed stationarity criterion.
  • Zero-Chain Construction: The hard instance uses a probability-p zero-chain oracle whose expected gradient equals the objective gradient and whose variance is bounded.The zero-chain and variance properties are inherited from the cited construction.

F.2 Defining the “Hard” Instance

The hard instance replaces a non-Lipschitz quadratic component with a Lipschitz construction while preserving the smoothness, oracle, and lower-bound properties required for the theorem.

  • F.2 Defining the “Hard” Instance: The construction replaces the non-Lipschitz quadratic term with qB,d(x) = x⊤ρB,d(x), which behaves quadratically near the origin and linearly for large norms.This modification addresses the non-Lipschitz behavior of the original quadratic term.
  • F.2 Defining the “Hard” Instance: The transformed instance preserves the zero-chain hardness structure through a random orthonormal embedding, a shrinking map, and an induced stochastic oracle.The proof defines transformed iterates and relates them to a bounded-iterate algorithm.
  • F.2 Defining the “Hard” Instance: Theorem 27 supplies smooth, Lipschitz functions with bounded initial suboptimality and stochastic-gradient variance for which randomized first-order algorithms require many iterations.The theorem states the distributional construction and its lower-bound guarantee.
  • F.2 Defining the “Hard” Instance: The main lower bound requires Ω(γG^2/(δϵ^3)) iterations to identify an x with E[∥∇F(x)∥δ] ≤ ϵ.This is obtained by parameterizing the smooth lower bound with H = ϵ/δ and linking the two stationarity notions.
  • Directional Derivative Setting: The same O(ϵ^-3δ^-1) complexity remains optimal with a directional derivative oracle because the lower-bound functions are continuously differentiable.In that setting, directional and standard gradient oracles coincide for the hard instance.
Loading 2302.03775v3…