CS Paper Radar

Incremental Stability of Gradient Flows under Generalized Polyak-Łojasiewicz Inequalities and Its Implications for General Systems

Andreas Oliveira, Arthur C. B. de Oliveira, Mario Sznaier, Eduardo Sontag

eess.SY math.OC ·submitted 2026-10-29 19:19 UTC · v1

Abstract

Gradient flows of twice continuously differentiable strongly convex and convex objectives are, respectively, incrementally exponentially stable and non-expansive in the Euclidean metric. In this work, we investigate to what extent these properties extend to nonconvex objectives satisfying generalized Polyak-Łojasiewicz inequalities. For objectives with a unique minimizer, we establish conditions under which the gradient flow is contracting in a state-dependent Riemannian metric and incrementally exponentially stable. For objectives with nonunique minimizers, we generalize the non-expansivity of convex objectives to incremental stability for more general nonconvex objectives. We focus on incremental stability due to its implication to convergence to equilibrium points; when paired with a Lyapunov function it implies pointwise convergence to a minimizer and continuity of the endpoint map. Along the way, we derive new structural results for incrementally stable nonlinear systems and extend the analysis to Heavy-Ball and Dynamical Inertial Newton flows.

Closest papers

Nearest neighbours by meaning across the whole index.

SPPID: Saddle-Point PID for Constrained Optimization

eess.SY math.OC ·2026-09-25 ·Veronica Centorrino, Rawan Hoteit, Efe C. Balta, John Lygeros
similarity 0.65
Abstract · 37 pages, 11 figures

This paper studies constrained optimization problems through the lens of feedback control. Building on the interpretation of Lagrange multipliers as feedback controllers, we propose the \emph{saddle-point PID (SPPID) dynamics}: a unified proportional--integral--derivative (PID) framework for continuous-time saddle-point dynamics. The proposed dynamics employ PID control for equality constraints and anti-windup PI control for inequality constraints. We show that SPPID is equivalent to a preconditioned primal--dual gradient flow of the augmented Lagrangian. This equivalence reveals the distinct role of each feedback component: integral action enforces constraint satisfaction, proportional action induces the augmented Lagrangian structure, and derivative action modifies the geometry of the primal dynamics via a state-dependent Riemannian metric. For convex problems, we establish convergence to the KKT set together with conditions for global asymptotic stability. For equality-constrained problems, we establish local exponential convergence for nonlinear equality constraints under standard assumptions, and show that projected gradient flow emerges as the infinite derivative-gain limit. For strongly convex problems with affine equality or inequality constraints, we establish global exponential convergence by leveraging contraction theory. Finally, we provide various numerical examples to illustrate the utility of SPPID.

0.42

Parallel Policy-Gradient Methods for Parameter Optimization of Nonlinear Feedback Controllers

eess.SY math.OC ·2026-09-12 ·An Nguyen, Leilei Cui
similarity 0.64
Abstract

Structured feedback controllers provide rigorous stability guarantees, but often require manual parameter tuning to achieve good closed-loop performance. Policy-gradient methods offer a systematic approach to parameter optimization; however, conventional gradient evaluation requires sequential forward state rollout and backward costate propagation. This letter develops a time-parallel policy-gradient framework for discrete-time nonlinear control-affine systems. We derive the policy-gradient expression where the state and costate rollouts required for policy-gradient evaluation are formulated as residual-minimization problems and solved using Gauss-Newton (GN) iterations with parallel associative scans. For closed-loop systems that are globally asymptotically stable and locally exponentially stable, we show that the residual-minimization problems satisfy a local Polyak-Lojasiewicz (PL) inequality and that the GN iterates converge locally at a quadratic rate. Moreover, the PL constant, the size of the convergence neighborhood, and the quadratic convergence bound are independent of the rollout horizon T. We also prove that, for any finite horizon T, the state solver recovers the exact trajectory from any initialization in at most T iterations. Finally, an inertia-wheel pendulum example with interconnection and damping assignment passivity-based control (IDA-PBC) demonstrates improved closed-loop performance and the computational benefits of the proposed parallel policy-gradient framework.

0.19

Weak Convexity and Proximal Bundle Methods for Nonsmooth Policy Optimization in Robust Control

eess.SY math.OC ·2026-09-05 ·Yuto Watanabe, Feng-Yi Liao, Yang Zheng
similarity 0.63
Abstract · 36 pages, 15 figures

We study policy optimization for discrete-time robust $\mathcal{H}_\infty$ control with static output-feedback, and present the first feasibility-preserving algorithm with a deterministic, non-asymptotic complexity guarantee. This problem naturally leads to a nonsmooth and nonconvex optimization over the set of stabilizing feedback gains. We first establish several structural properties of the $\mathcal{H}_\infty$ cost. In particular, we show that the cost is weakly convex on every convex subset of a sublevel set. For the state-feedback case, we further establish a weak Polyak--Łojasiewicz inequality, which ensures that every stationary point is globally optimal. Building on these properties, we develop a proximal bundle method for $\mathcal{H}_\infty$ policy optimization. The proposed method can be viewed as an implementable approximation of the proximal point method and uses only function value and subgradient information. We show that all iterates remain stabilizing and establish a deterministic non-asymptotic complexity bound of $\mathcal{O}(\max\{η^{-4},ε^{-2}\})$ for finding an $(η,ε)$-stationary point. Numerical experiments illustrate our theoretical results.

0.30

Riemannian ascent--descent for nonconvex nonconcave minimax landscapes: convergence to basin saddle points and applications to distributionally robust optimization

