Less Regret via Online Conditioning

By Matthew J. Streeter, H. Brendan McMahan. 2010

80 citations recorded by the source corpus.

We analyze and evaluate an online gradient descent algorithm with adaptive per-coordinate adjustment of learning rates. Our algorithm can be thought of as an online version of batch gradient descent with a diagonal preconditioner. This approach leads to regret bounds that are stronger than those of standard online gradient descent for general online convex optimization problems. Experimentally, we show that our algorithm is competitive with state-of-the-art algorithms for large scale machine learning problems.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Adaptive Bound Optimization for Online Convex Optimization (2010, background): “In concurrent work [Streeter and McMahan, 2010], we showed that for some problem families, a per-coordinate learning rate for online gradient descent provides asymptotically less regret than even the best non-increasing global learning rate (chosen in hind-sight, given the observed loss functions).”
Ad click prediction: a view from the trenches (2013, background): “In fact, Streeter and McMahan [29] have shown a family of problems where the performance for the standard algorithm is asymptotically much worse than running independent copies.”
A survey of Algorithms and Analysis for Adaptive Online Learning (2014, methodology): “algorithm for n-dimensions we need only apply the above technique on a per-coordinate basis, namely using learning rate t;i= p 2R 1 qP t s=1 g 2 s;i for coordinate i, where we assume X[ R 1;R 1]n. Streeter and McMahan (2010) take the per-coordinate approach directly; the more general approach here ”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, background): “Accumulating past gradients or subgradients to set a stepsize, η t ∝ 1 / t s =1 || g s || 2 ∗ , can be traced back to online learning (Auer et al., 2002; Streeter & McMahan, 2010).”
Training Deep Networks without Learning Rates Through Coin Betting (2017, methodology): “Then, as sketched in Section 4, it is enough to calculate the Fenchel conjugate of the wealth and use the standard construction for the per-coordinate updates [Streeter and McMahan, 2010].”
Large-Scale Learning with Less RAM via Randomization (2013, background): “…training massive-scale distributed learning systems, such as those used for predicting ad click through rates (CTR) for sponsored search (Richardson et al., 2007; Craswell et al., 2008; Bilenko & Richardson, 2011; Streeter & McMahan, 2010) or for ﬁltering email spam at scale (Goodman et al., 2007).”