# Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 32 references that are in the map.
- First posted on arXiv 5 May 2025.

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

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Exponentiated Gradient Meets Gradient Descent](https://mlsanity.com/paper/1902.01903/) (2019)
- [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018)
- [More is Less: Inducing Sparsity via Overparameterization](https://mlsanity.com/paper/2112.11027/) (2021)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Generalized Polyak Step Size for First Order Optimization with Momentum](https://mlsanity.com/paper/2305.12939/) (2023)
- [Convergent Bregman Plug-and-Play Image Restoration for Poisson Inverse Problems](https://mlsanity.com/paper/2306.03466/) (2023)
- [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [From the simplex to the sphere: Faster constrained optimization using the Hadamard parametrization](https://mlsanity.com/paper/2112.05273/) (2021)
- [A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval](https://mlsanity.com/paper/2010.10168/) (2020)
- [Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients](https://mlsanity.com/paper/2403.19448/) (2024)
- [Get rid of your constraints and reparametrize: A study in NNLS and implicit bias](https://mlsanity.com/paper/2207.08437/) (2022)

## Abstract (arXiv)

This paper focuses on applying entropic mirror descent to solve linear systems, where the main challenge for the convergence analysis stems from the unboundedness of the domain. To overcome this without imposing restrictive assumptions, we introduce a variant of Polyak-type stepsizes. Along the way, we strengthen the bound for ℓ1-norm implicit bias, obtain sublinear and linear convergence results, and generalize the convergence result to arbitrary convex L-smooth functions. We also propose an alternative method that avoids exponentiation, resembling the original Hadamard descent, but with provable convergence.