12 papers
Last-Iterate Convergence of Optimistic Multiplicative Weight Update
Francesco Orabona
Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where O…
A Robust Rate for Unprojected TD Learning with Linear Function Approximation
Wei-Cheng Lee, Francesco Orabona
We investigate the finite-time convergence properties of Temporal Difference (TD) learning with linear function approximation, a cornerstone of reinforcement learning. We are inter…
A Note on How to Remove the Term from the Squint Bound
Francesco Orabona
In Orabona and Pál [2016], we introduced the shifted KT potentials, to remove the factor in the parameter-free learning with expert bound. In this short technical note…
Online Conformal Prediction via Universal Portfolio Algorithms
Tuo Liu, Edgar Dobriban, Francesco Orabona
Online conformal prediction (OCP) seeks prediction intervals that achieve long-run coverage for arbitrary (possibly adversarial) data streams, while remaining as informative…
New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
Francesco Orabona, Ryan D'Orazio
The Polyak stepsize has been proven to be a fundamental stepsize in convex optimization, giving near optimal gradient descent rates across a wide range of assumptions. The universa…
A Best-of-Both-Worlds Proof for Tsallis-INF without Fenchel Conjugates
Wei-Cheng Lee, Francesco Orabona
In this short note, we present a simple derivation of the best-of-both-world guarantee for the Tsallis-INF multi-armed bandit algorithm from J. Zimmert and Y. Seldin. Tsallis-INF:…