Overview

Nonconvex optimization studies how to find useful solutions when objectives may have many local minima, saddle points, or irregular regions, as in deep learning, matrix recovery, control, and clustering. Common approaches include gradient and stochastic-gradient methods, proximal and difference-of-convex algorithms, alternating and coordinate updates, and manifold-aware methods; global search and convex relaxations are used when stronger guarantees are needed. Theory often measures progress through stationarity and analyzes convergence rates under assumptions such as smoothness, weak convexity, or gradient domination, while benchmarks test performance on large-scale and application-specific problems. A central tension is that efficient methods can often guarantee a stationary point, but proving global optimality or escaping poor solutions may require stronger assumptions, more computation, or problem-specific structure.

Latest papers

164 papers15 papers in the last four weeks, down 32% on the four weeks before. 0.1% of all new papers.

Nov 3, 2025

Disciplined Biconvex Programming

We introduce disciplined biconvex programming (DBCP), a modeling framework for specifying and solving biconvex optimization problems. Biconvex optimization problems arise in various applications, including machine learning, signal processing, computational science, and control. Solving a biconvex optimization problem in practice usually involves heuristic methods based on alternate convex search (ACS), which iteratively optimizes over one block of variables while keeping the other fixed, so that the resulting subproblems are convex and can be efficiently solved. However, designing and implementing an ACS solver for a specific biconvex optimization problem usually requires significant effort from the user, which can be tedious and error-prone. DBCP extends the principles of disciplined convex programming to biconvex problems, allowing users to specify biconvex optimization problems in a natural way based on a small number of syntax rules. The resulting problem can then be automatically split and transformed into convex subproblems, for which a customized ACS solver is then generated and applied. DBCP allows users to quickly experiment with different biconvex problem formulations, without expertise in convex optimization. We implement DBCP in the open-source Python package dbcp, as an extension to the well known domain specific language CVXPY for convex optimization.
Nov 3, 2025

The Optimization Landscape of Carathéodory Decomposition of Toeplitz Covariances

Toeplitz covariance estimation is a classical signal processing problem, yet the geometry of the Gaussian maximum-likelihood objective remains only partially understood. Recent Newton-type, majorization-minimization, and gradient-based methods often solve the nonconvex problem globally with enough samples, but also reveal a difficult computational landscape. We study this phenomenon through an overparameterized Carathéodory representation, which parameterizes the covariance by the frequencies and amplitudes of steering vectors. A simple example shows that, for any uniform frequency grid, optimizing only the amplitudes can leave a positive error even in the population setting, which motivates optimizing the frequencies as well. Our main result proves that this nonlinear parameterization adds no stationary points: for any sample covariance, every stationary point with a positive definite covariance gives a stationary point of the Toeplitz maximum-likelihood problem. In the population setting, every such point therefore recovers the true covariance. We also prove that gradient descent converges to the true covariance in the population setting, and to the unique maximum likelihood estimate when the sample covariance is close enough to the true covariance. These results do not require overparameterization. Numerically, overparameterization speeds up gradient descent and gives a more accurate estimate for a fixed number of iterations.
Oct 20, 2025

Stochastic Difference-of-Convex Optimization with Momentum

