13 papers
Monitoring for Shifts at Unknown Times: Parameter-Free Conditional Conformal Martingales
Tuo Liu, Drew Prinster, Francesco Orabona
Conditional conformal test martingales provide sequential tests for detecting distribution shifts, using a fixed reference dataset to avoid contamination from test-time samples. Pr…
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 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…
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:…
Beyond the Ideal: Analyzing the Inexact Muon Update
Egor Shulgin, Sultan AlRashed, Francesco Orabona +1
The Muon optimizer has rapidly emerged as a powerful, geometry-aware alternative to AdamW, demonstrating strong performance in large-scale training of neural networks. However, a c…
Position: Machine Learning Conferences Should Establish a "Refutations and Critiques" Track
Rylan Schaeffer, Joshua Kazdan, Yegor Denisov-Blanch +11
Science progresses by iteratively advancing and correcting humanity's understanding of the world. In machine learning (ML) research, rapid advancements have led to an explosion of…
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…
Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization
Tuo Liu, El Mehdi Saad, Wojciech Kotłowski +1
Dual averaging and gradient descent with their stochastic variants stand as the two canonical recipe books for first-order optimization: Every modern variant can be viewed as a des…
STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals
Václav Voráček, Francesco Orabona
The construction of confidence intervals for the mean of a bounded random variable is a classical problem in statistics with numerous applications in machine learning and virtually…
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…
New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
El Mehdi Saad, Wei-Cheng Lee, Francesco Orabona
We study fundamental limits of first-order stochastic optimization in a range of nonconvex settings, including L-smooth functions satisfying Quasar-Convexity (QC), Quadratic Growth…
ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning
Artavazd Maranjyan, El Mehdi Saad, Peter Richtárik +1
Asynchronous methods are fundamental for parallelizing computations in distributed machine learning. They aim to accelerate training by fully utilizing all available resources. How…