Efficient algorithms for online decision problems

By Adam Tauman Kalai, Santosh Srinivas Vempala. 2005

871 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

In Algorithms & Complexity

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “The connection between private ERM and private online learning was first explored in [38], and the idea of using stability induced by differential privacy for designing low-regret algorithms was explored in [2, 3, 41].”
Adaptive Bound Optimization for Online Convex Optimization (2010, background): “…leader algorithm, in that we prove bounds on three quantities: 1. the regret of a hypothetical be the leader algorithm (BTL), which on round t plays As shown in [Kalai and Vempala, 2005], the BTL algorithm has regret ≤ 0 even without any restrictions on the loss functions or the feasible set.”
Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017, methodology): “We will make use of the Follow the Perturbed Leader (FTPL) algorithm as a no-regret learner for online linear optimization problems [Kalai and Vempala, 2005].”
Introduction to Online Convex Optimization (2016, background): “The influential paper of Kalai and Vempala (63) coined the term “follow-the-leader” and introduced many of the techniques that followed in OCO.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “4 was introduced by Kalai and Vempala [110] for the full information setting.”
Online Meta-Learning (2019, positive): “One of the most successful algorithms in online learning is follow the leader (Hannan, 1957; Kalai & Vempala, 2005), which enjoys strong performance guarantees for smooth and convex functions.”
An Online Learning Approach to Generative Adversarial Networks (2017, methodology): “We use the following regret bound regarding the FTL (follow-the-leader) decision rule, derived in Kalai and Vempala (2005) (see also Shalev-Shwartz et al. (2012)), Lemma 4.”
Regret to the best vs. regret to the average (2007, methodology): “Typical regret minimization algorithms (such as Exponential Weights, Littlestone and Warmuth 1994; Freund 2003, Follow the Perturbed Leader, Kalai and Vempala 2005, and the Prod algorithm, Cesa-Bianchi et al. 2007) will yield a gain of T/2 − Θ(√T ), meeting their guarantee of O(√T ) regret with…”
Compiling Combinatorial Prediction Games (2018, methodology): “Based on the pioneering work of Hannan (1957), refined in (Hutter & Poland, 2005; Kalai & Vempala, 2005), the FPL algorithm achieves an expected regret of O(d 32 √ T ).”
Online Learning with Predictable Sequences (2012, methodology): “We show that randomized methods of the Follow the Perturbed Leader (FPL) style [12, 7] can also enjoy better bounds for predictable sequences.”
Bandit Algorithms (2020, methodology): “Like before we recommend Kallenberg [2002] for readers who want to refresh their memory and Billingsley [2008] for a more detailed account.”
Bohatei: Flexible and Elastic DDoS Defense (2015, methodology): “• Online adaptation ( § 6): To handle a dynamic adversary that changes the attack mix (C3), we design a defense strategy adaptation approach inspired by classical online algorithms for regret minimization [36].”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “More specifically, the authors assume the existence of a classification oracle on the space of policies, which can find the minimum cost policy when given the cost of each action on each of a sequence of contexts, and propose two algorithms: SparringFPL, which is based on the Follow-the-PerturbedLea”