Nonconvex Optimization

Follow this topic Ask about this topic

Momentum

10 papers in the last four weeks, up 100% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 92

Oct 7, 2026cs.LG

Gauss-Newton Accuracy and Indefinite Hessians: Uniform Coexistence in Low-Cost Sets

We study the accuracy of Gauss-Newton curvature in ridge-regularized nonlinear least squares. Under local regularity and persistence of level-set curvature magnitude along an exact-fit section, we prove uniform coexistence of two curvature regimes. Global minimizers exist, and every global minimizer has relative Hessian error below

(1+\sqrt2)/8

, while the same low-cost set contains a point with an indefinite Hessian and relative error at least

15/8

. One positive ridge cap works for all independent center and label perturbations in fixed neighborhoods and every positive ridge weight up to the cap. These neighborhoods do not shrink as the ridge weight tends to zero. A pointwise certificate based on the current prediction level set controls the normal, mixed, and tangent parts of the Hessian correction. We prove a sharp relative-error bound over the stated pointwise class when the prediction map and ridge vary. Analytic examples describe the roles of output alignment, curvature orientation, and persistence. A separate structural result gives full Jacobian row rank throughout low-cost sets and exact interpolation near a rank-deficient reference.

Kihun Rhee, Hanjoon Byun

Gauss-Newton Optimization Second-Order Optimization Nonconvex Optimization Ridge Regression

Oct 6, 2026cs.LG

Convex-Concave Reinforcement Learning

Policy learning drives many of the most consequential and heavily-invested applications of reinforcement learning today. Yet the core optimization problem it rests on (maximizing expected return) is notoriously non-convex, even under a direct policy parameterization, and the field has largely responded by avoiding it: optimizing convex surrogate approximations of the return under trust-region constraints (NPG, TRPO, PPO, AWR). We show that this seemingly unstructured problem is not actually structureless. In log-density-ratio coordinates

y := \log[π/π_n]

, the exact per-iteration objective, computable via per-decision importance sampling (PDIS), is a difference-of-convex-constrained difference-of-convex (DC-constrained DC) program. This structure lets us move beyond surrogate approximations: it recovers CPI, NPG, TRPO, and AWR as special cases along interpretable axes, and it opens a multi-step axis

k

that couples consecutive decisions. We solve the per-iteration program with sequential convex programming (SCP), the standard solver for difference-of-convex problems, and give convergence guarantees under mild conditions, bridging the difference-of-convex optimization and RL literatures. Empirically, multi-step Convex-Concave RL (CCRL) wins on diagnostic MDPs where credit must propagate across a horizon (its advantage growing with the dependency length), is competitive with a tuned PPO on classic control, and on a realistic, stochastic, mid-horizon healthcare domain converges markedly faster than tuned PPO to the same near-optimal survival, with an 11.3% higher area under the training curve.

Shripad V. Deshmukh, Yaswanth Chittepu, Dhawal Gupta +2

University of Massachusetts · Institute of Foundation Models

Reinforcement Learning Policy Gradient Methods Nonconvex Optimization Step-Level Credit Assignment in RL

Oct 5, 2026cs.CV

Robust Local Optimization Done Right

RANSAC scoring and local optimization (LO) impose different robustness requirements, motivating the separation of hypothesis selection from refinement. We systematically isolate the effects of robust-loss shape, incorrectly specified inlier scales, and optimization strategy on essential matrix, fundamental matrix, and homography estimation. A profile-marginal score marginalizes the nuisance inlier scale and selects an inlier partition, from which we estimate the scale that sets the LO loss width; this makes LO robust to an inlier scale specified too large, whereas one specified too small degrades selection itself. Refinement needs gradient from correspondences the seed currently rejects: optimizers that reweight from current residuals stay pinned to their seed, whereas methods with broad basins recover strongly perturbed seeds yet degrade accurate score-selected hypotheses, so basin size alone is insufficient to assess RANSAC LO. Joint half-quadratic optimization balances the two and is the most consistent strategy across model classes. An optimizer matched to the profile-marginal score, which never decreases it, does not reach the best accuracy, challenging the prescription that scoring and refinement objectives should match. Composed from these findings, our RANSAC reduces the median essential-matrix pose error of a state-of-the-art RANSAC on PhotoTourism from 2.23 degrees to 1.58 degrees with a correctly specified inlier scale and from 38 degrees to 6.2 degrees when it is grossly misspecified (128x too large).

James Pritts, Kevin Köser

Kiel University, Kiel, Germany

Relative Pose Estimation Nonconvex Optimization Robust Loss Functions Robust Estimation

Oct 1, 2026cs.LG

SoftServe: A Scalable Quasi-Newton Method for Deep Learning

Quasi-Newton (QN) methods have long been among the most effective methods for large-scale unconstrained convex optimization. Two obstacles have limited their use in deep learning: non-convexity and enormous parameter sizes. We introduce SoftServe, a family of QN methods designed to overcome these obstacles without line searches or ad hoc curvature corrections. SoftServe derives positivedefinite curvature estimates from the variational objective of Berglund et al. (2025), even in the presence of negative curvature. We develop diagonal and Kroneckerfactored variants that preserve positive definiteness by construction and scale to massive neural networks. Finally, SoftServe relies on the stable coupled Newton-Schulz iteration for the required matrix operations, replacing costly matrix decompositions with GPU-friendly matrix multiplications. SoftServe excels on problems that are severely ill-conditioned, including tasks such as recurrent networks, deep autoencoders, physics-informed neural networks, and a 136M-parameter physics-informed diffusion model, often achieving lower losses than established baselines including Adam, Muon, and SOAP.

Joohwan Ko, Tetiana Parshakova, Diana Cai +1

University of Massachusetts Amherst · CCM, Flatiron Institute · Cornell University

Deep Learning Optimization Second-Order Optimization Nonconvex Optimization Quasi-Newton Methods

Oct 1, 2026cs.LG

Removing spurious minima for planar features by skip connections

Understanding loss landscapes is central to explaining neural-network training, yet their structure remains only partially understood even in simple models. We study the Gaussian population loss of shallow, bias-free ReLU networks in the teacher--student setting. This provides a simple model for studying essential aspects such as feature learning and overparameterization. For teacher networks with positive output weights and planar features, we show that including a learned linear skip removes all spurious local minima with non-negative student output weights once the student network is at least as wide as the teacher network. In contrast, without the skip, we construct a fixed teacher network with positive output weights and only three hidden neurons in input dimension two whose spurious local minima persist at every student width at least three. Thus, a learned linear skip can remove spurious minima that persist under arbitrary overparameterization. Furthermore, we show that a positive output weight student network always learns the subspace spanned by the teacher features: student features at local minima with non-negative student output weights lie in the span of the teacher features. For ReLU networks in two dimensions, even heavily overparameterized student networks have effective width controlled by the teacher width: every critical point with positive student output weights has at most twice as many distinct student feature directions as teacher neurons. Finally, we transfer the benignity result to empirical minima over parameter balls of any prescribed radius, with the required sampling accuracy depending on that radius.

Jakob Paul Zimmermann, Moritz Grillo, Andrei Balakin +1

Freie Universität Berlin · Technische Universität Berlin

Shallow Neural Networks ReLU Neural Networks Neural Network Optimization Nonconvex Optimization Teacher-Student Learning

Sep 30, 2026math.OC

Generalized Geometry Block Proximal Linearized Method for Multiblock Nonconvex and Nonsmooth Optimization

This paper considers a class of multiblock nonconvex and nonsmooth optimization problems arising in many applications. Existing methods construct proximal linearized operators or their variants within standard Euclidean geometry to solve this class of problems, forcing their block variable updates to rely on the standard inner product and its induced norm. Nevertheless, this construction fails to capture the geometric structure of the target problem, leading to low numerical efficiency. To overcome these drawbacks, we propose a generalized geometry proximal linearized operator for updating block variables, and develop the Generalized Geometry Block Proximal Linearized (GGBPL) method based on this operator. Compared with existing proximal linearized operators, the proposed operator allows the block surrogate functions to be constructed using arbitrary inner products and general admissible metrics, thereby enabling the GGBPL method to adapt its updates to the geometric structure of various problems. We also introduce the inertial version of GGBPL, named the inertial GGBPL (iGGBPL) method. We further establish a new unified convergence framework under this generalized geometry, within which we prove that our methods guarantee convergence of the objective function values, establish global convergence of the generated sequence to a critical point, and derive the convergence rate of our methods. We also establish an

\mathcal{O}(\varepsilon^{-2})

iteration complexity bound for obtaining an

\varepsilon

-stationary point. We apply our methods to two nonconvex and nonsmooth problems: sparse nonnegative matrix factorization with

\ell_0

-constraints and sparse nonnegative CP decomposition with

\ell_0

-constraints. Numerical results demonstrate the superior numerical performance of our proposed methods over several state-of-the-art methods.

Weifeng Yang

Nonconvex Optimization Constrained Optimization

Sep 27, 2026math.OC

DCEmbed: Scalable Optimization over Neural Surrogates

