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 96

May 19, 2026cs.LG

Exploiting Non-Negativity in DAG Structure Learning

This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations generated by a linear structural equation model. DAG learning is a central task in signal processing, machine learning, and causal inference, but it remains challenging because acyclicity is a global combinatorial property. Continuous acyclicity constraints have led to important algorithmic advances by replacing the discrete DAG constraint with smooth equality constraints. However, existing formulations still involve difficult non-convex optimization landscapes and may suffer from degenerate first-order optimality conditions. Here, we restrict attention to DAGs with non-negative edge weights and exploit this additional structure to obtain a simpler characterization of acyclicity. Building on this characterization, we formulate a regularized non-negative DAG learning problem and develop an algorithm based on the method of multipliers. We further analyze the benign optimization landscape induced by non-negativity. In the population regime, we show that the true DAG is the unique global minimizer of the proposed augmented-Lagrangian formulation; moreover, the landscape contains no spurious interior stationary points, and the true DAG is the only acyclic KKT point. Numerical experiments on synthetic and real-world data show that the proposed method improves over state-of-the-art continuous DAG-learning alternatives.

Samuel Rey, Madeline navarro, Gonzalo Mateos

Dept. of Signal Theory and Communications, Universidad Rey Juan Carlos, Madrid, Spain · Dept. of Electrical and Computer Engineering, Rice University, Houston, TX 77005, USA · Dept. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA

Graph Structure Learning Structural Causal Models Causal Structure Learning Nonconvex Optimization Augmented Lagrangian Method Constrained Optimization

May 19, 2026cs.LG

An Exterior Method for Nonnegative Matrix Factorization

Nonnegative matrix factorization (NMF) seeks a low-rank approximation

X \approx UV^T

with nonnegative factors and is commonly solved using interior methods that enforce feasibility throughout optimization. We show that such constraint-driven approaches can impede progress in the nonconvex landscape, leading to slow convergence or convergence to suboptimal stationary points. We propose an exterior framework for NMF (eNMF) that separates low-rank approximation from nonnegativity enforcement. Our method initializes from the optimal unconstrained factorization and introduces a rotation procedure that maps unconstrained factors to an exterior point closest to the nonnegative orthant. This viewpoint yields an algorithmic framework in which simple iterative updates converge to KKT-satisfying stationary points on the boundary of the positive orthant. The exterior formulation also enables a geometric interpretation of NMF solutions, clarifying equivalence classes of factorizations under permutation and orthogonal transformations. An intriguing numerical result, involving 400 NMF experiments across both real and synthetic datasets, show that in 99% of the cases, different algorithms tend to converge towards equivalent factor matrices. We benchmark eNMF against 9 state-of-the-art NMF algorithms with 9 initialization schemes across 3 real-world and 2 synthetic datasets. eNMF consistently outperforms all 81 competitors, achieving up to 30% lower reconstruction error under equal-time settings and up to 150% speedup under equal-error settings. The downstream experiments further demonstrate substantial performance gains in audio processing and recommendation tasks, corroborating the practical benefits of the proposed exterior optimization framework. Code is available at https://github.com/roychowdhuryresearch/eNMF

Qiujing Lu, Tonmoy Monsoor, Ehsan Ebrahimzadeh +2

1ECE, UCLA · 2eBay Search Science Team

Non-Negative Matrix Factorization Low-Rank Matrix Decomposition Nonconvex Optimization Low-Rank Approximation Constrained Optimization Matrix Optimization

May 18, 2026cs.LG

Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization

Muon and related normalized optimizers decouple the choice of update direction from the choice of step scale, but their practical performance remains sensitive to the scale of the normalized step. We study adaptive scaling rules for Muon in general norm geometries and develop three complementary algorithms. For smooth non-convex objectives, we introduce Distance-Adaptive Muon, whose trust-region radius is set from the radius explored by the trajectory, and prove a stationarity guarantee under a bounded-trajectory assumption. We then turn to star-convex objectives, a tractable model of the favorable global geometry often used to reason about the empirical loss landscapes of deep neural networks, where objective-gap guarantees are possible. In this setting, we first introduce Scale-Calibrated Muon, which keeps Muon's exponential moving average but sets the step length from a local descent certificate computed from the current gradient and momentum. For this method, we prove a last-iterate O(1/T) objective-gap bound under a bounded initial sublevel-set assumption, where the corresponding radius parameter appears only in the analysis and not in the algorithm. Finally, we develop Distance-Free Muon, a recentered trust-region method that uses a scalar distance certificate and a majorized one-dimensional search to select the trust-region radius without requiring the unknown distance from the initialization to a global minimizer. Experiments on Transformer language modeling (GPT-124M/WikiText-103) and image classification (ViT-Tiny/CIFAR-100) show that the proposed adaptive scaling rules reduce sensitivity to manual scale tuning and match or improve tuned fixed-scale Muon baselines under the tested budgets.

Yury Demidovich, Abhishek Chakraborty, Grigory Malinovsky +2

King Abdullah University of Science and Technology · Arizona State University

