Robust Frequent Directions with Application in Online Learning

Luo Luo, Cheng Chen, Zhihua Zhang, Wu-Jun Li, Tong ZhangJMLR 2019 · OpenReview

TL;DR

This paper introduces Robust Frequent Directions (RFD), a novel matrix sketching technique that improves upon the standard Frequent Directions (FD) method by incorporating a regularization term. RFD addresses the rank deficiency issue often encountered with FD, leading to more robust and accurate matrix approximations. This improvement is then applied to online learning, resulting in a hyperparameter-free online Newton algorithm that achieves better performance and more robust regret bounds compared to existing methods.

What Problem Does This Paper Address?

Matrix sketching is a crucial technique for handling large-scale datasets in machine learning, enabling efficient matrix approximation. The Frequent Directions (FD) method is a popular deterministic sketching algorithm for online learning scenarios where data arrives sequentially. However, a key limitation of FD is that it often produces rank-deficient matrices, which can negatively impact the performance of downstream algorithms, particularly those requiring well-conditioned matrices (like Newton-type methods). While adding a regularization term can address this, it typically introduces a hyperparameter that needs careful tuning. This paper aims to overcome these limitations by proposing a new sketching method, Robust Frequent Directions (RFD), that adaptively incorporates regularization into the sketching process, making it robust and hyperparameter-free for online learning applications.

Methods

The core contribution is the Robust Frequent Directions (RFD) algorithm. Unlike standard FD, which focuses solely on low-rank approximation, RFD simultaneously updates the sketch matrix and a regularization term. This is achieved by framing the update as an optimization problem. RFD aims to approximate $A^TA$ by $B^TB + \alpha I$, where $B$ is the sketch matrix and $\alpha$ is the regularization parameter. The algorithm adaptively updates both $B$ and $\alpha$ jointly, ensuring that the resulting approximation is not only low-rank but also well-conditioned.

The paper then applies RFD to online learning, proposing a sketched online Newton algorithm (RFD-SON). This algorithm leverages RFD to approximate the Hessian matrix, which is crucial for second-order online learning methods. A key advantage of RFD-SON is that it is hyperparameter-free, meaning it does not require manual tuning of the regularization parameter $\alpha_0$. The algorithm adaptively adjusts $\alpha$ during training, leading to a well-conditioned Hessian and improved robustness. The authors also provide theoretical guarantees in the form of regret bounds for their RFD-SON algorithm.

Datasets

The paper evaluates its methods on six real-world datasets:

  • a9a
  • gisette
  • sido0
  • farm-ads
  • rcv1
  • real-sim

These datasets are standard benchmarks for machine learning tasks and are sourced from various repositories like LIBSVM and UCI Machine Learning Repository.

Key Insights and Ideas

  • Jointly optimizing sketch and regularization: The fundamental insight is that by treating the sketch matrix and the regularization term as coupled entities in an optimization problem, one can achieve a more robust and accurate matrix approximation than by treating them separately.
  • Hyperparameter-free online learning: Applying RFD to online Newton methods eliminates the need for hyperparameter tuning, which is a significant practical advantage and a common challenge in existing sketched second-order methods.
  • Improved theoretical guarantees: RFD leads to tighter error bounds for matrix approximation and more robust regret bounds for online learning algorithms, demonstrating its theoretical superiority.
  • Robustness against rank deficiency: RFD directly addresses the rank deficiency problem inherent in standard FD, making it more suitable for applications where matrix invertibility or conditioning is critical.

Key Results

  • Matrix Approximation: RFD consistently achieved lower spectral norm errors compared to FD and its variants (PFD, CFD) across various datasets. The error reduction was often close to half of that achieved by FD, aligning with theoretical predictions.
  • Online Learning Performance: RFD-SON demonstrated superior performance in terms of test error and online error rate compared to other online learning algorithms, including ADAGRAD, standard online Newton (FULL-ON), and sketched versions using FD, PFD, RP, and Oja's methods.
  • Hyperparameter Sensitivity: RFD-SON showed significantly less sensitivity to the regularization parameter $\alpha_0$ compared to other methods, often performing well even with small values of $\alpha_0$, and in some cases, achieving good results with $\alpha_0=0$. This validates its hyperparameter-free nature.
  • Computational Efficiency: While RFD introduces a regularization term, its computational cost is comparable to standard FD, especially when using accelerated algorithms. RFD-SON also benefits from efficient updates due to sketching.

Limitations and Future Work

  • Limitations: The paper primarily focuses on convex online optimization. While the authors mention that RFD is not limited to convex problems, their theoretical guarantees and experimental validation are concentrated on this setting. The performance in non-convex scenarios is not explored in depth.
  • Future Work: The authors suggest exploring the application of RFD in stochastic optimization and non-convex problems. Further research could also investigate more advanced adaptive regularization strategies or explore RFD's potential in other areas of machine learning that rely on matrix approximations.

Summary updated

Abstract

The frequent directions (FD) technique is a deterministic approach for online sketching that has many applications in machine learning. The conventional FD is a heuristic procedure that often outputs rank deficient matrices. To overcome the rank deficiency problem, we propose a new sketching strategy called robust frequent directions (RFD) by introducing a regularization term. RFD can be derived from an optimization problem. It updates the sketch matrix and the regularization term adaptively and jointly. RFD reduces the approximation error of FD without increasing the computational cost. We also apply RFD to online learning and propose an effective hyperparameter-free online Newton algorithm. We derive a regret bound for our online Newton algorithm based on RFD, which guarantees the robustness of the algorithm. The experimental studies demonstrate that the proposed method outperforms state-of-the-art second order online learning algorithms.
BibTeX
@article{luo2019robust,
  author = {Luo Luo and Cheng Chen and Zhihua Zhang and Wu-Jun Li and Tong Zhang},
  title = {{Robust Frequent Directions with Application in Online Learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=kgPmf_Cr3Re},
}
Figure