620. Entropic Mirror Descent for Linear Systems: Polyakâs Stepsize and Implicit Bias
Invited abstract in session MC-5: Optimization and machine learning II, stream Optimization for machine learning.
Monday, 14:00-16:00Room: B100/4013
Authors (first author is the speaker)
| 1. | Alexander Posch
|
| Mathematics, University of Vienna | |
| 2. | Yura Malitsky
|
| Faculty of Mathematics, University of Vienna |
Abstract
In this talk, we explore the use of entropic mirror descent for solving linear systems on the nonnegative orthant. We discuss the motivation behind this approach, such as its implicit bias when initialized close to the origin, and analyze its convergence properties. Although the method has a simple structure, its convergence behavior is more subtle, with a particular challenge being the unboundedness of the domain. We demonstrate how a Polyak-type stepsize can help overcome these challenges and lead to explicit rates. In particular, we establish sublinear convergence in the function values and give conditions under which the convergence is linear. We show how the convergence results generalize to the minimization of arbitrary convex L-smooth functions on the nonnegative orthant. Furthermore, we propose an alternative method that avoids the exponentiation in the mirror descent update, resembling gradient descent with Hadamard parametrization, but with provable convergence guarantees. Finally, we extend the convergence results to linear systems over the entire space.
Keywords
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers