Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems

Puya Latafat, Andreas Themelis, Panagiotis PatrinosMath. Program 2022 · DOI · OpenReview

Introduction

In the landscape of large-scale optimization, block-coordinate (BC) proximal gradient methods have become indispensable. By updating only a subset of variables at each iteration, these methods significantly reduce computational overhead and memory requirements. However, the theoretical foundations of BC methods have traditionally relied on two restrictive "crutches": the separability of the nonsmooth objective terms and the global convexity of the functions involved.

Real-world applications, such as distributed control and consensus-based machine learning, frequently violate these assumptions. This paper provides the first comprehensive convergence analysis for BC proximal gradient methods applied to problems featuring nonseparable nonsmooth and nonconvex terms. By introducing a novel Lyapunov framework, the authors establish "sure" convergence and provide explicit linear rates for widely used algorithms in previously unsupported settings.

The Theoretical Gap: Separability and Convexity

Most existing optimization theory assumes that the nonsmooth part of an objective function is a sum of independent functions, each corresponding to a specific variable block. While this simplifies the math, it fails to account for "sharing" problems or consensus constraints where variables are intrinsically coupled. Furthermore, while convexity ensures that local minima are global, modern neural networks and complex physical models are inherently nonconvex.

This research bridges this gap by developing a framework that handles both nonseparability and nonconvexity simultaneously, ensuring that BC methods remain robust even when the objective landscape is complex and the variables are tightly coupled.

Methodology: The Forward-Backward Envelope (FBE)

The central technical innovation of this work is the application of the Forward-Backward Envelope (FBE) as a Lyapunov function. In nonconvex optimization, the objective function value often fluctuates during iterations, making it difficult to prove that an algorithm is actually progressing toward a solution.

The FBE serves as a continuous, real-valued proxy for the original objective function. It shares the same minimizers as the original problem but possesses a critical property: it is guaranteed to decrease at every iteration of the BC scheme. This "sure descent" allows the authors to track algorithmic progress reliably, even when the underlying objective function behaves erratically.

Sampling Strategies

The paper analyzes the BC scheme under three primary scenarios:

  1. Randomized Sampling: Blocks are selected based on a minimum probability threshold.
  2. Essentially Cyclic Sampling: Every block is guaranteed an update within a fixed time window, a common requirement in deterministic systems.
  3. Kurdyka-Łojasiewicz (KL) Property: By utilizing the KL property, the authors prove global convergence to a single stationary point, ensuring the algorithm does not oscillate between multiple potential solutions.

Key Insights and Algorithmic Unification

Breaking the Separability Requirement

By leveraging the proximal mapping of the nonseparable term $G$, the authors demonstrate that block-updates are feasible even when variables are coupled. This allows the algorithm to maintain efficiency without requiring the objective to be decomposed into independent parts.

Unifying Finito and MISO

The study reveals that the popular Finito and MISO (Minimization by Incremental Surrogate Optimization) algorithms are specific instances of the authors' general BC framework. This unification allows for the derivation of the first linear convergence rates for these algorithms in nonconvex settings, providing a theoretical guarantee for their empirical success.

Linear Convergence without Global Convexity

A significant result is the proof of linear convergence rates. The authors show that if the smooth functions are strongly convex—even if the nonsmooth part is merely convex and the overall problem remains complex—the algorithm converges at a linear rate. They provide concrete formulas for the convergence constant $c$ for both randomized and cyclic sampling.

Applications: The Sharing Problem

The authors derive a novel incremental algorithm (Algorithm 3) specifically designed for the "sharing problem." This is a common structure in distributed resource allocation where agents must optimize local objectives while adhering to a global resource constraint. The new algorithm provides a more efficient path to convergence for these distributed systems.

Conclusion and Future Directions

This paper establishes a rigorous theoretical foundation for block-coordinate methods in the most challenging optimization environments. By proving that the FBE acts as a reliable descent metric, the authors have opened the door for more robust applications of BC methods in nonconvex machine learning and distributed control.

However, some limitations remain. The current analysis requires the smooth term of the objective to be a sum of functions of individual blocks. Future research may focus on extending this framework to cases where the smooth term is also nonseparable, potentially by quantifying the "strength of coupling" between blocks to maintain algorithmic stability.

Summary updated

Abstract

This paper analyzes block-coordinate proximal gradient methods for minimizing the sum of a separable smooth function and a (nonseparable) nonsmooth function, both of which are allowed to be nonconvex. The main tool in our analysis is the forward-backward envelope, which serves as a particularly suitable continuous and real-valued Lyapunov function. Global and linear convergence results are established when the cost function satisfies the Kurdyka–Łojasiewicz property without imposing convexity requirements on the smooth function. Two prominent special cases of the investigated setting are regularized finite sum minimization and the sharing problem; in particular, an immediate byproduct of our analysis leads to novel convergence results and rates for the popular Finito/MISO algorithm in the nonsmooth and nonconvex setting with very general sampling strategies.
BibTeX
@article{latafat2022block,
  author = {Puya Latafat and Andreas Themelis and Panagiotis Patrinos},
  title = {{Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems}},
  journal = {Math. Program.},
  year = {2022},
  doi = {10.1007/s10107-020-01599-7},
}
Figure