Computer Science – Learning
Scientific paper
2010-09-16
Computer Science
Learning
Extensively updated version of earlier draft with new analysis including a general treatment of composite objectives and exper
Scientific paper
We study three families of online convex optimization algorithms: follow-the-proximally-regularized-leader (FTRL-Proximal), regularized dual averaging (RDA), and composite-objective mirror descent. We first prove equivalence theorems that show all of these algorithms are instantiations of a general FTRL update. This provides theoretical insight on previous experimental observations. In particular, even though the FOBOS composite mirror descent algorithm handles L1 regularization explicitly, it has been observed that RDA is even more effective at producing sparsity. Our results demonstrate that FOBOS uses subgradient approximations to the L1 penalty from previous rounds, leading to less sparsity than RDA, which handles the cumulative penalty in closed form. The FTRL-Proximal algorithm can be seen as a hybrid of these two, and outperforms both on a large, real-world dataset. Our second contribution is a unified analysis which produces regret bounds that match (up to logarithmic terms) or improve the best previously known bounds. This analysis also extends these algorithms in two important ways: we support a more general type of composite objective and we analyze implicit updates, which replace the subgradient approximation of the current loss function with an exact optimization.
No associations
LandOfFree
A Unified View of Regularized Dual Averaging and Mirror Descent with Implicit Updates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Unified View of Regularized Dual Averaging and Mirror Descent with Implicit Updates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Unified View of Regularized Dual Averaging and Mirror Descent with Implicit Updates will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-28116