Accelerated Training for Matrix-norm Regularization: A Boosting Approach

Xinhua Zhang, Yaoliang Yu, Dale SchuurmansNeurIPS 2012 · OpenReview

TL;DR

This paper introduces a highly efficient boosting framework for solving matrix-norm regularized problems, such as trace-norm minimization. By interlacing greedy boosting steps with unconstrained local optimization, the authors achieve state-of-the-art training speeds and provide the first efficient "weak-oracle" for latent multiview learning.

The Challenge of Matrix-Norm Regularization

In machine learning, we often want to find "latent factors" in data—for instance, decomposing a massive user-movie rating matrix into a few hidden features. To keep these models simple and interpretable, researchers use trace-norm regularization as a proxy for low-rank solutions.

However, training these models is computationally expensive. Existing methods usually fall into two camps:

  1. Proximal Gradient Methods: These require a Singular Value Decomposition (SVD) at every step, which is agonizingly slow for large datasets.
  2. Greedy/Boosting Methods: These are faster but typically only solve the constrained version of the problem (e.g., "keep the norm below 10") rather than the regularized version (e.g., "minimize loss + penalty").

This paper bridges the gap by providing a mathematically rigorous boosting approach that optimizes the regularized objective directly, offering better convergence rates and practical speed.

Proposed Methodology

The authors propose two main algorithmic contributions to tackle these bottlenecks:

  1. Vanilla Boosting for $\ell_1$ Regularization: They reformulate the matrix problem into a boosting framework where each "weak hypothesis" is a rank-one matrix. They prove that this approach achieves an $\epsilon$-accurate solution in $O(1/\epsilon)$ iterations—a significant theoretical improvement over previous gradient-based boosting rates.
  2. Boosting with Local Search: This is the practical "speed-up." Standard boosting can be slow because it only adds one basis at a time. The authors use a variational representation of matrix norms to create a smooth, unconstrained local objective. This allows them to use efficient solvers like L-BFGS to "fine-tune" all currently selected bases simultaneously, drastically accelerating convergence.
  3. The Multiview Oracle: For complex problems like multiview learning (where data comes from multiple sources like text and images), finding the best "weak hypothesis" is usually NP-hard. The authors formulate a specific Semi-Definite Programming (SDP) relaxation and prove that it has zero duality gap, making the global optimization of multiview models computationally feasible for the first time.

Datasets Evaluated

The authors evaluated their approach on several diverse benchmarks:

  • Matrix Completion: MovieLens 100k, 1M, and 10M datasets (predicting user ratings).
  • Multitask/Multiclass Learning: A synthetic dataset with 250 features and 100 classes.
  • Multitask Learning: The "School" dataset (predicting exam scores for 15,362 students across 139 schools).
  • Multiview Learning: The Flickr dataset from NUS-WIDE (using low-level image features and tags to classify animals).

Key Insights

  • Direct Regularization: Unlike previous greedy methods that treat the norm as a hard constraint, this method tackles the $\lambda$-weighted penalty directly. This is crucial for many real-world applications where the regularization strength needs to be tuned precisely.
  • Smooth Local Search: The "aha moment" is the variational trick. By reparameterizing the matrix $X$ into $UV^\top$, they turn a non-smooth problem into a smooth, unconstrained one that standard optimization tools (like L-BFGS) can efficiently solve.
  • Strong Duality in Multiview: The proof that their SDP relaxation for the multiview oracle is exact is a major theoretical win. It ensures that their "weak learner" actually finds the best possible step, preventing the algorithm from getting stuck in poor local optima.

Key Results

  • Convergence: The method consistently drove the training objective down faster than state-of-the-art solvers (MMBS, DHM, JS).
Training objective and loss convergence on MovieLens-10m
  • Speed: On the MovieLens datasets, the proposed method reached a low Test NMAE (Normalized Mean Absolute Error) orders of magnitude faster than competitors.
Test error vs. running time across MovieLens datasets
  • Global Optimality: In the multiview experiments, the boosting approach found a globally better solution than standard alternating minimization, which frequently got trapped in local optima.

Limitations and Future Work

  • Convexity: The paper focuses on convex relaxations of the rank constraint. While the trace norm is a great proxy, it isn't the same as directly minimizing the rank, which remains a non-convex challenge.
  • Oracle Complexity: While the multiview oracle is "efficient" (polynomial time), solving an SDP inside every boosting iteration can still be heavy for extremely high-dimensional multiview problems.
  • Future Directions: The authors suggest exploring randomized boosting to further scale the $\ell_1$ regularization framework and extending the logic to more general non-linear regularizers.

Summary updated

Abstract

Sparse learning models typically combine a smooth loss with a nonsmooth penalty, such as trace norm. Although recent developments in sparse approximation have offered promising solution methods, current approaches either apply only to matrix-norm constrained problems or provide suboptimal convergence rates. In this paper, we propose a boosting method for regularized learning that guarantees $\epsilon$ accuracy within $O(1/\epsilon)$ iterations. Performance is further accelerated by interlacing boosting with fixed-rank local optimization---exploiting a simpler local objective than previous work. The proposed method yields state-of-the-art performance on large-scale problems. We also demonstrate an application to latent multiview learning for which we provide the first efficient weak-oracle.
BibTeX
@inproceedings{zhang2012accelerated,
  author = {Xinhua Zhang and Yaoliang Yu and Dale Schuurmans},
  title = {{Accelerated Training for Matrix-norm Regularization: A Boosting Approach}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2012},
  url = {https://openreview.net/forum?id=BJE0VPbdZB},
}
Figure