Neural surrogates can accelerate large-scale optimization by replacing expensive or intractable model components with efficient learned approximations, but solving the resulting embedded problems can remain prohibitively costly. For instance, standard exact encodings of neural networks with ReLU activations allow the problem to be solved by mixed-integer solvers, but add large numbers of binary variables to accommodate the nonlinearity of the activations, which can render the problem computationally prohibitive. To address this, we propose DCEmbed, a heuristic for optimization problems with embedded neural surrogates that leverages the difference-of-convex (DC) representation of the network and avoids adding activation binaries. Exploiting shared structure within the DC representation of a ReLU network, we derive a reduced-size, exact formulation for its convex components that can be embedded in optimization problems using just two linear inequalities and one continuous auxiliary variable per hidden neuron. Using this, the problem is solved via an iterative penalty convex-concave procedure, where only the concave portions of the neural terms are approximated at each stage. The original objective, constraints, and any discrete decisions are retained, allowing standard convex or mixed-integer optimization solvers to optimize the host and surrogate jointly at each iteration. In experiments on quadratic programs, mixed-integer resource allocation, and neural two-stage stochastic programming, our method demonstrates much faster progress toward high-quality feasible solutions than approaches using exact mixed-integer embeddings. In particular, DCEmbed achieves

4\times

lower normalized primal integral than the best exact baseline on the resource allocation problem, while in two-stage stochastic programming it reaches the global surrogate optimum

\sim 5\times

faster than Gurobi ML.

Akshay Sreekumar, Nicolas Christianson, Priya L. Donti +2

Stanford University Stanford, CA, USA · Johns Hopkins University Baltimore, MD, USA · Massachusetts Institute of Technology Cambridge, MA, USA

Neural Surrogate Modeling Surrogate-Assisted Optimization Nonconvex Optimization

Sep 27, 2026math.OC

lapanda: A Matrix-Free Differentiable Solver for Nonconvex Constrained Optimization Layers

Differentiable optimization brings the structural guarantees of mathematical optimization to network pipelines, allowing them to be trained end-to-end. However, its application remains challenging for nonconvex constrained problems, as existing differentiable solvers often suffer from limited modeling expressiveness due to their reliance on specialized problem structures, while also incurring substantial computation time and memory overhead in both the forward and backward passes. To address these challenges, we propose lapanda, a matrix-free differentiable solver for nonconvex optimization with general constraints. It reformulates the problem to a sequence of augmented Lagrangian subproblems, each handled by a first-order inner solver through a proximal averaged quasi-Newton algorithm with adaptive linesearch, thus enabling efficient forward optimization. We establish local well-posedness of the solution map and convergence of the outer iterations, and further derive a sensitivity alignment between the original problem and the final subproblem in the backward pass, demonstrating that the subproblem sensitivity, which can be computed efficiently in a matrix-free manner, provides a principled approximation to the exact optimizer sensitivity. We evaluate lapanda on nonconvex constrained Rosenbrock benchmarks, imitation learning with several representative constrained optimal control problems, and embedded robotic obstacle-avoidance tasks. Compared with state-of-the-art differentiable solvers, lapanda delivers substantial reductions in computation time and memory footprint while maintaining reliable constraint satisfaction and learning performance.

Yuankun Chen, Zifei Nie, Kangyu Lin +2

School of Artificial Intelligence, Jilin University, China · Graduate School of Informatics, Kyoto University, JPN · Department of Civil and Systems Engineering, Johns Hopkins University, USA

Differentiable Programming Nonconvex Optimization Quasi-Newton Methods Augmented Lagrangian Method Differentiable Optimization

Sep 21, 2026math.OC

Transformer-Informed Trajectory Optimization for Relative Motion in Cislunar Orbits

Autonomous spacecraft guidance and control requires a fast solution to non-convex trajectory optimization, which can be accelerated by providing a near-optimal initial guess to an optimization protocol, i.e., warm-starting. A robust warm starting method is especially useful for rendezvous, proximity operations, and docking (RPOD) in cislunar space, where the underlying dynamics become severely nonlinear and chaotic compared to those in Earth orbit, especially at perilune. This paper extends the Autonomous Rendezvous Transformer (ART), a transformer-based warm-start trajectory generation method, to cislunar RPOD scenarios for the first time. To accurately and reliably solve the nonconvex optimal control problems (OCPs) posed by these scenarios, a new and enhanced version of ART, ART-TWIN (Two-Way INference), is introduced. Inspired by forward-backward shooting methods used in other trajectory design applications, ART-TWIN autoregressively generates two arcs, one from the initial state and one from the desired terminal state, that are patched together at the midpoint of the timeseries. When evaluated on a set of simulated rendezvous scenarios that are initialized at perilune, ART-TWIN is demonstrated to substantially accelerate convergence and increase feasibility guarantees when used as a warm-start to sequential convex programming (SCP), compared to convex relaxations and the original ART. These results illustrate the necessity of ART-TWIN's dual-arc generation to enable the viability of and gain benefits from using transformer-based warm-start methods in the most challenging areas of the cislunar dynamical regime.

Walter J. Manuel, Yuji Takubo, Simone D'Amico

Department of Aeronautics and Astronautics, Stanford University, Stanford, CA 94305

Trajectory Optimization Spacecraft Rendezvous and Proximity Operations Nonconvex Optimization

Sep 15, 2026math.NA

Near-Optimal Nonconvex Matrix Completion

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an

n\times n

matrix of rank

r

with incoherence parameter

μ

and condition number

κ

, the two methods achieve exact recovery with high probability from

O(μnr\log n\log(nκ))

and

O(μnr\log n\log(2μrκ))

observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Jian-Feng Cai, Xiliang Lu, Juntao You

Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.

Riemannian Optimization Nonconvex Optimization Matrix Completion

Sep 8, 2026cs.LG

Adaptively Incorporating Directional Hints into Zeroth-Order Optimization

We study zeroth-order optimization of non-convex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order

O(1/T)

rate and the zeroth-order

O(d/T)

rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on non-convex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.

Alexander Ryabchenko, Jian Qian, Wenlong Mou

University of Toronto and Vector Institute · University of Hong Kong

Zeroth-Order Optimization Nonconvex Optimization Derivative-Free Optimization

Sep 8, 2026cs.LG

Sparse Data Augmentation for Optimization with Provable Guarantees

In nonconvex optimization problems arising in geometric machine learning, data augmentation is commonly used to promote invariance by averaging empirical losses over transformations of the data. Computing the fully augmented objective, however, requires access to every element of the transformation group

G

, which may be prohibitively expensive when

G

is large or accessible only through sampling. We study whether full augmentation can instead be approximated using a small, fixed sample of transformations acquired before optimization and reused thereafter. Under suitable regularity conditions, we show that, with probability at least

1-δ

, gradient descent (GD) on the resulting sparsely augmented objective returns an

\varepsilon

-stationary point of the fully augmented objective using

\mathcal{O}\bigl((\log |G|+\log(1/δ))/\varepsilon^2\bigr)

group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses

\mathcal{O}(1/\varepsilon^4)

transformation queries. Therefore, gradient descent with fixed sparse augmentation requires fewer transformation queries than both GD applied to the fully augmented objective and group-SGD. Our proof techniques, which may be of independent interest, establish a uniform approximation of the full group-averaged gradient field by a random group average using spectral properties of group-induced operators and tools from representation theory.

Behrooz Tahmasebi, Melanie Weber

Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA.

Data Augmentation Nonconvex Optimization

Sep 7, 2026cs.CV

Poisson Image Denoising Using Minimax Concave and Reweighted $\ell_1$ Penalties: Nonblind and Blind Approaches

Images are important tools in various sciences. Despite the development of photo-taking tools, creating clear and image without noise remains challenging in practice. In particular, Poisson noise has an effect on medical and astronomical images, and reduces their quality. Additionally, blur is another factor that has an effect on image quality. The problem of image restoration becomes very complicated when we have no information about the Point Spread Function (PSF). These types of problems are known as blind case. However, in some images, such as some astronomical images, the type of PSF can be specified, and these types of problems are known as nonblind problems. Total Variation (TV) is a widely used method for solving such inverse problems, where the selection of the penalty function is the most critical factor that affects the method's performance. In this paper, to improve edge preservation, we employ a reweighted

\ell_1

-regularization of the fractional order derivative. Furthermore, we propose a nonblind and blind image deblurring approach under Poisson noise using the Minimax Concave Penalty (MCP), which is a continuous, sparsity promoting, and nearly unbiased regularizer. This formulation leads to a nonconvex optimization model. To solve the proposed model, we introduce an efficient numerical algorithm based on the Alternating Direction Method of Multipliers (ADMM) and provide an analysis of its convergence. Finally, the effectiveness of the proposed algorithm are demonstrated through extensive experiments on various images.

Reza Parvaz

aDepartment of Engineering Sciences, Faculty of Advanced Technologies,Sep University of Mohaghegh Ardabili, Ardabil, Iran

Image Deblurring Nonconvex Optimization Image Denoising

Sep 1, 2026cs.LG

Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle

We revisit median-of-means estimation from a deterministic optimization viewpoint and develop a family of block-Lp estimators for robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least a fraction 1 minus epsilon of good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least 1 divided by 1 minus 2 epsilon. This matches the classical median-of-means bound and proves that the trimmed-block oracle constant 1 divided by 1 minus epsilon cannot be attained within the convex class. We then introduce a nonconvex block-Lp family for p between 0 and 1 and derive finite-sample deterministic robustness bounds for all global minimizers. As p decreases from 1 toward 0, these bounds continuously approach the trimmed-block oracle constant. For sufficiently small p, the global minimizers coincide with those of the oracle under a mild separation condition. We also show that the block-Lp objectives have a benign landscape, with all local minima remaining close to the truth and no bad basins. Combining these results with block-level concentration yields sub-Gaussian deviation bounds under finite 2 plus delta moments and high-dimensional extensions to robust mean estimation and sparse regression.