Muon Optimizer Nonconvex Optimization Adaptive Gradient Methods

May 18, 2026cs.LG

Proximal basin hopping: global optimization with guarantees

Global optimization is a challenging problem, with plenty of algorithms displaying empirical success, but scarce theoretical backing. In this work, we propose a new theoretical framework called Proximal Basin Hopping (PBH), carefully tailored to combine proximal optimization and local minimization. We use it to construct a practical algorithm that converges to the global minimizer with high probability, when using a finite amount of samples. Proximal Basin Hopping outperforms well known algorithms with theoretical backing on standard synthetic hard functions, and real problems such as fitting scaling laws for deep learning. Furthermore, the higher the dimension, the better the performance gap.

Guillaume Lauga, Cesare Molinari, Samuel Vaiter

LJAD · LJAD Université Côte d’Azur France · MaLGA +3

Global Optimization Nonconvex Optimization

May 15, 2026cs.LG

Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing

Sampling-based optimization (SBO), like cross-entropy method and evolutionary algorithms, has achieved many successes in solving non-convex problems without gradients, yet its convergence is poorly understood. In this paper, we establish a non-asymptotic convergence analysis for SBO through the lens of smoothing. Specifically, we recast SBO as gradient descent on a smoothed objective, mirroring noise-conditioned score ascent in diffusion models. Our first contribution is a landscape analysis of the smoothed objective, demonstrating how smoothing helps escape local minima and uncovering a fundamental coverage-optimality trade-off: smoothing renders the landscape more benign by enlarging the locally convex region around the global minimizer, but at the cost of introducing an optimality gap. Building on this insight, we establish non-asymptotic convergence guarantees for SBO algorithms to a neighborhood of the global minimizer. Furthermore, we propose an annealed SBO algorithm, Diffusion-Inspired Dual-Annealing (DIDA), which is provably convergent to the global optimum. We conduct extensive numerical experiments to verify our landscape results and also demonstrate the compelling performance of DIDA compared to other gradient-free optimization methods. Lastly, we discuss implications of our results for diffusion models.

Zeji Yi, Chaoyi Pan, Guanya Shi +1

Carnegie Mellon University

Optimization Convergence Analysis Black-Box Optimization Global Optimization Nonconvex Optimization Stochastic Optimization Convergence Derivative-Free Optimization

May 13, 2026cs.DS

Min-Max Optimization Requires Exponentially Many Queries

We study the query complexity of min-max optimization of a nonconvex-nonconcave function

f

over

[0,1]^d \times [0,1]^d

. We show that, given oracle access to

f

and to its gradient

\nabla f

, any algorithm that finds an

\varepsilon

-approximate stationary point must make a number of queries that is exponential in

1/\varepsilon

or

d

.

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

Bocconi University · Politecnico di Milano · University of Oxford

Query Complexity Oracle Complexity Min-Max Optimization Nonconvex Optimization

May 11, 2026math.OC

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine (PA) functions, a basic task in nonsmooth optimization. PA functions form a canonical model for nonsmooth stationarity testing and capture the local polyhedral geometry that appears in ReLU-type training losses. Recent work by Tian and So (SODA 2025) shows that testing approximate stationarity notions for PA functions is computationally intractable in the worst case, and identifies fixed-dimensional tractability as an open direction. We address this direction from the viewpoint of parameterized complexity, with the ambient dimension

d

as the parameter. In this paper, we give XP algorithms in fixed dimension for the tractable sides, and prove W[1]-hardness for the complementary sides. Moreover, lower bounds under the Exponential Time Hypothesis rule out algorithms running in time

ρ(d)\size^{o(d)}

for any computable function

ρ

, where

\size

denotes the total binary encoding length of the stationarity-testing instance. As a further consequence, our results yield the corresponding parameterized complexity picture for testing local minimality of continuous PA functions. We further extend our hardness results to a family of shallow ReLU CNN training losses, with stationarity tested in the trainable weight space. Thus, the same parameterized-complexity picture also appears for simple CNN training losses.

Yuhan Ye

MIT

Shallow Neural Networks Nonconvex Optimization Parameterized Complexity Nonsmooth Convex Optimization

May 11, 2026cs.LG

Fix the Loss, Not the Radius: Rethinking the Adversarial Perturbation of Sharpness-Aware Minimization

Sharpness-Aware Minimization (SAM) improves generalization by minimizing the worst-case loss within a fixed parameter-space radius neighborhood. SAM and its variants mainly rely on a first-order linearized surrogate, while flat minima are inherently a second-order (curvature) notion.We revisit this mismatch and propose Loss-Equated SAM (LE-SAM), which inverts the traditional SAM mechanism that fixed perturbation radius with a fixed loss-space budget,effectively removing gradient-norm-dominated learning signals and shifting optimization toward curvature-dominated terms. Extensive experiments across diverse benchmarks and tasks demonstrate the strong generalization ability of LESAM that consistently outperforms SAM and even its variants, achieving the state-of-the-art performance.

Jinping Wang, Qinhan Liu, Zhiwu Xie +1

