Eecient Algorithms for Online Decision Problems

By D. Kalai, Santosh Srinivas Vempala. 2003

How researchers see this paper

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

Citations in the corpus

Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017, methodology): “This ceases to be an efficient or practical algorithm when the number of subgroups is large, as is our case, leading to our use and analysis of Follow the Perturbed Leader for the Learner and best response for the Auditor.”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, neutral): “The algorithm is similar to the follow the perturbed leader and lazy projection algorithms developed in the context of online optimization [KV05], though in this form the algorithm seems to be originally due to Nesterov [Nes09].”
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.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “…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-Perturbed-Leader algorithm (Kalai and Vempala, 2005), and ProjectedGD , which builds on the projected gradient ascent algorithm (Zinkevich, 2003).”
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.”
How to Use Heuristics for Differential Privacy (2018, methodology): “The following theorem is folklore, but follows essentially from the original analysis of “follow the perturbed leader” by Kalai and Vem-pala [KV05].”
Non-Stationary Stochastic Optimization (2013, background): “Additional algorithms were shown to be rate optimal under further assumptions on the function class (see, e.g., Kalai and Vempala 2005, Hazan et al. 2007), or other feedback structures such as multi-point access (Agarwal et al. 2010).”
Learning in games with continuous action sets and unknown payoff functions (2016, methodology): “…[53] on online convex programming, the most widely used class of algorithms for no-regret learning is the family of online mirror descent (OMD) schemes pioneered by Shalev-Shwartz and Singer [45] and the closely related “Follow the Regularized Leader” (FoReL) method of Kalai and Vempala [22].”
Oracle-Based Robust Optimization via Online Learning (2014, methodology): “Two regret-minimization algorithms that we shall use henceforth (at least in spirit) are Online Gradient Descent (Zinkevich, 2003) and Follow the Perturbed Leader (Kalai and Vempala, 2005).”
Efficient Optimal Learning for Contextual Bandits (2011, background): “One attempt to get around this is the follow-the-perturbed-leader al-gorithm (Kalai and Vempala, 2005) which provides a computationally tractable solution in certain special-case structures.”
Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games (2020, background): “In the rich online learning literature [Zinkevich, 2003, Kalai and Vempala, 2005, Shalev-Shwartz and Singer, 2007, Arora et al., 2012, Shalev-Shwartz et al., 2012, Hazan, 2016], perhaps the simplest algorithm that achieves the minimax-optimal regret guarantee is Zinkevich’s online gradient descent…”
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization (2013, methodology): “…conditional gradient algorithm, we give algorithms for online convex optimization over polyhedral sets that perform only a single linear optimization step over the domain on each iteration while having optimal regret guarantees in terms of the game length, answering an open question of [20, 16].”