Optimal non-euclidean learning via optimization and stability

par Prof. Patrick Rebeschini

mercredi 22 janv. 2025, 10:00 → 11:00 Europe/Paris

Ridge regression and gradient descent are two foundational approaches in Euclidean learning, representing statistical regularization and algorithmic regularization, respectively. Extending this framework to non-Euclidean geometries has been extensively explored in statistics through methods such as M-estimation, with notable examples like the Lasso. However, the development of optimization solvers that achieve optimal statistical rates in non-Euclidean contexts remains less advanced.

In this talk, we present recent progress in designing generalized gradient descent methods that attain optimal minimax statistical rates in non-Euclidean convex settings. This includes linear regression with the square loss when the ground-truth regressor lies within a convex body, as well as general learning with loss functions that are convex and smooth with respect to ℓp norms. In the latter case, we resolve an open question posed by Attia and Koren in 2022 regarding the development of a black-box scheme to map optimization solvers into learning algorithms that achieve optimal uniform stability.

(Based on joint work with Tobias Wegel and Gil Kur, as well as with Simon Vary and David Martínez-Rubio)