Wenzhou-Kean University · International Frontier Interdisciplinary Research Institute, Wenzhou-Kean University

Neural Network Generalization Sharpness-Aware Minimization Deep Learning Optimization Nonconvex Optimization Flat Minima

May 10, 2026cs.LG

Dimension-Free Saddle-Point Escape in Muon

Modern Large Language Model (LLM) training is fundamentally bottlenecked by pathologically flat saddle points in extreme high-dimensional landscapes. Motivated by this challenge, we analyze the saddle-point escape dynamics of the emerging Muon optimizer, demonstrating its resilience against the

\mathcal{O}(D)

dimensional curse that severely traps element-wise adaptive optimizers like AdamW. By extending generalized matrix perturbation theory, we develop a theoretical framework to capture Muon's non-equilibrium optimization trajectories. This theoretical machinery mathematically proves that Muon elegantly bypasses the dimensional curse via a non-linear spectral shaping mechanism. By leveraging resolvent functional calculus and macroscopic Cauchy contour integration, we avoid isotropic noise assumptions and Tracy-Widom edge singularities. We establish that structural incoherence securely shields the trajectory from orthogonal drift, enabling a dimension-free saddle-point escape, and triggering a deterministic

\mathcal{O}(1)

discrete ballistic ejection under sufficient spectral gap. Consequently, we provide an algebraically dimension-free escape bound for Muon, formalizing the underlying mechanics of its non-convex optimization dynamics.

Yanlin Long, Yufei Gu, Zeke Xie

xLeaF Lab, The Hong Kong University of Science and Technology (Guangzhou)

Muon Optimizer Nonconvex Optimization Gradient Descent Dynamics

May 9, 2026math.OC

Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets

We study optimistic bilevel optimization when the lower-level problem has a non-isolated manifold of minimizers. In this setting, the hyper-objective may be non-differentiable because the upper-level criterion must choose among multiple lower-level solutions. Under a local Polyak--Łojasiewicz (PŁ) condition, we show that differentiability does not require the lower-level solution set to be a singleton: uniqueness of the optimistic selection is sufficient. This yields an explicit pseudoinverse-based hyper-gradient formula extending the classical singleton-minimizer result. We further characterize the regularity of the hyper-objective: non-degeneracy of the selected minimizer along the solution manifold yields local smoothness, while failure of uniqueness can create many non-differentiable points and failure of non-degeneracy can destroy all positive Hölder regularity of the hyper-gradient. Motivated by this theory, we propose HG-MS, a select-then-differentiate method combining explicit optimistic selection with efficient pseudoinverse-based hyper-gradient computation. Despite the nonconvex nature of optimistic selection over the lower-level solution manifold, we show that HG-MS converges to a stationary point of the optimistic objective with complexity governed by the intrinsic dimension of the solution manifold rather than its ambient dimension. Empirically, we test a practical variant of HG-MS for matched-budget LLM source reweighting. This variant preserves the select-then-differentiate principle and obtains the best GSM8K/MATH scores across the tested backbones, along with competitive or best MT-Bench instruction-following results.

Saeed Masiha, Zebang Shen, Negar Kiyavash +1

EPFL School of Management of Technology, Station 5, 1015 Lausanne, Switzerland · ETH Department of Computer Science, Universitätstrasse 6, 8092 Zürich, Switzerland

Nonconvex Optimization Bilevel Optimization Differentiable Optimization

May 9, 2026cs.LG

FedVSSAM: Mitigating Flatness Incompatibility in Sharpness-Aware Federated Learning

Sharpness-aware minimization (SAM) is an effective method for improving the generalization of federated learning (FL) by steering local training toward flat minima. Under data heterogeneity, however, device-side SAM searches for locally flat basins that are incompatible with the flat region preferred by the global objective. We identify this structural failure mode as flatness incompatibility, which explains why improving local flatness alone may provide limited training and generalization improvement for the global model. We reveal that flatness incompatibility arises from data heterogeneity and the friendly adversary phenomenon, and is further amplified by local updates and partial device participation. To mitigate this issue, we propose Federated Learning with variance-suppressed sharpness-aware minimization (FedVSSAM), which constructs a variance-suppressed adjusted direction and uses it consistently in local flatness search, local descent, and global update. FedVSSAM anchors both perturbation and update directions to a more stable global direction, instead of correcting only an isolated local perturbation. We establish non-convex convergence guarantees of FedVSSAM and prove that the mean-square deviation between the adjusted direction and the global gradient is effectively controlled. Experiments demonstrate that FedVSSAM mitigates flatness incompatibility and outperforms the baselines across diverse FL settings.

Bingnan Xiao, Yuan Gao, Bingcong Li +3

Fudan University · ETH Zurich · Edith Cowan University +1

Sharpness-Aware Minimization Non-IID Federated Learning Nonconvex Optimization Flat Minima Federated Learning Heterogeneous Federated Learning

May 8, 2026cs.CE

Exploring the non-convexity in machine learning using quantum-inspired optimization

