RECORD
Robust Frequent Directions with Application in Online Learning
Machine Learning · Submitted 15 May 2017
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim The experimental studies demonstrate that the proposed method outperforms state-of-the-art second order online learning algorithms.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The frequent directions (FD) technique is a deterministic approach for online sketching that has many applications in machine learning. | background 1.00 | 0.07 | 0.04 | asserted 1.00 |
| s1 | The conventional FD is a heuristic procedure that often outputs rank deficient matrices. | background 0.63 | 0.10 | 0.02 | asserted 0.84 |
| s2 | To overcome the rank deficiency problem, we propose a new sketching strategy called robust frequent directions (RFD) by introducing a regularization term. | contribution 0.97 | 0.93 | 0.18 | asserted 0.99 |
| s3 | RFD can be derived from an optimization problem. | method 0.93 | 0.81 | 0.05 | asserted 1.00 |
| s4 | It updates the sketch matrix and the regularization term adaptively and jointly. | method 0.99 | 0.83 | 0.06 | asserted 1.00 |
| s5 | RFD reduces the approximation error of FD without increasing the computational cost. | result 0.97 | 0.86 | 0.33 | asserted 1.00 |
| s6 | We also apply RFD to online learning and propose an effective hyperparameter-free online Newton algorithm. | contribution 0.98 | 0.95 | 0.10 | asserted 1.00 |
| s7 | We derive a regret bound for our online Newton algorithm based on RFD, which guarantees the robustness of the algorithm. | result 0.50 | 0.96 | 0.18 | asserted 1.00 |
| s8 | The experimental studies demonstrate that the proposed method outperforms state-of-the-art second order online learning algorithms. | result 1.00 | 0.94 | 0.56 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
How the literature uses it
2 arXiv papers cite this in 4 sentences
Papers citing it · 2 sentences without a confident label
Compares with it 2 papers
-
In this section, we investigate the numerical performance of $$ and compare it against competing algorithms, namely, GROUSE [ref] , the method of frequent directions (FD) [ref] , and the power method (PM) [ref] , all detailed in Section [ref].
MOSES: A Streaming Algorithm for Linear Dimensionality Reduction · Experiments · 0.99
-
The algorithms considered in this instance are: $$ (on a single node network), GROUSE [ref] , Frequent Directions (FD) [ref] , the Power Method (PM) [ref] , and a variant of Projection Approximation Subspace Tracking (PAST) [ref] , named SPIRIT (SP) [ref] .
Federated Principal Component Analysis · Computational performance evaluation · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.