# Explicit Regularization of Stochastic Gradient Methods through Duality

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2020.

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

- [Explicit Regularization in Overparametrized Models via Noise Injection](https://mlsanity.com/paper/2206.04613/) (2022)
- [Duality for Neural Networks through Reproducing Kernel Banach Spaces](https://mlsanity.com/paper/2211.05020/) (2022)
- [Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias?](https://mlsanity.com/paper/2504.12883/) (2025)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [Regularized Gauss-Newton for Optimizing Overparameterized Neural Networks](https://mlsanity.com/paper/2404.14875/) (2024)
- [Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization](https://mlsanity.com/paper/2505.11434/) (2025)

## Abstract (arXiv)

We consider stochastic gradient methods under the interpolation regime where a perfect fit can be obtained (minimum loss at each observation). While previous work highlighted the implicit regularization of such algorithms, we consider an explicit regularization framework as a minimum Bregman divergence convex feasibility problem. Using convex duality, we propose randomized Dykstra-style algorithms based on randomized dual coordinate ascent. For non-accelerated coordinate descent, we obtain an algorithm which bears strong similarities with (non-averaged) stochastic mirror descent on specific functions, as it is is equivalent for quadratic objectives, and equivalent in the early iterations for more general objectives. It comes with the benefit of an explicit convergence theorem to a minimum norm solution. For accelerated coordinate descent, we obtain a new algorithm that has better convergence properties than existing stochastic gradient methods in the interpolating regime. This leads to accelerated versions of the perceptron for generic ℓp-norm regularizers, which we illustrate in experiments.