We study the online stochastic difference-of-convex (DC) program min⁡x∈RnF(x)=G(x)−H(x)+r1(x)−r2(x)\min_{x \in R^n} F(x) = G(x) - H(x) + r_1(x) - r_2(x), which covers sparse learning with nonconvex penalties, robust regression with smooth robust losses, and non-negative positive--unlabeled learning. We propose momentum-based DCA (MDCA), which combines a damped DCA step with a momentum estimator for ∇H\nabla H and uses a constant per-iteration batch size. With exact solutions of the convex subproblems, MDCA with Polyak momentum uses O(ε−4)\mathcal{O}( ε^{-4}) stochastic gradients of HH to reach εε-stationarity, and momentum-based variance reduction (MVR) uses O(ε−3)\mathcal{O}(ε^{-3}) under averaged smoothness, with a single O(ε−1)\mathcal O(ε^{-1}) warm-up batch in place of the periodic large batches of DCA-PAGE, whose εε-dependence it matches. We also introduce a single-loop variant (S-MDCA) that replaces the subproblem solve by one stochastic prox-gradient step; for every fixed smoothing parameter γγ for which the separately smoothed surrogate FγF_γ is bounded below, it reaches εε-stationarity of FγF_γ in O(ε−4)\mathcal{O}(ε^{-4}) iterations, which does not by itself imply stationarity of FF. A variance--drift trade-off lemma describes how the momentum parameter trades estimator variance against iterate-drift bias in steady-state upper bounds. Guarantees are given for two criteria: the critical-distance measure, and a DCA fixed-point residual that requires no smoothness of r2r_2 and vanishes exactly at DC-critical points; both give the same εε-dependence. Experiments on two LIBSVM classification datasets illustrate the methods' behaviour.
Oct 2, 2025

Smooth Quasar-Convex Optimization with Constraints

Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current nearly optimal algorithms work only in affine spaces due to the loss of one degree of freedom when working with general convex constraints. Obtaining an accelerated algorithm that makes nearly optimal O~(1/(γε))\widetilde{O}(1/(γ\sqrt{\varepsilon})) first-order queries to a γγ-quasar convex smooth function with constraints was independently asked as an open problem in Martínez-Rubio (2022); Lezane, Langer, and Koolen (2024). In this work, we solve this question by designing an inexact accelerated proximal point algorithm that we implement using a first-order method achieving the aforementioned rate and, as a consequence, we improve the complexity of the accelerated geodesically Riemannian optimization solution in Martínez-Rubio (2022). We also analyze projected gradient descent and Frank-Wolfe algorithms in this constrained quasar-convex setting. To the best of our knowledge, our work provides the first analyses of first-order methods for quasar-convex smooth functions with general convex constraints.
Aug 31, 2025

Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization

The ProbAbilistic Gradient Estimator algorithm (PAGE), a stochastic algorithm introduced by Li et al. in 2021, was designed to find stationary points for the average of smooth nonconvex functions. In this work, we study PAGE within the broad framework of ττ-weakly convex functions, providing a continuous interpolation between the general nonconvex LL-smooth regime (τ=Lτ=L) and the convex regime (τ=0τ=0). We establish new convergence rates for PAGE, showing that its complexity improves as ττ decreases.
Jul 26, 2025

Douglas-Rachford Splitting for Group-Sparse Feedback Linear-Quadratic Control

In this paper, we study the distributed linear quadratic problem with fixed communication topology (DFT-LQ) and the sparse feedback linear quadratic (SF-LQ) problem through a unified optimization framework. Specifically, both problems are formulated as a nonconvex, nonsmooth optimization problem equipped with an ℓ0\ell_0-penalty under affine constraints. To solve this problem, we first investigate the application of the Douglas-Rachford (DR) splitting algorithm. Under the local condition that the generated iterates remain on a fixed smooth manifold, we establish the convergence of the DR splitting to a stationary point. Furthermore, we characterize this stationary point as the global minimizer of a corresponding DFT-LQ problem. To bypass the restriction of the smooth manifold assumption, we introduce a projected subgradient descent algorithm that achieves global convergence without relying on smooth-manifold structures. This algorithm may serve as a warm-start mechanism that effectively drives the iterates toward the desired smooth manifolds, thereby establishing a favorable initialization where the convergence theory of the DR splitting algorithm becomes fully applicable. Numerical experiments shed light on the effectiveness of the proposed methods in distributed group-sparse controller design.
Jul 25, 2025

Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions

We develop efficient algorithms for optimizing piecewise smooth (PWS) functions when their smooth regions are unknown to the algorithm. For convex PWS functions satisfying a quadratic growth (QG) condition, we demonstrate that the bundle-level (BL)-type method~\cite{lemarechal1995new} achieves global linear convergence---to our knowledge, the first such result for any algorithm for this problem class. We extend the method to solve weakly convex PWS problems, achieving the same order of complexity as in smooth non-convex optimization. Furthermore, we introduce a verifiable and accurate termination criterion for PWS optimization. Like the gradient norm in smooth optimization, this certificate tightly characterizes the optimality gap under the QG condition and can be evaluated without knowledge of any problem parameters. We develop a search subroutine for this certificate and embed it within a guess-and-check framework, resulting in almost parameter-free algorithms for both convex QG and weakly convex PWS problems.
Apr 4, 2025

Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles

We present quantum speedups for sampling from distributions of the form π∝e−fπ\propto e^{-f} on Rd\mathbb{R}^d. We consider two stochastic oracle models: a stochastic gradient oracle, where f=1n∑i=1nfif=\frac{1}{n}\sum_{i=1}^n f_i and component gradients {∇fi}i∈[n]\{\nabla f_i\}_{i \in [n]} are available, and a stochastic evaluation oracle, where only noisy values of ff are available. Our framework accelerates classical stochastic Langevin Monte Carlo (LMC) and Hamiltonian Monte Carlo (HMC) algorithms by replacing stochastic gradient estimators with variance-controlled quantum mean estimation and gradient estimation subroutines. Unlike quantum walk based approaches, our algorithms do not require reversibility or exact gradients, and they preserve the structure of the underlying Markov chain. In the finite-sum setting, quantum mean estimation combined with classical variance-reduction techniques improves the stochastic gradient-query complexity for the approximate sampling task. In the stochastic zeroth-order setting, we develop gradient estimators robust to noisy function evaluations, yielding improved evaluation complexity for LMC and HMC. These results apply to strongly log-concave and/or non-log-concave distributions satisfying a log-Sobolev inequality, with convergence guarantees in Wasserstein distance and Kullback--Leibler divergence. We also show that faster sampling methods lead to quantum speedups for optimization, including for non-smooth and approximately convex objectives.
Dec 18, 2024

Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes

We present a novel class of projected gradient (PG) methods for minimizing a smooth but not necessarily convex function over a convex compact set. We first provide a novel analysis of the constant-stepsize PG method, achieving a unified iteration complexity for finding an approximate stationary point for convex and nonconvex problems. We then develop an "auto-conditioned" projected gradient (AC-PG) variant that achieves the same iteration complexity without requiring the input of the Lipschitz constant of the gradient or any line search procedure. The key idea is to estimate the Lipschitz constant using first-order information gathered from the previous iterations, and to show that the error caused by underestimating the Lipschitz constant can be properly controlled. We then generalize the PG methods to the stochastic setting, by proposing a stochastic projected gradient (SPG) method and a variance-reduced stochastic gradient (VR-SPG) method, achieving new unified complexity bounds in different oracle settings. We also present auto-conditioned stepsize policies for both stochastic PG methods and establish comparable convergence guarantees.
Sep 16, 2024

Convergence of Sharpness-Aware Minimization Algorithms using Increasing Batch Size and Decaying Learning Rate

The sharpness-aware minimization (SAM) algorithm and its variants, including gap guided SAM (GSAM), have been successful at improving the generalization capability of deep neural network models by finding flat local minima of the empirical loss in training. Meanwhile, it has been shown theoretically and practically that increasing the batch size or decaying the learning rate avoids sharp local minima of the empirical loss. In this paper, we consider the GSAM algorithm with increasing batch sizes or decaying learning rates, such as cosine annealing or linear learning rate, and theoretically show its convergence. Moreover, we numerically compare SAM (GSAM) with and without an increasing batch size and conclude that using an increasing batch size { achieves a lower worst-case ℓ∞\ell_\infty adaptive sharpness} than compared with using a constant batch size and learning rate.
Jun 18, 2024

Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum

