# First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods arXiv: https://arxiv.org/abs/2307.07605 · HTML: https://mlsanity.com/paper/2307.07605/ ## Key facts - No citing papers in the map yet (data through 14 Oct 2026). - Builds on 28 of its 49 references that are in the map. - First posted on arXiv 14 Jul 2023. ## Builds on (most cited first, 28 of 28) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017) - [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018) - [Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems](https://mlsanity.com/paper/1410.1390/) (2014) - [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017) - [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018) - [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021) - [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021) - [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019) - [Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints](https://mlsanity.com/paper/1908.00131/) (2019) - [Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs](https://mlsanity.com/paper/1802.03504/) (2018) - [A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization](https://mlsanity.com/paper/1812.10229/) (2018) - [Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis](https://mlsanity.com/paper/1605.02408/) (2016) - [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020) - [Dissolving Constraints for Riemannian Optimization](https://mlsanity.com/paper/2203.10319/) (2022) - [On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization](https://mlsanity.com/paper/1906.05622/) (2019) - [New characterizations of Hoffman constants for systems of linear constraints](https://mlsanity.com/paper/1905.02894/) (2019) - [Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary](https://mlsanity.com/paper/1702.04300/) (2017) - [A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees](https://mlsanity.com/paper/1904.03563/) (2019) - [Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications](https://mlsanity.com/paper/1604.00543/) (2016) - [Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms](https://mlsanity.com/paper/1804.02729/) (2018) - [Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems](https://mlsanity.com/paper/2006.08048/) (2020) - [Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints](https://mlsanity.com/paper/2008.07080/) (2020) - [On the Iteration Complexity of Smoothed Proximal ALM for Nonconvex Optimization Problem with Convex Constraints](https://mlsanity.com/paper/2207.06304/) (2022) - [Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs](https://mlsanity.com/paper/1705.07229/) (2017) - [Linearly-constrained nonsmooth optimization for training autoencoders](https://mlsanity.com/paper/2103.16232/) (2021) - [An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity](https://mlsanity.com/paper/2205.05428/) (2022) - [Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems](https://mlsanity.com/paper/1702.01850/) (2017) ## Abstract (arXiv) Many recent studies on first-order methods (FOMs) focus on 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 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. In addition, we present an inexact proximal gradient (IPG) method by using the more relaxed one of the two assumed first-order oracles. The oracle complexity of the proposed IPG, to find a (near) ε-stationary point of the considered problem and its reformulation, matches our established lower bounds up to a logarithmic factor. Therefore, our lower complexity bounds and the proposed IPG method are almost non-improvable.