Logarithmic regret algorithms for online convex optimization

By Elad Hazan, Amit Agarwal, Satyen Kale. 2006

1,314 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Adaptive Gradient-Based Meta-Learning Methods (2019, background): “Then the ε -EWOO algorithm, which for ε > 0 uses the actions of EWOO run on the functions ˜ (cid:96) t ( x ) = for all x ∗ > 0 .”
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2011, methodology): “Another procedure, for which the standard online analysis of SGD applies (Hazan et al., 2007), is to return the average point ¯ w T = 1 T ( w 1 + . . . + w T ) .”
New Insights and Perspectives on the Natural Gradient Method (2014, methodology): “Note that while this is the same convergence rate (O(1/k)) as the one which appears in Hazan et al. (2007) (see our Section 11), the constant is much better.”
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2012, background): “2), and O (1 / √ T ) error for general convex F Zinkevich (2003); Hazan et al. (2007); Hazan & Kale (2011).”
Introduction to Online Convex Optimization (2016, methodology): “Logarithmic regret algorithms for online convex optimization and the Online Newton Step algorithm were presented in (54).”
Slow Learners are Fast (2009, background): “Their convergence properties are well understood and have been analyzed in a number of diﬀerent frameworks such as by means of asymptotics (Murata et al., 1994), game theory (Hazan et al., 2007), or stochastic programming (Nesterov and Vial, 2000).”
Online Meta-Learning (2019, neutral): “Thus, there is a large body of work on developing computationally cheaper algorithms (Cesa-Bianchi & Lugosi, 2006; Hazan et al., 2006; Zinkevich, 2003; Shalev-Shwartz, 2012).”
Agnostic System Identification for Model-Based Reinforcement Learning (2012, positive): “LQR can be solved by dynamic programming on V and K . a procedure can be interpreted as an online learning al-gorithm (Hazan et al., 2006; Kakade & Shalev-Shwartz, 2008), more speciﬁcally, Follow-the-(Regularized)-Leader (Hazan et al., 2006), and that using any no-regret online al-gorithm ensures…”
Variable Metric Stochastic Approximation Theory (2009, methodology): “The general convex optimization framework by Zinkevich (2003) that Hazan et al.”
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “Relevant theoretical guarantees, in the context of regret minimization, were given in Hazan et al. (2007); Duchi et al. (2011).”
The implicit bias of gradient descent on nonseparable data (2019, methodology): “(Hazan et al., 2007; Mahdavi et al., 2015) assume a bounded domain, exploit the exponential concavity of the logistic loss and apply online Newton step to give a O (1 /t ) rate.”
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization (2013, background): “2 Online convex optimization and its application to stochastic and offline optimization The problem of online convex optimization (OCO) [38, 17, 16] takes the form of the following repeated game.”
Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization (2010, background): “In particular, for , stochastic gradient descent achieves the rate (12) up to logarithmic factors [16], and closely related algorithms proposed in very recent works [17], [18] match the lower bound exactly up to constant factors.”
(Near) Dimension Independent Risk Bounds for Differentially Private Learning (2014, methodology): “As a direct application of our private algorithm over the simplex, we provide a privacy preserving variant of the Follow the Regularized Leader (FTRL) algorithm commonly used in online learning (Hazan et al., 2007; ShalevShwartz, 2011).”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “These results have been extended by many machine learning researchers, yielding tighter bounds and probabilistic guarantees (Hazan et al., 2006; Hazan & Kale, 2014; Rakhlin et al., 2012).”
An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback (2015, background): “improved bounds for strongly-convex functions; regret/error bounds holding with high-probability rather than just in expectation; and improved bounds if allowed k > 2 observations per round instead of just two (Hazan et al., 2007; Shalev-Shwartz, 2007; Agarwal et al., 2010).”