106 citations · 525 across the 44 of their papers we have counts for
47 papers
Normalized Gradients for All
Francesco Orabona
In this short note, I show how to adapt to Hölder smoothness using normalized gradients in a black-box way. Moreover, the bound will depend on a novel notion of local Hölder smooth…
Implicit Interpretation of Importance Weight Aware Updates
Keyi Chen, Francesco Orabona
Due to its speed and simplicity, subgradient descent is one of the most used optimization algorithms in convex machine learning algorithms. However, tuning its learning rate is pro…
Generalized Implicit Follow-The-Regularized-Leader
Keyi Chen, Francesco Orabona
We propose a new class of online learning algorithms, generalized implicit Follow-The-Regularized-Leader (FTRL), that expands the scope of FTRL framework. Generalized implicit FTRL…
Tighter PAC-Bayes Bounds Through Coin-Betting
Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij +1
We consider the problem of estimating the mean of a sequence of random elements where is a fixed scalar function, ar…
Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
Ashok Cutkosky, Harsh Mehta, Francesco Orabona
We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for findi…
Robustness to Unbounded Smoothness of Generalized SignSGD
Michael Crawshaw, Mingrui Liu, Francesco Orabona +2
Traditional analyses in non-convex optimization typically rely on the smoothness assumption, namely requiring the gradients to be Lipschitz. However, recent evidence shows that thi…
Implicit Parameter-free Online Learning with Truncated Linear Models
Keyi Chen, Ashok Cutkosky, Francesco Orabona
Parameter-free algorithms are online learning algorithms that do not require setting learning rates. They achieve optimal regret with respect to the distance between the initial po…
Understanding AdamW through Proximal Methods and Scale-Freeness
Zhenxun Zhuang, Mingrui Liu, Ashok Cutkosky +1
Adam has been widely adopted for training deep neural networks due to less hyperparameter tuning and remarkable performance. To improve generalization, Adam is typically used in ta…
Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers
Jeffrey Negrea, Blair Bilodeau, Nicolò Campolongo +2
Quantile (and, more generally, KL) regret bounds, such as those achieved by NormalHedge (Chaudhuri, Freund, and Hsu 2009) and its variants, relax the goal of competing against the…
Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio
Francesco Orabona, Kwang-Sung Jun
A classic problem in statistics is the estimation of the expectation of random variables from samples. This gives rise to the tightly connected problems of deriving concentration i…
Online Learning with Optimism and Delay
Genevieve Flaspohler, Francesco Orabona, Judah Cohen +4
Inspired by the demands of real-time climate and weather forecasting, we develop optimistic online learning algorithms that require no parameter tuning and have optimal regret guar…
On the Initialization for Convex-Concave Min-max Problems
Mingrui Liu, Francesco Orabona
Convex-concave min-max problems are ubiquitous in machine learning, and people usually utilize first-order methods (e.g., gradient descent ascent) to find the optimal solution. One…
A closer look at temporal variability in dynamic online learning
Nicolò Campolongo, Francesco Orabona
This work focuses on the setting of dynamic regret in the context of online learning with full information. In particular, we analyze regret bounds with respect to the temporal var…
On the Last Iterate Convergence of Momentum Methods
Xiaoyu Li, Mingrui Liu, Francesco Orabona
SGD with Momentum (SGDM) is a widely used family of algorithms for large-scale optimization of machine learning problems. Yet, when optimizing generic convex functions, no advantag…
Parameter-free Stochastic Optimization of Variationally Coherent Functions
Francesco Orabona, Dávid Pál
We design and analyze an algorithm for first-order stochastic optimization of a large class of functions on . In particular, we consider the \emph{variationally coher…
Adam: A Stochastic Method with Adaptive Variance Reduction
Mingrui Liu, Wei Zhang, Francesco Orabona +1
Adam is a widely used stochastic optimization method for deep learning applications. While practitioners prefer Adam because it requires less parameter tuning, its use is problemat…
A High Probability Analysis of Adaptive SGD with Momentum
Xiaoyu Li, Francesco Orabona
Stochastic Gradient Descent (SGD) and its variants are the most used algorithms in machine learning applications. In particular, SGD with adaptive learning rates and momentum is th…
Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting
Keyi Chen, John Langford, Francesco Orabona
Parameter-free stochastic gradient descent (PFSGD) algorithms do not require setting learning rates while achieving optimal theoretical performance. In practical applications, howe…
Temporal Variability in Implicit Online Learning
Nicolò Campolongo, Francesco Orabona
In the setting of online learning, Implicit algorithms turn out to be highly successful from a practical standpoint. However, the tightest regret analyses only show marginal improv…
A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
Xiaoyu Li, Zhenxun Zhuang, Francesco Orabona
Stochastic Gradient Descent (SGD) is a popular tool in training large-scale machine learning models. Its performance, however, is highly variable, depending crucially on the choice…
Online Learning: A Modern Introduction Using Convex Optimization
Francesco Orabona
In this book, I introduce the concepts of online learning through a modern view based on convex optimization. Here, online learning refers to the framework of regret minimization u…
Parameter-Free Locally Differentially Private Stochastic Subgradient Descent
Kwang-Sung Jun, Francesco Orabona
We consider the problem of minimizing a convex risk with stochastic subgradients guaranteeing -locally differentially private (-LDP). While it has been shown that stochastic…
Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
Kwang-Sung Jun, Ashok Cutkosky, Francesco Orabona
In this paper, we consider the nonparametric least square regression in a Reproducing Kernel Hilbert Space (RKHS). We propose a new randomized algorithm that has optimal generaliza…
Momentum-Based Variance Reduction in Non-Convex SGD
Ashok Cutkosky, Francesco Orabona
Variance reduction has emerged in recent years as a strong competitor to stochastic gradient descent in non-convex problems, providing the first algorithms to improve upon the conv…