STOCHASTIC ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR STRUCTURED REGULARIZATION

Taiji SuzukiJournal of the Japanese Society of Computational Statistics 2015 · DOI

Abstract

In this paper, we present stochastic optimization variants of the alternating direction method of multipliers (ADMM). ADMM is a useful method to solve a regularized risk minimization problem where the regularization term is complicated and not easily dealt with in an ordinary manner. For example, structured regularization is one of the typical applications of such regularization in which ADMM is effective. It includes group lasso regularization, low rank tensor regularization, and fused lasso regularization. Since ADMM is a general method and has wide applications, it is intensively studied and refined these days. However, ADMM is not suited to optimization problems with huge data. To resolve this problem, online stochastic optimization variants and a batch stochastic optimization variant of ADMM are presented. All the presented methods can be easily implemented and have wide applications. Moreover, the theoretical guarantees of the methods are given.

Introduction

In modern machine learning, the pursuit of model interpretability and domain-specific accuracy often leads to the use of "structured" regularization. Unlike the standard Lasso, which promotes simple sparsity, structured regularizations—such as overlapped group lasso, low-rank tensor regularization, and fused lasso—capture complex relationships between features. While the Alternating Direction Method of Multipliers (ADMM) has emerged as a powerful "Swiss Army knife" for these problems due to its ability to decouple loss functions from complex penalties, its traditional formulation is a batch method. This requirement to process the entire dataset at every iteration makes it computationally prohibitive for the massive datasets common in contemporary applications.

Conversely, standard stochastic gradient descent (SGD) methods, while efficient for big data, struggle with structured penalties. The "proximal mapping" required to handle these complex regularizers is often computationally expensive or impossible to compute directly within a standard SGD framework. This paper bridges this gap by introducing stochastic variants of ADMM that combine the flexibility of splitting methods with the scalability of stochastic optimization.

Proposed Stochastic ADMM Variants

The paper proposes three distinct stochastic variants designed to handle different data scenarios while maintaining theoretical rigor.

1. Online Stochastic ADMM (OPG-ADMM & RDA-ADMM)

For streaming data or scenarios where data is too large to fit in memory, the author introduces two online variants:

  • RDA-ADMM (Regularized Dual Averaging): This variant utilizes the average of all past gradients to inform the current model update, providing stability in the presence of noise.
  • OPG-ADMM (Online Proximal Gradient): This variant focuses on the current gradient for more immediate updates.

The Linearization Innovation: A critical technical contribution is the use of a linearization technique. By adding a specific quadratic term to regularize the update, the author transforms potentially expensive sub-problems into simple projection steps. This ensures that the per-iteration cost remains low, even when the underlying regularization is complex.

2. Batch Stochastic ADMM (SDCA-ADMM)

For fixed but massive datasets, the paper introduces SDCA-ADMM, based on Stochastic Dual Coordinate Ascent. This method randomly selects a "sub-batch" of data at each step to update dual variables. This approach is particularly effective for strongly convex problems, where it can achieve linear (exponential) convergence rates.

Theoretical Contributions and Insights

The proposed methods are not merely heuristic; they are backed by strong theoretical guarantees:

  • Optimal Convergence: The online methods (OPG and RDA) achieve the minimax optimal convergence rate of $O(1/\sqrt{T})$ for general convex functions. For strongly convex functions, OPG-ADMM achieves a rate of $O(\log(T)/T)$.
  • Independence from Penalty Complexity: A significant theoretical finding is that the primary terms in the convergence bounds do not depend on the complexity of the regularization function ($L_\psi$). This implies that the methods remain robust and efficient even as the "structure" of the sparsity becomes increasingly intricate.
  • Efficiency through Splitting: The core insight is that ADMM’s ability to decouple the loss function from the regularization term allows for a simple gradient step for the data and a specialized, efficient proximal step for the complex penalty.

Experimental Results

The algorithms were evaluated against synthetic data and real-world benchmarks, including the 20 Newsgroups text classification dataset and the a9a (Adult) census dataset. Key findings include:

  • Superiority over Standard SGD: In tasks involving overlapped group penalties, the stochastic ADMM variants outperformed standard RDA and OPG. The latter methods were slowed down by "heavy" proximal mappings that the ADMM framework successfully bypassed.
  • Scalability: SDCA-ADMM demonstrated significantly faster convergence than standard batch ADMM, particularly as the number of observations increased, proving its utility for large-scale empirical risk minimization.

Conclusion and Future Directions

This work provides a robust framework for applying structured regularization to big data. By linearizing sub-problems and applying stochastic updates, the proposed ADMM variants offer a scalable alternative to traditional batch methods without sacrificing the ability to handle complex penalties.

Future research directions include the development of adaptive methods for choosing sub-batch sizes ($K$) in SDCA-ADMM, the incorporation of second-order information (such as quasi-Newton methods) to further accelerate convergence, and investigating methods to mitigate the impact of data correlation on iteration complexity.

Summary updated

Abstract

In this paper, we present stochastic optimization variants of the alternating direction method of multipliers (ADMM). ADMM is a useful method to solve a regularized risk minimization problem where the regularization term is complicated and not easily dealt with in an ordinary manner. For example, structured regularization is one of the typical applications of such regularization in which ADMM is effective. It includes group lasso regularization, low rank tensor regularization, and fused lasso regularization. Since ADMM is a general method and has wide applications, it is intensively studied and refined these days. However, ADMM is not suited to optimization problems with huge data. To resolve this problem, online stochastic optimization variants and a batch stochastic optimization variant of ADMM are presented. All the presented methods can be easily implemented and have wide applications. Moreover, the theoretical guarantees of the methods are given.
BibTeX
@article{suzuki2015stochastic,
  author = {Taiji Suzuki},
  title = {{STOCHASTIC ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR STRUCTURED REGULARIZATION}},
  journal = {Journal of the Japanese Society of Computational Statistics},
  year = {2015},
  doi = {10.5183/jjscs.1502004\_218},
}
Figure