cs.LG math.OCstat.ML ·2026-09-12 ·Rishabh Dixit, Pranav Upadrashta, Alex Cloninger
hot direction similarity 0.62
Abstract

We study a class of distributionally robust optimization (DRO) problems for the statistical risk problem, formulated as minimax problems over the product of a Euclidean space and a Riemannian manifold. Because the resulting minimax landscape is nonconvex nonconcave in general, no globally convergent first order method is known to be available. We instead introduce the notion of a \emph{basin saddle point}, a Nash equilibrium defined locally on the Cartesian product of a $δ$ basin around a connected component of the local minima critical set and a geodesic ball on the measure manifold. We develop an abstract convergence framework for a Riemannian gradient ascent multistep descent iteration to a basin saddle point under a local Łojasiewicz type growth condition, with exponent $β\in (1,2]$, in the $δ$ basin around connected components of the local minima critical sets. Under Lipschitz regularity of critical sets we establish linear convergence for $β= 2$ and polynomial convergence for $β\in (1,2)$ to a basin saddle point, with explicit dependence on the sectional curvature of the manifold. We then instantiate this framework for the statistical risk DRO problem over Gaussian measures, where the ambiguity set is naturally modeled as the product of Euclidean space and the Bures Wasserstein manifold of covariance matrices, which we relax to a penalized DRO formulation. We derive nonasymptotic Hessian estimates for the resulting Lagrangian, establish existence and local uniqueness of its maximizer, and prove that an alternating Riemannian gradient scheme converges to a basin saddle point of the penalized DRO problem, recovering the linear and polynomial rates of the abstract theory with all constants explicit in terms of data dimension, loss moments, and the reference covariance.

0.42

Accelerated Safe Gradient Flow

eess.SY math.OC ·2026-10-01 ·Xuting Gao, Sonia Martínez
similarity 0.60
Abstract · Submitted to IEEE Control Systems Letters

This letter introduces an accelerated safe gradient flow (A-SGF) for strongly convex constrained optimization problems. The A-SGF filters a nominal second-order accelerated flow through a second-order control barrier function quadratic program. We establish conditions for strict feasibility and local Lipschitz continuity of the resulting vector field, prove forward invariance of a lifted safe set, and show that its unique equilibrium is the constrained minimizer. A variational Lyapunov analysis isolates the effect of the safety correction and gives explicit conditions on the barrier gains under which A-SGF retains the same convergence rate as the unconstrained Nesterov accelerated method. A nonlinear 2D example demonstrate anytime feasibility and faster convergence of the algorithm.

0.24

Follow the Regularized Leader Does Not Converge in Constrained Optimization

cs.GT math.OC ·2026-10-26 ·Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm
similarity 0.59
Abstract

Follow the regularized leader (FTRL) is a foundational algorithm in online learning whose regret properties have been extensively studied for decades. However, in stark contrast to mirror descent---and gradient descent in particular---the convergence of FTRL to first-order stationary points in constrained nonconvex optimization was not well understood. In this paper, we show that continuous-time FTRL can fail to converge even asymptotically in infinitely smooth constrained optimization problems: its Karush-Kuhn-Tucker (KKT) gap can remain bounded away from zero indefinitely. This is especially surprising in light of the fact that continuous-time FTRL guarantees a monotonic improvement of the objective value. As a result, we establish that non-convergent behavior of no-regret dynamics---which besets general variational inequality problems---can occur even in potential systems. From a technical standpoint, our construction relies on an infinitely differentiable function where the gradient flow dynamics exhibit decelerating oscillations without ever converging pointwise, which we in turn embed into higher-dimensional FTRL dynamics that sustain a perpetually large KKT gap. We complement our negative result by showing that FTRL with Euclidean regularization does converge when the objective function is analytic. This shows that the analytic property plays a more fundamental role for FTRL than for gradient flow: it governs not only pointwise convergence, but convergence to first-order stationarity itself.

0.19

Non-Euclidean Gradient Descent Has Many Edges of Stability

cs.LG math.OC ·2026-10-10 ·Peter Zaika, Zakhar Shumaylov
theory similarity 0.59
Abstract

Recent observations that deep learning models train at the edge of stability have renewed interest in understanding stability properties of classical optimization algorithms. For quadratic objectives, standard gradient descent has a sharp stability threshold: it converges from every initialization when $η<2/L$, diverges from almost every initialization when $η>2/L$, and diverges from every nonzero initialization when $η>2/μ$. For non-Euclidean gradient descent, the corresponding known guarantees are weaker: convergence holds for every initialization when $η<2/S$, where $S$ is the generalized sharpness, while every nonzero initialization diverges when $η>2/μ$. The behavior in the intermediate regime $2/S<η<2/μ$ is not fully characterized. We show that Hilbertian norms are the only ones for which $2/S$ is an almost-everywhere sharp threshold for every positive-definite quadratic objective. Using linear conjugacy between non-Euclidean and Euclidean gradient descent, we show that for general norms the intermediate regime can contain arbitrarily many edges of stability associated with distinct attracting directions. We identify a forward-invariant region of exponentially divergent directions beyond the generalized stability threshold. When the directions of minimum curvature are finite and nondegenerate, we prove that, sufficiently close to $2/μ$ from below, only their invariant directions remain convergent. We give smooth two-dimensional constructions with arbitrarily many distinct thresholds, arbitrarily large relative threshold separation and show these properties to be stable.

0.12

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

cs.AI math.OCeess.SP ·2026-08-31 ·Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabi
similarity 0.58
Abstract · 45 pages. SNMP

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.

0.24