Primal-Dual Error Bounds and KKT Metric Subregularity in Convex Composite Optimization
Abstract
We study primal and dual error bounds for convex composite optimization problems and their Fenchel duals. For the primal problem, we use a proximal-gradient residual, while for the generally nonsmooth dual problem we use a subdifferential residual. We introduce a reduced primal--dual KKT mapping whose zero set coincides with the Cartesian product of the primal and dual solution sets under the standing solvability and strong-duality assumptions. We establish implications in both directions between metric subregularity of the reduced KKT mapping and the primal and dual local error bounds. If the composite matrix has full row rank and the smooth gradient is locally Lipschitz continuous, KKT metric subregularity is equivalent to the primal local error bound. If the smooth term is strongly convex, it is equivalent to the dual local error bound. Under full row rank and strong convexity, KKT metric subregularity is equivalent to the simultaneous validity of both error bounds. We also establish relations between the Luo--Tseng and local error bounds. The framework is then applied to quadratic--polyhedral models, strongly convex smooth models with general convex regularizers, and regularized least-squares models beyond polyhedrality and strong convexity, providing a unified treatment of primal, dual, and KKT error-bound properties.
Related
- Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods
- Beyond Finite-Sum Optimization: A Primal-Dual Method for Decentralized Finite-Max Optimization
- A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
- On the Regularization of Primal-Dual Dynamics in Time-Dependent Nonconvex Optimization
- Inertial Primal-Dual Dynamics Methods Featuring Implicit Hessian-Driven Damping for Convex Optimization Problems in Continuous and Discrete Time
BibTeX
@misc{li2026primaldual,
title = {{Primal-Dual Error Bounds and KKT Metric Subregularity in Convex Composite Optimization}},
author = {Jiani Li and Qingna Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08587},
eprint = {2610.08587},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08587},
}
RIS
TY - UNPB
TI - Primal-Dual Error Bounds and KKT Metric Subregularity in Convex Composite Optimization
AU - Jiani Li
AU - Qingna Li
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08587
UR - https://arxiv.org/abs/2610.08587
AB - We study primal and dual error bounds for convex composite optimization problems and their Fenchel duals. For the primal problem, we use a proximal-gradient residual, while for the generally nonsmooth dual problem we use a subdifferential residual. We introduce a reduced primal--dual KKT mapping whose zero set coincides with the Cartesian product of the primal and dual solution sets under the standing solvability and strong-duality assumptions. We establish implications in both directions between metric subregularity of the reduced KKT mapping and the primal and dual local error bounds. If the composite matrix has full row rank and the smooth gradient is locally Lipschitz continuous, KKT metric subregularity is equivalent to the primal local error bound. If the smooth term is strongly convex, it is equivalent to the dual local error bound. Under full row rank and strong convexity, KKT metric subregularity is equivalent to the simultaneous validity of both error bounds. We also establish relations between the Luo--Tseng and local error bounds. The framework is then applied to quadratic--polyhedral models, strongly convex smooth models with general convex regularizers, and regularized least-squares models beyond polyhedrality and strong convexity, providing a unified treatment of primal, dual, and KKT error-bound properties.
ER -