# First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2017.

## Built on by (most cited first, 30 of 37)

- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Convergent Bregman Plug-and-Play Image Restoration for Poisson Inverse Problems](https://mlsanity.com/paper/2306.03466/) (2023)
- [Joint Majorization-Minimization for Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2106.15214/) (2021)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning](https://mlsanity.com/paper/2306.14522/) (2023)
- [Deep Equilibrium models for Poisson Imaging Inverse problems via Mirror Descent](https://mlsanity.com/paper/2507.11461/) (2025)
- [Learning Graph Structure from Convolutional Mixtures](https://mlsanity.com/paper/2205.09575/) (2022)
- [Convergent plug-and-play with proximal denoiser and unconstrained regularization parameter](https://mlsanity.com/paper/2311.01216/) (2023)
- [Block Alternating Bregman Majorization Minimization with Extrapolation](https://mlsanity.com/paper/2107.04395/) (2021)
- [Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements](https://mlsanity.com/paper/2107.08011/) (2021)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition](https://mlsanity.com/paper/2503.02386/) (2025)
- [Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms](https://mlsanity.com/paper/2404.08073/) (2024)
- [Stable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2405.10754/) (2024)
- [On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem](https://mlsanity.com/paper/2507.15264/) (2025)
- [Provable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2210.09248/) (2022)
- [Sharper Bounds for Proximal Gradient Algorithms with Errors](https://mlsanity.com/paper/2203.02204/) (2022)
- [Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning](https://mlsanity.com/paper/2303.15866/) (2023)
- [An Efficient Alternating Algorithm for ReLU-based Symmetric Matrix Decomposition](https://mlsanity.com/paper/2503.16846/) (2025)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [A Nonlocal Graph-PDE and Higher-Order Geometric Integration for Image Labeling](https://mlsanity.com/paper/2205.03991/) (2022)
- [SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization](https://mlsanity.com/paper/2207.08195/) (2022)
- [A Variational Approach for Joint Image Recovery and Feature Extraction Based on Spatially-Varying Generalised Gaussian Models](https://mlsanity.com/paper/2209.01375/) (2022)
- [Edge-guided Low-light Image Enhancement with Inertial Bregman Alternating Linearized Minimization](https://mlsanity.com/paper/2403.01142/) (2024)
- [Low Complexity Regularized Phase Retrieval](https://mlsanity.com/paper/2407.16413/) (2024)
- [Joint Cooperative and Non-Cooperative Localization in WSNs with Distributed Scaled Proximal ADMM Algorithms](https://mlsanity.com/paper/2509.18213/) (2025)
- [On the Tension Between Optimality and Adversarial Robustness in Policy Optimization](https://mlsanity.com/paper/2512.01228/) (2025)
- [External Division of Two Bregman Proximity Operators for Poisson Inverse Problems](https://mlsanity.com/paper/2602.11482/) (2026)
- [A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis](https://mlsanity.com/paper/2603.12838/) (2026)

## Abstract (arXiv)

We focus on nonconvex and nonsmooth minimization problems with a composite objective, where the differentiable part of the objective is freed from the usual and restrictive global Lipschitz gradient continuity assumption. This longstanding smoothness restriction is pervasive in first order methods (FOM), and was recently circumvent for convex composite optimization by Bauschke, Bolte and Teboulle, through a simple and elegant framework which captures, all at once, the geometry of the function and of the feasible set. Building on this work, we tackle genuine nonconvex problems. We first complement and extend their approach to derive a full extended descent lemma by introducing the notion of smooth adaptable functions. We then consider a Bregman-based proximal gradient methods for the nonconvex composite model with smooth adaptable functions, which is proven to globally converge to a critical point under natural assumptions on the problem's data. To illustrate the power and potential of our general framework and results, we consider a broad class of quadratic inverse problems with sparsity constraints which arises in many fundamental applications, and we apply our approach to derive new globally convergent schemes for this class.