The escalating complexity of modern machine learning necessitates solving challenging non-convex optimization problems, particularly in high-dimensional regimes and scenarios contaminated by gross outliers. Traditional approaches, relying on convex relaxations or specialized local search heuristics, frequently succumb to suboptimal local minima and fail to recover the true underlying discrete structures. In this paper, we propose treating these non-convex challenges as a global search problem and introduce a unified framework based on Quantum-Inspired Evolutionary Optimization (QIEO). By leveraging a probabilistic representation inspired by quantum superposition, QIEO maintains a global view of the search space, enabling it to tunnel through local optima that trap conventional gradient-based and greedy solvers. We comprehensively evaluate QIEO across diverse non-convex applications, including sparse signal recovery (gene expression analysis and compressed sensing) and robust linear regression. Extensive benchmarking against state-of-the-art continuous solvers (ADAM, Differential Evolution), classical metaheuristics (Genetic Algorithms), and specialized non-convex algorithms (Iterative Hard Thresholding) demonstrates that QIEO consistently achieves superior structural fidelity, lower mean squared error, and enhanced robustness without support inflation. Our findings suggest that embracing a quantum-inspired global search provides a resilient, unified paradigm for overcoming the inherent intractability of discrete nonconvex machine learning landscapes.

Kandula Eswara Sai Kumar, Parth Dhananjay Danve, Abhishek Chopra +1

1*BosonQ Psi (BQP), New York, USA.

Evolutionary Optimization Quantum-Inspired ML Nonconvex Optimization Linear Regression

May 8, 2026cs.LG

Flatness and Gradient Alignment Are Both Necessary: Spectral-Aware Gradient-Aligned Exploration for Multi-Distribution Learning

Sharpness-aware and gradient-alignment methods have been shown to improve generalization, however each family of methods targets a single geometric property of the loss landscape, while ignoring the other. In this paper, we show that this omission is structurally unavoidable and that both flatness and gradient alignment should be considered in multi-distribution learning settings. Specifically, we derive an excess-risk decomposition that yields two additive leading-order terms: (i) an alignment term, controlled by the trace of

\bar{H}^{-1}Σ_g

and (ii) a curvature term, controlled by

\bar{H}

, where

\bar{H}

is the average Hessian and

Σ_g

is the covariance of the gradient across distributions. Notably,

\bar{H}

appears inverted in one and non-inverted in the other. We further show, via a counterexample, that neither quantity bounds the other in general, so no algorithm targeting only one term can guarantee low excess risk. Motivated by this decomposition, we propose SAGE (Spectral-Aware Gradient-Aligned Exploration) that targets both terms. The curvature component replaces SAM's gradient-scaled perturbation with the polar factor of each layer's gradient matrix, computed via Newton-Schulz iteration, so that the ascent step probes all directions with similar magnitude. On the other hand, the alignment component injects isotropic noise at the descent step, the magnitude of which scales with cross-distribution gradient disagreement. Experiments on five domain-generalization and two multi-task learning benchmarks show that the proposed method establishes a new state-of-the-art on DomainBed and acts as a general-purpose improvement to base MTL solvers, remaining competitive with, or even surpassing, state-of-the-art methods.

Aristotelis Ballas, Christos Diou

Department of Informatics and Telematics Harokopio University of Athens Omirou 9, Athens, Greece

Sharpness-Aware Minimization Multi-Task Learning Cross-Domain Generalization Nonconvex Optimization Statistical Learning Theory Gradient Alignment

May 7, 2026stat.ML

Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions

This paper presents a parametric solution to piecewise linear regression through the Adaptive Block Gradient Descent (ABGD) algorithm. The heart of the method is the parametrization of piecewise linear functions as the difference of max-affine (DoMA) functions. A non-asymptotic local convergence analysis for ABGD is provided under sub-Gaussian covariate and noise distributions. To initialize ABGD, we adapt a prior algorithm originally developed for the simpler setting of max-affine functions. When suitably initialized, ABGD converges linearly to an

ε

-accurate estimate given

\tilde{\mathcal{O}}(d\max(σ_z/ε,1)^2)

observations where

σ_z^2

denotes the noise variance. This implies exact recovery given

\tilde{\mathcal{O}}(d)

samples in the noiseless case. Also, such a rate is shown to be minimax optimal up to logarithmic factors. Synthetic numerical results corroborate the theoretical guarantees for ABGD. We also observe competitive performance compared to the state-of-the-art methods on real-world datasets.

Haitham Kanj, Kiryung Lee

Department of Electrical and Computer Engineering The Ohio State University, Columbus, OH, USA

Gradient Descent Sample Complexity Nonconvex Optimization Linear Regression Stochastic Optimization Convergence

May 7, 2026cs.LG

When Descent Is Too Stable: Event-Triggered Hamiltonian Learning to Optimize

Fixed-budget nonconvex optimization can fail not because local descent is unstable, but because it is too stable: after reaching a nearby stationary point, an optimizer may spend the remaining evaluations refining an uninformative local minimum. We formulate this failure mode as a control problem over optimizer dynamics, where the learner must decide when to descend, when to exploit a promising basin, and when stagnation should trigger movement elsewhere. We introduce SHAPE, a structured adaptive port-Hamiltonian task-family optimizer for event-triggered minima hunting under local information. Starting from gradient-descent dynamics, SHAPE lifts optimization to an augmented phase space

