Extended Regularized Dual Averaging Methods for Stochastic Optimization
Preprint
Abstract
We introduce a new algorithm, extended regularized dual averaging (XRDA), for solving regularized stochastic optimization problems, which generalizes the regularized dual averaging (RDA) method. The main novelty of the method is that it allows a flexible control of the backward step size. For instance, the backward step size used in RDA grows without bound, while for XRDA the backward step size can be kept bounded. We demonstrate experimentally that additional control over the backward step size can significantly improve the convergence rate of the algorithm while preserving desired properties of the iterates, such as sparsity. Theoretically, we show that the XRDA method achieves the same convergence rate as RDA for general convex objectives.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- BinaryRelax: A Relaxation Approach for Training Deep Neural Networks with Quantized WeightsSIAM Journal on Imaging Sciences, 2018
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Learning by mirror averagingThe Annals of Statistics, 2008
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point ProblemsSIAM Journal on Optimization, 2004
- Mirror descent and nonlinear projected subgradient methods for convex optimizationOperations Research Letters, 2003
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998
- Regression Shrinkage and Selection Via the LassoJournal of the Royal Statistical Society Series B: Statistical Methodology, 1996
- Problem Complexity and Method Efficiency in OptimizationJournal of the Operational Research Society, 1984
- The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programmingUSSR Computational Mathematics and Mathematical Physics, 1967