Convergence guarantees for a class of non-convex and non-smooth optimization problems

Abstract

We consider the problem of finding critical points of functions that are non-convex and non-smooth. Studying a fairly broad class of such problems, we analyze the behavior of three gradient-based methods (gradient descent, proximal update, and Frank-Wolfe update). For each of these methods, we establish rates of convergence for general problems, and also prove faster rates for continuous sub-analytic functions. We also show that our algorithms can escape strict saddle points for a class of non-smooth functions, thereby generalizing known results for smooth functions. Our analysis leads to a simplification of the popular CCCP algorithm, used for optimizing functions that can be written as a difference of two convex functions. Our simplified algorithm retains all the convergence properties of CCCP, along with a significantly lower cost per iteration. We illustrate our methods and theory via applications to the problems of best subset selection, robust estimation, mixture density estimation, and shape-from-shading reconstruction.

arXiv comment50 pages, 2 figures

References in corpus (6)

• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

Cited by in corpus (13)

• SAT: Improving Adversarial Training via Curriculum-Based Loss Smoothing
• Efficient Nonnegative Tensor Factorization via Saturating Coordinate Descent
• Efficiency of Coordinate Descent Methods For Structured Nonconvex Optimization
• Data driven Dirichlet sampling on manifolds
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
• Statistically Efficient Off-Policy Policy Gradients
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• A Proximal Linearization-based Decentralized Method for Nonconvex Problems with Nonlinear Constraints
• M-estimation with the Trimmed l1 Penalty
• Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence
• Distributed proximal gradient algorithm for non-smooth non-convex optimization over time-varying networks
• Riemannian Proximal Policy Optimization
• BAMSProd: A Step towards Generalizing the Adaptive Optimization Methods to Deep Binary Model