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

Weifeng Yang

math.OCSep 30, 2026

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

Authors: Weifeng Yang

Abstract

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.

Figures & tables

Notation	Definition
$\left\{{x_{i}}\right\}^{n}_{i=1}$	$\{x_{1},x_{2},......,x_{n}\}$
$\left[n\right]$	$\left\{i\right\}_{i=1}^{n}$
$x_{(n)}$	$\left\{{x_{i}}\right\}^{n}_{i=1}$
$x_{(n)}+y_{(n)}$	$\left\{{x_{i}}+{y_{i}}\right\}^{n}_{i=1}$
$L_{\nabla_{x_{j}}H}$	the Lipschitz constant of $\nabla_{x_{j}}H(\left\{{x_{i}}\right\}^{N}_{i=1})$
$x^{k}_{i}$	the $i$ -th block of $\left\{{x_{i}}\right\}^{n}_{i=1}$ within the $k$ -th outer loop

Table 1 : Summary of frequently used notations

Figure 1 : Average convergence behavior on the lp_ship12l (left) and BASEHOCK (right) datasets. The inset enlarges the final stage objective function values of the four best-performing methods.

Figure 2 : Average convergence behavior on the lp_ship12l (left) and BASEHOCK (right) datasets with

r=400

. The inset enlarges the final stage objective function values of the four best-performing methods.

Figure 3 : Average convergence behavior on the lp_ship12l (left) and BASEHOCK (right) datasets with

r=500

. The inset enlarges the final stage objective function values of the four best-performing methods.

Panel of Table 2 — Table 2 : Average and standard deviation results on the matrix datasets. The best performance is highlighted in bold.

Panel of Table 3 — Table 3 : Average and standard deviation results on the tensor datasets. The best performance is highlighted in bold.

Figure 4 : Average convergence behavior on the BreastMNIST (left) and microPNW (right) datasets. The inset enlarges the final stage objective function values of the four best-performing methods.

Figure 5 : Average convergence behavior on the BreastMNIST (left) and microPNW (right) datasets with

R=60

. The inset enlarges the final stage objective function values of the four best-performing methods.

Figure 6 : Average convergence behavior on the BreastMNIST (left) and microPNW (right) datasets with

R=70

. The inset enlarges the final stage objective function values of the four best-performing methods.

Explore similar work

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

Proximal Operators Stochastic Convex Optimization Convex Optimization Nonconvex Momentum Stochastic Gradient Descent Inertial+1

Ask PDF

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

Primal-Dual Methods Nonconvex Lipschitz Continuity Bregman Divergences

Ask PDF

Date pendingmath.OC

Block-Norm Geometries for Online Mirror Descent with Sparse Losses

The performance of online mirror descent depends critically on the geometry induced by its mirror map, yet standard algorithms largely rely on two canonical choices: Euclidean and entropic geometry. We show that these two geometries can both be substantially suboptimal when loss gradients are sparse. We introduce a family of randomized block-norm mirror maps that interpolates between Euclidean and entropic geometries and adapts to intermediate sparsity structure. For several standard convex sets, including

\ell_p

balls, ellipsoids, boxes, and Minkowski sums of norm balls, we prove polynomial-in-dimension improvements in regret bounds over the better of online projected gradient descent and exponentiated gradient. We further construct explicit online convex optimization instances for which these improvements are realized: on a simple polytope, an intermediate block geometry achieves a

\text{poly}(d)

separation in regret from both Euclidean and entropic geometries in dimension

d

, while on the probability simplex we obtain a separation of order

\Omega(\sqrt{\log d}/\log\log d)

. Finally, we study geometry selection when sparsity is unknown. We show that naively alternating between mirror maps can incur linear regret, even though either mirror map alone has sublinear regret, and give a Hedge meta-algorithm that competes with the best mirror map in a finite portfolio. For random block geometries, this yields regret within an

O(\sqrt{\log\log d})

factor of the best random uniform block norm chosen in hindsight.

Swati Gupta, Jai Moondra, Mohit Singh

MIT · CMU · Georgia Tech

Mirror Descent Spectral Norm

Ask PDF