Angshul Majumdar

Department of Electronics and Communications Engineering, IIIT Delhi, India

Nonconvex Optimization Corruption Robustness Robust Estimation

Aug 31, 2026math.OC

Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy

This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at KKT stationary points. Leveraging a unified game-theoretic interpretation of eight classical algorithm families--including block coordinate descent, ADMM, generalized Benders decomposition, successive convex approximation, interior-point methods, mirror descent, Frank-Wolfe, and Riemannian gradient descent--we show that the normalized multiplier vector carries an algorithm-independent structural fingerprint. Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid. We establish four structural theorems characterizing the partition: invariance under natural KKT symmetries, local stability under data perturbation with explicit Lipschitz margins from Robinson's strong regularity, codimension-one regime transitions, and the topological identification of the Hybrid regime as the Lebesgue-null boundary of the core regimes. A linear-time classifier is proposed with provable guarantees on correctness, iteration stabilization, sample complexity, and online tracking under data drift. Numerical experiments on 104 mixed-integer nonlinear programs and a downlink beamforming instance validate the theoretical predictions. The framework provides a foundational tool for regime-aware algorithm design and robustness analysis in non-convex optimization.

Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabi

Department of Computer Engineering, Sharif University of Technology, Azadi, Tehran, 11365-9517, Tehran, Iran.

Nonconvex Optimization Constrained Optimization

Aug 31, 2026stat.ML

Estimating Population-Risk Curves Along Nonconvex Gradient Flows from the Training Sample

We estimate the conditional population-risk curve of a realized smooth nonconvex gradient flow from the training sample. Flow approximate leave-one-out (Flow-ALO) propagates a deletion response and evaluates omitted observations at approximate deleted paths. The risk-curve error decomposes into response approximation, exact-LOO fluctuation, and deletion-to-full risk transfer. On each fixed finite horizon, bounded centered training-loss gradients, a one-sided Hessian lower bound, locally Lipschitz Hessians, and a strict tube-closure condition yield an explicit

(n-1)^{-2}

bound for the deletion-response error. Bounded evaluation-loss gradients transfer the deletion-response bound to the score without requiring the Hessian to be invertible. Direct first-order jackknife cancellation and exact-LOO concentration control deletion-to-full risk transfer and fluctuation, respectively, completing recovery of the conditional population-risk curve. For bounded smooth two-layer mean-field networks training both layers, the score-error bound is uniform in width.

Mingzhi Song

Department of Mathematics, The University of Hong Kong

Nonconvex Optimization Statistical Learning Theory

Aug 29, 2026cs.CV

A Globally Convergent Algorithm for Total Scaled-Gradient Variation via Cone-Constrained Bilinear Decomposition

The total scaled-gradient variation (TSGV) regularizer, derived from sparse modeling of piecewise-linear structures, has been shown to preserve edges and corners in image restoration. However, its highly nonconvex and nonlinear nature poses severe computational challenges, as existing methods often suffer from parameter sensitivity or lack convergence guarantees. To overcome this, we propose a tailored bilinear decomposition that decouples the nonlinear weighted gradient in the TSGV regularizer. This approach yields an equivalent optimization problem governed by cone or sphere constraints, depending on the chosen scaling function. In particular, the cone constraint plays a central role in characterizing edge- and corner-preserving behavior. We solve this reformulation using the alternating minimization method (AMM) equipped with a majorization--minimization strategy, ensuring a monotonic decrease in energy without step-size tuning. Furthermore, we provide a geometric interpretation of the edge-preserving properties of these constraints by analyzing their asymptotic behavior near image singularities. We establish the global convergence of the proposed method to a critical point within the Kurdyka--Łojasiewicz framework. Extensive numerical experiments on Gaussian denoising and non-line-of-sight (NLOS) imaging show that the proposed method achieves PSNR and SSIM competitive with or superior to representative variational methods, especially at high noise levels, and improves the structural reconstruction under dense and sparse scanning.

Haibin Su, Chunlin Wu, Huibin Chang +1

Yau Mathematical Sciences Center, Tsinghua University, Beijing 100084, China · School of Mathematical Sciences, Nankai University, Tianjin, 300071, China · School of Mathematical Sciences and Institute of Mathematics and Interdisciplinary Sciences, Tianjin Normal University, Tianjin, 300387, China

Image Reconstruction Nonconvex Optimization Image Restoration Image Denoising

Aug 12, 2026math.OC

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.

Frank E. Curtis, Lingjun Guo, Daniel P. Robinson

Department of Industrial and Systems Engineering, Lehigh University

Optimization Convergence Analysis Nonconvex Optimization Augmented Lagrangian Method

Aug 7, 2026math.OC

Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization

Sequence convergence to a boundary Karush--Kuhn--Tucker (KKT) point has long remained unclear for nonconvex mirror descent with Legendre kernels. The difficulty arises from the blow-up of the gradient of the Legendre kernel at the boundary. Recent work~\cite{dingtoh2026nonkkt} shows that mirror descent can accumulate at non-KKT boundary points despite decreasing objective values, precluding a convergence guarantee to KKT points in general. Despite this negative result, mirror descent remains effective in many real applications. Motivated by this contrast, we address the boundary difficulty directly and establish KKT convergence of mirror descent for a broad class of structured nonconvex problems. We analyze mirror descent in reparameterized variables, where the Hessian metric is flattened and remains nondegenerate as the boundary is approached. Under extension and definability conditions jointly coupling the objective, the Legendre kernel, and the feasible region, the reparameterized sequence has finite length and converges, thereby recovering convergence to a KKT point of the original sequence. Our general framework applies to some concrete instances: Shannon entropy, Fermi--Dirac entropy, and power kernels on polyhedron.

Kuangyu Ding, Kim-Chuan Toh

School of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA. · Department of Mathematics, National University of Singapore, Singapore 119076.

Nonconvex Optimization Mirror Descent

Aug 6, 2026cs.LG

The Tamed Subgradient Unadjusted Langevin Algorithm beyond Convexity

We study the problem of sampling from target distributions whose potentials are simultaneously non-smooth, subject to superlinear gradient growth, and non-convex. We introduce the Subgradient Tamed Unadjusted Langevin Algorithm (SG-TULA), a discretisation of the Langevin diffusion that operates directly on subgradients, without relying on computationally demanding smoothing procedures. To handle the superlinear regime, taming techniques are employed to produce a stable, explicit scheme. We derive non-asymptotic convergence bounds in Wasserstein-2 distance, with all constants tracked explicitly in terms of dimension and inverse temperature, improving upon the currently known rates for subgradient-based Langevin algorithms. We further provide excess risk estimates for the associated optimisation problem. We verify the assumptions, with explicit constants, for the regularized pretraining potential of a LLM in the GPT-2 lineage and the boosted coordinate-wise variant of SG-TULA pretrains the former competitively against finetuned AdamW and Muon, for which no comparable non-asymptotic guarantees are presently available.

Iosif Lytras, Nikolaos Makras, Sotirios Sabanis

School of Mathematics, University of Edinburgh, UK · National Technical University of Athens, Greece · Athena/Archimedes Research Centre, Greece

Stochastic Gradient Langevin Dynamics Langevin Dynamics Nonconvex Optimization

Aug 6, 2026math.OC

Muon on the Stiefel Manifold Admits an Exact Closed-Form Update

We study Muon, a recently proposed matrix-aware optimization method, in the context of the Stiefel manifold. This manifold consists of matrices with orthonormal columns and is ubiquitous in machine learning and scientific computing. Existing extensions of Muon to this manifold rely on heuristic, approximate, or iterative updates with varying computational efficiency. We show that the corresponding Stiefel Muon update admits an exact closed-form solution and use this result to develop Skewon, a practical algorithm for orthogonality-constrained optimization with an efficient implementation. We further establish first-order convergence guarantees for Skewon in the smooth non-convex setting.

Mikhail Solonko, Molozhavenko Alexander, Maxim Rakhuba

HSE University, Moscow, Russia.

Stiefel Manifold Optimization Riemannian Optimization Muon Optimizer Nonconvex Optimization Constrained Optimization Matrix Optimization

Aug 6, 2026math.OC

An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization

In this paper, we consider a class of multiblock nonconvex nonsmooth optimization problems, which covers many applications such as the analysis of pre-earthquake anomalies and machine learning. To solve this class of problems, we propose the inertial block proximal linearized method with two-phase adaptive momentum (IBPL

^+

-TP). Compared to the current methods, our method possesses three main advantages: (1) it introduces a two-phase adaptive momentum strategy to effectively update the extrapolation parameters, (2) it allows using two different extrapolation points to accelerate the convergence, (3) it allows the extrapolation parameters of these two extrapolation points to be independent of and unconstrained by all other parameters. While maintaining the above advantages, we prove that our method ensures the monotonic convergence of the objective function of this class of problems, and we also prove that the sequence generated by our method globally converges to a critical point, as well as establish the convergence rate of our method. To demonstrate the effectiveness of our method, we apply it to solve two nonconvex and nonsmooth machine learning problems, namely sparse nonnegative matrix factorization with

\ell_0

-constraints and sparse nonnegative CP decomposition with

\ell_0

-constraints. The numerical experimental results on solving these problems show that our method outperforms several state-of-the-art methods.

Weifeng Yang

Yunnan Earthquake Administration, Kunming 650224, China

