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:
- 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.
- 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.
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