(q, p)

, where the primal state

q

represents the candidate solution, the cotangent variable

p

carries directional sensitivity, and a controller

u

provides processed information from current gradient oracle. Within each stage, a learned Hamiltonian vector field induces structured local descent; across stages, a fixed event clock in the implementation updates ports and memory when local equilibria are detected, with stage-dependent horizons treated in the analysis as a direct generalization. This design preserves a passivity-compatible structure while allowing the same trained policy to use clean, stochastic, or estimated gradient inputs. Experiments on fixed-budget nonconvex optimization tasks show that SHAPE improves best-so-far performance compared with fixed-policy optimizers. These results suggest that adaptive Hamiltonian energy shaping provides a principled mechanism for balancing descent, exploration, and budget allocation in difficult optimization landscapes.

Yi Wang, Chandrajit Bajaj

1Oden Institute · Department of Computer Science

Dynamical Systems Learning to Optimize Nonconvex Optimization Event-Triggered Control Port-Hamiltonian Systems Hamiltonian Dynamics

May 6, 2026stat.ML

Convexity in Disguise: A Theoretical Framework for Nonconvex Low-Rank Matrix Estimation

Nonconvex methods have emerged as a dominant approach for low-rank matrix estimation, a problem that arises widely in machine learning and AI for learning and representing high-dimensional data. Existing analyses for these methods often require additional regularization to mitigate nonconvexity, even though such regularization is often unnecessary in practice. Moreover, most analyses rely on problem-specific arguments that are difficult to generalize to more complex settings. In this paper, we develop a theoretical framework for studying nonconvex procedures across a broad class of low-rank matrix estimation problems. Rather than focusing on a specific model, we reveal a fundamental mechanism that explains why nonconvex procedures can behave well in low-rank estimation. Our key device is a {\it benign regularizer} that does not alter the original update rule, but yields an equivalent locally strongly convex formulation of the algorithm. This perspective uncovers a disguised convexity inherent in the nonconvex procedure and provides a new route to theoretical guarantees for nonconvex low-rank matrix estimation.

Chengyu Cui, Gongjun Xu

Department of Statistics, University of Michigan

Nonconvex Optimization

May 6, 2026cs.LG

Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS

We introduce Graph Normalization (GN), a principled dynamical system on graphs that serves as a differentiable approximation engine for the NP-hard Maximum Weight Independent Set (MWIS) problem. MWIS encompasses many combinatorial challenges, including optimal assignment, scheduling, set packing, and MAP inference in discrete Markov Random Fields. Unlike Belief Propagation, we prove GN always converges to a binary indicator of a Maximum Independent Set. GN realizes a fast quasi-Newton descent through an exact Majorization-Minimization step, systematically improving the MWIS relaxed primal objective. We establish an equivalence between GN and the Replicator Dynamics of a nonlinear evolutionary game, where vertices compete for inclusion in an independent set. While a non-potential game, the GN game follows Fisher's Fundamental Theorem of Natural Selection, where the average fitness equals the MWIS primal objective and strictly increases. This connection leads to a weighted extension of the Motzkin-Straus theorem, showing MISes are in bijection with the local minima of a quadratic form over a tilted simplex. For the Assignment Problem, GN acts as a variant of the Sinkhorn algorithm that naturally converges to a hard assignment while generalizing to arbitrary constraint graphs. We demonstrate GN's performance as a fast binarization engine for the state-of-the-art Bregman-Sinkhorn relaxed MWIS solver. On real-world benchmarks with up to 1M edges, GN identifies solutions within 1% of the best known results in seconds on a CPU. GN opens new avenues for deep learning architectures requiring differentiable, "hard" decisions under constraints, with applications in structured sparse attention, dynamic network pruning, and Mixture-of-Experts. Beyond core AI, the GN framework enables end-to-end learning of constrained optimization in computer vision, computational biology, and resource allocation.

Laurent Guigues

Dynamical Systems Replicator Dynamics Combinatorial Optimization Nonconvex Optimization Differentiable Optimization

May 5, 2026cs.LG

A Provably Convergent and Practical Algorithm for Gromov--Wasserstein Optimal Transport

Gromov--Wasserstein optimal transport (GWOT) aligns metric measure spaces by matching their within-domain relational structures, but large-scale GWOT remains challenging because its objective is nonconvex and projection onto the transport polytope is often solved only approximately in practice. This leads to a gap between practical projected-gradient implementations and convergence theory, which typically assumes exact projections. For squared-loss GWOT, we propose an inexact projected-gradient framework with a verifiable feasibility-residual-based inexact condition for the projection subproblem. This condition is directly computable and avoids unknown quantities such as the exact projection point. Under this implementable condition, we prove subsequential convergence to stationary points and, with a mild tolerance-decay condition, convergence of the whole sequence. The resulting method retains the simplicity and sparsity of projected-gradient schemes while providing rigorous convergence guarantees, turning projected-gradient methods into a principled and scalable approach for GWOT with provable reliability.

