Separable Approximations and Decomposition Methods for the Augmented Lagrangian

Rachael Tappenden, Peter Richtárik, Burak BükeOptim. Methods Softw 2013 · OpenReview

TL;DR

This paper bridges the gap between two optimization methods, DQAM and PCDM, for solving large-scale problems involving augmented Lagrangians. They show these methods are equivalent under certain conditions and demonstrate that PCDM offers significantly better theoretical performance, especially for problems with strong convexity.

What Problem Does This Paper Address?

Modern data-driven applications often lead to massive optimization problems. A common challenge is when the objective function is separable into blocks of variables, but a set of "linking" constraints makes the overall problem nonseparable, hindering efficient solution. The augmented Lagrangian method is a standard approach to handle these constraints, but the resulting augmented Lagrangian itself can be nonseparable. This paper focuses on decomposition methods that approximate the augmented Lagrangian to make it separable, thereby enabling more efficient, block-wise optimization. Specifically, they compare two such methods: the established Diagonal Quadratic Approximation Method (DQAM) and the more recent Parallel Coordinate Descent Method (PCDM).

Methods

The paper delves into two main decomposition techniques:

  • Diagonal Quadratic Approximation Method (DQAM): This method approximates the augmented Lagrangian by ignoring cross-product terms between different blocks of variables. This makes the problem separable and amenable to parallel processing. The paper presents generalizations of DQAM for non-quadratic functions.
  • Parallel Coordinate Descent Method (PCDM): This method, developed by Richtárik and Takáč, offers more flexibility by allowing for the update of a subset of blocks at each iteration, controlled by a "sampling" parameter. This is particularly useful when the number of processors is less than the number of blocks.

The authors establish an equivalence between DQAM and a specific variant of PCDM for feasibility problems. They also derive improved complexity bounds for PCDM under strong convexity and provide a detailed comparison of the theoretical performance of both methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithm comparison, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Equivalence Under Specific Conditions: The paper reveals that DQAM and a "fully parallel" variant of PCDM are essentially equivalent for feasibility problems when a specific step-size parameter is chosen. This provides a deeper understanding of their relationship.
  • PCDM's Superior Theoretical Performance: Under strong convexity, PCDM demonstrates significantly better theoretical convergence rates than DQAM. This advantage is particularly pronounced when the problem's strong convexity constant is much larger than the sum of the individual block strong convexity constants.
  • Flexibility of PCDM: PCDM's ability to update a subset of blocks (controlled by the parameter $\tau$) makes it more versatile. This allows it to adapt to the available parallel processing resources, unlike DQAM which always updates all blocks.
  • "Correction Step" vs. "One-Sided Approximation": DQAM requires a "correction step" to ensure convergence due to its local, two-sided approximation. In contrast, PCDM's one-sided global approximation inherently guarantees objective function reduction on average, eliminating the need for an explicit correction step.
  • Optimal Block Updates: The paper shows that for parallel processing, it's optimal for PCDM to update a number of blocks equal to the number of available processors ($\tau = p$).

Key Results

  • Complexity Bound Improvement: The paper proves an improved complexity bound for PCDM under strong convexity. This bound is shown to be at least $8(L'/L)(\omega-1)^2$ times better than the best known bound for DQAM, where $\omega$ is the degree of partial separability and $L', L$ are Lipschitz constants.
  • Speedup Factor: For $\omega=10$, the theoretical iteration complexity of DQAM can be over 1000 times worse than PCDM.
  • Numerical Evidence (Figure 2): While the paper's primary focus is theoretical, the numerical results in Figure 2 suggest that PCDM(τ) (PCDM with τ blocks updated) significantly outperforms DQAM and the standard PCDM (updating all blocks) in terms of time units required, especially when τ is matched to the number of processors.

Limitations and Future Work

  • DQAM Assumptions: The convergence guarantees for DQAM are derived under the assumption that the objective function is quadratic and strongly convex. This limits its applicability compared to PCDM.
  • Numerical Results: The numerical experiments are limited in scope, focusing on specific problem structures and parameter choices.
  • Future Work: The paper suggests exploring the practical advantages of PCDM further and investigating its performance on a wider range of problems. The authors also mention that they do not analyze the complexity of their generalized DQAM algorithms in this paper, which could be a direction for future research.

Summary updated

Abstract

In this paper we study decomposition methods based on separable approximations for minimizing the augmented Lagrangian. In particular, we study and compare the Diagonal Quadratic Approximation Method (DQAM) of Mulvey and Ruszczy\'{n}ski and the Parallel Coordinate Descent Method (PCDM) of Richt\'arik and Tak\'a\v{c}. We show that the two methods are equivalent for feasibility problems up to the selection of a single step-size parameter. Furthermore, we prove an improved complexity bound for PCDM under strong convexity, and show that this bound is at least $8(L'/\bar{L})(\omega-1)^2$ times better than the best known bound for DQAM, where $\omega$ is the degree of partial separability and $L'$ and $\bar{L}$ are the maximum and average of the block Lipschitz constants of the gradient of the quadratic penalty appearing in the augmented Lagrangian.
BibTeX
@inproceedings{tappenden2013separable,
  author = {Rachael Tappenden and Peter Richtárik and Burak Büke},
  title = {{Separable Approximations and Decomposition Methods for the Augmented Lagrangian}},
  booktitle = {Optim. Methods Softw},
  year = {2013},
  url = {https://openreview.net/forum?id=CO2uFhyTcif},
}
Figure