A Dual Augmented Block Minimization Framework for Learning with Limited Memory

Ian En-Hsu Yen, Shan-Wei Lin, Shou-De LinNeurIPS 2015 · OpenReview

Training massive machine learning models often hits a hard physical wall: the limits of your machine's RAM. When a dataset is ten times larger than available memory, standard "in-memory" algorithms fail, and "online" methods (processing one sample at a time) become agonizingly slow due to constant disk I/O.

To address this, researchers from the University of Texas at Austin and National Taiwan University have introduced Dual-Augmented Block Minimization (DA-BCD). This framework provides a mathematically sound way to train general convex models—such as Lasso and L1-regularized SVMs—under strict memory constraints without sacrificing global convergence.

By combining the Proximal Point Method with block-coordinate descent, DA-BCD ensures global convergence for non-strongly convex problems where previous limited-memory methods typically stalled or failed.

The Problem: I/O Bottlenecks in Big Data

In the era of "Big Data," datasets frequently reach the terabyte range, while standard compute nodes might only have a few dozen gigabytes of RAM. This creates a massive bottleneck: I/O overhead.

Existing solutions for out-of-core learning usually fall into two camps:

  1. Online Learning: These methods process one sample at a time. While highly memory-efficient, they require many passes (epochs) over the data and spend the vast majority of their time waiting for the disk to fetch the next sample.
  2. Dual Block Coordinate Descent (D-BCD): This approach loads a "block" of data into memory, solves a sub-problem to near-optimality, and then moves to the next block. This is significantly faster because it maximizes computation per I/O operation.

The Gap: D-BCD was originally designed for Support Vector Machines (SVMs) with L2-regularization. Mathematically, D-BCD only guarantees global convergence if the "dual" version of the problem is smooth. This requires the "primal" problem to be strongly convex. Popular models like Lasso (L1-regularization) or standard L1-SVMs are not strongly convex. Consequently, applying the standard D-BCD approach to these models often causes the optimization to stall or fail to reach the optimum.

The Solution: Dual-Augmented Block Minimization

The authors propose Dual-Augmented Block Minimization (DA-BCD) to bridge this mathematical gap.

The core innovation is the integration of the Proximal Point Method (also known as the Dual Augmented Lagrangian technique). Instead of solving the original problem directly, the algorithm solves a sequence of "proximal" sub-problems.

  • The Trick: The authors add a simple quadratic term—$\frac{1}{2\eta}\|w - w^t\|^2$—to the objective function.
  • The Result: This "augmentation" forces the primal problem to become strongly convex. Because of the relationship between primal and dual problems (Strong/Smooth Duality), this guarantees that the dual problem is smooth.
  • The Framework: With a smooth dual, the efficient Block Coordinate Descent method can be safely applied. The system loads a block of data, optimizes it using any standard solver (like coordinate descent), updates the model, and repeats.

Crucially, this framework is "solver-agnostic." If you have a fast solver that works in-memory, you can plug it into the DA-BCD framework to make it work for out-of-memory data.

Experimental Setup and Datasets

The authors evaluated their framework on four large-scale benchmark datasets. To simulate a strict limited-memory environment, the data was split into 10 partitions, meaning only 1/10th of the data could fit in memory at any given time.

  • Classification: webspam (315k samples, 680k features) and rcv1 (202k samples, 7.9M features).
  • Regression: year-pred (463k samples) and E2006 (16k samples, 30k features). For regression, Random Fourier Features were used to approximate non-linear kernels, significantly increasing the feature count.

Key Results

The authors compared DA-BCD against standard D-BCD, Online Mirror Descent (OnlineMD), and ADMM (a popular distributed optimization algorithm).

Performance comparison of DA-BCD against baselines across four datasets.
  • Global Convergence: On L1-regularized problems, the standard D-BCD flatlined and failed to reach the optimum, confirming the theoretical limitations of applying it to non-strongly convex problems. DA-BCD, however, converged successfully every time.
  • Speed and I/O Efficiency: DA-BCD was significantly faster than OnlineMD. Because OnlineMD processes samples one by one, it suffers from an unbalanced ratio of computation to I/O time. DA-BCD's ability to perform multiple optimization passes on a block while it is already in RAM makes it vastly more efficient.
  • Outperforming Distributed Baselines: DA-BCD also outperformed ADMM variants. The authors attribute this to ADMM's more "conservative" updates on dual variables compared to the direct, aggressive block minimization utilized in DA-BCD.

Limitations and Future Work

While DA-BCD offers a robust solution for limited-memory training, it has a few constraints:

  • Parameter Memory: The framework assumes that the model parameter vector ($w$) itself can fit in memory. For extreme-scale models with billions of features where $w$ exceeds RAM, this specific approach would require further modification.
  • Hyperparameter Sensitivity: Practical performance depends heavily on choosing an appropriate block size and tuning the number of inner iterations ($S$) performed on each block.
  • Convexity Requirement: The current theoretical guarantees rely strictly on convexity. Extending this robust limited-memory framework to non-convex problems, such as deep neural networks, remains a challenging and open frontier for future research.

Summary updated

Abstract

In past few years, several techniques have been proposed for training of linear Support Vector Machine (SVM) in limited-memory setting, where a dual block-coordinate descent (dual-BCD) method was used to balance cost spent on I/O and computation. In this paper, we consider the more general setting of regularized \emph{Empirical Risk Minimization (ERM)} when data cannot fit into memory. In particular, we generalize the existing block minimization framework based on strong duality and \emph{Augmented Lagrangian} technique to achieve global convergence for ERM with arbitrary convex loss function and regularizer. The block minimization framework is flexible in the sense that, given a solver working under sufficient memory, one can integrate it with the framework to obtain a solver globally convergent under limited-memory condition. We conduct experiments on L1-regularized classification and regression problems to corroborate our convergence theory and compare the proposed framework to algorithms adopted from online and distributed settings, which shows superiority of the proposed approach on data of size ten times larger than the memory capacity.
BibTeX
@inproceedings{yen2015dual,
  author = {Ian En-Hsu Yen and Shan-Wei Lin and Shou-De Lin},
  title = {{A Dual Augmented Block Minimization Framework for Learning with Limited Memory}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=H1W2pI-uWB},
}
Figure