# Primal-Dual Rates and Certificates

arXiv: https://arxiv.org/abs/1602.05205 · HTML: https://mlsanity.com/paper/1602.05205/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2016.

## Built on by (most cited first, 3 of 3)

- [An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification](https://mlsanity.com/paper/2208.06058/) (2022)
- [FAStEN: An Efficient Adaptive Method for Feature Selection and Estimation in High-Dimensional Functional Regressions](https://mlsanity.com/paper/2303.14801/) (2023)
- [A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval](https://mlsanity.com/paper/2304.12522/) (2023)

## Abstract (arXiv)

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.