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

DOI10.1137/21M145896XzbMATH Open1519.90136arXiv2204.02593MaRDI QIDQ6155875FDOQ6155875

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)

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.

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

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

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)

Cites Work

• On the use of stochastic Hessian information in optimization methods for machine learning
• Robust Stochastic Approximation Approach to Stochastic Programming
• On stochastic gradient and subgradient methods with adaptive steplength sequences
• 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
• Lectures on stochastic programming. Modeling and theory.
• Stable laws and domains of attraction in free probability theory
• Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication
• Large-scale machine learning with stochastic gradient descent
• Adaptive estimation algorithms (convergence, optimality, stability)
• Algorithms of robust stochastic optimization based on mirror descent method
• Optimization methods for large-scale machine learning
• Robust Consensus in the Presence of Impulsive Channel Noise
• Perturbed iterate analysis for asynchronous stochastic optimization
• On the adaptivity of stochastic gradient-based optimization
• Title not available (Why is that?)
• 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)