Momentum Methods Nonconvex Optimization

Aug 3, 2026cs.RO

Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles

We present a biconvex approach for minimum-time motion planning around convex obstacles that is guaranteed to converge, is anytime, and supports derivative constraints to arbitrary order. We jointly convexify the minimum-time objective and all derivative constraints through a change of variables, and handle collision avoidance via time-varying separating planes, reducing the problem to a biconvex program. This program is solved by alternating between computing maximum-margin separating planes and optimizing the trajectory. By only adding planes for obstacles that the current iterate collides with, the trajectory can jump around obstacles and escape local minima. The method is guaranteed to converge starting from a simple collision-free polygonal curve. In our experiments on drone navigation and dual-arm bin unloading, we find that the proposed method reliably produces high-quality trajectories with computation times comparable to state-of-the-art decomposition-based motion planners, while handling a larger class of problems and being substantially more robust to bad initialization. Project page:https://wernerpe.github.io/bmtp-website/

Peter Werner, Tobia Marcucci, Daniela Rus

Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory · University of California Santa Barbara

Constrained Motion Planning Trajectory Optimization Trajectory Generation Nonconvex Optimization Motion Planning Robot Collision Avoidance

Jul 29, 2026cond-mat.dis-nn

On the robustness of noisy solutions in non-convex neural networks

Optimization in non-convex neural network models is strongly influenced by the geometry of the solution space: sparse, isolated, point-like clusters are typically algorithmically inaccessible, whereas wide and flat regions can be found efficiently despite being relatively rare. At zero temperature this picture has been formalized in binary perceptrons through the overlap gap property (OGP), which limits algorithmic access to configurations with zero training error above a critical constraint density

α_{\rm OGP}

. Here we extend this description to finite temperature, where a positive training error is allowed and statistically penalized. We first show that the frozen one-step replica-symmetry-breaking solution, dominating the zero temperature equilibrium measure, survives at any finite temperature. We furthermore derive a general criterion, based on the smoothness of the single-pattern Gibbs weight near the decision boundary, that determines when a finite-temperature relaxation of the loss removes freezing. We then extend the OGP construction to finite temperature and show that dense, algorithmically accessible regions of finite-energy configurations persist beyond

α_{\rm OGP}

, up to a threshold

α_{\rm OGP}(ε)

that grows with the allowed training error

ε

. Finally, in the teacher-student setting, we show that these wide, finite-energy regions still retain good generalization. Using a finite energy message-passing algorithm, we demonstrate numerically that thermal noise enables effective generalization in the regime of constraint densities where both recovering the teacher and finding a zero temperature solution are computationally hard.

Enrico M. Malatesta, Alessandra Passalacqua, Riccardo Zecchina

Department of Computing Sciences, Bocconi University, Milano, Italy · Bocconi Institute for Data Science and Analytics (BIDSA)

Stochastic Optimization Neural Network Generalization Nonconvex Optimization

Jul 28, 2026math.OC

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias

O(τ_{\mathrm{mix}}/T)

uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under

σ^2\mapsto 2ΛG_σ^2

and

L^2\mapsto 2ΛL^2

, where

Λ=O(τ_{\mathrm{mix}}\log T)

. For positive centered noise, the tuned method achieves expected sample complexity

\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})

. The exactly noiseless specialization achieves

\widetilde{O}(\varepsilon^{-2})

with mixing-time-free constants, while a mixing-time-oblivious variant achieves

\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})

. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.

Zhaojun Peng

School of Computer Science Nanjing University of Information Science and Technology

Stochastic Optimization Nonconvex Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Variance Reduction

Jul 28, 2026stat.ML

Lloyd's $K$ -Means Clustering Algorithm Is Frank-Wolfe in Disguise

Lloyd's

K

-means algorithm, also known as naïve

K

-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all

K

-partitions of a dataset via iterative cluster refinement. In this work, we establish a novel connection between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a prominent first-order method for projection-free optimization. We demonstrate that Lloyd's algorithm is a special case of FW. Leveraging recent advances in FW methods for concave objectives, we derive a non-asymptotic

\mathcal{O}(1/t)

convergence rate to a local minimum of the SSE objective. To account for empty clusters, an outcome possible under Lloyd's greedy assignment, we develop an FW variant for semismooth objectives while retaining the same convergence rate that is solely controlled by the initial SSE value. We illustrate our findings with a simulation study for spherical Gaussian mixtures and a real-world image segmentation dataset.

Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien

Department of Mathematics & Statistics and School of Data Science Old Dominion University Norfolk, VA 23529, USA · Information Systems & Analytics Department Miami University Oxford, OH 45056, USA · Canada CIFAR AI Chair Department of Computer Science and Operations Research & Mila Université de Montréal Montréal (QC) Canada

Clustering Unsupervised Clustering Nonconvex Optimization

Jul 24, 2026cs.LG

Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Hölder Regularity

We study adaptive gradient descent for continuously differentiable, possibly nonconvex objectives under one-sided Hölder regularity. Unlike classical Hölder- or Lipschitz-gradient assumptions, which control the full gradient variation, our condition bounds only the directional term appearing in the descent inequality. This can allow less conservative step sizes when large gradient changes are orthogonal to, or favorable along, the update direction. We propose an adaptive scalar-step method based on an estimate of positive one-sided Hölder curvature, combined with a simple sufficient-decrease safeguard. For nonconvex objectives on a convex region containing the accepted update segments, we prove an explicit best-iterate stationarity bound with a rate determined by the Hölder exponent. Unlike predetermined diminishing step-size schemes, the method adapts to the local descent geometry. We evaluate the approach on two full-batch benchmarks designed to separate directional curvature from full gradient variation. On a binary classification problem, the method achieves the lowest final cross-entropy, objective value, and gradient norm, together with the largest classification margin among the compared scalar gradient methods. On a nonconvex Hölder regression problem, it attains the lowest final objective gap and gradient norm. These results indicate that one-sided Hölder curvature is an effective adaptive step-size signal when full-gradient variation is inflated by directions that do not hinder descent.

Arzu Ahmadova, Ismail Huseynov

Weierstrass Institute for Applied Analysis and Stochastics Berlin, Germany · Physikalisch-Technische Bundesanstalt (PTB), Germany · Technical University of Berlin, Germany

Learning Rate Scheduling Nonconvex Optimization Adaptive Gradient Methods

Jul 23, 2026cs.LG

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

Spectral methods are among the most widely used techniques for community detection, clustering, and graph learning. Their performance, however, critically depends on the accurate estimation of the underlying spectral subspace and can deteriorate substantially in the presence of noise, outliers, or model perturbations. To address this limitation, we propose a Regularized Projection Matrix Approximation (RPMA) framework for robust estimation of rank-

K

projection matrices. RPMA extends classical spectral projection by incorporating a regularization term, producing projection estimates that are more robust, sparse, and interpretable. We formulate the proposed model as an optimization problem on the manifold of rank-

K

projection matrices and exploit its geometric equivalence to the Grassmann manifold. Based on this manifold characterization, we derive the first- and second-order optimality conditions, establish the local stability of the regularized leading eigenspace, and characterize the stability of the critical-point landscape under sufficiently small regularization. To efficiently solve the resulting nonconvex optimization problem, we develop a Riemannian gradient projection algorithm with backtracking line search, together with a more efficient Cayley--Sherman--Morrison--Woodbury (Cayley--SMW) gradient method that avoids repeated eigendecompositions. Extensive experiments on both synthetic and real-world datasets demonstrate that RPMA substantially improves the recovery accuracy of projection matrices and consistently outperforms conventional spectral projection methods for community detection and clustering under noisy environments.

Zhuan Liang, Zheng Zhai

Department of Statistics, Faculty of Arts and Sciences at Beijing Normal University, Zhuhai

Spectral Regularization Riemannian Optimization Nonconvex Optimization Graph Clustering Spectral Methods

Jul 21, 2026math.OC

Online Optimization of Difference-of-Convex Compositions with Smooth Mappings

We study online optimization for a broad class of structured non-convex non-smooth problems where each loss is a composition of a difference-of-convex function with a smooth mapping, and the feasible region is defined by constraint functions of the same kind. We propose a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. We show that this residual is a proper stationarity measure for the original problem: its fixed-point condition implies first-order stationarity. Our analysis relies on a tangent-cone characterization for a feasible region described by composite difference-of-convex constraints, which is of independent interest and allows each update to be computed via a convex optimization oracle, despite the non-convexity of the problem. We establish a local-regret bound and a bound on the total number of inner convex subproblems. We also derive an error bound connecting the proximal residual to the distance to stationarity, providing a quantitative certificate of approximate stationarity.

Jingwei Ji, Jong-Shi Pang, Renyuan Xu

Management Science and Engineering, Stanford University · The Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Nonconvex Optimization Constrained Optimization

Jul 12, 2026stat.ML

Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization

We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition:

y_i=g(\inner{\ba_i}{\bPhi\bw^\ast+\bPsi\bz^\ast})+e_i

,

i=1,\dots,m

, with

m\ll n

, incoherent orthonormal bases

\bPhi,\bPsi

, a scalar link

g

, and noise

e_i

that may be heavy-tailed or contaminated. We propose a regularization-based framework combining a Huberized data fidelity with generalized folded-concave penalties (SCAD, MCP), and a two-block proximal alternating algorithm with backtracking (NLD-PALM) whose whole iterate sequence provably converges to critical points under the Kurdyka--Łojasiewicz property, with local linear rates. On the statistical side we establish restricted strong convexity of the Huberized nonlinear loss through an exact sign-definite decomposition, and derive estimation error bounds of order

