# The Stochastic Proximal Distance Algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 41 references that are in the map.
- First posted on arXiv 21 Oct 2022.

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

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [The Proximal Robbins-Monro Method](https://mlsanity.com/paper/1510.00967/) (2015)
- [Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints](https://mlsanity.com/paper/1407.0088/) (2014)
- [Ergodic convergence of a stochastic proximal point algorithm](https://mlsanity.com/paper/1504.05400/) (2015)
- [Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting](https://mlsanity.com/paper/1504.04407/) (2015)
- [Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure](https://mlsanity.com/paper/1610.00970/) (2016)
- [A Proximal Distance Algorithm for Likelihood-Based Sparse Covariance Estimation](https://mlsanity.com/paper/2109.04497/) (2021)
- [Generalized Linear Model Regression under Distance-to-set Penalties](https://mlsanity.com/paper/1711.01341/) (2017)
- [Statistical inference with implicit SGD: proximal Robbins-Monro vs. Polyak-Ruppert](https://mlsanity.com/paper/2206.12663/) (2022)
- [The proximal distance algorithm](https://mlsanity.com/paper/1507.07598/) (2015)
- [Extensions to the Proximal Distance Method of Constrained Optimization](https://mlsanity.com/paper/2009.00801/) (2020)

## Built on by (most cited first, 1 of 1)

- [Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts](https://mlsanity.com/paper/2601.19811/) (2026)

## Abstract (arXiv)

Stochastic versions of proximal methods have gained much attention in statistics and machine learning. These algorithms tend to admit simple, scalable forms, and enjoy numerical stability via implicit updates. In this work, we propose and analyze a stochastic version of the recently proposed proximal distance algorithm, a class of iterative optimization methods that recover a desired constrained estimation problem as a penalty parameter ρ rightarrow ∞. By uncovering connections to related stochastic proximal methods and interpreting the penalty parameter as the learning rate, we justify heuristics used in practical manifestations of the proximal distance method, establishing their convergence guarantees for the first time. Moreover, we extend recent theoretical devices to establish finite error bounds and a complete characterization of convergence rates regimes. We validate our analysis via a thorough empirical study, also showing that unsurprisingly, the proposed method outpaces batch versions on popular learning tasks.