Primal-Dual Rates and Certificates
arXiv:1602.05205
Abstract
We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to diagnose progress, in particular in machine learning applications. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many L1, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model. Our approach provides efficiently computable duality gaps which are globally defined, without modifying the original problems in the region of interest.
appearing at ICML 2016 - Proceedings of the 33rd International Conference on Machine Learning, New York, NY, USA, 2016. JMLR: W&CP volume 48
References in corpus (7)
- On the Global Linear Convergence of Frank-Wolfe Optimization Variants
- Randomized Dual Coordinate Ascent with Arbitrary Sampling
- An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
- SDCA without Duality
- Distributed Mini-Batch SDCA
- Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
- A Primal-Dual Algorithmic Framework for Constrained Convex Minimization