σ\sqrt{s\log(n)/m}

that hold at \emph{every} localized stationary point, an oracle rate

σ\sqrt{s/m}

free of

\log n

and shrinkage bias under a beta-min condition, and a co-equal recovery theorem for \emph{unknown} monotone links via a linear surrogate and a clipped Plan--Vershynin decoupling. The estimator requires no knowledge of the sparsity levels, and its guarantees hold under symmetric noise with only finite variance. Experiments at

n=512

under a frozen data-driven regularization rule show an earlier phase transition than convex

\ell_1

demixing and greedy hard-thresholding baselines, a

35\times

accuracy advantage over squared-loss estimation under

5\%

gross outliers, and successful demixing of spike-plus-background signals observed through a saturating amplifier.

Raziyeh Takbiri

School of Electrical Engineering, Iran University of Science and Technology, Tehran, Iran

Sparse Recovery Nonconvex Optimization

Jul 10, 2026cs.LG

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles

Schedule-Free methods have attracted growing interest for alleviating the burden of designing and tuning a learning rate scheduler, while matching and sometimes even outperforming optimizers with tuned schedulers. Despite their strong empirical results, their convergence theory in nonconvex optimization, where modern machine learning objectives typically arise, has remained largely unexplored. In this paper, we provide worst-case analyses of Schedule-Free gradient descent and Schedule-Free stochastic gradient descent, in their standard form and without auxiliary modifications or restrictive conditions, for smooth but possibly nonconvex objectives. Based on a Lyapunov analysis derived from the continuous-time limiting ordinary differential equation associated with these methods, we show that Schedule-Free gradient descent and Schedule-Free stochastic gradient descent achieve the optimal worst-case convergence rates attainable among first-order methods. We further formulate Schedule-Free gradient descent as a nonautonomous dynamical system and prove strict-saddle avoidance under an arbitrarily small one-time perturbation. These theoretical results provide a better understanding of the strong performance that Schedule-Free methods demonstrate.

Jiseok Chae, Donghwan Kim

Natural Science Research Institute KAIST Daejeon, Republic of Korea · Department of Mathematical Sciences KAIST Daejeon, Republic of Korea

Learning Rate Scheduling Optimization Convergence Analysis Nonconvex Optimization Gradient Descent Dynamics Stochastic Gradient Descent

Jul 9, 2026math.OC

Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity

We study nonasymptotic convergence of primal-dual methods for a class of nonconvex constrained optimization problems with a convex-composite structure. In this class, both the objective and the functional inequality constraints are given by convex Lipschitz outer functions composed with smooth nonlinear inner mappings. The analysis is complicated by constraint violation in a nonconvex functional inequality system and by the lack of an a priori bound on the multipliers. To address these issues, we restrict the dual variable to an auxiliary compact set and analyze a smoothed prox-linear augmented Lagrangian method through a nonsmooth nonconvex-concave minimax reformulation. The main contribution is a finite-time mechanism for converting stationarity of the truncated minimax problem into a KKT certificate for the original constrained problem. We show that, for a sufficiently large penalty parameter, all but a controlled number of iterates enter a near-feasible region. On this region, a local conic regularity condition uniformly bounds the associated prox-linear multipliers and thereby makes the artificial dual truncation inactive at the selected iterates. Building on this mechanism, we establish explicit convergence rates for the proposed method in terms of the KKT residual. With dual regularization, a global dual error bound together with a bias-balancing argument gives an

O(K^{-1/3})

rate. In the unregularized case, under additional local structural assumptions including piecewise linearity of the outer functions, a local dual error bound yields the sharper

O(K^{-1/2})

rate.

Linglingzhi Zhu, Jiajin Li

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.

Primal-Dual Optimization Nonconvex Optimization Augmented Lagrangian Method

Jul 8, 2026cs.LG

Higher-Order Geometric Updates for Levenberg-Marquardt Method via Riemann Normal Coordinates

Nonlinear least-squares objectives form the foundation of scientific machine-learning tasks, yet even curvature-aware optimizers remain geometrically inconsistent at finite step sizes: Levenberg-Marquardt (LM) derives its direction from local Riemannian metrics but realizes it as a straight parameter update. Here we introduce RNC-LM, which carries the LM direction along a locally constructed curved trajectory in Riemann normal coordinates. A recursive reformulation of the geodesic equation generates arbitrary finite-order corrections while reusing the same damped Gauss-Newton matrix factorization, and curve length is controlled separately from damping. On a reaction-diffusion physics-informed neural network benchmark, RNC-LM reduces relative

L^2

errors below

8\times10^{-3}

, whereas L-BFGS, LM and LM with geodesic acceleration remain near one. On a large-scale machine-learning potential fitting task with 985,160 configurations, fourth-order RNC-LM reaches a fixed training-error target with a

34\times

wall-clock speedup over LM. These results establish finite-step geometric realization as a distinct optimizer design principle.

Jianing Liu, Dong H. Zhang

State Key Laboratory of Chemical Reaction Dynamics and Department of Chemical Physics, University of Science and Technology of China, Hefei, 230026, China · State Key Laboratory of Chemical Reaction Dynamics, Dalian Institute of Chemical Physics, Chinese Academy of Sciences, Dalian, 116023, China. · University of Chinese Academy of Sciences, Beijing, 100049, China +1

Gauss-Newton Optimization Riemannian Optimization Nonconvex Optimization

Jul 7, 2026math.OC

On the Condition Number Upper Bound of the L-BFGS Inverse Hessian Approximation Matrix with a Two-Sided Geometric Envelope Safeguarding Mechanism

The limited-memory BFGS (L-BFGS) algorithm is a cornerstone of large-scale optimization due to its linear memory and computational costs. However, in ill-conditioned or non-convex landscapes, the implicit inverse Hessian approximation can suffer from an exploding condition number, leading to numerical instability and degraded convergence. To address this, we propose Two-Sided L-BFGS, a safeguarded variant that dynamically constrains the condition number of the inverse Hessian operator via a two-sided geometric envelope. Moreover, we show that Two-Sided L-BFGS preserves accumulated curvature information and maintains standard

O(mn)

memory and per-iteration time complexities. We prove that this geometric envelope yields a uniform bound on the condition number of every inverse Hessian approximation generated by the algorithm. By tracking the algebraic evolution of the extreme eigenvalues through

m

consecutive quasi-Newton updates starting from a scaled identity matrix, the resulting bound is expressed explicitly as a function of the memory depth, problem dimension, and envelope hyperparameters. Moreover, we show that Two-Sided L-BFGS preserves asymptotic global convergence in non-convex regimes under standard smoothness and strong Wolfe line-search assumptions, matching the theoretical guarantees of L-BFGS variants utilizing the Li-Fukushima cautious update rule. Numerical experiments on high-dimensional optimization problems demonstrate that the proposed method maintains well-conditioned inverse Hessian approximations and improves robustness and convergence behavior on ill-conditioned benchmarks.

Don Li

Department of Mathematics & Statistics Portland State University Portland, OR 97201, USA

Second-Order Optimization Nonconvex Optimization Quasi-Newton Methods

Jul 6, 2026cs.LG

Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

This work delivers two key contributions: one to efficient feature selection in reinforcement learning (RL), the other to the theory of non-monotone inclusions. On the RL side, the estimation bias inherent in conventional regularization schemes is addressed by augmenting classical least-squares temporal-difference (LSTD) policy evaluation with the sparsity-inducing, non-convex projected minimax concave (PMC) penalty. Because the PMC penalty is weakly convex, the resulting fixed-point problem is no longer monotone; instead, it falls under a broader class of non-monotone inclusions involving the sum of a monotone Lipschitz operator and a hypomonotone operator. On the theory side, novel convergence conditions are developed for the forward-reflected-backward splitting (FRBS) method applied to this broader class of non-monotone inclusion problems. Under mild conditions, Lyapunov stability and the existence of a limit point of the sequence of FRBS iterates are established; alternatively, under the weak Minty variational inequality assumption, exact convergence is guaranteed. Numerical tests on benchmark datasets show that the proposed FRBS iterates, applied to the non-convexly regularized LSTD problem, substantially outperform state-of-the-art feature-selection methods, especially when many noisy features are present.

Kyohei Suzuki, Konstantinos Slavakis

Department of Information and Communications Engineering, Institute of Science Tokyo, Yokohama, 226-8501, Japan

Temporal-Difference Learning Nonconvex Optimization

Jul 2, 2026math.OC

Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization

In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods.

Siyuan Zhang, Nachuan Xiao, Xin Liu

Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Nonsmooth Convex Optimization Decentralized Optimization

Jun 30, 2026math.OC

Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics

Low-rank matrix optimization is often carried out via the Burer-Monteiro (BM) formulation, but choosing the factorization rank

r

is delicate and can substantially slow optimization. We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve optimization efficiency even when the target rank is unknown. We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization. The first, overparameterized DMD, uses a rank

r

larger than necessary and enjoys faster convergence as

r

increases. The second, recursive DMD, is motivated by the incremental eigenpair learning, or saddle-to-saddle, behavior of overparameterized DMD. It achieves lower memory and computational costs, complementing overparameterized DMD. Both approaches are exponentially faster than gradient descent applied to the BM formulation. Numerical experiments on matrix factorization, sensing, and completion corroborate our theoretical findings and demonstrate the practical effectiveness of DMD.

