Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizes

arXiv:2211.04655 · math.OC, cs.LG · Submitted 2022-11-09 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizes".

Jane: The gist: This work proves an asymptotic convergence result to a Clarke stationary point for perturbed iterate SGD using adaptive step sizes in environments with numerical error,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: I was looking at the title again, "Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizes." It sounds very technical, but it’s really about making SGD work reliably in the messy real world of finite precision computing.

Jane: It sounds like they are taking standard optimization techniques and adding layers of robustness to handle the noise coming from how computers actually calculate things. That makes sense when you consider the environment where these models run, which is rarely perfectly clean.

Lu: The authors are focusing on a very broad class of problems, specifically loss functions that are Lipschitz continuous, which means they have some kind of smoothness property we can measure with this constant L zero(xi) <ref:2211.04655#pg1>. This gives them a solid mathematical foundation to work with.

Meng: So the implication for us is that if you’re running an AI system in a real deployment setting, you don't have to assume perfect math; you can design an optimization algorithm that handles the inevitable numerical errors in the gradient calculation and step updates.

Lalam: They are looking at how these perturbations—the errors in computing the loss function stochastic gradient and even the SGD update itself—affect the convergence path toward a stationary point.

The paper's summary: Tom: The summary highlights that they prove an asymptotic result to a Clarke stationary point, which is a specific type of stationary point for non-smooth functions, as well as non-asymptotic convergence to an approximate stationary point in expectation after K iterations <ref:2211.04655#pg2>.

Jane: So they’re saying that even with these numerical errors, the sequence of iterates will eventually get arbitrarily close to a Clarke stationary point as time goes on, provided you let time go to infinity. But for practical purposes, they also give a concrete bound on how close you can get after a finite number of steps.

Lu: They achieve this by analyzing the convergence of the mapping d alpha k h to the Clarke subdifferential d h <ref:2211.04655#pg3>, which is a key step in understanding how fast your iterates are moving toward a point where the gradient is zero.

Meng: What I find interesting from that is that they are not assuming perfect computation; they’re modeling the error explicitly with things like stochastic rounding for discrete variables, which shows they've thought about the practical implementation side.

Lalam: They show how this framework can be applied to a wide range of neural network architectures because they define a function grad eF that is measurable almost everywhere and can be computed using back propagation <ref:2211.04655#pg1>.

The paper's improvements: Tom: They introduce some specific enhancements to the original setup, like defining the perturbed iterate SGD, PISGD, where you have a decomposition of the total step size eta k into a deterministic part and a stochastic part psi k <ref:2211.04655#pg1>.

Jane: They also address the issue of adaptive step sizes by showing that they can prove non-asymptotic convergence results for all adaptive step sizes that satisfy a certain definition, specifically Definition five point one.five as long as there’s some positive lower bound on the stochastic component L k <ref:2211.04655#pg2>.

Lu: They relaxed one of the earlier assumptions to get these non-asymptotic bounds, introducing Assumption six point one which provides a weak descent condition and an improved second moment bound for the approximated gradient <ref:2211.04655#pg3>. This is what lets them prove those stronger convergence rates.

Meng: For production, that means we can use adaptive step sizes like gradient clipping or normalization, not just whatever simple fixed schedule you started with; as long as they meet that new definition and have some positive stochastic component, the algorithm still has a provable performance bound.

Lalam: They also modeled the numerical error from basic arithmetic operations by showing how Assumption five point seven holds with a specific constant c three derived from Proposition five point eight <ref:2211.04655#pg3>. This makes the numerical error manageable within their analysis framework, which is crucial because it’s what we actually encounter when running code.

Conclusion: Tom: So to wrap up, this paper establishes a solid asymptotic convergence result to a Clarke stationary point and non-asymptotic convergence guarantees for an approximate stationary point in expectation after a finite number of iterations <ref:2211.04655#pg2>.

Jane: The main implication is that we have tools to analyze optimization algorithms in environments with numerical error, giving us both theoretical limits on long-term behavior and practical bounds on how good the solution is for a fixed training time.

Lu: It gives us a path forward by showing how to handle the subdifferential convergence continuously, which is fundamental for minimizing non-smooth functions <ref:2211.04655#pg3>.

Meng: If you're deploying this, you can use these guarantees to set a practical stopping criterion and know what level of accuracy you can expect given your hardware limitations and the noise in your gradient computation.

Lalam: The paper, "Perturbed Iterate SGD for Lipschitz Continuous Loss Functions with Numerical Error and Adaptive Step Sizes," gives us a way to understand convergence under realistic computational constraints, showing that even with noise in the steps themselves, we can still get strong results for our AI models.

Michael R. Metel

