Preprint
First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods
ArXiv.org
07/14/2023
DOI: 10.48550/arxiv.2307.07605
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. 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.
Details
- Title: Subtitle
- First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods
- Creators
- Wei Liu - Rensselaer Polytechnic InstituteQihang Lin - University of Iowa, Business AnalyticsYangyang Xu - Rensselaer Polytechnic Institute
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.2307.07605
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 07/14/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984445753102771
Metrics
2 Record Views