Research map / Optimization / Nonconvex and smooth optimization
Primal-Dual Rates and Certificates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Equip existing optimization algorithms with the proposed primal-dual certificate framework | Convex problems of the form f(Aα) + g(α) · General convex optimization | duality-gap guarantee | Helped |
| Restrict the regularizer's domain to a bounded set using the Lipschitzing trick | Norm-regularized problems · General norm-regularized problems | duality-gap certificate availability | Helped |
| Use Lipschitzing with an L1-norm ball | Lasso · Lasso | iterations to duality gap ε: T≥max{0,nlog(βε_D^(0)/(2B^2R^2n)}+n+20n^2B^2R^2/(βε) | Helped |
| Use coordinate-wise Lipschitzing for L1 regularization | Coordinate descent · Lasso | duality-gap convergence: O(ε^-1) | Helped |
| Use coordinate descent with Lipschitz g_i* and report the average iterate | Coordinate descent · Partially separable problems | iterations to duality gap ε: O(ε^-1) | Helped |
| Use an individual iterate rather than an averaged solution for general sublinearly convergent algorithms | General optimization algorithms · Problems with Lipschitz g* | iterations to duality gap ε: O(ε^-2) | Hurt |
| Average the parameter vector for coordinate descent with Lipschitz g_i* | Coordinate descent · Partially separable problems | duality-gap convergence: O(ε^-1) versus O(ε^-2) | Helped |
| Use APPROX to obtain certificates for the iterate itself rather than only an average | APPROX · Problems with Lipschitz g* | iterations to duality gap ε: O(ε^-1) | Helped |
| Apply the framework to Elastic Net using coordinate descent on the primal or dual formulation | Coordinate descent · Elastic Net | iterations to duality gap ε: T≥(n+nR^2/(ληζ))log([n+nR^2/(ληζ)]ε_D^(0)/ε); T≥(d+dP^2/(ληζ))log([d+dP^2/(ληζ)]ε_D^(0)/ε) | Mixed |
| Add the L2 component of the Elastic Net regularizer | Elastic Net · Elastic Net as η→0 | duality-gap finiteness | Helped |
Closest papers by meaning
- Random extrapolation for primal-dual coordinate descent (ICML 2020 · similarity 0.87)
- Celer: a Fast Solver for the Lasso with Dual Extrapolation (ICML 2018 · similarity 0.86)
- Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms (ICML 2017 · similarity 0.86)
- Scalable First-order Method for Certifying Optimal k-Sparse GLMs (ICML 2025 · similarity 0.85)
- Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums (ICML 2021 · similarity 0.85)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.