Yudong Wei, Liang Zhang, Bingcong Li +1

Department of Mathematics, ETH Zurich, Zurich, Switzerland · Department of Computer Science, ETH Zurich, Zurich, Switzerland

Low-Rank Matrix Decomposition Nonconvex Optimization Matrix Optimization Matrix Factorization Gradient Descent Dynamics

Jun 26, 2026cs.MA

A Fast Convergent Algorithm for Solving Non-convex Partially-Decoupled Generalized Nash Equilibrium Problems

Solving multi-agent optimal control problems in aerospace such as pursuit-evasion and contested space operations can be modeled as non-convex differential games for which, there are limited algorithms. In this work, a relaxation of generalized Nash Equilibrium problems (GNEPs) to exclude inter-agent control coupling in dynamics, which is representative of many multi-agent systems is introduced. The main contribution is an algorithm for solving a broad class of differential games named FALCON: Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria is presented. Methodologically, sequential convex programming (SCP) is utilized to create tractable convex sub-games which can then be solved via standard convex programming methods involving a potential game reformulation. FALCON is demonstrated to have global convergence guarantees to an open-loop Nash equilibrium for non-convex differential games under mild assumptions. This is numerically shown through both cooperative and competitive differential games.

Bennet Outland, Vishala Arya

Smead Aerospace Engineering Sciences Department, 3775 Discovery Drive, Boulder, CO, USA

Game Theory Nonconvex Optimization Optimal Control Nash Equilibrium Computation

Jun 26, 2026math.OC

Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor models for which a global Lipschitz-gradient constant need not exist. We show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal--dual fixed-point map whose strict-saddle KKT points are unstable fixed points; consequently, from random initialization the iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points. We extend the analysis to a multi-block star consensus formulation for distributed optimization. The technical novelty lies in a determinant reduction with a Bregman-specific symmetrization and scaling step in the two block spectral argument, together with a null space cancellation exploiting the star graph structure in the consensus case. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting idea beyond the separable consensus setting.

Shuang Li, Zhihui Zhu, Qiuwei Li

Department of Electrical and Computer Engineering, Iowa State University, Ames, Iowa 50014, USA · Department of Computer Science and Engineering, Ohio State University, Columbus, Ohio 43210, USA · DAMO Academy, Alibaba Group US, Bellevue, Washington 98004, USA

Optimization Convergence Analysis Distributed Optimization Alternating Direction Method of Multipliers Nonconvex Optimization

Jun 26, 2026cs.LG

Difference of Convex Programming in the Wasserstein Space with Applications to MMD Optimization

Optimizing functionals over the space of probability measures is now ubiquitous in machine learning. A widely used approach is to perform the optimization directly over the Wasserstein space, but many objective functionals of practical interest are non-convex along Wasserstein geodesics, making the analysis of standard first-order methods challenging. In this work, we study a class of objectives over the Wasserstein space that admit a difference-of-convex (DC) decomposition and we lift the classical convex-concave procedure (CCCP) to this setting. Under smoothness and strong convexity assumptions on the convex components of the decomposition, we prove almost stationarity along the iterates of the resulting algorithm. Our main focus is on the Maximum Mean Discrepancy (MMD) and the Energy Distance (ED) functionals, for which we develop explicit Wasserstein DC decompositions, and establish local convergence of the scheme under mild assumptions. Empirically, we show that well-chosen DC decompositions yield faster and more stable convergence than Wasserstein gradient descent on these MMD objectives.

Clément Bonet, Pierre-Cyril Aubin-Frankowski, Youssef Mroueh

CMAP, CNRS, Ecole Polytechnique, IP Paris · CERMICS, CNRS, ENPC, IP Paris · IBM Research

Maximum Mean Discrepancy Nonconvex Optimization Optimal Transport

Jun 25, 2026cs.LG

Finding Stationary Points by Comparisons

We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable

f\colon\mathbb R^n\to\mathbb R

with Lipschitz gradient and Hessian, we develop an algorithm that visits an

ε

-stationary point using

\widetilde O(n^2/ε^{1.5})

queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy

δ

using

\widetilde O(n^2\log(1/δ))

queries. We further study this problem with a quantum comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an

ε

-stationary point, which takes

\widetilde O(n/ε^{1.5})

queries.

Helin Wang, Chenyi Zhang, Xiwen Tao +2

School of Electronics Engineering and Computer Science, Peking University · Center on Frontiers of Computing Studies, Peking University · Computer Science Department, Stanford University +1

Black-Box Optimization Zeroth-Order Optimization Nonconvex Optimization

Jun 21, 2026math.OC

Adam Converges in Nonsmooth Nonconvex Optimization

Adam is one of the most widely implemented and influential modern optimizers. Why is it effective across different optimization problems in practice? This question arguably lies at the center of the optimization community over the last decade and has motivated a substantial body of work aimed at understanding its convergence behavior. However, existing studies have mainly focused on the convergence rate of Adam in smooth nonconvex optimization, which unfortunately does not adequately capture practical settings, since many real-world problems are nonsmooth, such as those arising in training neural networks. Thus, these studies cannot fully explain the popularity and empirical success of Adam. Recently, an insightful and powerful framework called Online-to-Nonconvex Conversion has opened a new way to analyze Adam for nonsmooth nonconvex optimization. Unfortunately, prior works along this line share two common limitations. First, all of them ignore the important bias-correction term in the original Adam algorithm. Second and more importantly, many of them require extra operations that are not used in Adam, such as a clipping step. Therefore, the convergence guarantee for the original Adam method still remains unclear. In this work, we present the first finite-time analysis for the classical form of Adam, i.e., with the bias-correction step and without further algorithmic modifications, and prove that a randomly scaled learning rate ensures a convergence rate of

1/T^{\frac{2}{13}}

for nonsmooth nonconvex optimization. Moreover, our result provably applies to the modern heavy-tailed noise regime, which is closer to practice. Interestingly, our theory is established under the parameter choice

β_1=β_2

, aligning with the recent empirical studies.

Zijian Liu

Department of Technology, Operations, and Statistics Leonard N. Stern School of Business New York University New York, NY 10012, USA

Heavy-Tailed Noise Nonconvex Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Nonsmooth Convex Optimization

Jun 18, 2026cs.LG

On the Oracle Complexity of Interpolation-Based Gradient Descent

Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimization parameters, can be leveraged to improve the oracle complexity of gradient descent (GD) methods. In this paper, we propose an inexact gradient method, piecewise polynomial interpolation-based gradient descent (PPI-GD), which approximates the full gradient in each iteration by querying the first-order oracle at equidistant points in the data domain to construct polynomial interpolants of the resulting gradient samples over appropriately sized patches of the data domain. We analyze the oracle complexity of PPI-GD for strongly convex and non-convex loss functions when the data space dimension is bounded by a polylogarithmic function of the number of training samples, and find it to outperform several GD variants in key regimes when the loss function is sufficiently smooth. Furthermore, our analysis extends several techniques from the error analysis of bicubic spline interpolants to the setting of

d

-variate tensor product polynomial interpolants which may be of independent interest in interpolation analysis.

Dongmin Lee, William Lu, Anuran Makur

Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA · Department of Computer Science and the Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

Oracle Complexity Gradient Descent Nonconvex Optimization Statistical Learning Theory Empirical Risk Minimization

Jun 18, 2026math.OC

Semiglobal Input-Delay Tolerance Algorithm for Distributed Nonconvex Optimization of Networked Nonlinear Systems

This paper studies a class of distributed optimization problems in networked nonlinear systems (NNSs) subject to input delays and consensus constraints. It introduces input-delay tolerant semiglobal convergence (IDTSC), meaning that for any prescribed compact initial set there exists an admissible delay bound under which the optimal solution is computed within consensus constraints and all node states converge to the solution. Building on a hierarchical design and input-to-state stability analysis, a new semiglobal input-delay tolerant (SIDT) algorithm is developed that practically achieves IDTSC for distributed optimization under the coupling between input delays and nonlinear dynamics. Further, by relaxing strict convexity requirements through the Polyak-Łojasiewicz condition, the SIDT algorithm broadens its applicability to nonconvex optimization. Finally, numerical experiments corroborate the theory on NNSs with input delays.

Jing-Zhe Xu, Zhi-Wei Liu, Ming-Feng Ge +2

School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China · School of Mechanical Engineering and Electronic Information, China University of Geosciences, Wuhan 430074, China

Dynamical Systems Optimization Convergence Analysis Distributed Optimization Nonconvex Optimization

Jun 17, 2026cs.CV

Low-Rank Tensor Completion Based on Fractional Regularization with Ky Fan p-k Norm

This paper addresses low-rank tensor completion (LRTC) by proposing a novel nonconvex surrogate, namely the ratio of the tensor nuclear norm to the tensor Ky Fan p-k norm (TNPK), to accurately approximate the tensor tubal rank. The TNPK possesses appealing properties, including scale invariance, parameter flexibility, and the existence of closed-form solutions under specific choices of p and k. With specific parameter settings of p and k, it reduces to the ratio of the tensor nuclear norm to the tensor Ky Fan k norm (TNK) or the ratio of the tensor nuclear norm to the tensor Frobenius norm (TNF). We construct a LRTC model and, under the tensor null space property (NSP), prove that low-rank tensors are local minimizers of the proposed model. Moreover, we derive the proximal operator of the Ky Fan p-k inverse-norm and further develop an efficient alternating direction method of multipliers (ADMM) algorithm with guaranteed subsequential convergence under mild conditions. Extensive experiments on synthetic and real-world datasets validate the superior performance of our method against state-of-the-art competitors.

