Adaptive Online Gradient Descent

By Peter L. Bartlett, Elad Hazan, Alexander Rakhlin. 2007

256 citations recorded by the source corpus.

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

Adaptive Gradient-Based Meta-Learning Methods (2019, neutral): “[7] Peter L.”
Task-Free Continual Learning (2018, neutral): “A ﬁrst set of online learning algorithms consists of different techniques designed to learn a linear model [9, 6, 36, 12].”
Parallel training of Deep Neural Networks with Natural Gradient and Parameter Averaging (2014, methodology): “er methods to prevent instability– namely, the limit on parameter change per layer per minibatch (Appendix C.3); and the natural gradient method itself. Another popular modiﬁcation of SGD is Adagrad (Hazan et al., 2007). This method divides the learning rate for each parameter by the standard deviat”
Slow Learners are Fast (2009, methodology): “We extend this to bounds which are dependent on strong convexity [1, 7] to obtain adaptive algorithms which can take advantage of well-behaved optimization problems in practice.”
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, methodology): “However, if the cost functions are strongly convex, say with convexity parameter σ, then the same algorithm with stepsize αt = 1/(σt) gives an O(ln t) regret bound (e.g., Hazan et al., 2006; Bartlett et al., 2008).”
Online Learning: A Comprehensive Survey (2018, methodology): “In literature, different OGD variants have been proposed to improve either theoretical bounds or practical issues, such as adaptive OGD (Hazan et al., 2007b), and mini-batch OGD (Dekel et al., 2012), amongst others.”
On Learning Rates and Schrödinger Operators (2020, result): “As a notable advantage, the continuous-time perspective allows us to work without assumptions on the boundedness of the domain and gradients, as opposed to older analyses of SGD (see, for example, [HRB08]).”
Exploiting easy data in online optimization (2014, background): “bsmooth convex functions cMatching the performance of AOGD [5] (AB)-Prod Proof”
On optimization methods for deep learning (2011, methodology): “Recent work on SGDs focuses on adaptive strategies for the learning rate (Shalev-Shwartz et al., 2007; Bartlett et al., 2008; Do et al., 2009) or improving SGD convergence by approximating second-order information (Vishwanathan et al.”
Learning in high-dimensional multimedia data: the state of the art (2015, background): “Online learning has been studied in several research fields including game theory, information theory and machine learning [1, 56].”
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization (2011, methodology): “Mirror-descent type first order algorithms, such as projected gradient methods, attain regret bounds of the form (Zinkevich, 2003; Bartlett et al., 2007; Duchi et al., 2010)”
A survey of Algorithms and Analysis for Adaptive Online Learning (2014, methodology): “1 When it is not known a priori whether the loss functions f t are strongly convex, the r t can be chosen adaptively to add only as much strong convexity as needed, following Bartlett et al. (2007).”
Online Learning with Predictable Sequences (2012, background): “to develop algorithms that yield tighter bounds for \more regular" sequences, while still providing protection against worst-case sequences. Some successful results of this type have appeared in [8, 11,10,9,5] within the framework of prediction with expert advice and online convex optimization.”
Optimal Stragies and Minimax Lower Bounds for Online Convex Games (2008, background): “[1]: If Lt consists of continuous twice differentiable functions f , where ‖∇f‖ ≤ Gt and∇(2)f σtI , then RT ≤ 1 2 T ∑”
Proximal regularization for online and batch learning (2009, methodology): “1 from (Bartlett et al., 2008), we obtain the following bound:3 For comparison, (Bartlett et al.”
An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization (2021, background): “This means the minimax-optimal rate for regret is Θ(log t) (Hazan et al., 2007; Bartlett et al., 2007).”