Preprint
A Near-optimal Method for Linearly Constrained Composite Non-convex Non-smooth Problems
ArXiV.org
Cornell University
03/28/2025
DOI: 10.48550/arxiv.2503.22927
Abstract
We study first-order methods (FOMs) for solving \emph{composite nonconvex nonsmooth} optimization with linear constraints. Recently, the lower complexity bounds of FOMs on finding an (ε,ε)-KKT point of the considered problem is established in \cite{liu2025lowercomplexityboundsfirstorder}. However, optimization algorithms that achieve this lower bound had not been developed. In this paper, we propose an inexact proximal gradient method, where subproblems are solved using a recovering primal-dual procedure. Without making the bounded domain assumption, we establish that the oracle complexity of the proposed method, for finding an (ε,ε)-KKT point of the considered problem, matches the lower bounds up to a logarithmic factor. Consequently, in terms of the complexity, our algorithm outperforms all existing methods. We demonstrate the advantages of our proposed algorithm over the (linearized) alternating direction method of multipliers and the (proximal) augmented Lagrangian method in the numerical experiments.
Details
- Title: Subtitle
- A Near-optimal Method for Linearly Constrained Composite Non-convex Non-smooth Problems
- Creators
- Wei LiuQihang LinYangyang Xu
- Resource Type
- Preprint
- Publication Details
- ArXiV.org
- DOI
- 10.48550/arxiv.2503.22927
- ISSN
- 2331-8422
- Publisher
- Cornell University; Ithaca, New York
- Language
- English
- Date posted
- 03/28/2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9984804801702771
Metrics
17 Record Views