Lower-bound analyses for nonconvex strongly-concave minimax optimization problems have shown that stochastic first-order algorithms require at least O(ε−4)\mathcal{O}(\varepsilon^{-4}) sample complexity to find an ε\varepsilon-stationary point. Some works indicate that this complexity can be improved to O(ε−3)\mathcal{O}(\varepsilon^{-3}) when the stochastic loss gradient is Lipschitz continuous. The question of achieving enhanced convergence rates under distinct conditions, remains open. In this work, we address this question for optimization problems that are nonconvex in the minimization variable and strongly concave or Polyak-Lojasiewicz (PL) in the maximization variable. We introduce novel bias-corrected momentum algorithms utilizing efficient Hessian-vector products. We establish convergence conditions and demonstrate a lower iteration complexity of O(ε−3)\mathcal{O}(\varepsilon^{-3}) for the proposed algorithms. The effectiveness of the proposed method is validated through applications to robust logistic regression and robust adaptive cruise control.
Jul 13, 2023

Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

This paper considers the problem of understanding the behavior of a general class of accelerated gradient methods on smooth nonconvex functions. Motivated by some recent works that have proposed effective algorithms, based on Polyak's heavy ball method and the Nesterov accelerated gradient method, to achieve convergence to a local minimum of nonconvex functions, this work proposes a broad class of Nesterov-type accelerated methods and puts forth a rigorous study of these methods encompassing the escape from saddle points and convergence to local minima through both an asymptotic and a non-asymptotic analysis. In the asymptotic regime, this paper answers an open question of whether Nesterov's accelerated gradient method (NAG) with variable momentum parameter avoids strict saddle points almost surely. This work also develops two metrics of asymptotic rates of convergence and divergence, and evaluates these two metrics for several popular standard accelerated methods such as the NAG and Nesterov's accelerated gradient with constant momentum (NCM) near strict saddle points. In the non-asymptotic regime, this work provides an analysis that leads to the "linear" exit time estimates from strict saddle neighborhoods for trajectories of these accelerated methods as well the necessary conditions for the existence of such trajectories. Finally, this work studies a sub-class of accelerated methods that can converge in convex neighborhoods of nonconvex functions with a near optimal rate to a local minimum and at the same time this sub-class offers superior saddle-escape behavior compared to that of NAG.
Jun 7, 2023

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix M∈Rn×nM \in \mathbb{R}^{n \times n}, a non-negative weight matrix W∈R≥0n×nW \in \mathbb{R}_{\geq 0}^{n \times n}, a parameter kk, the goal is to output two matrices X,Y∈Rn×kX,Y\in \mathbb{R}^{n \times k} such that ∥W∘(M−XY⊤)∥F\| W \circ (M - X Y^\top) \|_F is minimized, where ∘\circ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis [GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [LLR16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the cost of each iteration of [LLR16] from ∥W∥0k2\|W\|_0k^2 to ∥W∥0k\|W\|_0 k where ∥W∥0\|W\|_0 denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization. We also replace the random initialization of [LLR16], whose claimed guarantee fails, by subspace iteration from a Gaussian start, so our total running time of O~((∥W∥0k+nk3)log⁡(1/ε))\widetilde O((\|W\|_0 k+nk^3)\log(1/ε)) includes the initialization. In exchange, our guarantee needs the weight matrix to be within spectral distance γnγn of the all-ones matrix for a γγ that is polynomially small in nn.
Feb 21, 2023

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

Given a matrix M∈Rm×nM\in \mathbb{R}^{m\times n}, the low rank matrix completion problem asks us to find a rank-kk approximation of MM as UV⊤UV^\top for U∈Rm×kU\in \mathbb{R}^{m\times k} and V∈Rn×kV\in \mathbb{R}^{n\times k} by only observing a few entries specified by a set of entries Ω⊆[m]×[n]Ω\subseteq [m]\times [n]. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if MM has incoherent rows and columns, then alternating minimization provably recovers the matrix MM by observing a nearly linear in nn number of entries. While the sample complexity has been subsequently improved [GLZ17], alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency. In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time O~(∣Ω∣k)\widetilde O(|Ω| k), which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require O~(∣Ω∣k2)\widetilde O(|Ω| k^2) time.