Classical analysis of convex and non-convex optimization methods often
requires the Lipshitzness of the gradient, which limits the analysis to
functions bounded by quadratics. Recent work relaxed this requirement to a
non-uniform smoothness condition with the Hessian norm bounded by an affine
function of the gradient norm, and proved convergence in the non-convex setting
via gradient clipping, assuming bounded noise. In this paper, we further
generalize this non-uniform smoothness condition and develop a simple, yet
powerful analysis technique that bounds the gradients along the trajectory,
thereby leading to stronger results for both convex and non-convex optimization
problems. In particular, we obtain the classical convergence rates for
(stochastic) gradient descent and Nesterov's accelerated gradient method in the
convex and/or non-convex setting under this general smoothness condition. The
new analysis approach does not require gradient clipping and allows
heavy-tailed noise with bounded variance in the stochastic setting.
Description
Convex and Non-Convex Optimization under Generalized Smoothness
%0 Generic
%1 li2023convex
%A Li, Haochuan
%A Qian, Jian
%A Tian, Yi
%A Rakhlin, Alexander
%A Jadbabaie, Ali
%D 2023
%K optimization
%T Convex and Non-Convex Optimization under Generalized Smoothness
%U http://arxiv.org/abs/2306.01264
%X Classical analysis of convex and non-convex optimization methods often
requires the Lipshitzness of the gradient, which limits the analysis to
functions bounded by quadratics. Recent work relaxed this requirement to a
non-uniform smoothness condition with the Hessian norm bounded by an affine
function of the gradient norm, and proved convergence in the non-convex setting
via gradient clipping, assuming bounded noise. In this paper, we further
generalize this non-uniform smoothness condition and develop a simple, yet
powerful analysis technique that bounds the gradients along the trajectory,
thereby leading to stronger results for both convex and non-convex optimization
problems. In particular, we obtain the classical convergence rates for
(stochastic) gradient descent and Nesterov's accelerated gradient method in the
convex and/or non-convex setting under this general smoothness condition. The
new analysis approach does not require gradient clipping and allows
heavy-tailed noise with bounded variance in the stochastic setting.
@misc{li2023convex,
abstract = {Classical analysis of convex and non-convex optimization methods often
requires the Lipshitzness of the gradient, which limits the analysis to
functions bounded by quadratics. Recent work relaxed this requirement to a
non-uniform smoothness condition with the Hessian norm bounded by an affine
function of the gradient norm, and proved convergence in the non-convex setting
via gradient clipping, assuming bounded noise. In this paper, we further
generalize this non-uniform smoothness condition and develop a simple, yet
powerful analysis technique that bounds the gradients along the trajectory,
thereby leading to stronger results for both convex and non-convex optimization
problems. In particular, we obtain the classical convergence rates for
(stochastic) gradient descent and Nesterov's accelerated gradient method in the
convex and/or non-convex setting under this general smoothness condition. The
new analysis approach does not require gradient clipping and allows
heavy-tailed noise with bounded variance in the stochastic setting.},
added-at = {2023-08-21T20:10:22.000+0200},
author = {Li, Haochuan and Qian, Jian and Tian, Yi and Rakhlin, Alexander and Jadbabaie, Ali},
biburl = {https://www.bibsonomy.org/bibtex/22a114bffcc4877d586b251c4535d4de5/vincentqb},
description = {Convex and Non-Convex Optimization under Generalized Smoothness},
interhash = {e7521c27dd217de3d71b0f7f2999f81d},
intrahash = {2a114bffcc4877d586b251c4535d4de5},
keywords = {optimization},
note = {cite arxiv:2306.01264Comment: 39 pages},
timestamp = {2023-08-21T20:10:22.000+0200},
title = {Convex and Non-Convex Optimization under Generalized Smoothness},
url = {http://arxiv.org/abs/2306.01264},
year = 2023
}