Large deviations rates for stochastic gradient descent with strongly convex functions

2022-11-02 · Dragana Bajovic, Dusan Jakovetic, Soummya Kar

Recent works have shown that high probability metrics with stochastic gradient descent (SGD) exhibit informativeness and in some cases advantage over the commonly adopted mean-square error-based ones. In this work we provide a formal framework for the study of general high probability bounds with SGD, based on the theory of large deviations. The framework allows for a generic (not-necessarily bounded) gradient noise satisfying mild technical assumptions, allowing for the dependence of the noise distribution on the current iterate. Under the preceding assumptions, we find an upper large deviations bound for SGD with strongly convex functions. The corresponding rate function captures analytical dependence on the noise distribution and other problem parameters. This is in contrast with conventional mean-square error analysis that captures only the noise dependence through the variance and does not capture the effect of higher order moments nor interplay between the noise geometry and the shape of the cost function. We also derive exact large deviation rates for the case when the objective function is quadratic and show that the obtained function matches the one from the general upper bound hence showing the tightness of the general upper bound. Numerical examples illustrate and corroborate theoretical findings.

📄 PDF Abstract BibTeX arXiv:2211.00969

Code (0)

등록된 구현이 없습니다.

Tasks

Informativeness

Methods 이 논문이 사용한 방법론

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

Large Spikes in Stochastic Gradient Descent: A Large-Deviations View

2026-03-10 · Benjamin Gess, Daniel Heydecker arxiv

Large loss spikes in stochastic gradient descent are studied through a rigorous large-deviations analysis for a shallow, fully connected network in the NTK scaling. In contrast to full-batch gradient descent, the catapul…

A Large Deviations Perspective on Policy Gradient Algorithms

2023-11-13 · Wouter Jongeneel, Daniel Kuhn, Mengmeng Li

Motivated by policy gradient methods in the context of reinforcement learning, we identify a large deviation rate function for the iterates generated by stochastic gradient descent for possibly non-convex objectives sati…

Policy Gradient Methods reinforcement-learning Reinforcement Learning

The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations

2025-03-20 · Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

In this paper, we examine the time it takes for stochastic gradient descent (SGD) to reach the global minimum of a general, non-convex loss function. We approach this question through the lens of randomly perturbed dynam…

What is the long-run distribution of stochastic gradient descent? A large deviations analysis

2024-06-13 · Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

In this paper, we examine the long-run distribution of stochastic gradient descent (SGD) in general, non-convex problems. Specifically, we seek to understand which regions of the problem's state space are more likely to …

Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descent

2024-07-02 · Adrien Schertzer, Loucas Pillaud-Vivien

We study the dynamics of a continuous-time model of the Stochastic Gradient Descent (SGD) for the least-square problem. Indeed, pursuing the work of Li et al. (2019), we analyze Stochastic Differential Equations (SDEs) t…