Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization

2023/03/06 by Ziyi Chen, Yi Zhou, Chen, Ziyi +5 · 11 citations
Computer Science · Engineering · #FOS: Mathematics #Machine Learning and ELM #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2303.02854

openalex publication_date 2023/03/06 · openalex created_date 2023/03/09 · openalex updated_date 2026/07/28

Abstract

Various optimal gradient-based algorithms have been developed for smooth nonconvex optimization. However, many nonconvex machine learning problems do not belong to the class of smooth functions and therefore the existing algorithms are sub-optimal. Instead, these problems have been shown to satisfy certain generalized-smooth conditions, which have not been well understood in the existing literature. In this paper, we propose a notion of α-symmetric generalized-smoothness that extends the existing notions and covers many important functions such as high-order polynomials and exponential functions. We study the fundamental properties and establish descent lemmas for the functions in this class. Then, to solve such a large class of nonconvex problems, we design a special deterministic normalized gradient descent algorithm that achieves the optimal iteration complexity O(ε^-2), and also prove that the popular SPIDER variance reduction algorithm achieves the optimal sample complexity O(ε^-3) in the stochastic setting. Our results show that solving generalized-smooth nonconvex problems is as efficient as solving smooth nonconvex problems.

Cited by

• Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
• Normalized First-Order Methods for Convex (L0, L1)-Smooth Optimization with Inexact Gradients
• Frank-Wolfe Algorithms for (L0, L1)-smooth functions
• Extragradient Method for (L₀, L₁)-Lipschitz Root-finding Problems
• Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis
• Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives
• CaCuTe: Casual Cubic-Model Technique for Faster Optimization
• Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
• Decentralized Stochastic Nonconvex Optimization under the (L₀,L₁)-Smoothness
• Revisiting Randomized Smoothing: Nonsmooth Nonconvex Optimization Beyond Global Lipschitz Continuity
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L₀, L₁)-Smoothness

Related

• Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimization
• Trust Region Methods For Nonconvex Stochastic Optimization Beyond Lipschitz Smoothness
• Oracle Complexity in Nonsmooth Nonconvex Optimization
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness
• Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms