Complexity-Optimal and Parameter-Free First-Order Methods for Finding Stationary Points of Composite Optimization Problems

This paper develops and analyzes an accelerated proximal descent method
for finding stationary points of nonconvex composite optimization
problems. The objective function is of the form f+h where h
is a proper closed convex function, f is a differentiable function
on the domain of h, and ∇f is Lipschitz continuous on
the domain of h. The main advantage of this method is that it is
"parameter-free" in the sense that it does not require knowledge
of the Lipschitz constant of ∇f or of any global topological
properties of ∇f. It is shown that the proposed method can obtain
an ε-approximate stationary point with iteration complexity
bounds that are optimal, up to logarithmic terms over ε,
in both the convex and nonconvex settings. Some discussion is also
given about how the proposed method can be leveraged in other existing
optimization frameworks, such as min-max smoothing and penalty frameworks
for constrained programming, to create more specialized parameter-free
methods. Finally, numerical experiments are presented to support the
practical viability of the method.

Article

Download

View Complexity-Optimal and Parameter-Free First-Order Methods for Finding Stationary Points of Composite Optimization Problems