Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918374565478400 |
|---|---|
| author | Malitsky, Yura Posch, Alexander |
| author_facet | Malitsky, Yura Posch, Alexander |
| contents | 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 $\ell_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02614 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias Malitsky, Yura Posch, Alexander Optimization and Control Machine Learning 90C25 (Primary) 65K05, 47J25, 90C30 (Secondary) 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 $\ell_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. |
| title | Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias |
| topic | Optimization and Control Machine Learning 90C25 (Primary) 65K05, 47J25, 90C30 (Secondary) |
| url | https://arxiv.org/abs/2505.02614 |