- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies online k-means and online weighted low-rank approximation (WLRA), where a learner chooses a compressed representation before each data point arrives. For k-means, multiplicative weights over experts defined on a grid in a random Johnson–Lindenstrauss projection, with Follow-the-Leader centers kept in the ambient space, give regret against an oblivious stream. For WLRA, two algorithms over charts of the Grassmannian give sublinear regret against the best rank- subspace and a comparison, both in time exponential in ; a polynomial-time alternative runs online gradient descent over a reduced Fantope for a weighted projection surrogate. Experiments on MNIST, MovieLens and synthetic streams evaluate an adaptive hierarchical heuristic and the Fantope update.
Critical strengths
-
A clear separation of comparator classes and an explanation of the computational barrier. The paper distinguishes regret against the exact rank- comparator, a comparison and a relaxed surrogate, and its online-to-offline reduction (Appendix G) shows that efficient algorithms with the exact-comparator guarantee are unlikely unless .
-
Two useful geometric observations. The marginal Johnson–Lindenstrauss argument avoids a union bound over the horizon, and the stationarity of the cumulative loss at its minimizer allows a discretization scale instead of .
Critical weaknesses
- The experiments do not test the paper's results, and the figures do not show the comparisons described in the text. The real-data experiments (Section 5 and Appendix H.2) evaluate an adaptive binary-tree heuristic that, as the authors state, is neither of the analyzed Grassmannian algorithms, yet the plots label it "Grassmannian HRD"; there is no experiment for online k-means. The reported reductions of 73.78–85.93% on MNIST and 77.65–86.43% on MovieLens are measured against a "fixed random control" whose matrix is not an orthogonal projector (Appendix H.1). On MNIST its cumulative loss is about 4800 over 5000 unit-norm rows for every (Figure 1), almost the loss of predicting zero, whereas a random rank- orthogonal projector in loses , and per row on average. Against the meaningful baselines (FTRL, Fantope OGD and the offline SVD), the curves in Figures 1 and 2 coincide at the plotted scale, whose range is set by the control, and no numbers are given for these comparisons, so claims such as a lower cumulative loss than FTRL at and cannot be checked. The feature spaces are fitted by SVD on the evaluated streams before the first round, and the real-data runs are ten permutations of a single dataset.
All real-data runs are unweighted, so they solve online PCA, for which polynomial-time algorithms with optimal regret against the best rank- subspace exist (Warmuth & Kuzmin, 2008; Nie et al., 2016). Both are cited but not compared. In MovieLens, where weights would naturally encode missing ratings, the missing entries are filled with zeros instead. The weighted experiments (Appendix H.3) use and and measure the eigenspace extracted from the Fantope iterate, not the loss controlled by Theorem 4.3; in Figures 3 and 5 the unweighted Fantope and online-PCA curves overlap as well.
- The theoretical gains are smaller than presented, and the paper is hard to follow. For online k-means, the expert class is independent of and only at a fixed accuracy , where Theorem 3.1 leaves an additive term. Sublinear regret requires (Remark 1); the class then has experts, all updated every round, and the regret is . A grid over the centers in gives regret with experts, so the projection helps only when , and only against an oblivious stream. For WLRA, the second-order discretization halves the exponent of the running time ( leaves instead of ) but improves the regret only by a constant factor. The polynomial-time result (Theorem 4.3) is projected online gradient descent for a convex quadratic over a reduced Fantope, against an anchor-restricted fractional comparator, with no stated relation to the WLRA optimum. The paper combines these four constructions with frequently repeated caveats, and its experimental sections read like documentation of a script ("The supplied runner specifies ten seeded stream permutations for each rank") rather than a description of a designed study.
Questions for authors
-
Can the authors report, on MNIST and MovieLens, each method's excess cumulative loss over the offline SVD with its variability across runs, with the control replaced by a random orthogonal rank- projector and the feature map fitted on data outside the evaluated stream?
-
Can the authors compare with the online PCA algorithms of Warmuth & Kuzmin (2008) and Nie et al. (2016) in the unweighted experiments, and evaluate a weighted problem on real data, for example MovieLens with small positive weights on missing ratings?
-
Can at least one theorem-backed algorithm be run in a regime where its cost is manageable (small ), measuring the quantity its theorem bounds?
Thank you for their insightful comments. We have added various experiments to address the reviewer's concerns. Exact details have been added in Section 5 and Appendix H, but short summaries have been given below.
We replaced the adaptive hierarchy with implementations of Algorithms 4 and 5 using the prescribed chart grids and local updates, finite-step MCMC, and tuned η=1000 on real data. Across ten paired orders on MNIST and MovieLens at k=10,15,20, both have slightly higher mean loss than FTRL, within 0.71. We now report numerical losses and SVD excesses.
We have added three synthetic studies, each using five fresh validation seeds and pre-update weighted fitting loss; uncertainties below are sample SDs.
WeightedImportanceCycleNoisy (d=6, k=2, T=2000, κ=64) combines cyclic signal directions, a frequent low-importance distractor, and small Gaussian noise. Algorithms 4 and 5 achieve 209.25±4.66 and 208.69±6.23, versus 281.03±3.74 for weighted FTRL, with lower loss on every seed. Ignoring weights raises their mean losses to 353.84 and 355.90, supporting the value of feature weights for the algorithms.
WeightedShift uses the same d,k,κ with T=4000 and no added noise. In this experiment, competing directions repeatedly exchange their cumulative weighted-energy advantage. Algorithms 4 and 5 achieve 921.96±9.28 and 923.08±6.61, versus 1742.10±9.33 for weighted FTRL, about 47 lower. This experiment is consistent with the theoretical robustness of the Grassmannian algorithms compared to FTRL, as it can be a more unbiased estimator.
The tracking study (d=60, k=20, T=6000) combines a rotating signal with stronger distractor noise. Weights encode inverse noise variance before normalization. Rounded Fantope achieves 229.93±2.86, versus 255.50±2.86 for weighted FTRL and 546.10±2.72 when Fantope ignores weights, supporting reliability weighting under drift.
Air Quality (d=12, k=2, T=1512) uses chronological observations with observed-entry weight 1 and missing-entry weight 0.01. Fantope achieves weighted fitting loss 238.52, versus 463.87 and 462.48 for weighted FTRL with 3 and 30 ALS iterations. This exploratory, dataset-specific comparison gives a 48.43% reduction over the stronger baseline.
We have added Loss MEG and GD from Nie et al. (2016), including the MEG update of Warmuth and Kuzmin (2008). At MNIST k=10, they give 1347.31±0.09 and 1344.88±0.59, versus 1230.06±0.73 and 1229.05±0.59 for Algorithms 4 and 5. Both Grassmannian methods have lower mean loss in all six configurations. The PCA rates are untuned and the initialization is isotropic.