Nonlinear Gradient Mappings and Stochastic Optimization: A General Framework with Applications to Heavy-Tail Noise

DOI10.1137/21M145896XMaRDI QIDQ6155875zbMATH OpenFDO

Authors Dušan Jakovetić, Dragana Bajović, Anit Kumar Sahu, Soummya Kar

Publication date 7 June 2023

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.02593

zbMATH Keywords

asymptotic normalitystochastic approximationstochastic optimizationconvergence ratenonlinear mappingstochastic gradient descentmean square analysisheavy-tail noise

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25) Stochastic approximation (62L20) Stochastic programming (90C15)

Abstract: We introduce a general framework for nonlinear stochastic gradient descent (SGD) for the scenarios when gradient noise exhibits heavy tails. The proposed framework subsumes several popular nonlinearity choices, like clipped, normalized, signed or quantized gradient, but we also consider novel nonlinearity choices. We establish for the considered class of methods strong convergence guarantees assuming a strongly convex cost function with Lipschitz continuous gradients under very general assumptions on the gradient noise. Most notably, we show that, for a nonlinearity with bounded outputs and for the gradient noise that may not have finite moments of order greater than one, the nonlinear SGD's mean squared error (MSE), or equivalently, the expected cost function's optimality gap, converges to zero at rate~$O(1/t^{z}eta)$, $zetain(0,1)$. In contrast, for the same noise setting, the linear SGD generates a sequence with unbounded variances. Furthermore, for the nonlinearities that can be decoupled component wise, like, e.g., sign gradient or component-wise clipping, we show that the nonlinear SGD asymptotically (locally) achieves a $O(1/t)$ rate in the weak convergence sense and explicitly quantify the corresponding asymptotic variance. Experiments show that, while our framework is more general than existing studies of SGD under heavy-tail noise, several easy-to-implement nonlinearities from our framework are competitive with state of the art alternatives on real data sets with heavy tail noises.

Recommendations

• Stochastic gradient descent with noise of machine learning type. I: Discrete time analysis
• Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance
• Stochastic gradient Hamiltonian Monte Carlo for non-convex learning
• Convergence rates for the stochastic gradient descent method for non-convex objective functions
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming

Cites work

• scientific article; zbMATH DE number 7370566 (Why is no real title available?)
• Adaptive estimation algorithms (convergence, optimality, stability)
• Algorithms of robust stochastic optimization based on mirror descent method
• Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication
• Large-scale machine learning with stochastic gradient descent
• Lectures on stochastic programming. Modeling and theory.
• On stochastic gradient and subgradient methods with adaptive steplength sequences
• On the adaptivity of stochastic gradient-based optimization
• On the use of stochastic Hessian information in optimization methods for machine learning
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
• Optimization methods for large-scale machine learning
• Perturbed iterate analysis for asynchronous stochastic optimization
• Robust Consensus in the Presence of Impulsive Channel Noise
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stable laws and domains of attraction in free probability theory
• Stochastic distributed learning with gradient quantization and double-variance reduction

Cited in

(6)

• Nonlinear Consensus+Innovations under Correlated Heavy-Tailed Noises: Mean Square Convergence Rate and Asymptotics
• Algorithms with gradient clipping for stochastic optimization with heavy-tailed noise
• Cauchy noise loss for stochastic optimization of random matrix models via free deterministic equivalents
• Stochastic generalized gradient methods for training nonconvex nonsmooth neural networks
• High-probability complexity bounds for non-smooth stochastic convex optimization with heavy-tailed noise
• Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact

This page was built for publication: Nonlinear Gradient Mappings and Stochastic Optimization: A General Framework with Applications to Heavy-Tail Noise

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6155875)