Logo image
Back
Lower Complexity Bounds of First-Order Methods for Affinely Constrained Composite Nonconvex Problems
Journal article   Peer reviewed

Lower Complexity Bounds of First-Order Methods for Affinely Constrained Composite Nonconvex Problems

Wei Liu, Qihang Lin and Yangyang Xu
Mathematics of operations research, Vol.51(2), pp.1659-1682
05/2026
DOI: 10.1287/moor.2023.0377

View Online

Abstract

Many recent studies on first-order methods (FOMs) focus on composite nonconvex nonsmooth 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 smooth nonconvex cases. In this paper, we make the first attempt to establish lower complexity bounds of FOMs for solving a class of composite nonconvex nonsmooth optimization with linear constraints. Assuming two different first-order oracles, we establish lower complexity bounds of FOMs to produce a (near) [Formula: see text]-stationary point of a problem (and its reformulation) in the considered problem class for any given tolerance [Formula: see text]. Our lower bounds indicate that the existence of a nonsmooth 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 a longer arXiv version of this work. Funding: This work was partly supported by the Office of Naval Research [Grant N00014-22-1-2573] and the National Science Foundation [Grants DMS-2053493, DMS-2406896, and IIS-2147253].
 nonconvex nonsmooth optimization first-order methods lower complexity bound

Details

Metrics

7 Record Views
Logo image