Primal-Dual Adaptive Subgradient Methods

Abstract

We propose adaptive primal-dual subgradient methods for constrained convex optimization. Our first method applies an AdaGrad-style step-sizes to the dual problem and recovers primal solutions by averaging the associated Fenchel-type oracle outputs. It achieves 𝒪̃(T^−1/2) convergence for the dual objective residual, primal objective residual, and feasibility gap in the nonsmooth regime, while automatically improving to 𝒪(T⁻¹) when the dual objective is smooth. We further develop an accelerated variant, which retains the 𝒪̃(T^−1/2) nonsmooth rate while achieving 𝒪(T⁻²) convergence in the smooth regime under mild assumptions. These guarantees require no prior knowledge of the underlying regularity. We demonstrate the empirical performance of the proposed methods on optimal transport and semidefinite relaxation of the Max-Cut problem.

Effective Dual Subgradient Methods Through Sequential Subgradient-Aligned Rays
Hansi Abeynanda, Chathuranga Weeraddana, Carlo Fischione
arXiv23 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Unifying Variational View of Accelerated Primal-Dual Methods
Cheng Chang, Mehran Mesbahi
arXiv11 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Inertial Primal-Dual Dynamics Methods Featuring Implicit Hessian-Driven Damping for Convex Optimization Problems in Continuous and Discrete Time
Xiangkai Sun, Zeying Gao, Liang He +1
arXiv29 Aug 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods
Harbir Antil
arXiv23 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Numerical analysis & scientific computingarXiv
Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
Necdet Serhat Aybat, Jinxin Wang
arXiv29 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{prakhya2026primaldual,
  title = {{Primal-Dual Adaptive Subgradient Methods}},
  author = {Karthik Prakhya and Zimeng Wang and Alp Yurtsever},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.28300},
  eprint = {2610.28300},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.28300},
}

RIS

TY  - UNPB
TI  - Primal-Dual Adaptive Subgradient Methods
AU  - Karthik Prakhya
AU  - Zimeng Wang
AU  - Alp Yurtsever
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.28300
UR  - https://arxiv.org/abs/2610.28300
AB  - We propose adaptive primal-dual subgradient methods for constrained convex optimization. Our first method applies an AdaGrad-style step-sizes to the dual problem and recovers primal solutions by averaging the associated Fenchel-type oracle outputs. It achieves 𝒪̃(T^−1/2) convergence for the dual objective residual, primal objective residual, and feasibility gap in the nonsmooth regime, while automatically improving to 𝒪(T^−1) when the dual objective is smooth. We further develop an accelerated variant, which retains the 𝒪̃(T^−1/2) nonsmooth rate while achieving 𝒪(T^−2) convergence in the smooth regime under mild assumptions. These guarantees require no prior knowledge of the underlying regularity. We demonstrate the empirical performance of the proposed methods on optimal transport and semidefinite relaxation of the Max-Cut problem.
ER  -

Abstract

Related

Cite