Logo image
Back
Lower Complexity Bounds of First-order Methods for Affinely Constrained Composite Non-convex Problems
Preprint   Open access

Lower Complexity Bounds of First-order Methods for Affinely Constrained Composite Non-convex Problems

Wei Liu, Qihang Lin and Yangyang Xu
ArXiV.org
Cornell University
02/24/2025
DOI: 10.48550/arxiv.2502.17770
url
https://doi.org/10.48550/arxiv.2502.17770View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

Many recent studies on first-order methods (FOMs) focus on \emph{composite non-convex non-smooth} optimization with linear and/or nonlinear function constraints. Upper (or worst-case) complexity bounds have been established for these methods. However, little can be claimed about their optimality as no lower bound is known, except for a few special \emph{smooth non-convex} cases. In this paper, we make the first attempt to establish lower complexity bounds of FOMs for solving a class of composite non-convex non-smooth optimization with linear constraints. Assuming two different first-order oracles, we establish lower complexity bounds of FOMs to produce a (near) ϵ-stationary point of a problem (and its reformulation) in the considered problem class, for any given tolerance ϵ>0. Our lower bounds indicate that the existence of a non-smooth convex regularizer can evidently increase the difficulty of an affinely constrained regularized problem over its nonregularized counterpart. In addition, we show that our lower bound of FOMs with the second oracle is tight, with a difference of up to a logarithmic factor from an upper complexity bound established in the extended arXiv version of this paper.
 Mathematics - Optimization and Control

Details

Metrics

5 Record Views
Logo image