math.OC, cs.LG

Submitted: 2022-11-09

Updated: 2026-10-08

Code: https://github.com/akamaster/pytorch_resnet_cifar10

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 82/100

The gist: The gist: This work proves an asymptotic convergence result to a Clarke stationary point for perturbed iterate SGD using adaptive step sizes in environments with numerical error, alongside

Key concepts

Clarke $\epsilon$-subdifferential ($\partial_\epsilon h$): This mathematical tool helps define a generalized gradient for functions that might not be smooth everywhere. It is crucial for analyzing convergence to a 'stationary point' when the loss function is not perfectly differentiable, allowing the algorithm to converge even in complex, non-smooth scenarios.
PISGD with Numerical Error: This is an iterative optimization method where the update step incorporates errors from finite-precision arithmetic during gradient calculations. It models how these computational mistakes affect the learning process by introducing a specific error term ($\hat{e}_k$) into the standard SGD update rule.
Adaptive Step Sizes: Instead of using a fixed learning rate, this method uses step sizes ($\eta_k$) that change based on stochastic components. This adaptation is key to proving non-asymptotic convergence bounds, especially when dealing with the variance introduced by numerical errors and the loss function's properties.
Stochastic Rounding: This technique models how discrete random variables ($b_k$) are used in the gradient calculation. It simulates real-world scenarios where stochastic rounding occurs, allowing researchers to bound the expected behavior of gradients that arise from these discrete approximations.

Terminology

Loss Function — 3× in this paper · explained in 2 episodes

Summary

The gist: This work proves an asymptotic convergence result to a Clarke stationary point for perturbed iterate SGD using adaptive step sizes in environments with numerical error, alongside non-asymptotic convergence guarantees to an approximate stationary point in expectation

Lipschitz Continuous Loss Functions

The analysis is based on the assumption that the loss function is Lipschitz continuous, specifically that for almost all random vector ξ ∈ R n, F(w, ξ) − F(w′, ξ) ≤ L0(ξ)∥w − w′∥2 for all w, w′ ∈ R d The convergence analysis utilizes the Clarke ϵ-subdifferential ∂pϵ h: R d → R d, which is defined as co(∂h(x): x ∈ Bpϵ(w)) Proposition 2.2 proves that the sequence of mappings Σ∂pαk h converges continuously to ∂h The analysis also defines the function ∇eF: R d × R n → R d to be a Borel measurable function equal to ∇F almost everywhere it exists, which can be computed using back propagation for a wide range of neural network architectures

PISGD with Numerical Error and Adaptive Step Sizes

The proposed algorithm is the Perturbed Iterate SGD (PISGD) with adaptive step sizes defined by wk+1 = wk − ηˆkψk M X M i=1 ∇eF(wk + uˆk, ξ k,i) The total step size ηk is decomposed into a deterministic component ˆηk and a stochastic component ψk The model of PISGD with numerical error is given by wk+1 = wk − ηˆkψk M X M i=1 ∇bF(wk + uˆk, ξ k,i, b k,i) + eˆ k The algorithm step is broken down into two half steps where at step “k + 1/2”, all elements of S k:= Σwk, ηˆk, ψk, M, Σ∇bF(wk + uˆk, ξ k,i, b k,i) have been computed

Modelling Details of PISGD with Numerical Error and Adaptive Step Sizes

The sampling of uˆ k is replaced by a sample uˆ k ∈ R d from a probability distribution Pbk, where the sequence of probability distributions ΣPbk and parameters αk are assumed to be deterministic The inclusion of the random vector b ∈ R s in ∇bF models the use of stochastic rounding, where b k is a discrete uniformly distributed random variable over a finite set V k Assumption 5.1 provides bounds on the expected gradient, stating that for all k ≥ K, almost surely E[∇bF(wk + uˆ k, ξ, b k) Fk-1], ∇fαk(wk)] ≥ c1∥∇fαk(wk)∥22 and E[∥∇bF(wk + uˆ k, ξ, b k)∥ 22 Fk-1] ≤ c2Q

Convergence Analysis of PISGD with Numerical Error

The asymptotic convergence result to a Clarke stationary point is proven in Theorem 5.10, which states that if Assumptions 5.1 and 5.7 hold, PISGD (6) almost surely generates a subsequence of indices Σki such that lim i→∞∥∇fαki(wki)∥2 = 0 The proof relies on the Robbins-Siegmund inequality and shows that the requirement for convergence is satisfied for a specific choice of K = O α−2ν−4 iterations

Convergence Analysis with Unrestricted Adaptive Step Size Range