Shan Fan, Feng Zhang, Jianjun Wang +2

School of Mathematics and Statistics, Southwest University, Chongqing 400715, China · School of Mathematical Sciences/Research Center for Image and Vision Computing, University of Electronic Science and Technology of China, Chengdu 611731, China · Faculty of Computer Science and Control Engineering, Shenzhen University of Advanced Technology, Shenzhen 518055, China

Tensor Completion Nonconvex Optimization Low-Rank Approximation

Jun 15, 2026cs.CC

The Complexity of Min-Max Optimization for Quadratic Polynomials

We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

Bocconi University · Politecnico di Milano · University of Oxford

Min-Max Optimization Nonconvex Optimization

Jun 13, 2026cs.LG

When to use what Schatten- $p$ norm in deep learning?

Schatten-

\infty

based optimizers such as Muon have shown promising empirical performance, but there remains seemingly conflicting observations regarding whether they are beneficial. We resolve this conflict by showing that the conclusion is regime dependent. Even when the objective is smooth in the Schatten-

\infty

geometry, smaller Schatten-

p

geometries can be optimal, specifically in the low-dimensional regime, which we show includes Chinchilla scaling. This conclusion follows from a new noise-robust acceleration result for the SODA framework for

p>2

. The same analysis explains why Muon-like methods do not require warmup, why they naturally favor large batches, and yields a batch size scaling rule for arbitrary

p

.

Thomas Pethick

Deep Learning Optimization Muon Optimizer Nonconvex Optimization Stochastic Optimization Convergence Accelerated Gradient Methods

Jun 12, 2026math.OC

Operator Calculus for Population-Based Optimization: Modular Convergence and Finite-Population Guarantees

Population-based optimizers combine update rules such as mutation, selection, and recombination. When one rule changes, it is often unclear which convergence guarantees survive or how the new combination should be assessed. We develop an operator calculus: an operator is a population-update rule, and the calculus specifies how separately checked effects can be combined. Under explicit regularity and small-step conditions, the leading changes caused by the updates add, yielding reusable building blocks for convergence analysis. The framework distinguishes finding and retaining a good solution, reducing the population's mean objective, and concentrating candidates near an optimizer, and identifies the extra approximation conditions needed for finite evaluation-budget guarantees. Applications include distribution adaptation, recombinative evolution, and consensus dynamics, with verified nonconvex cases. Controlled experiments on a common nonconvex problem collection show how component effects change with population geometry and the performance measure: a rule can worsen the mean objective yet produce better candidates.

Pekka Malo, Lauri Viitasaari, Patrik Nummi +3

Aalto University, Department of Information and Service Management, Finland. · Aalto University, Department of Information and Communications Engineering, Finland. · Indian Institute of Management Ahmedabad, Operations and Decision Sciences, India. +1

Evolutionary Optimization Optimization Convergence Analysis Metaheuristic Optimization Nonconvex Optimization Mean-Field Theory

Jun 3, 2026cs.LG

Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

We study the deterministic first-order oracle complexity of finding

ε

-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions. While the classical

ε^{-2}

rate is optimal under only Lipschitz gradients, higher-order smoothness leads to accelerated first-order upper bounds, most notably the

ε^{-7/4}

rate under Lipschitz Hessians and the

ε^{-5/3}

rate under Lipschitz third derivatives. The matching lower bounds, however, have remained open. We resolve this gap by proving a new dimension-free first-order lower bound for higher-order smooth nonconvex functions, valid for every finite smoothness order. In particular, our construction gives a matching

Ω(ε^{-7/4})

lower bound in the Hessian-Lipschitz case and a matching

Ω(ε^{-5/3})

lower bound in the third-order-smooth regime. The hard instance is based on a \emph{block-chain} mechanism that enforces blockwise oracle revelation while preserving the smoothness structure needed for the scalar hard instance. The lower-bound construction was discovered with the assistance of ChatGPT 5.5 Pro and subsequently verified by the authors.

Dongruo Zhou

Department of Computer Science, Indiana University Bloomington, IN 47408, USA

Optimization Convergence Analysis Nonconvex Optimization

Jun 1, 2026cs.LG

From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization

Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal

O(\sqrt{T})

regret for general convex losses and

O(\log T)

regret under strong convexity. Recent work has shown that Follow-the-Perturbed-Leader (FTPL) achieves optimal

O(\sqrt{T})

regret even for online non-convex Lipschitz losses, assuming access to an approximate offline-optimization oracle, but these guarantees do not exploit curvature. We show that FTPL can be made curvature-adaptive in the non-convex setting, without knowing in advance how curvature will accumulate over time. Our algorithm replaces the fixed perturbation scale of standard FTPL with a time-varying scale chosen using only past information. We give a simple follow-the-leader tuning rule for this scale and show that it competes, up to constants, with the best choice in hindsight. The resulting method achieves

O(\sqrt{T})

regret for arbitrary non-convex Lipschitz losses and improves as cumulative curvature grows; with sufficiently accurate oracle calls, it achieves

O(\log T)

regret when cumulative curvature grows linearly, which includes the classical strongly convex regime. We complement these upper bounds with matching lower bounds for prescribed cumulative-curvature sequences, already for one-dimensional convex losses, showing that the tradeoff between worst-case non-convex regret and curvature-driven fast rates is intrinsic.

Moses Charikar, Chirag Pabbaraju, Ambuj Tewari

Stanford University. · University of Michigan, Ann Arbor.

Online Convex Optimization Nonconvex Optimization

May 31, 2026cs.LG

Learning-based Directed Graph Abstraction of Combinatorial Spaces for Order-Preserving Search in Mixed-Combinatorial Nonlinear Optimization

Mixed-combinatorial nonlinear programming (MCNLP) problems arise in many engineering design and planning applications, e.g., due to categorical, component, and geometric design choices, as well as joint task and motion planning. Traditional representations of combinatorial spaces, such as integer or binary encoding, often introduce spurious relations, increase dimensionality, and require additional compatibility constraints. Instead, this paper draws on recent developments in robot planning and vehicle/network routing domains that aim to learn search heuristics over combinatorial spaces using graph neural networks (GNNs). More specifically, this paper presents a first-of-its-kind structured abstraction of the combinatorial space by learning a mapping from an undirected fully connected graph of combinations to a directed graph indicating improvement directions using an Edge Field Graph Network (EFGN). To demonstrate the utility of this new way of abstracting the combinatorial space in solving MCNLPs, we adopt a recent optimization framework that purely searches over the non-combinatorial (e.g., continuous) variables and retrieves the best-suited combination for each candidate design by using the abstraction model, akin to a recommender system. The presented direction-aware abstraction model provides a potentially more scalable and interpretable retrieval of combinations compared to the original recommendation system in that framework. For evaluation, the proposed method is integrated with a well-known particle swarm optimization and genetic algorithm solvers on three benchmark nonlinear problems with varying numbers of combinations and variables. Compared to baseline solvers using indexified combinations, the GNN-based recommender consistently achieves better mean optimum values and robustness across multiple runs.

Gishnu Madhu, Feng Liu, Souma Chowdhury

University at Buffalo Buffalo, New York, 14260

Graph Structure Learning Graph Neural Networks Nonconvex Optimization Neural Combinatorial Optimization

May 29, 2026cs.LG

GLENS: Global Search via Learning from Solver Iterates with Diffusion Models

We consider the problem of generating a large collection of initial guesses for local minima of multimodal non-convex continuous optimization problems. The goal is for these initial guesses to be high-quality (i.e., a numerical solver converges quickly) and diverse (i.e., represent many different local minima). Identifying multiple locally optimal solutions enables flexible downstream decision-making, but typically requires expensive global search. Existing data-driven methods predict initial guesses using only the final converged optima from offline solver runs, which discards information about the local neighborhoods of solutions and limits the available training data. We propose GLENS (Global Search via Learning from Solver Iterates), a data-efficient global search method that leverages intermediate solver iterates as free data augmentation. GLENS consists of two components: a neighborhood structure model that uses diffusion models to learn the local geometry around optima conditioned on problem parameters, and a solver behavior model that learns refinement directions to further guide samples towards nearby optima during diffusion sampling. Experiments on modified non-convex benchmark problems and a two-robot obstacle-avoidance navigation problem show that GLENS generates high-quality initial guesses while preserving the multimodal distribution of diverse local optima. The resulting initial guesses lead to faster solver convergence across different problem settings and solvers. We also analyze how key hyperparameter choices affect the performance.

Anjian Li, Bartolomeo Stellato, Ryne Beeson

Department of Electrical and Computer Engineering, Princeton University, Princeton, 08544, NJ, USA. · Department of Operations Research and Financial Engineering, Princeton University, Princeton, 08544, NJ, USA. · Department of Mechanical and Aerospace Engineering, Princeton University, Princeton, 08544, NJ, USA.

Learning to Optimize Diffusion Sampling Global Optimization Multimodal Optimization Nonconvex Optimization

May 28, 2026cs.LG

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

