# Online Learning Under A Separable Stochastic Approximation Framework

arXiv: https://arxiv.org/abs/2305.07484 · HTML: https://mlsanity.com/paper/2305.07484/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 61 references that are in the map.
- First posted on arXiv 12 May 2023.

## Builds on (most cited first, 22 of 22)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [The loss surface of deep and wide neural networks](https://mlsanity.com/paper/1704.08045/) (2017)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [Block stochastic gradient iteration for convex and nonconvex optimization](https://mlsanity.com/paper/1408.2597/) (2014)
- [Global Convergence of Online Limited Memory BFGS](https://mlsanity.com/paper/1409.2045/) (2014)
- [Train Like a (Var)Pro: Efficient Training of Neural Networks with Variable Projection](https://mlsanity.com/paper/2007.13171/) (2020)
- [Online Nonnegative Matrix Factorization with Outliers](https://mlsanity.com/paper/1604.02634/) (2016)
- [Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization](https://mlsanity.com/paper/1911.07363/) (2019)
- [slimTrain -- A Stochastic Approximation Method for Training Separable Deep Neural Networks](https://mlsanity.com/paper/2109.14002/) (2021)
- [A Provable Splitting Approach for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2301.10499/) (2023)
- [A block coordinate descent optimizer for classification problems exploiting convexity](https://mlsanity.com/paper/2006.10123/) (2020)
- [A generalization of variable elimination for separable inverse problems beyond least squares](https://mlsanity.com/paper/1302.0441/) (2013)
- [Efficient quadratic penalization through the partial minimization technique](https://mlsanity.com/paper/1606.02395/) (2016)
- [Embedded Point Iteration Based Recursive Algorithm for Online Identification of Nonlinear Regression Models](https://mlsanity.com/paper/2207.09958/) (2022)

## Abstract (arXiv)

We propose an online learning algorithm for a class of machine learning models under a separable stochastic approximation framework. The essence of our idea lies in the observation that certain parameters in the models are easier to optimize than others. In this paper, we focus on models where some parameters have a linear nature, which is common in machine learning. In one routine of the proposed algorithm, the linear parameters are updated by the recursive least squares (RLS) algorithm, which is equivalent to a stochastic Newton method; then, based on the updated linear parameters, the nonlinear parameters are updated by the stochastic gradient method (SGD). The proposed algorithm can be understood as a stochastic approximation version of block coordinate gradient descent approach in which one part of the parameters is updated by a second-order SGD method while the other part is updated by a first-order SGD. Global convergence of the proposed online algorithm for non-convex cases is established in terms of the expected violation of a first-order optimality condition. Numerical experiments show that the proposed method accelerates convergence significantly and produces more robust training and test performance when compared to other popular learning algorithms. Moreover, our algorithm is less sensitive to the learning rate and outperforms the recently proposed slimTrain algorithm (Newman et al., 2022). The code has been uploaded to GitHub for validation.