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

• URL: http://arxiv.org/abs/2606.28307v1
• Date: Fri, 26 Jun 2026 17:52:39 GMT
• Title: Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization
• Abstract summary: We analyze Bregman ADMM for non linearly constrained problems under two-sided relative smoothness.<n>We extend the analysis to multiblock star consensus formulation for distributed optimization.
• Score: 20.87701856262044
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: 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.

Related papers

• Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy [1.1907026010541673]
  This paper introduces a structural taxonomy for constrained non-constrained optimization based on the signature Lagrange multipliers at KKT stationary points.<n>Four vector-free shape features this partition dual space into five operational regimes: Unconstrained, ResourceLimited, Saturation, Strongly--Coupled, and Hybrid.
  arXiv  Detail & Related papers  (2026-08-31T23:22:05Z)
• Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards [1.370633147306388]
  $text-mathrmNPTS_mathrmSG$ is an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits.<n>We prove that $text-mathrmNPTS_mathrmSG$ achieves regret matching the instance-dependent lower bound to leading order in $log n$.
  arXiv  Detail & Related papers  (2026-06-08T08:26:37Z)
• Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL [8.809468023364703]
  Design of robust reinforcement learning algorithms poses fundamental challenges.<n>We propose an approximate DRRL framework based on a first-order expansion of the relevant robust functional.<n>To learn the fixed point of this approximate equation, we propose Mean-Variance Approximation (MVSA)
  arXiv  Detail & Related papers  (2026-05-08T19:24:28Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms [18.425648833592312]
  We show that tBMM converges to an $ilon$-stationary point within $O(epsilon-2)$. Under a mild iteration, the results still hold when the subproblem is solved in iterations in each provided the total optimality gap is bounded.
  arXiv  Detail & Related papers  (2024-05-05T22:53:14Z)
• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence [25.717501580080846]
  This paper revisits the convergence of gradient Forward Mirror (SMD) in the contemporary non optimization setting. For the training, we develop provably convergent algorithms for the problem of linear networks.
  arXiv  Detail & Related papers  (2024-02-27T17:56:49Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization [2.9112649816695204]
  We study a first order primal-dual method for solving convex-concave saddle point problems over real Banach spaces. Our framework is general and does not need strong convexity of the entropies inducing the Bregman divergences in the algorithm. Numerical applications are considered including entropically regularized Wasserstein barycenter problems and regularized inverse problems on the simplex.
  arXiv  Detail & Related papers  (2021-12-22T14:47:44Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.