A note on alternating minimization algorithms: Bregman frame

Tao Sun, Lizhi Cheng

TL;DR

This paper introduces the Bregman frame, a unified mathematical framework that encompasses several popular alternating minimization (AM) algorithms under one umbrella. By using Bregman distances, the authors provide a single, generalized convergence analysis that proves these algorithms converge to critical points, particularly when the objective function satisfies the Kurdyka-Lojasiewicz (KL) property.

What Problem Does This Paper Address?

Many optimization problems in machine learning and signal processing involve minimizing a function with two or more blocks of variables, such as $\min_{y,z} f(y) + H(y,z) + g(z)$. The most common approach is Alternating Minimization (AM), where you fix one variable and solve for the other, then swap.

Over the years, researchers have developed many variations of AM to handle different constraints or improve stability:

  • Standard AM: Direct minimization of each block.
  • Proximal Linearized AM (PLAM): Uses a linear approximation of the coupling term $H$ plus a quadratic penalty.
  • Augmented AM (AAM): Adds a proximal term to the standard objective to ensure sufficient descent.

The challenge is that each of these variants typically requires its own unique convergence proof. The authors address this fragmentation by proposing a "frame" that treats all these algorithms as special cases of a single generalized algorithm.

Methods

The core of the paper is the Bregman Alternating Minimization Algorithm (Algorithm 1). Instead of using standard Euclidean distances for regularization, it uses Bregman distances ($B_\phi$).

The update steps are defined as:

  1. $y^{k+1} \in \arg\min_y \{ H(y, z^k) + f(y) + B_{\phi^k}(y, y^k) \}$
  2. $z^{k+1} \in \arg\min_z \{ H(y^{k+1}, z) + g(z) + B_{\psi^k}(z, z^k) \}$

Why this is clever:

By choosing different "distance-generating" functions ($\phi$ and $\psi$), the authors show that:

  • Setting $\phi, \psi = 0$ recovers Standard AM.
  • Setting $\phi, \psi$ to specific quadratic forms recovers AAM.
  • Setting $\phi$ to a specific combination of a quadratic term and the gradient of $H$ recovers PLAM.

This allows the authors to write one set of proofs that applies to all these algorithms (and even hybrid versions where one block uses AM and the other uses PLAM).

Datasets

Not discussed in the paper. This is a theoretical note focused on mathematical proofs and algorithmic formulation; it does not include numerical experiments or empirical evaluations on specific datasets.

Key Insights and Ideas

  • Linearization as a Bregman Distance: One of the most interesting "aha" moments is the demonstration that the "linearization" step in algorithms like PLAM is mathematically equivalent to choosing a specific Bregman distance. This bridges the gap between proximal methods and gradient-based methods.
  • Sufficient Descent: The paper proves that as long as the chosen Bregman functions are strongly convex, the algorithm guarantees a "sufficient descent" in the objective function value at every iteration.
  • Global Convergence via KL Property: In non-convex optimization, proving that an algorithm converges to a point (rather than just having its gradient go to zero) is difficult. The authors use the Kurdyka-Lojasiewicz (KL) property—a condition satisfied by most functions used in practice (like polynomials and logs)—to prove that the sequence of iterates actually converges to a specific critical point.

Key Results

  • Unified Formulation: The paper successfully maps AM, PLAM, and AAM into the Bregman frame.
  • Convergence to Critical Points: The authors prove that any cluster point of the sequence generated by the Bregman frame is a critical point of the objective function $\Phi$.
  • Sequence Convergence: Under the assumption that the objective function is a KL function, the authors prove the sequence $\{y^k, z^k\}$ converges globally.
  • Multi-block Extension: The authors briefly demonstrate that this framework isn't limited to two variables; it can be extended to $n$-block minimization problems.

Limitations and Future Work

  • Theoretical Focus: The paper lacks empirical testing. While the math is sound, it doesn't provide guidance on which specific Bregman function ($\phi$) performs best for specific real-world problems (e.g., image deblurring vs. matrix completion).
  • Smoothness Requirements: The coupling function $H$ is assumed to have Lipschitz continuous gradients. While standard, this limits the framework's application to problems with non-smooth coupling terms.
  • Parameter Selection: The convergence relies on choosing parameters (like $\alpha_k$ and $\beta_k$) that are large enough relative to the Lipschitz constants. In practice, estimating these constants can be difficult.

Summary updated

Abstract

In this paper, we propose a Bregman frame for several classical alternating minimization algorithms. In the frame, these algorithms have uniform mathematical formulation. We also present convergence analysis for the frame algorithm. Under the Kurdyka-Lojasiewicz property, stronger convergence is obtained.
BibTeX
@misc{sun2016note,
  author = {Tao Sun and Lizhi Cheng},
  title = {{A note on alternating minimization algorithms: Bregman frame}},
  year = {2016},
  eprint = {1605.08290},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.08290},
}
Figure