Ling Liang, Lei Yang

Department of Mathematics The University of Tennessee Knoxville, TN 37916, USA · School of Computer Science and Engineering Guangdong Province Key Laboratory of Computational Science Sun Yat-sen University Guangzhou, Guangdong 510275, China

Gradient Descent Nonconvex Optimization Constrained Optimization Optimal Transport

May 4, 2026math.OC

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate

We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve

O(ε^{-5/3}\log(1/ε))

oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.

Sichao Xiong, Sadok Jerad, Coralia Cartis

Department of Computer Science University of Oxford Oxford, OX1 3QG · Mathematical Institue University of Oxford Oxford, OX2 6GG

Optimization Convergence Analysis Gradient Descent Nonconvex Optimization Accelerated Gradient Methods

Apr 25, 2026cs.LG

A Layer Separation Optimization Framework for Cross-Entropy Training in Deep Learning

This paper investigates the deep learning optimization problem with softmax cross-entropy loss. We propose a layer separation strategy to alleviate the strong nonconvexity encountered during training deep networks. For cross-entropy models with fully connected and convolutional neural networks, we introduce auxiliary variables associated with hidden layer outputs and construct corresponding layer separation models, which decompose the original deeply nested optimization problem into a sequence of more manageable subproblems. We also conduct theoretical analyses, proving that the new layer separation loss provides an upper bound for the original cross-entropy loss. Moreover, we design alternating minimization algorithms and prove that, under appropriate conditions, these algorithms exhibit decreasing properties of the loss function. Numerical experiments validate the effectiveness of the proposed methods and indicate improved optimization behavior, especially for fully connected and convolutional neural networks.

Yaru Liu, Michael K. Ng, Yiqi Gu

School of Mathematical Sciences, University of Electronic Science and Technology of China, Sichuan 611731, China · Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, China

Deep Learning Optimization Nonconvex Optimization

Apr 25, 2026cs.IT

A Unified Fractional Regularization Framework for Sparse Recovery

We propose a unified fractional regularization framework for sparse signal recovery based on the

\ell_1/\ell_p^q

model. This model generalizes several widely used sparsity-promoting regularizers and provides additional flexibility through the parameters

p

and

q

. Our main theoretical contribution is the characterization of the equivalence between the first-order stationary points of the

\ell_1/\ell_p^q

formulation and the subtractive

\ell_1-α\ell_p

model, thereby offering a unified perspective on these nonconvex regularizers. In addition, we establish a new sufficient recovery condition under the Restricted Isometry Property (RIP), which shows that the proposed framework can provide relaxed recovery guarantees and improved robustness. To solve the resulting nonconvex problem, we develop a majorization--minimization (MM) algorithm and prove its convergence by using the Kurdyka--Łojasiewicz (KL) property. Numerical experiments on sparse recovery problems with different sensing matrices and MRI reconstruction demonstrate that the proposed approach outperforms existing methods in recovery accuracy.

Yinhao Zhao, Haoyu He, Chuanqi Ma +1

School of Information Science and Technology, ShanghaiTech University, 201210

Sparse Recovery Nonconvex Optimization

Apr 21, 2026cs.GR

An Efficient Multilevel Preconditioned Nonlinear Conjugate Gradient Method for Incremental Potential Contact

Incremental Potential Contact (IPC) guarantees intersection-free simulation but suffers from high computational costs due to the expensive Hessian assembly and linear solves required by Newton's method. While Preconditioned Nonlinear Conjugate Gradient (PNCG) avoids Hessian assembly, it has historically struggled with poor convergence in stiff, contact-rich scenarios due to the lack of effective preconditioners; simple Jacobi preconditioners fail to capture the global coupling, while advanced hierarchy-based preconditioners like Multilevel Additive Schwarz (MAS) are computationally prohibitive to rebuild at every nonlinear iteration. We present MAS-PNCG, a method that unlocks the power of hierarchical preconditioning for nonlinear optimization. Our key technical innovation is a Sparse-Input Woodbury update algorithm that incrementally adapts the fine-level MAS components to rapidly evolving contact sets. This bypasses the need for full preconditioner rebuilds, reducing maintenance cost to near-zero while capturing the complex spectral properties of the contact system. Furthermore, we replace heuristic PNCG search directions with a Hessian-aware 2D subspace minimization that optimally combines the preconditioned gradient and previous direction. We also apply a fast per-subdomain conservative CCD method that ensures penetration-free trajectories while avoiding overly restrictive global step sizes. Experiments demonstrate that our MAS-PNCG outperforms state-of-the-art Newton-PCG solvers, GIPC and StiffGIPC, both preconditioned with MAS up to 5.66

\times

and 2.07

\times

respectively.

Yu Zhang, Xing Shen, Kemeng Huang +5

S-Lab, Nanyang Technological University, Singapore · Shanghai AI Laboratory, China · University of Hong Kong, China +3

