We study the problem of online learning with non-convex losses, where the learner has access to an offline optimization oracle. We show that the classical Follow the Perturbed Leader (FTPL) algorithm achieves optimal regret rate of in this setting. This improves upon the previous best-known regret rate of…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
30 results for “Follow-The-Perturbed-Leader”
FTPL policy achieves best-of-both-worlds regret in decoupled bandits with reduced computational cost.
problem Decoupled multi-armed bandit problem with observed and unobserved losses.
method Follow-the-Perturbed-Leader (FTPL) policy that avoids convex optimization and resampling.
result Achieves constant regret in stochastic regime and optimal regret in adversarial regime.
Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.
problem Optimizing FTPL policy in combinatorial semi-bandit problems.
method Geometric resampling (GR) and conditional geometric resampling (CGR) for FTPL in semi-bandit setting.
result FTPL achieves optimal regret bounds in both Fréchet and Pareto distributions.
FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.
problem Optimizing regret bounds for m-set semi-bandit problems in adversarial and stochastic settings.
method Follow-the-Perturbed-Leader (FTPL) with Fréchet perturbation.
result Achieves near optimal regret bounds of in adversarial setting and logarithmic regret in stochastic setting.
Adaptive learning rates improve FTPL's BOBW guarantees in bandit problems.
problem Improving Follow-the-Perturbed-Leader's BOBW guarantees in bandit problems.
method Introducing surrogate probability functions to compute adaptive learning rates without exact probabilities.
result BOBW guarantees for FTPL with Pareto perturbations for any .
Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.
problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.
method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.
result FTPL with certain Fréchet-type tail distributions achieves regrets in adversarial bandits.
FTPL method shows near-optimal regret bounds for AMDPs with bandit feedback.
problem Minimizing regret in AMDPs with adversarial losses and bandit feedback.
method Follow-the-Perturbed-Leader (FTPL) method for AMDPs.
result FTPL achieves near-optimal regret bounds for AMDPs with bandit feedback.
Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, accuracy.
Advances FTPL results for bandit problems with unbounded perturbations.
problem Improving analytical foundations of FTPL in bandit problems.
method Revisiting classical FTRL-FTPL duality for unbounded perturbations.
result Establishes Best-of-Both-Worlds (BOBW) results for FTPL under a broad family of asymmetric unbounded perturbations.
New algorithm reduces regret in online learning for piecewise continuous functions.
problem Exponential loss in efficiency when moving from classical to adversarial learning.
method Introduces generalized bracketing numbers and Follow-the-Perturbed-Leader algorithm.
result Optimal scaling of optimization oracle calls with average regret.
We show a principled way of deriving online learning algorithms from a minimax analysis. Various upper bounds on the minimax value, previously thought to be non-constructive, are shown to yield algorithms. This allows us to seamlessly recover known methods and to derive new ones. Our framework also captures such "unort…
New algorithms handle unpredictable actions in sequential learning.
problem Learning with unreliable composite actions in online optimization.
method Follow-The-Perturbed-Leader method with Counting Asleep Times loss estimation.
result Significant improvement in performance guarantees for sleeping bandit problem.
New algorithm reduces prediction errors across various loss functions.
problem Online forecasting algorithms' inability to adapt to different loss functions.
method Design of a novel Follow-the-Perturbed-Leader (FTPL) algorithm with self-concordant noise.
result Simultaneously achieves regret for bounded proper losses and regret for bounded smooth proper losses.
Optimal multiclass U-calibration error found to be Θ(√KT).
problem Online multiclass U-calibration with low regret for all bounded proper losses.
method Follow-the-Perturbed-Leader algorithm and lower bound construction.
result Optimal U-calibration error is Θ(√KT).
New algorithms adapt to friendly environments in online learning.
problem Oracle-efficient algorithms struggle with friendly environments.
method Follow-the-perturbed-leader algorithms with approximability condition.
result Best-of-both-worlds bound in oracle-efficient setting.
This paper improves FTPL algorithm for semi-bandit problems with best-of-both-worlds guarantees.
problem Optimizing regret in adversarial and stochastic -set semi-bandit problems.
method Extending FTPL with geometric resampling (GR) to -set semi-bandits and analyzing its performance.
result FTPL with Fréchet and Pareto distributions achieves regret in adversarial setting and logarithmic regret in stochastic setting.
In this note, we present a version of the Thompson sampling algorithm for the problem of online linear generalization with full information (i.e., the experts setting), studied by Kalai and Vempala, 2005. The algorithm uses a Gaussian prior and time-varying Gaussian likelihoods, and we show that it essentially reduces …
Coop-FTPL algorithm minimizes network regret in semi-bandit settings.
problem Online combinatorial optimization with semi-bandit feedback on a network of agents.
method Cooperative Follow The Perturbed Leader (Coop-FTPL) algorithm with new loss estimation procedure.
result Expected regret of Coop-FTPL is of order Q mkT log(k)(kα1 /Q + m), with a state-of-the-art computational complexity of T^3/2.
New algorithm optimizes multi-armed bandits with low computational cost.
problem Optimizing multi-armed bandits with low computational cost.
method Proposes a new FTPL algorithm with optimistic principle for ambiguity.
result Unified regret analysis and low computational costs.
We propose a framework for ensuring safe behavior of a reinforcement learning agent when the reward function may be difficult to specify. In order to do this, we rely on the existence of demonstrations from expert policies, and we provide a theoretical framework for the agent to optimize in the space of rewards consist…
In many online learning problems the computational bottleneck for gradient-based methods is the projection operation. For this reason, in many problems the most efficient algorithms are based on the Frank-Wolfe method, which replaces projections by linear optimization. In the general case, however, online projection-fr…
Unified algorithm for linear bandits with improved regret bound.
problem Adversarial linear bandits with improved regret.
method Self-concordant perturbations in FTPL framework.
result Regret bound of for hypercube and ball.
Recent work on follow the perturbed leader (FTPL) algorithms for the adversarial multi-armed bandit problem has highlighted the role of the hazard rate of the distribution generating the perturbations. Assuming that the hazard rate is bounded, it is possible to provide regret analyses for a variety of FTPL algorithms f…
We propose a sample-efficient alternative for importance weighting for situations where one only has sample access to the probability distribution that generates the observations. Our new method, called Geometric Resampling (GR), is described and analyzed in the context of online combinatorial optimization under semi-b…
Game-theoretic models of learning are a powerful set of models that optimize multi-objective architectures. Among these models are zero-sum architectures that have inspired adversarial learning frameworks. An important shortcoming of these zeros-sum architectures is that gradient-based training leads to weak convergenc…
New insights link no-regret learning to online conformal prediction in adversarial settings.
problem Understanding the relationship between no-regret learning and online conformal prediction in adversarial environments.
method Analysis of existing algorithms and new connections between no-regret learning and conformal prediction.
result No-regret learning algorithms can provide group-conditional coverage guarantees in adversarial settings.
Most of machine learning deals with vector parameters. Ideally we would like to take higher order information into account and make use of matrix or even tensor parameters. However the resulting algorithms are usually inefficient. Here we address on-line learning with matrix parameters. It is often easy to obtain onlin…
We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the to…
New methods improve online matrix optimization with reduced computational cost.
problem Online matrix optimization with operator norm constraints.
method Gradient-based prediction scheme with smoothed potentials for nuclear norm.
result Adaptive matrix optimizers match Shampoo's regret up to a constant factor.
No-regret incentive-compatible online learning under exact truthfulness with non-myopic expertscs.LG
A new mechanism reduces expert belief regret in online forecasting.
problem Minimizing expert belief regret in strategic forecasting.
method Developed a no-regret mechanism for non-myopic experts using online I-ELF.
result Achieved regret for full-information setting.