Adaptive Regularization for Weight Matrices

Koby Crammer, Gal Chechik

Abstract

Matrix-based models are essential for tasks like similarity learning and multi-class classification, but applying second-order online learning to them is often computationally prohibitive. This paper introduces AROMA (Adaptive Regularization Of MAtrix models), a framework that uses a factored covariance approach to capture feature correlations efficiently. By reducing memory requirements from $O(n^4)$ to $O(n^2)$, AROMA significantly outperforms existing state-of-the-art methods in both precision and convergence speed.

Introduction

In machine learning, weights are typically represented as vectors. However, many problems—such as learning distance metrics or handling multi-class classification—are more naturally formulated using matrices. Second-order online learning algorithms like AROW are powerful because they maintain a distribution over weights, allowing the model to adapt its learning rate based on confidence.

The primary challenge is scalability. For an $n \times n$ matrix, a full second-order covariance matrix requires $n^4$ parameters, which is impractical for high-dimensional features. AROMA addresses this by introducing a scalable framework for matrix-based second-order learning.

Methodology: The AROMA Framework

The authors propose two variants of the AROMA algorithm:

  1. d-AROMA (Diagonal): This baseline assumes independence between all parameters in the weight matrix, tracking only $n \times m$ variance terms. While efficient ($O(nm)$), it fails to capture feature correlations.
  2. f-AROMA (Factored): This core contribution utilizes a matrix-variate normal distribution. By factoring the covariance into two smaller matrices using a Kronecker product, it captures correlations within the input and output spaces separately. This reduces the parameter count to $O(n^2 + m^2 + nm)$, making it feasible for large-scale applications.

Both versions are online, updating their internal distributions incrementally with each new example.

Experimental Evaluation

AROMA was evaluated on two similarity-ranking tasks:

  • Caltech-256: Image similarity using 1,000-dimensional "bag-of-visterms" vectors.
  • 20 Newsgroups: Document similarity using 1,000-dimensional tf-idf vectors.

Key Results and Discussion

The experimental results demonstrate the clear advantages of the factored approach.

Superior Precision

On the Caltech-256 dataset, f-AROMA achieved a significant performance boost. It improved precision at the top-ranked result by 50% compared to OASIS, the previous state-of-the-art.

Precision vs. top k results on Caltech-256, comparing AROMA variants with several baseline methods.

Faster Convergence

Beyond final precision, f-AROMA converges much faster than competing methods. In text classification tasks, it reached peak performance levels up to ten times faster than OASIS.

Robustness and Theoretical Guarantees

A notable finding was AROMA's robustness to its primary hyperparameter, $r$. Performance remained stable across three orders of magnitude, simplifying the tuning process. Furthermore, the authors established theoretical mistake bounds, proving the algorithm's reliability relative to the best fixed matrix.

Conclusion

AROMA successfully bridges the gap between the expressive power of second-order learning and the scalability requirements of matrix models. By leveraging covariance factorization, it provides a robust, high-performance solution for large-scale similarity learning and classification tasks. Future work may explore enforcing symmetry constraints for specific metric learning applications and further optimizing for extremely high-dimensional, dense data.

Summary updated

Abstract

Algorithms for learning distributions over weight-vectors, such as AROW were recently shown empirically to achieve state-of-the-art performance at various problems, with strong theoretical guaranties. Extending these algorithms to matrix models pose challenges since the number of free parameters in the covariance of the distribution scales as $n^4$ with the dimension $n$ of the matrix, and $n$ tends to be large in real applications. We describe, analyze and experiment with two new algorithms for learning distribution of matrix models. Our first algorithm maintains a diagonal covariance over the parameters and can handle large covariance matrices. The second algorithm factors the covariance to capture inter-features correlation while keeping the number of parameters linear in the size of the original matrix. We analyze both algorithms in the mistake bound model and show a superior precision performance of our approach over other algorithms in two tasks: retrieving similar images, and ranking similar documents. The factored algorithm is shown to attain faster convergence rate.
BibTeX
@inproceedings{crammer2012adaptive,
  author = {Koby Crammer and Gal Chechik},
  title = {{Adaptive Regularization for Weight Matrices}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
  url = {https://openreview.net/forum?id=H1Nlkhbubr},
}
Figure