Primal-Dual Rates and Certificates
This work addresses the need for practitioners in machine learning to monitor optimization progress, offering a general solution for norm-regularized generalized linear models, though it is incremental as it builds on existing optimization methods.
The authors tackled the problem of diagnosing progress in optimization for machine learning by proposing an algorithm-independent framework that provides primal-dual certificates and convergence rate guarantees, resulting in new rates for Lasso, L1, Elastic Net, group Lasso, and TV-regularized problems, with efficiently computable duality gaps.
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.