REVIEW 7 cited by
Variance-reduced Clipping for Non-convex Optimization
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
Gradient clipping is a standard training technique used in deep learning applications such as large-scale language modeling to mitigate exploding gradients. Recent experimental studies have demonstrated a fairly special behavior in the smoothness of the training objective along its trajectory when trained with gradient clipping. That is, the smoothness grows with the gradient norm. This is in clear contrast to the well-established assumption in folklore non-convex optimization, a.k.a. $L$--smoothness, where the smoothness is assumed to be bounded by a constant $L$ globally. The recently introduced $(L_0,L_1)$--smoothness is a more relaxed notion that captures such behavior in non-convex optimization. In particular, it has been shown that under this relaxed smoothness assumption, SGD with clipping requires $O(\epsilon^{-4})$ stochastic gradient computations to find an $\epsilon$--stationary solution. In this paper, we employ a variance reduction technique, namely SPIDER, and demonstrate that for a carefully designed learning rate, this complexity is improved to $O(\epsilon^{-3})$ which is order-optimal. Our designed learning rate comprises the clipping technique to mitigate the growing smoothness. Moreover, when the objective function is the average of $n$ components, we improve the existing $O(n\epsilon^{-2})$ bound on the stochastic gradient complexity to $O(\sqrt{n} \epsilon^{-2} + n)$, which is order-optimal as well. In addition to being theoretically optimal, SPIDER with our designed parameters demonstrates comparable empirical performance against variance-reduced methods such as SVRG and SARAH in several vision tasks.
Forward citations
Cited by 7 Pith papers
-
Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
AdaGrad-type algorithms provably need a complexity quadratic in the initial gap and smoothness constants under relaxed smoothness, so they cannot match the optimal rate of clipped SGD.
-
A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
SLIP is the first single-loop stochastic bilevel optimizer with eO(1/epsilon^4) oracle complexity under unbounded upper-level smoothness, both in expectation and with high probability.
-
Revisiting Randomized Smoothing: Nonsmooth Nonconvex Optimization Beyond Global Lipschitz Continuity
For functions satisfying an (α,β) subgradient growth condition, the paper's variance-reduced randomized smoothing method reaches a (δ,ε)-Goldstein stationary point in Õ(d^{3/2}δ^{-1}ε^{-3}) function evaluations with h...
-
Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness
Shuffling gradient methods converge without Lipschitz smoothness under a sub-quadratic ℓ-smoothness condition, matching Lipschitz-case rates when ℓ is constant.
-
A Fast Newton Method Under Local Lipschitz Smoothness
A new adaptive Newton method with negative curvature steps achieves near-optimal complexity for nonconvex optimization using only local Hessian Lipschitz smoothness.
-
Generalized Convexity and Smoothness via Conjugate Duality: Optimization Theory for Deep Neural Networks
The paper introduces H(psi)-convexity and H(Psi)-smoothness via Legendre functions, proves generalized GD/SGD convergence rates, and reformulates DNN training as composite optimization controlled by gradient energy an...
-
Outlier-Robust Training of Machine Learning Models
The paper presents a robust loss kernel framework and an Adaptive Alternation Algorithm that reweights samples, claiming an enlarged convergence region under arbitrary outliers; the proof of the main convergence theor...
Discussion (0). Continue with ORCID to comment.