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

arXiv: https://arxiv.org/abs/1804.09629 · HTML: https://mlsanity.com/paper/1804.09629/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2018.

## Built on by (most cited first, 15 of 15)

- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Over-the-Air Federated Learning via Second-Order Optimization](https://mlsanity.com/paper/2203.15488/) (2022)
- [Predictive GAN-powered Multi-Objective Optimization for Hybrid Federated Split Learning](https://mlsanity.com/paper/2209.02428/) (2022)
- [Convex Optimization for Parameter Synthesis in MDPs](https://mlsanity.com/paper/2107.00108/) (2021)
- [Non-Asymptotic Guarantees for Robust Statistical Learning under Infinite Variance Assumption](https://mlsanity.com/paper/2201.03182/) (2022)
- [Pontryagin Optimal Control via Neural Networks](https://mlsanity.com/paper/2212.14566/) (2022)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [Revisiting Frank-Wolfe for Structured Nonconvex Optimization](https://mlsanity.com/paper/2503.08921/) (2025)
- [Enforcing Fair Predicted Scores on Intervals of Percentiles by Difference-of-Convex Constraints](https://mlsanity.com/paper/2505.12530/) (2025)
- [Supervised Dictionary Learning with Auxiliary Covariates](https://mlsanity.com/paper/2206.06774/) (2022)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [A Novel Plug-and-Play Approach for Adversarially Robust Generalization](https://mlsanity.com/paper/2208.09449/) (2022)
- [Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results](https://mlsanity.com/paper/2209.05372/) (2022)
- [CONTRAST: Continual Multi-source Adaptation to Dynamic Distributions](https://mlsanity.com/paper/2401.02561/) (2024)
- [Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise](https://mlsanity.com/paper/2607.25190/) (2026)

## Abstract (arXiv)

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.