Nonconvex Optimization

Apr 18, 2026cs.LG

Towards Fully Parameter-Free Stochastic Optimization: Grid Search with Self-Bounding Analysis

Parameter-free stochastic optimization aims to design algorithms that are agnostic to the underlying problem parameters while still achieving convergence rates competitive with optimally tuned methods. While some parameter-free methods do not require the specific values of the problem parameters, they still rely on prior knowledge, such as the lower or upper bounds of them. We refer to such methods as partially parameter-free''. In this work, we target achieving fully parameter-free'' methods, i.e., the algorithmic inputs do not need to satisfy any unverifiable condition related to the true problem parameters. We propose a powerful and general grid search framework, named \textsc{Grasp}, with a novel self-bounding analysis technique that effectively determines the search ranges of parameters, in contrast to previous work. Our method demonstrates generality in: (i) the non-convex case, where we propose a fully parameter-free method that achieves near-optimal convergence rate, up to logarithmic factors; (ii) the convex case, where our parameter-free methods are competitive with strong performance in terms of acceleration and universality. Finally, we contribute a sharper guarantee for the model ensemble, a final step of the grid search framework, under interpolated variance characterization.

Yuheng Zhao, Yu-Hu Yan, Amit Attia +3

National Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · Tel Aviv University

Stochastic Optimization Nonconvex Stochastic Optimization Nonconvex Optimization

Mar 11, 2026cs.RO

ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets

This paper presents a numerical solver for computing continuous trajectories in non-convex environments. Our approach relies on a customized implementation of the Alternating Direction Method of Multipliers (ADMM) built upon two key components: First, we parameterize trajectories as polynomials, allowing the primal update to be computed in closed form as a minimum-control-effort problem. Second, we introduce the concept of a spatio-temporal allocation graph based on a mixed-integer formulation and pose the slack update as a shortest-path search. The combination of these ingredients results in a solver with several distinct advantages over the state of the art. By jointly optimizing over both discrete and continuous domains, our method accesses a larger search space than existing decoupled approaches, enabling the discovery of superior trajectories. Additionally, the solver's structural robustness ensures reliable convergence from naive initializations, removing the bottleneck of complex warm starting in non-convex environments.

Lukas Pries, Jon Arrizabalaga, Zachary Manchester +1

Autonomous Aerial Systems Lab, Dep. of Aerospace and Geodesy, TU Munich, Germany · Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, USA

Trajectory Optimization Alternating Direction Method of Multipliers Nonconvex Optimization Constrained Optimization Motion Planning

Dec 5, 2025stat.ML

BalLOT: Balanced $k$ -means clustering with optimal transport

We consider the fundamental problem of balanced

k

-means clustering. In particular, we introduce an optimal transport approach to alternating minimization called BalLOT, and we show that it delivers a fast and effective solution to this problem. We establish this with several theoretical guarantees and a variety of numerical experiments. On the theory front, we first prove that for generic data, BalLOT produces integral couplings at each step. Next, we perform a landscape analysis to provide theoretical guarantees for both exact and partial recoveries of planted clusters under the stochastic ball model. We also propose initialization schemes that achieve one-step recovery of planted clusters. To conclude, we present numerical experiments that corroborate our theoretical results.

Wenyan Luo, Dustin G. Mixon

Department of Mathematics, The Ohio State University, Columbus, Ohio, USA · Translational Data Analytics Institute, The Ohio State University, Columbus, Ohio, USA

Clustering Nonconvex Optimization

Nov 27, 2025math.OC

On the Condition Number Dependency in Bilevel Optimization

Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an

ε

-stationary point with first-order methods when the upper-level problem is nonconvex, and the lower-level problem is strongly convex. Recent works (Ji et al., ICML 2021; Arbel and Mairal, ICLR 2022; Chen et al., JMLR 2025) achieve a

\tilde{\mathcal{O}}(\bar κ_y^4 ε^{-2})

upper bound that is near-optimal in

ε

, which can be reduced to

\tilde{\mathcal{O}}(\bar κ_y^{7/2} ε^{-2})

by a naive application of Nesterov acceleration in the inner loop, where

\bar κ_y

is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new

Ω(κ_y^{5/2} ε^{-2})

lower bound, where

κ_y < \bar κ_y

is the lower-level condition number that is of the same order as

\bar κ_y

when the smoothness constants are

\mathcal{O}(1)

. Our lower bound establishes the first provable gap in terms of condition number dependency between bilevel problems and minimax problems in this setup. Our lower bounds can be extended to various settings, including high-order smooth functions, stochastic oracles, and convex hyper-objectives: (1) For second-order and arbitrarily smooth problems, we show lower bounds of

Ω({κ_y^{31/14}} ε^{-12/7})

and

Ω(κ_y^{21/10} ε^{-8/5})

, respectively. (2) For convex-strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from

Ω(κ_y /\sqrtε)

to

Ω(κ_y^{3/2} / \sqrtε)

. (3) For smooth stochastic problems, we also show a lower bound of

Ω(κ_y^4 ε^{-4})

