Research map / Optimization / Nonconvex and smooth optimization
Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes APDPro, an accelerated primal-dual method that progressively estimates the strong convexity of the Lagrangian (via dual lower bounds and cut constraints) plus a restart variant rAPDPro, achieving O(1/sqrt(eps)) for convex problems with strongly convex function constraints.
Problem
Minimizing a convex function subject to strongly convex function constraints; prior best complexity was O(1/eps) even with constraint strong convexity.
Approach
Progressively estimate a lower bound on the strong convexity of the Lagrangian in x by bounding the dual variables from below (via the optimal dual's lower bound from subgradient separation), and add cut constraints on the dual update to keep the dual away from the origin; a restart scheme further adapts epoch lengths and yields finite active-set identification for group Lasso-type problems.
Key results
- APDPro/rAPDPro achieve O(1/sqrt(eps)) complexity for strongly convex constraints, improving on the prior O(1/eps) bound.
- On sparse personalized PageRank experiments, rAPDPro and msAPD clearly outperform APD, APD+restart and Mirror-Prox in optimality gap and constraint violation.
- rAPDPro identifies the optimal active set (sparsity pattern) within a finite number of iterations on the tested datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use progressive strong convexity estimation and dual cut constraints | APDPro · Strongly convex function-constrained optimization | iteration complexity: \mathcal{O}(1/\varepsilon) -> \mathcal{O}(1/\sqrt{\varepsilon}) | Helped |
| Restart APDPro with dynamically adjusted epoch lengths | APDPro · Strongly convex function-constrained optimization | dependence on primal diameter in iteration complexity: \mathcal{O}\brbra{{D_X}/{\sqrt{\varepsilon}}} -> \mathcal{O}\brbra{\log\brbra{{D_X}/{\sqrt{\varepsilon}}}} | Helped |
| Restart APD instead of using standard APD | APD · Strongly convex function-constrained optimization | iteration complexity | Helped |
| Use multistage step sizes and dynamically adjust iterations by stage | APD · Strongly convex function-constrained optimization | iteration complexity | Helped |
| Use rAPDPro or msAPD instead of APD, APD+restart, or Mirror-Prox | Sparse Personalized PageRank · Sparse Personalized PageRank | relative function value gap | Helped |
| Use rAPDPro or msAPD instead of APD, APD+restart, or Mirror-Prox | Sparse Personalized PageRank · Sparse Personalized PageRank | constraint violation | Helped |
| Restart APDPro and use its last iterate | rAPDPro · Sparse Personalized PageRank | active-set identification accuracy | Helped |
| Use multistage updates | msAPD · Sparse Personalized PageRank | convergence performance over iterations | Mixed |
| Use the restart strategy rather than APDPro without restart | APDPro · Sparse Personalized PageRank | convergence performance | Helped |
Limitations
- Requires a known lower bound r on the norm of subgradients of f at the optimum
- Requires known upper bound on dual variables (D_Y); line search not handled
- Requires solving quadratic subproblems with linear constraints for dual updates
Experimental setup
Datasets: Network Datasets (bio-CE-HT, bio-CE-LC, econ-beaflw, among 6 selected)
Benchmarks: Network Datasets bio-CE-HT bio-CE-LC econ-beaflw
Metrics: relative function value gap constraint violation active-set identification accuracy
Baselines: APD APD+restart Mirror-Prox
Builds on: accelerated primal-dual method (APD) ConEx Mirror-Prox
Closest papers by meaning
- The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization (NeurIPS 2022 · similarity 0.91)
- Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter (ICML 2017 · similarity 0.90)
- Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k^2) Rate on Squared Gradient Norm (ICML 2021 · similarity 0.89)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.88)
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.88)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.88)
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.