mlsanityData to 14 Oct 2026

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

arXiv 2505.02614 ↗First posted 5 May 2025math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

20 of 32 references.

References · 20

  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  2. 2017Implicit Regularization in Matrix Factorizationcited by 322
  3. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  4. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  5. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  6. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  7. 2019Implicit Regularization for Optimal Sparse Recoverycited by 80
  8. 2019Revisiting the Polyak step sizecited by 55
  9. 2019Exponentiated Gradient Meets Gradient Descentcited by 32
  10. 2018An explicit analysis of the entropic penalty in linear programmingcited by 24
  11. 2021More is Less: Inducing Sparsity via Overparameterizationcited by 24
  12. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
8 more
  1. 2023Generalized Polyak Step Size for First Order Optimization with Momentumcited by 15
  2. 2023Convergent Bregman Plug-and-Play Image Restoration for Poisson Inverse Problemscited by 14
  3. 2021Implicit Regularization in Matrix Sensing via Mirror Descentcited by 11
  4. 2022Smooth over-parameterized solvers for non-smooth structured optimizationcited by 11
  5. 2021From the simplex to the sphere: Faster constrained optimization using the Hadamard parametrizationcited by 10
  6. 2020A Continuous-Time Mirror Descent Approach to Sparse Phase Retrievalcited by 9
  7. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientscited by 5
  8. 2022Get rid of your constraints and reparametrize: A study in NNLS and implicit biascited by 3

Built on by

Not cited yet.