The paper demonstrates that non-asymptotic convergence results can be proven for all adaptive step sizes satisfying Definition 5.1.5 with ΨL k > 0 almost surely for all k ∈ N This is achieved by relaxing Assumption 5.1 to Assumption 6.1, which introduces a weak descent condition and an improved second moment bound for the approximated gradient Theorem 6.3 provides a convergence bound E[dist(0, ∂∞ α f(wˆ))2] ≤ κ1fα(w1)√K + κ2Q√K + κ3√dL0α√K((ΨU k) 2c2Q + c3), where K = O α−2ν−4 iterations

Numerical Demonstration of an Adaptive Step Size & Empirical Verification of Assumption 5.1

Experiments on ResNet 20 and ResNet 32 trained on CIFAR-10 and CIFAR-100 using QPyTorch show that PNSGD is equal to or greater than SGD and PISGD in terms of the mean, minimum, and maximum accuracy The empirical verification of Assumption 5.1 is done by plotting ˆc k 1 for the first 100 training steps of the R20C10 experiments to observe how well Assumption 5.1 holds

Conclusion

The paper establishes a new asymptotic convergence result to a Clarke stationary point and non-asymptotic convergence guarantees for approximate stationary points in expectation for stochastic Lipschitz continuous loss functions with error in computing stochastic gradients and the SGD step itself It also demonstrates that variance reduction through an increased mini-batch size is important, allowing non-asymptotic convergence guarantees for an unrestricted class of adaptive step sizes

How it works

The PISGD algorithm uses a perturbed mini-batch SGD form wk+1 = wk − ηˆkψk M X M i=1 ∇eF(wk + uˆk, ξ k,i) The total step size ηk is defined as ηhat k ψ k ≥ 0 where ˆη k is deterministic and ψ k is stochastic The model of PISGD with numerical error incorporates the approximation of the stochastic gradient ∇bF, where b ∈ R s is a discrete random vector used to perform stochastic rounding

Key Components and Assumptions

The analysis relies on several key assumptions, including Assumption 2.1 that the loss function is non-negative f: R d → R≥0 Proposition 3.1 establishes bounds on the rounding error E[δ] = 0 and Var(δ) ≤ β−2t4 Assumption 5.7 requires that almost surely E[eˆ k Fk-1, Gk] = 0 and E[∥eˆ k∥ squared Fk-1] ≤ c3ηhat 2 k

Adaptive Step Size Classes

The paper defines an admissible sequence of step sizes using Definition 5.9, which requires that for all k ≥ K, almost surely (1) ∆k ≤ c4 ηhat k αk and (2) ∆k ≤ 2c1ΨU k − ∆c1 Proposition 5.6 shows that the gradient clipping algorithm fits within Definition 5.9

Numerical Error Modeling

The error vector eˆ k models the error from computing the addition, subtraction, multiplication, and division with finite precision in (6) Assumption 5.7 holds with c3 = 1/4((M squared + 1)c2Q + M), which is derived using Proposition 5.8

Convergence Results

The asymptotic convergence result to a Clarke stationary point is proven in Theorem 5.10, and the non-asymptotic convergence to an approximate stationary point in expectation is shown in Theorem 6.

Improvements for AI systems

Bold header: Adaptive Step Size Convergence Guarantees

Adaptive step sizes, including gradient normalization and clipping (e.g., gradient normalization or gradient clipping), can be used to stabilize PISGD, allowing for "non-asymptotic convergence results for all adaptive step sizes satisfying Definition 5.1.5 with ΨLk > 0 almost surely. This enables training over arbitrarily many iterations and to any desired accuracy" in fixed-point environments.

Bold header: Numerical Error Robustness

The algorithm can be implemented to handle numerical error by modeling the error from basic arithmetic operations as a random vector, where the analysis shows that Assumption 5.7 holds with c3 = 1/4((M squared + 1)c2Q + M). This ensures that the expected error of the step is bounded, leading to convergence guarantees even when using finite-precision arithmetic.

Bold header: Convergence to Approximate Stationary Points

The system provides a non-asymptotic convergence to an approximate stationary point in expectation after a predetermined number of iterations, proven by Theorem 5.14. This means the iterates converge such that dist(0, ∂∞αf(ŵ)) ≤ κ1fα(w1)√K + κ2Q√K + κ3√dL0α√K((ΨU)2c2Q + c3), which can be controlled to ensure E[dist(0, ∂∞αf(ŵ))] ≤ ν for any desired accuracy.

Bold header: Model-Specific Optimization

The system can utilize specific adaptive step size strategies like Restricted Gradient Normalization (RGN) for fixed-point environments, where the step size is constructed using mk−1ave g k−1nrm to dynamically choose the range of the stochastic component, minimizing clipping probability.