arXiv research

New aggregation strategy handles unbounded losses with regret bounds.

Optimal bounds on regret and constraint violation in adversarial COCO.

Mutation improves FTRL convergence in zero-sum games.

New algorithm expands FTRL framework with improved worst-case regret bounds.

Algorithm optimizes functions without parameters, converging to global minima.

Develops a Best-of-Both-Worlds algorithm for linear contextual bandits with Tsallis entropy.

FTRL algorithm with negative entropy regularizer achieves best-of-three-world results for linear bandits.

Adaptive learning rate improves FTRL's performance in online learning.

Paper proves suboptimal convergence rate of last iterate for SGDM.

We study the problem of online learning with a notion of regret defined with respect to a set of strategies. We develop tools for analyzing the minimax rates and for deriving regret-minimization algorithms in this scenario. While the standard methods for minimizing the usual notion of regret fail, through our analysis …

The paper proposes a method to construct confidence sets using likelihood ratios for sequential decision-making.

New algorithms reduce regret in both stochastic and adversarial partial monitoring problems.

New algorithms reduce regret in online MDPs by adapting to data and variance.

Develops parameter-free online mirror descent for optimal dynamic regret.

Improved regret bound for adversarial MDPs with linear function approximation.

Paper optimizes multi-agent learning in Markov games with generative model.

New learning dynamics achieve fast convergence in games without needing to know utility scales.

New algorithm optimizes multi-armed bandits with low computational cost.

We revisit the fundamental problem of prediction with expert advice, in a setting where the environment is benign and generates losses stochastically, but the feedback observed by the learner is subject to a moderate adversarial corruption. We prove that a variant of the classical Multiplicative Weights algorithm with …

In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincaré recurrence from normal-form games to zero-sum two-player imperfect information games and other sequential game settings. We then investigate how adapting th…

New adaptive learning rate improves FTRL's adaptivity to sparsity, game-dependency, and best-of-both-worlds.

The online problem of computing the top eigenvector is fundamental to machine learning. In both adversarial and stochastic settings, previous results (such as matrix multiplicative weight update, follow the regularized leader, follow the compressed leader, block power method) either achieve optimal regret but run slow,…

New bounds for online portfolio selection without smoothness assumptions.

New algorithm reduces regret in collaborative multi-agent bandit problems.

In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required $Ω(n^4)$ running time [BSS14, Zou12], our sparsification routine can be implemented in almost-quadratic running time $O(n^{2+\varepsilon})$. The funda…

New algorithm reduces regret and constraint violation in online convex optimization with predictions.

Unified algorithm for linear bandits with improved regret bound.

New study shows FTRL mechanism works with correlated events.

New algorithm for online optimization over symmetric cones, unifying previous methods.

Study learns optimal strategies in imperfect information games with self-play.

Study on online regression with noise, achieving near-optimal regret bounds.

New algorithm reduces regret in both adversarial and stochastic contexts.

New algorithm achieves best-of-both-worlds performance in various online learning settings.

Algorithm learns both stochastic and adversarial MDPs with best-of-both-worlds guarantees.

Efficient algorithm converges to Nash equilibrium in bilinear problems with bandit feedback.

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 under worst-case assumptions. I attempted to unify all the literature as instantiations of Online Mirror Descent and Follow-the-Regularized-L…

New algorithm reduces regret in online portfolio and quantum state learning.

GALA adapts learning rates online by aligning gradients, improving deep learning model performance.

We propose a new algorithm for adversarial multi-armed bandits with unrestricted delays. The algorithm is based on a novel hybrid regularizer applied in the Follow the Regularized Leader (FTRL) framework. It achieves $\mathcal{O}(\sqrt{kn}+\sqrt{D\log(k)})$ regret guarantee, where $k$ is the number of arms, $n$ is the …

Recently, much work has been done on extending the scope of online learning and incremental stochastic optimization algorithms. In this paper we contribute to this effort in two ways: First, based on a new regret decomposition and a generalization of Bregman divergences, we provide a self-contained, modular analysis of…

Improved FTRL algorithm for multi-armed bandits with various regularizers and multiple optimal arms.

New algorithms minimize regret with global costs in online learning.

New algorithm achieves data-dependent regret bounds in MDPs with unknown transitions.

Algorithm finds optimal regularizers for online linear optimization.

This paper considers online convex optimization (OCO) problems - the paramount framework for online learning algorithm design. The loss function of learning task in OCO setting is based on streaming data so that OCO is a powerful tool to model large scale applications such as online recommender systems. Meanwhile, real…

FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.

This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given…

Adaptive learning rates improve FTPL's BOBW guarantees in bandit problems.