H. Brendan McMahan
Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and Implicit Updates.
Fri, 09/17/2010 - 15:02 — SomNambulAuthors: H. Brendan McMahan
Subjects: Learning
AbstractWe study two families of online convex optimization algorithms: mirror
descent and follow-the-regularized-leader. We prove that many mirror descent
algorithms (such as online gradient descent) are actually instances of a more
general follow-the-leader algorithm which uses proximal regularization
(additional strong convexity centered at the current feasible point). Further,
under certain step-size assumptions, other mirror-descent algorithms are
equivalent to follow-the-leader algorithms with origin-centered regularization
(such as dual averaging).Adaptive Bound Optimization for Online Convex Optimization.
Thu, 07/08/2010 - 15:01 — SomNambulAuthors: Matthew Streeter, H. Brendan McMahan
Subjects: Learning
AbstractWe introduce a new online convex optimization algorithm that adaptively
chooses its regularization function based on the loss functions observed so
far. This is in contrast to previous algorithms that use a fixed regularization
function such as L2-squared, and modify it only via a single time-dependent
parameter. Our algorithm's regret bounds are worst-case optimal, and for
certain realistic classes of loss functions they are much better than existing
bounds. These bounds are problem-dependent, which means they can exploit the
structure of the actual problem instance.Less Regret via Online Conditioning.
Fri, 02/26/2010 - 16:01 — SomNambulAuthors: Matthew Streeter, H. Brendan McMahan
Subjects: Learning
AbstractWe 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.
User login