Recent work has analyzed the convergence of first-order methods under non-uniform smoothness assumptions that better model the loss landscape in machine learning tasks. We generalize this assumption to objectives whose curvature is an affine function of the objective value. This property is satisfied by a broad class of problems, including logistic regression, generalized linear models with a logistic link function, softmax policy gradient in reinforcement learning, and a class of neural networks. Under this assumption and gradient domination conditions, we establish a general convergence rate for the steepest descent method, and deterministic, diagonal variants of RMSProp and Adam. Our results imply that for logistic regression on separable data and the softmax policy gradient objective, sign GD converges linearly and is provably faster than GD. Furthermore, we show that for a class of two-layer neural networks on separable data, RMSProp and Adam can converge at a linear rate with a constant step-size and momentum parameter. Finally, we present a lower bound demonstrating that, under our assumption, RMSProp and Adam are provably faster than AdaGrad, AMSGrad, gradient descent, and heavy-ball momentum.

Sharan Vaswani, Yifan Sun, Reza Babanezhad

1Simon Fraser University · 2Stony Brook University · 3Samsung AI, Montreal.

Optimization Convergence Analysis Gradient Descent Nonconvex Optimization Adaptive Gradient Methods

May 28, 2026cs.RO

Caspar: CUDA Accelerator for Symbolic Programming with Adaptive Reordering

We present Caspar, a library that makes the power of modern GPUs more accessible in robotics and provides a state-of-the-art nonlinear GPU solver that can be applied to a wide range of different optimization problems. Caspar bridges the gap between expressive symbolic programming in Python and high-performance GPU runtimes in C++ by automatically generating optimized CUDA kernels from symbolic expressions. Building on the SymForce library, users can easily define and combine symbolic expressions, including Lie group operations, to generate custom CUDA kernels. To use Caspar as a solver, users need only define the symbolic residual functions; Caspar then uses symbolic differentiation to generate the necessary GPU kernels and interfaces to perform nonlinear optimization. In this paper, we present the core components of Caspar and showcase its performance by performing bundle adjustment on the Bundle Adjustment in the Large (BAL) dataset. We benchmark Caspar against other state-of-the-art bundle adjusters and show that it is 5 to 20 times faster than the best alternative, requires less memory, and achieves similar accuracy. This illustrates the benefit of our symbolic GPU programming approach. Caspar is released as part of SymForce and is freely available at https://github.com/symforce-org/symforce

Emil Martens, Aaron Miller, Matias Varnum +1

Norwegian University of Science and Technology · Skydio

Bundle Adjustment GPU Kernel Optimization GPU Acceleration High-Performance Computing Nonconvex Optimization GPU Kernel Generation

May 28, 2026math.OC

MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization

In this paper, we study a structured class of nonconvex constrained stochastic problems with difference-of-convex (DC) regularization, where the feasible set is possibly nonconvex and the concave part of the DC regularizer is allowed to be nonsmooth. The fundamental challenge lies in maintaining feasibility for nonconvex constraints while achieving favorable oracle complexity. Although single-loop algorithms efficiently solve unconstrained DC optimization problems, their potential for constrained optimization with DC structure remains largely unexplored. To address this gap, we develop MoSSP, a Momentum-based Single-loop Stochastic Penalty method for such problems with provable complexity guarantees. The key idea is to apply a single stochastic proximal-gradient step to the Moreau envelope of the penalty plus the convex DC part, with the concave part's proximal mapping computed in parallel. We derive two algorithm variants: a Polyak-momentum version with

O(\varepsilon^{-4})

oracle complexity for finding stochastic

\varepsilon

-KKT points, and an improved

O(\varepsilon^{-3})

version incorporating recursive momentum. Experimental results demonstrate the effectiveness of the proposed algorithms.

Luxuan Li, Chunfeng Cui, Xiao Wang

School of Mathematical Sciences, Beihang University, Beijing 100191, China · School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China.

Stochastic Optimization Nonconvex Stochastic Optimization Nonconvex Optimization

May 27, 2026cs.LG

Designing Active Tether-Net Systems for Space Debris Capture with Graph-Learning-Aided Mixed-Combinatorial Optimization

Active tether-net systems are a promising solution for capturing large non-cooperative targets, such as space debris, by deploying a flexible net manipulated by maneuverable units (MUs). However, concurrent systematic explorations of design and control choices of the tether-net system to understand its full potential remain limited, partly due to the complex, constrained, nonlinear optimization problem that it presents -- one that involves a mixture of continuous, integer and categorical variables, with the latter two arising from net connectivity and component choices, respectively. Classical binary encoding methods are often ineffective for solving highly nonlinear and multimodal Mixed Combinatorial Nonlinear Programmings (MCNLPs) in engineering design, while integer coding approaches can introduce spurious relations among combinations. Given the graph-structured characteristics of the combinatorial space, this paper adopts and extends a new graph-learning-aided optimization approach to solve this MCNLP problem. Here, a Graph Neural Network (GNN) is trained to score (as output) and thereof recommend candidate combinations represented as nodes in a graph, with the continuous variable vector portion of a candidate design given as input. As a result, the MCNLP optimization reduces to an NLP, which can be solved using standard solvers. While this reduction approach is agnostic to the choice of the NLP solver, here a state-of-the-art Particle Swarm Optimization (PSO) algorithm with gradient-based fine-tuning is used as the solver. Demonstrated on the problem of concurrently designing the morphology of the net, choice of mass and thrusters in the MUs and aiming points used by the controller of the tether-net system, the GNN-based recommender is shown to provide significantly faster convergence to similar optimal solutions, compared to direct solution of the MCNLP problem.

Feng Liu, Achira Boonrath, Gishnu Madhu +2

University at Buffalo Buffalo, New York, 14260

Metaheuristic Optimization Nonconvex Optimization Neural Combinatorial Optimization

May 24, 2026cs.LG

Theoretical Analysis of Sparse Optimization with Reparameterization, Weight Decay, and Adaptive Learning Rate

Sparse optimization is a fundamental challenge in various practical applications. A popular approach to sparse optimization is

\ell_p

regularization. However, it may encounter optimization instability due to the unbounded gradients when

0<p<1

. In this paper, we introduce a novel approach to sparse optimization termed ReWA, based on Reparameterization, Weight decay, and Adaptive learning rate. ReWA is closely connected to

\ell_p

-regularization, yet it unveils a distinct optimization landscape that helps mitigate instability issues. Experiments on CIFAR-10 and ImageNet with ResNets demonstrate that ReWA leads to significant sparsity improvements over the

\ell_1

-regularization approach while preserving test accuracy.

Huangyu Xu, Jingqin Yang, Qianqian Xu +1

State Key Laboratory of AI Safety, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China · IIIS, Tsinghua University, Beijing, China +3

Nonconvex Optimization

May 23, 2026cs.LG

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a

(δ, ε)

-Goldstein stationary point with zeroth-order oracle complexity of

{\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}})

, where

d

is the problem dimension and

p\in(1,2]

is the order of bounded moments. Note that our dependence on dimension

d

matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters

δ

and

ε

is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.

Zhuanghua Liu, Luo Luo

Stochastic Optimization Gradient Clipping Zeroth-Order Optimization Heavy-Tailed Noise Nonconvex Optimization Nonsmooth Convex Optimization+1

May 22, 2026math.OC

RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs

We study nonsmooth difference-of-convex programs whose subtracted convex term is a finite maximum of smooth convex functions. In this setting, standard DCA iterations may converge to critical points that are not directionally stationary, whereas exact active-vertex screening can be expensive when active sets are large or combinatorial. We propose RA-DCA, a vertex-first randomized active-set DCA that projects active gradients onto sampled directions, checks a sampled vertex residual, and uses a small linear program only as a low-residual convex-combination fallback. The method preserves the descent structure of DCA and reduces the randomized screening layer to matrix multiplications. Under the stated regularity, numerical active-set consistency, and random-embedding assumptions, every accumulation point generated by the safeguarded method is directionally stationary with probability one. MATLAB experiments first test the theorem on degenerate max-affine, max-quadratic, and sparse support-function models, where the safeguard avoids nonstationary critical points and closely tracks a full active-vertex scan. Block top-k tests then show that the same screening idea remains useful when exact aggregate enumeration is combinatorial. Trimmed-regression, complementarity, and QUBO diagnostics separate cases where active-set selection helps from cases dominated by multistart search, the DC split, or other problem-specific features.

Yi-Shuai Niu

Beijing Institute of Mathematical Sciences and Applications (BIMSA), Beijing, China

Nonconvex Optimization

May 22, 2026cs.LG

Convex Compositional Reasoning Models

Compositional energy-based models can generalize to larger combinatorial reasoning problems by reusing a learned factor energy across many local constraints. In our paper, we show that a key bottleneck in compositional reasoning is not composition itself, but the non-convex geometry of the learned energy landscape. To solve this problem, we introduce Convex Compositional Energy Minimization (CCEM), a framework that parameterizes each factor with an input-convex neural network and optimizes the composed energy over a tight convex relaxation of the feasible set. Because convexity is preserved under summation, the global relaxed objective remains convex, enabling deterministic projected first-order optimization. CCEM is trained in two stages: factor-level contrastive learning to shape local energy basins, followed by end-to-end refinement through an unrolled projected solver. Our experiments show that our models trained on small subproblems or a single problem size transfer to larger instances without retraining.

Meir Roketlishvili, Semyon Semenov, Maksim Bobrin +7

Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE · Applied AI Institute, Computational Imaging Lab · AXXX

Compositional Reasoning Energy-Based Models Nonconvex Optimization Input Convex Neural Networks Neural Combinatorial Optimization