Journal article
Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
SIAM journal on optimization, Vol.33(1), pp.1-35
03/31/2023
DOI: 10.1137/22M1469584
Abstract
We propose a double-loop inexact accelerated proximal gradient (APG) method for a strongly convex composite optimization problem with two smooth components of different smoothness constants and computational costs. Compared to APG, the inexact APG can reduce the time complexity for finding a near-stationary point when one smooth component has higher computational cost but a smaller smoothness constant than the other. The strongly convex composite optimization problem with this property arises from subproblems of a regularized augmented Lagrangian method for affine-constrained composite convex optimization and also from the smooth approximation for bilinear saddle-point structured nonsmooth convex optimization. We show that the inexact APG method can be applied to these two problems and reduce the time complexity for finding a near-stationary solution. Numerical experiments demonstrate significantly higher efficiency of our methods over an optimal primal-dual first-order method by Hamedani and Aybat [SIAM J. Optim., 31 (2021), pp. 1299-1329] and the gradient sliding method by Lan, Ouyang, and Zhou [arXiv2101.00143, 2021].
Details
- Title: Subtitle
- Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
- Creators
- Qihang Lin - University of IowaYangyang Xu - Rensselaer Polytechnic Institute
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.33(1), pp.1-35
- DOI
- 10.1137/22M1469584
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Grant note
- DOI: 10.13039/100000001, name: National Science Foundation, award: DMS-2053493, DMS-2208394; DOI: 10.13039/100000006, name: Office of Naval Research, award: N00014-22-1-2573
- Language
- English
- Date published
- 03/31/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380597102771
Metrics
45 Record Views