Stochastic gradient algorithms from ODE splitting perspective

Daniil Merkulov, Ivan V. OseledetsarXiv 2020 · arXiv

Standard Stochastic Gradient Descent (SGD) is typically analyzed as a noisy version of continuous-time gradient descent. This paper offers a fresh perspective by reframing SGD as a deterministic "splitting scheme" for Ordinary Differential Equations (ODEs). By solving local mini-batch ODEs more precisely—rather than just taking a crude Euler step like standard SGD—the authors develop a new optimization method that is highly robust to large learning rates.

Reframing SGD as a Splitting Scheme

In continuous time, standard gradient descent can be modeled as a "gradient flow" ODE, where parameters flow smoothly downhill along the gradient of the loss function. To analyze SGD in this framework, researchers usually add artificial noise to the ODE to simulate mini-batch randomness. However, the exact distribution of this noise is often unknown and dataset-dependent.

The authors propose a deterministic alternative: viewing SGD as a first-order splitting scheme. In numerical mathematics, splitting schemes solve complex ODEs by sequentially solving simpler constituent ODEs (in this case, mini-batch gradient flows). Vanilla SGD approximates these local solutions with a basic "Euler step," which leads to instability and divergence when the learning rate (step size) is too large.

Methods: Accurate Local Integration

The proposed approach upgrades the standard SGD update rule by treating the mini-batch gradient flow as a local ODE problem to be solved accurately:

  1. Splitting Optimization: For each mini-batch, the algorithm integrates the local ODE over a time step $h$ (the learning rate). While linear least squares problems have exact analytical solutions, more complex models like logistic and softmax regression utilize numerical ODE solvers, such as the explicit Runge-Kutta Dormand-Prince method.
  2. Efficiency via QR Decomposition: Solving high-dimensional ODEs at every step is computationally expensive. The authors exploit the fact that mini-batch sizes $b$ are typically much smaller than the parameter count $p$. By performing a QR decomposition on the batch data matrix, they project the local ODE down to $b$ dimensions, making numerical integration highly efficient.
  • Theoretical Unification: The authors prove that their splitting scheme, when applied with a batch size of 1 and an infinite learning rate, perfectly recovers the Kaczmarz method for solving linear systems. This provides a rigorous new link between SGD and classical iterative methods.
  • Error Bounds: New, tighter upper bounds on global splitting error are derived, specifically tailored for machine learning contexts where the ODE involves sums of rank-deficient, negative semidefinite matrices.

Experimental Results

The authors evaluated the method on synthetic Random Linear Least Squares, real-world Tomography data (AIRTools II), and classification tasks using MNIST and Fashion MNIST.

Convergence time across different datasets and learning rates. The Splitting method remains stable at high learning rates where SGD diverges.

The primary advantage of the Splitting approach is its extreme robustness to learning rates. Across all tested problems, standard SGD diverged once the learning rate crossed a specific threshold. In contrast, the Splitting method remained stable and converged even at learning rates orders of magnitude larger than those that broke SGD.

Iterations to converge for Softmax regression. The Splitting method achieves convergence in significantly fewer iterations at high learning rates.

Because the Splitting method can safely utilize these much larger step sizes, it requires significantly fewer iterations to reach target test errors compared to vanilla SGD. For example, on the Fashion MNIST dataset, the iteration count required for convergence drops dramatically as the learning rate increases, a regime where SGD cannot operate.

Limitations and Future Directions

While the QR decomposition trick mitigates dimensionality issues, running a Runge-Kutta solver per iteration remains more computationally intensive than a simple SGD update. Additionally, the current implementation assumes a static dataset where batches can be pre-processed for QR decomposition. While this work proves the concept of step-size robustness for linear and simple non-linear models, extending ODE splitting to deep, non-convex neural networks remains an open research challenge.

Summary updated

Abstract

We present a different view on stochastic optimization, which goes back to the splitting schemes for approximate solutions of ODE. In this work, we provide a connection between stochastic gradient descent approach and first-order splitting scheme for ODE. We consider the special case of splitting, which is inspired by machine learning applications and derive a new upper bound on the global splitting error for it. We present, that the Kaczmarz method is the limit case of the splitting scheme for the unit batch SGD for linear least squares problem. We support our findings with systematic empirical studies, which demonstrates, that a more accurate solution of local problems leads to the stepsize robustness and provides better convergence in time and iterations on the softmax regression problem.
BibTeX
@misc{merkulov2020stochastic,
  author = {Daniil Merkulov and Ivan V. Oseledets},
  title = {{Stochastic gradient algorithms from ODE splitting perspective}},
  year = {2020},
  eprint = {2004.08981},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.08981},
}
Figure