7 papers · 1 filter
Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification
Alex Buna, Shirley Xiaoqi Liu, Patrick Rebeschini
In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic lo…
Self-Concordant Perturbations for Linear Bandits
Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1
We consider the adversarial linear bandits setting and present a unified algorithmic framework that bridges Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FT…
Generalization in Nonlinear Least Squares via Learned Feature Geometry
Ayub Kharel, Ilja Kuzborskij, Patrick Rebeschini +1
We study the generalization of ridge-regularized nonlinear least-squares models via on-average algorithmic stability, deriving error bounds for local minimizers in terms of a data-…
Learning mirror maps in policy mirror descent
Carlo Alfano, Sebastian Towers, Silvia Sapora +2
Policy Mirror Descent (PMD) is a popular framework in reinforcement learning, serving as a unifying perspective that encompasses numerous algorithms. These algorithms are derived t…
Non-stationary Bandit Convex Optimization: A Comprehensive Study
Xiaoqi Liu, Dorian Baudry, Julian Zimmert +2
Bandit Convex Optimization is a fundamental class of sequential decision-making problems, where the learner selects actions from a continuous domain and observes a loss (but not it…
Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis
Tyler Farghly, Patrick Rebeschini, George Deligiannidis +1
The success of denoising diffusion models raises important questions regarding their generalisation behaviour, particularly in high-dimensional settings. Notably, it has been shown…