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:
- 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.
- 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.
Key Insights and Theoretical Links
- 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.
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.
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