Jun 2026· arXiv.org· Vol abs/2606.28307· 0 citations· 46 references
Computer ScienceMathematics
TL;DR
It is shown 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, which yields almost-sure second-order stationarity of limiting KKT points.
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.
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.
In this paper, we propose a balanced augmented Lagrangian method based on accelerated stochastic ADMM (b-ASADMM) to efficiently solve structured separable nonconvex optimization problems subject to linear constraints. The objective function in this problem comprises potentially nonsmooth and smooth functions, where the smooth function is an average of multiple nonconvex smooth functions. The involved smooth subproblem is tackled by an accelerated stochastic gradient method based on weighting of stochastic item and pre-variable. The involved nonsmooth subproblem is solved under incorporation of Bregman distance to avoid the case that subproblem does not have a closed-form solution due to the complicated quadratic term or other hindering. The involved balanced augmented Lagrangian method advances the original ALM by balancing its subproblems and improving its implementation. In contrast to most deterministic and stochastic ADMMs, our dual variable allows a more flexible and larger step-size region. By standard smoothness assumption, we establish the global convergence and iteration complexity of the generated sequence. Furthermore, we provide a linear convergence rate of b-ASADMM under a local error bound condition and the weakly convex property of the nonsmooth component. Numerical experiments on the graph-guided fused Lasso problem and the smooth clipped absolute deviation penalty problem are conducted to verify the effectiveness of b-ASADMM.
We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions. Our focus is on obtaining non-asymptotic bounds for the expected excess risk rather than sampling guarantees for the full target distribution. The key ingredient of our analysis is a direct passage from relative entropy to objective-value error, based on a weighted Csisz\'ar--Kullback--Pinsker inequality and exponential-moment estimates. This avoids intermediate Wasserstein bounds and yields sharper dependence on the Log-Sobolev constant, a quantity that may scale exponentially with the inverse temperature and the dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds on $\mathbb{E}[F(x_k)]-\min F$ in terms of the inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to an inexact-gradient version of ULA, allowing for biased and stochastic gradient surrogates whose mean-square error grows at most quadratically in the state. This framework covers stochastic gradients and zeroth-order estimators based only on function evaluations. In particular, we show that both Gaussian and spherical finite-difference estimators fit into the inexact-ULA theory and obtain explicit function-evaluation complexity bounds for zeroth-order Langevin optimization. To the best of our knowledge, these are the first non-asymptotic global non-convex optimization complexity bounds for zeroth-order ULA. We also provide numerical experiments illustrating the behavior of the proposed zeroth-order Langevin schemes.
E. Naldi, Marco Rando, Lorenzo Rosasco et al.· 0 citations
In this paper, we study dual semismooth Newton (SSN) methods for degenerate polyhedral projection problems, where generalized Jacobians of the dual residual may remain singular even arbitrarily close to the solution set. Rather than regularizing these singular systems, we exploit the nonuniqueness of the dual representation. We introduce a primal--dual lifted projection-equivalent set that always possesses extreme points without additional structural assumptions on the polyhedron, and show that its extreme-point geometry identifies dual representatives at which nonsingular generalized Jacobians of the dual residual can be constructed. This geometry is further linked to a full-column-rank condition and a generalized weak strict Robinson constraint qualification, showing that the regularity required by the Newton step can be recovered rather than imposed \emph{a priori}. We also establish displacement bounds that connect representative selection throughout the algorithm with the local Newton mechanism. Building on this variational framework, we develop an inexact dual SSN method with local superlinear convergence and a globalized version combining monotone representative selection with a Wolfe line search. The resulting method is globally convergent and eventually recovers the fast local rate. Numerical experiments on regularized optimal transport, battery-scheduling feasibility restoration, and occupation-measure projection demonstrate its robustness in highly degenerate settings.
We develop a primal--dual interior-point method for nonsymmetric conic optimization based on a conjugate-free scaling matrix. The scaling is obtained from a single-secant BFGS update of the primal barrier Hessian. In contrast to multi-secant BFGS scalings, it does not require conjugate-barrier derivatives. This feature is important for high-dimensional nonsymmetric cones, where conjugate-barrier derivatives may be unavailable in closed form or expensive to compute. We embed the conjugate-free scaling in a homogeneous self-dual predictor--corrector framework. Using a split central-path neighborhood that separately controls the conic variables and the scalar homogeneous variables, we prove that the scaling matrix remains uniformly comparable to the primal barrier Hessian. This comparison bound is used to prove neighborhood preservation and to show that the complementarity measure and the linear residual decrease at a uniform rate. Consequently, the method attains an iteration bound of $\mathcal{O}(\sqrt{\nu}\log(1/\varepsilon))$, improving the $\mathcal{O}(\nu\log(1/\varepsilon))$ bound of Badenbroek and Dahl [Optim. Methods Softw., 37 (2022), pp. 1027--1064] and matching the best-known complexity order for interior-point methods. Numerical experiments on instances involving the operator perspective epigraph cone and the quantum relative entropy cone show that the method is competitive with QICS, a specialized solver for conic models arising in quantum information.