.

Lesi Chen, Jingzhao Zhang

IIIS, Tsinghua University

Nonconvex Optimization Bilevel Optimization

Nov 24, 2025math.OC

Anytime-Feasible First-Order Optimization via Safe Sequential QCQP

This paper presents the Safe Sequential Quadratically Constrained Quadratic Programming (SS-QCQP) algorithm, a first-order method for smooth inequality-constrained nonconvex optimization that guarantees feasibility at every iteration. The method is derived from a continuous-time dynamical system whose vector field is obtained by solving a convex QCQP that enforces monotonic descent of the objective and forward invariance of the feasible set. The resulting continuous-time dynamics achieve an

O(1/t)

ergodic convergence rate for the stationarity measure under standard constraint qualification conditions. We then propose a safeguarded Euler discretization with adaptive step-size selection that preserves this convergence rate while maintaining both descent and feasibility in discrete time. To enhance scalability, we develop an active-set variant (SS-QCQP-AS) that selectively enforces constraints near the boundary, substantially reducing computational cost without compromising theoretical guarantees. Numerical experiments on a multi-agent nonlinear optimal control problem demonstrate that SS-QCQP and SS-QCQP-AS maintain feasibility, exhibit the predicted convergence behavior, and deliver solution quality comparable to second-order solvers such as SQP and IPOPT.

Jiarui Wang, Mahyar Fazlyab

Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD 21218 USA

Constrained Optimization Nonconvex Optimization

Nov 17, 2025math.OC

Power Homotopy for Zeroth-Order Non-Convex Optimizations

The existing method of GS-PowerOpt solves the non-convex optimization problem of the form

\max_{\boldsymbol{x} \in \mathbb{R}^d} f(\boldsymbol{x})

through maximizing a Gaussian-smoothed surrogate

F_{N,σ}(\boldsymbolμ) = \mathbb{E}_{\boldsymbol{x}\sim\mathcal{N}(\boldsymbolμ,σ^2 I_d)}[e^{N f(\boldsymbol{x})}]

. We analyze the role of the smoothing radius

σ>0

and identify a limitation of the fixed-

σ

design used in GS-PowerOpt. Specifically,

σ

induces an inherent exploration--refinement tradeoff: a larger

σ

improves global exploration and finite-time surrogate optimization, but may distort the location of the surrogate maximizer; in contrast, a smaller

σ

better preserves local structure but can weaken gradient signals away from high-value regions. To address this limitation, we propose GS-PowerHP, a power-smoothed homotopy method with an incrementally decaying

σ

schedule. The proposed mechanism uses larger smoothing radii in early iterations to maintain informative gradient signals when the iterate is far from high-value regions, and gradually decreases

σ

to improve local refinement near the maximizer. We provide theoretical results showing that this decaying schedule improves the exploration--refinement tradeoff of fixed-

σ

power smoothing. Empirically, GS-PowerHP consistently outperforms the fixed-

σ

baseline and exhibits robust performance across different optimization tasks, including adversarial attacks on ImageNet (

d=150{,}528

), where it substantially improves over other smoothing-based zeroth-order methods.

Chen Xu

Department of Engineering, Shenzhen MSU-BIT University, China.

Zeroth-Order Optimization Nonconvex Optimization

Nov 3, 2025math.OC

Disciplined Biconvex Programming

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

Hao Zhu, Joschka Boedecker

IMBIT//BrainLinks-BrainTools · Department of Computer Science, University of Freiburg

Nonconvex Optimization Constrained Optimization

Nov 3, 2025cs.LG

The Optimization Landscape of Carathéodory Decomposition of Toeplitz Covariances

Toeplitz covariance estimation is a classical problem in statistical signal processing, yet the geometry of the Gaussian maximum-likelihood objective remains only partially understood. Recent algorithms, including Newton-type, majorization-minimization, and gradient-based methods, indicate that the nonconvex problem can often be globally solved when the number of samples is sufficiently large, but they also reveal a difficult computational landscape. In this work, we study this phenomenon through an overparameterized Caratheodory representation of positive definite Toeplitz covariance matrices. The Caratheodory decomposition parameterizes the covariance using a combination of steering vectors with different frequencies and amplitudes. Our first result shows that fixed-grid amplitude optimization is fundamentally insufficient. Even in the population setting, and even with arbitrarily many fixed frequency grid points, amplitude-only optimization can have a strictly positive error floor under grid mismatch. This motivates optimizing both amplitudes and frequencies. In this case, our main theoretical result proves that the joint optimization has a benign population landscape: every stationary point that produces a positive definite covariance matrix recovers the true Toeplitz covariance. These findings suggest a simple interpretation of the Toeplitz covariance problem: the population landscape is globally benign, but may be highly ill-conditioned. In our numerical experiments, overparameterization improves convergence speed and finite-sample accuracy. In particular, it allows simple gradient descent to approach the Cramer Rao bound while keeping the implementation simple.

Daniel Busbib, Ami Wiesel

School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem 91904, Israel

Nonconvex Optimization Matrix Optimization Covariance Estimation