Controlled Block Proximal Linearized Method for Nonconvex and Nonsmooth Optimization

Weifeng YangarXiv 2026 · arXiv

TL;DR

The paper introduces the Controlled Block Proximal Linearized (CBPL) method, a new optimization framework for complex machine learning models like sparse Nonnegative Matrix Factorization (NMF). It solves a fundamental paradox where standard optimization goals actually force "graph collapse" (losing all data structure), using a clever "control potential" to keep variables bounded and meaningful without changing the original problem's objective.

What Problem Does This Paper Address?

In many machine learning tasks—like topic modeling or image feature extraction—researchers use nonconvex and nonsmooth optimization, specifically matrix and tensor factorizations. However, these models suffer from two major headaches:

  1. Scale Degeneracy: You can multiply one factor by a million and divide another by a million without changing the final reconstruction. This "non-coercivity" means standard algorithms can have variables that blow up to infinity or shrink to zero, leading to numerical instability.
  2. The Graph Collapse Paradox: To make representations more meaningful, we often add "graph regularization" to keep similar data points close together. The author proves a startling result: the mathematically "perfect" solution (a full critical point) to these problems often requires every data point to become identical. This "collapse" destroys the very discriminating structure the graph was meant to organize.

Existing methods usually fix this by adding extra penalties (like $L_2$ regularization) or hard constraints, but these actually change the underlying model and its optimal solutions.

Methods

The author proposes the CBPL method, which belongs to the family of block coordinate descent algorithms. The key innovation is the Control Potential ($C$).

  • The "Control" Mechanism: Instead of adding a penalty to the objective function itself, the control potential is incorporated into the update step. It acts like a guardrail: if the variables start to drift toward infinite scales or toward a "collapsed" graph state, the control potential's gradient pushes them back.
  • Proximal Linearization: The algorithm linearizes the smooth parts of the objective and applies a proximal step for the nonsmooth parts (like $\ell_0$ sparsity constraints or nonnegativity).
  • Effective Stationarity: Since "full criticality" is harmful (it causes collapse), the paper defines a new target called "effective stationarity." This ensures the algorithm finds a point that is optimal along all directions that actually change the data reconstruction, while ignoring the "degenerate" directions that just swap scales.
  • Mathematical Rigor: The author uses the Kurdyka–Łojasiewicz (KL) property to prove that the algorithm doesn't just wander around; the entire sequence of iterates is guaranteed to converge to a single, finite, and meaningful limit.

Datasets

The method was evaluated on several diverse datasets to prove its versatility:

  • lp_ship12l: A large, sparse matrix from the SuiteSparse collection.
  • BASEHOCK: A text-based feature selection dataset.
  • BreastMNIST: A medical imaging dataset (ultrasound images) processed into tensors.
  • microPNW: A seismic dataset used for tensor decomposition.

Key Insights and Ideas

  • The Structural Conflict: The most "aha" moment is the proof that scale criticality is equivalent to graph collapse. This identifies a fundamental flaw in how we traditionally think about "solving" graph-regularized models.
  • Guiding without Changing: CBPL is philosophically interesting because it uses a potential function to guide the dynamics of the optimization without moving the goalposts (the original objective function).
  • Safe Step Parameters: The paper provides explicit, computable formulas for step sizes. This removes the need for "line searches" (guessing and checking step sizes), making the algorithm much more efficient in practice.

Key Results

  • Non-Collapse Guarantee: Unlike standard methods, CBPL maintained a "uniform positive lower bound" on graph action. In plain English: it successfully prevented the data points from merging into a single useless blob.
  • Convergence Speed: In experiments, the "stationarity certificate" (a measure of how close the algorithm is to a solution) dropped by 3 to 6 orders of magnitude within just 60 seconds of computation.
  • Stability: The Frobenius norms of the factors remained stable throughout the iterations, proving that the control potential effectively managed the scale degeneracy problem.

Limitations and Future Work

  • Manual Control Design: While the paper provides explicit control potentials for NMF and Tucker decompositions, applying CBPL to a brand-new type of model would require the user to mathematically derive a suitable control potential for that specific geometry.
  • Cyclic Updates: The current framework relies on a cyclic update rule (updating block 1, then block 2, etc.). Future work could explore stochastic or parallel block updates, which are often faster for truly massive "Big Data" applications.
  • Global vs. Local: Like almost all nonconvex optimization methods, CBPL converges to a local optimum. Finding the global optimum in these complex landscapes remains an open challenge.

Summary updated

Abstract

We consider multiblock nonconvex and nonsmooth optimization without assuming bounded iterates or coercivity of the original objective. We propose the Controlled Block Proximal Linearized (CBPL) method, which incorporates a control potential into block updates while retaining the original objective, variables, and constraints. Under explicit control design conditions and the KL property, the control yields boundedness, finite length, whole-sequence convergence of the original variables, and convergence of objective values. At the limit, one limiting subgradient of the original objective vanishes on all effective comparison directions. We apply CBPL to graph-regularized nonnegative matrix factorization (NMF), CP decomposition, and independent-core matrix tri-factorization (NMTF) with $\ell_0$ norm sparsity constraints. We characterize their reconstruction-preserving scale degeneracies, proving that scale criticality is equivalent to graph collapse and that full criticality forces such collapse. Explicit controls provide compact sublevel sets and a uniform positive lower bound on graph action, including with an independent Tucker core, while retaining genuine reconstruction-changing directions. Each block admits an explicit projection and a computable safe step parameter. For ordinary NMF and CP models, whole-sequence convergence to a full critical point follows. Experiments with direct safe updates demonstrate convergence, sustained graph action, and controlled factor and core scales.
BibTeX
@misc{yang2026controlled,
  author = {Weifeng Yang},
  title = {{Controlled Block Proximal Linearized Method for Nonconvex and Nonsmooth Optimization}},
  year = {2026},
  eprint = {2610.34390},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34390},
}
Figure