acceptodds
Under review as a conference paper at ICLR 2027

Online Geometric Optimization via Projection, Hierarchical Discretization, and Convex Relaxation

Abstract

We study online optimization problems in which a learner must choose a compressed representation before observing each incoming data point. We focus on two settings: online -means clustering and online weighted low-rank approximation (WLRA). For online -means, we revisit multiplicative-weights methods over discretized experts and show how marginal Johnson–Lindenstrauss projections reduce the effective dimension without requiring uniform distance preservation over the entire stream. We further decouple projected Voronoi assignment from ambient center recovery by maintaining Follow-the-Leader centroids directly in , avoiding pseudo-inverse distortion. For online WLRA, we formulate the rank- comparator class as the Grassmannian and develop a hierarchical region decomposition coupled with tree-structured multiplicative weights. This yields sublinear regret against the best fixed rank- subspace, while making explicit the exponential cost of Grassmannian discretization. A second Grassmannian algorithm obtains a comparison using a number of regions independent of the horizon. We then introduce a Fantope relaxation that gives polynomial-time online updates and sublinear regret for a weighted projection surrogate against a reduced fractional comparator. Together, these results give a unified view of online approximation under nonconvex geometric structure, supported by empirical evaluations on online low-rank approximation.

Primary area:
learning theory
Keywords:
online learning, clustering, low-rank approximation

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_vRhUOpenReview ↗
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 O(T3/4 polylog T)O(T^{3/4}\,\mathrm{polylog}\,T) against an oblivious stream. For WLRA, two algorithms over charts of the Grassmannian give sublinear regret against the best rank-kk subspace and a (1+ε)(1+\varepsilon) comparison, both in time exponential in k(d−k)k(d-k); 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
  1. A clear separation of comparator classes and an explanation of the computational barrier. The paper distinguishes regret against the exact rank-kk comparator, a (1+ε)(1+\varepsilon) 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 NP⊆BPP\mathrm{NP}\subseteq\mathrm{BPP}.

  2. 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 T−1/4T^{-1/4} instead of T−1/2T^{-1/2}.

Critical weaknesses
  1. 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 BB⊤BB^\top is not an orthogonal projector (Appendix H.1). On MNIST its cumulative loss is about 4800 over 5000 unit-norm rows for every kk (Figure 1), almost the loss of predicting zero, whereas a random rank-kk orthogonal projector in d=50d=50 loses 1−k/d=0.81-k/d=0.8, 0.70.7 and 0.60.6 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 k=15k=15 and k=20k=20 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-kk 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 d=20d=20 and k=3k=3 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.

  1. The theoretical gains are smaller than presented, and the paper is hard to follow. For online k-means, the expert class is independent of dd and TT only at a fixed accuracy ε\varepsilon, where Theorem 3.1 leaves an additive O(εT)O(\varepsilon T) term. Sublinear regret requires ε=T−1/4\varepsilon=T^{-1/4} (Remark 1); the class then has exp⁡(O~(kT))\exp(\tilde O(k\sqrt T)) experts, all updated every round, and the regret is O~(T3/4)\tilde O(T^{3/4}). A grid over the centers in Rd\mathbb R^d gives regret O~(kdT)\tilde O(\sqrt{kdT}) with TO(kd)T^{O(kd)} experts, so the projection helps only when d≳Td\gtrsim\sqrt T, and only against an oblivious stream. For WLRA, the second-order discretization halves the exponent of the running time (Tk(d−k)/4T^{k(d-k)/4} leaves instead of Tk(d−k)/2T^{k(d-k)/2}) 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
  1. 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-kk projector and the feature map fitted on data outside the evaluated stream?

  2. 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?

  3. Can at least one theorem-backed algorithm be run in a regime where its cost is manageable (small k(d−k)k(d-k)), measuring the quantity its theorem bounds?

1 comment

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.

The experiments do not test the paper's results, and the figures do not show the comparisons described in the text.

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\eta=1000 on real data. Across ten paired orders on MNIST and MovieLens at k=10,15,20k=10,15,20, both have slightly higher mean loss than FTRL, within 0.710.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=6d=6, k=2k=2, T=2000T=2000, κ=64\kappa=64) combines cyclic signal directions, a frequent low-importance distractor, and small Gaussian noise. Algorithms 4 and 5 achieve 209.25±4.66209.25\pm4.66 and 208.69±6.23208.69\pm6.23, versus 281.03±3.74281.03\pm3.74 for weighted FTRL, with lower loss on every seed. Ignoring weights raises their mean losses to 353.84353.84 and 355.90355.90, supporting the value of feature weights for the algorithms.

WeightedShift uses the same d,k,κd,k,\kappa with T=4000T=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.28921.96\pm9.28 and 923.08±6.61923.08\pm6.61, versus 1742.10±9.331742.10\pm9.33 for weighted FTRL, about 4747% 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=60d=60, k=20k=20, T=6000T=6000) combines a rotating signal with stronger distractor noise. Weights encode inverse noise variance before normalization. Rounded Fantope achieves 229.93±2.86229.93\pm2.86, versus 255.50±2.86255.50\pm2.86 for weighted FTRL and 546.10±2.72546.10\pm2.72 when Fantope ignores weights, supporting reliability weighting under drift.

Air Quality (d=12d=12, k=2k=2, T=1512T=1512) uses chronological observations with observed-entry weight 11 and missing-entry weight 0.010.01. Fantope achieves weighted fitting loss 238.52238.52, versus 463.87463.87 and 462.48462.48 for weighted FTRL with 3 and 30 ALS iterations. This exploratory, dataset-specific comparison gives a 48.43%48.43\% reduction over the stronger baseline.

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?

We have added Loss MEG and GD from Nie et al. (2016), including the MEG update of Warmuth and Kuzmin (2008). At MNIST k=10k=10, they give 1347.31±0.091347.31\pm0.09 and 1344.88±0.591344.88\pm0.59, versus 1230.06±0.731230.06\pm0.73 and 1229.05±0.591229.05\pm0.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.

Reviewer_Tb3dOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the online k-means and online WLRA problems. The authors develop algorithms that combine techniques such as marginal JL projection, projected Voronoi experts, and Grassmannian constructions to solve these two problems. They conduct extensive numerical experiments on real and synthetic data to evaluate a practical hierarchical heuristic and Fantope updates.

Critical strengths
  1. This paper carefully claims its scope. Specifically, it distinguishes inverse-polynomial-accuracy hardness from hardness at a fixed constant approximation factor.

  2. The authors are candid about limitations and provide counterexamples. They provide solid empirical diagnostics for heterogeneous reliability, and the extensive empirical results provide evidence that coordinate reliability can be useful for the proposed update.

Critical weaknesses
  1. The simulation experiments do not evaluate the algorithms and objectives covered by the main guarantees. For example, the hierarchy evaluated on MNIST and MovieLens is a data-dependent heuristic with adaptive splits and updated subspace centers, whereas Theorem 4.1 analyzes fixed representatives in a hierarchy constructed before the stream.

  2. The computational lower bound does not establish the optimality of the proposed tradeoffs. Appendix G provides an online-to-offline computational barrier rather than a regret lower bound matching Theorems 4.1–4.3.

  3. The relevance of the assumptions to the motivating applications is only partially established. The theoretical assumptions used in this paper remain unclear for the cited recommendation and streaming applications, and they deserve a more precise discussion.

  4. The Fantope method changes the loss, permits fractional decisions that may have rank greater than kk, and restricts the comparator to an anchor subspace. Although these changes are explicitly acknowledged, their practical consequences remain largely unquantified.

Questions for authors
  1. It is recommended that the authors conduct a small positive-weight experiment that runs the actual algorithms from Theorems 4.1 and 4.2.

  2. The practicality of the paper would be improved if the authors provided a concrete application that best matches strictly positive, sufficiently well-conditioned weights and a fixed-subspace comparator.

  3. Could the authors quantify the rounding gap and the loss attributable to the anchor restriction, either theoretically or through a focused diagnostic?

  4. Do the main conclusions remain valid if the fixed control is replaced by an orthonormal random subspace and the preprocessing is fitted on a separate calibration set or a past-only prefix?

1 comment

Thank you for the helpful 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.

It is recommended that the authors conduct a small positive-weight experiment that runs the actual algorithms from Theorems 4.1 and 4.2.

We replaced the adaptive hierarchy with implementations of Algorithms 4 and 5.

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=6d=6, k=2k=2, T=2000T=2000, κ=64\kappa=64) combines cyclic signal directions, a frequent low-importance distractor, and small Gaussian noise. Algorithms 4 and 5 achieve 209.25±4.66209.25\pm4.66 and 208.69±6.23208.69\pm6.23, versus 281.03±3.74281.03\pm3.74 for weighted FTRL, with lower loss on every seed. Ignoring weights raises their mean losses to 353.84353.84 and 355.90355.90, supporting the value of feature weights for the algorithms.

WeightedShift uses the same d,k,κd,k,\kappa with T=4000T=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.28921.96\pm9.28 and 923.08±6.61923.08\pm6.61, versus 1742.10±9.331742.10\pm9.33 for weighted FTRL, about 4747% 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=60d=60, k=20k=20, T=6000T=6000) combines a rotating signal with stronger distractor noise. Weights encode inverse noise variance before normalization. Rounded Fantope achieves 229.93±2.86229.93\pm2.86, versus 255.50±2.86255.50\pm2.86 for weighted FTRL and 546.10±2.72546.10\pm2.72 when Fantope ignores weights, supporting reliability weighting under drift.

Air Quality (d=12d=12, k=2k=2, T=1512T=1512) uses chronological observations with observed-entry weight 11 and missing-entry weight 0.010.01. Fantope achieves weighted fitting loss 238.52238.52, versus 463.87463.87 and 462.48462.48 for weighted FTRL with 3 and 30 ALS iterations. This exploratory, dataset-specific comparison gives a 48.43%48.43\% reduction over the stronger baseline.

The computational lower bound does not establish the optimality of the proposed tradeoffs.

We agree that Appendix G does not establish optimality of our tradeoffs. However, we argue that our algorithmic improvement is still significant. Our second-order analysis exploits stationarity of the cumulative loss at the hindsight optimum to reduce the representative count from Tk(d−k)/2T^{k(d-k)/2} to Tk(d−k)/4T^{k(d-k)/4} while preserving the regret order. This halves the exponent governing the horizon dependence of the discretization, rather than merely improving a constant factor in its size. The locally convexified method provides a further improvement, as it achieves a global (1+ε)(1+\varepsilon) comparison with sublinear additive error using a number of cells independent of TT at fixed accuracy. These results demonstrate concrete gains even though the optimal computational tradeoff remains open.

Could the authors quantify the rounding gap and the loss attributable to the anchor restriction, either theoretically or through a focused diagnostic?

Yes. We quantify rounding and anchor restriction separately. Let SVS_V be the best fractional-surrogate value and CVC_V the best rank-kk WLRA value within the anchor. We obtain SV≤(κ+1)24κCV.S_V\le \frac{(\kappa+1)^2}{4\kappa}C_V. For rounding, let R(P)R(P) project onto the top-kk eigenspace of VPV⊤VPV^\top. We separately establish $\ell_t(\operatorname{range}R(P)) \le \kappa(k+1)^2\widetilde\ell_t(P),$ which bounds the rounded prediction's fitting loss in terms of its fractional surrogate loss.

For unweighted data and an orthonormal anchor, the restriction costs exactly

=\sum_{i=1}^k\lambda_i(\Sigma) -\sum_{i=1}^k\lambda_i(V^\top\Sigma V), \qquad \Sigma=\sum_t x_tx_t^\top.$$ The two sums measure the energy captured by the best unrestricted and anchor-restricted rank-$k$ subspaces, respectively. Their difference therefore isolates the anchor cost. Our rounded-Fantope experiment complements these bounds by evaluating rank-$k$ fitting loss directly, although it does not isolate the two effects empirically. > Do the main conclusions remain valid if the fixed control is replaced by an orthonormal random subspace and the preprocessing is fitted on a separate calibration set or a past-only prefix? Calibration-only preprocessing is also compatible with our theoretical framework. Conditional on a feature map fitted to a separate calibration set, the analyzed algorithms operate on a fixed transformed stream and compete with the best fixed subspace in that representation. Their guarantees apply under the stated boundedness and stream assumptions. With a past-only calibration prefix, the same argument applies to the evaluation suffix, with the feature map and Fantope anchor held fixed.
Reviewer_CErqOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Regret bounds for two online problems where the learner picks a compressed representation before seeing each point. For online k-means, multiplicative weights over projected Voronoi experts with ambient Follow-the-Leader means. For online weighted low-rank approximation (WLRA), two Grassmannian discretization algorithms with running time exponential in k(d−k)k(d-k), an online-to-offline barrier for polynomial-time algorithms, and online gradient descent over a reduced Fantope for a surrogate loss. Experiments on MNIST, MovieLens and synthetic streams use a practical unweighted hierarchy and the Fantope update.

Critical strengths

The computational barrier (Theorem G.2, Corollary G.3) is useful. It explains why a polynomial-time algorithm with small regret against the exact rank-k comparator is unlikely, at least at inverse-polynomial accuracy. The authors also say plainly what each guarantee does and does not cover, and they list the limits of their experiments in Appendix H.4.

Critical weaknesses

W1. None of the main guarantees gives both a meaningful bound and a usable algorithm. Theorem 3.1 has an additive O(εT)O(\varepsilon T) term, so regret is sublinear only if ε→0\varepsilon \to 0 with TT. With the suggested ε=T−1/4\varepsilon = T^{-1/4}, log⁡∣E∣\log|E| grows like T\sqrt{T} up to log factors, so the claimed independence from dd and TT holds only at fixed ε\varepsilon, where the regret is linear. Theorems 4.1 and 4.2 are exponential in k(d−k)k(d-k). The T−1/4T^{-1/4} resolution in Theorem 4.1 halves the exponent of the expert count but leaves the regret order unchanged. Theorem 4.3 is standard OGD on a convex set for a different loss and a restricted comparator, and the paper itself notes that it makes no comparison to the WLRA optimum.

W2. The experiments do not support the conclusions drawn from them. The tested hierarchy is neither of the analyzed algorithms and the real-data runs are unweighted, as the authors acknowledge. The headline reductions on MNIST (74–86%) are measured against a control that Appendix H.4 says is not an orthogonal rank-k projector. In Fig. 1 its loss is near 4800 for all three values of kk, close to the 5000 from predicting zero, while a random rank-kk orthogonal projector would give about 4000, 3500 and 3000 in expectation. The hierarchy and FTRL also start from the first kk coordinate vectors of Truncated SVD features. Their span is the best rank-kk subspace for the fitted data before row normalization, and should still be close afterwards. Their overlap with the offline optimum from the first rounds therefore says little about learning, and I do not think the claim that the hierarchy adapts to low-dimensional structure is supported.

Questions for authors
  1. What cumulative loss does a fixed subspace spanned by the first kk SVD coordinates achieve with no updates? Why does the fixed random control's loss not change with kk?
  2. How does Theorem 3.1 compare with the (1+ε)(1+\varepsilon)-approximate regret guarantee of Cohen-Addad et al. (2021), given the additive O(εT)O(\varepsilon T) term here?
2 comments

Thank you for the thoughtful 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.

W1. None of the main guarantees gives both a meaningful bound and a usable algorithm.

It is unlikely that a meaningful bound and a usable algorithm can exist in tandem, due to the results in Appendix G which rule out the stated exact-comparator and uniform inverse-accuracy WLRA guarantees with polynomial parameter dependence unless NP⊆BPP\mathrm{NP}\subseteq\mathrm{BPP}. Our WLRA algorithms therefore address both sides of this tradeoff. The Grassmannian methods retain the standard weighted fitting loss and a global fixed-subspace comparator, while second-order discretization and local convexification reduce the computational cost of obtaining these guarantees. The Fantope method instead prioritizes computational efficiency, achieving sublinear regret for an anchored fractional surrogate with polynomial-time updates. Its guarantee concerns a different loss and comparator, as explicitly stated, but provides a tractable alternative with a rigorous performance guarantee. Thus, the results offer complementary guarantees rather than a single algorithm that resolves the computational barrier.

W2. The experiments do not support the conclusions drawn from them.

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\eta=1000 on real data. Across ten paired orders on MNIST and MovieLens at k=10,15,20k=10,15,20, both have slightly higher mean loss than FTRL, within 0.710.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=6d=6, k=2k=2, T=2000T=2000, κ=64\kappa=64) combines cyclic signal directions, a frequent low-importance distractor, and small Gaussian noise. Algorithms 4 and 5 achieve 209.25±4.66209.25\pm4.66 and 208.69±6.23208.69\pm6.23, versus 281.03±3.74281.03\pm3.74 for weighted FTRL, with lower loss on every seed. Ignoring weights raises their mean losses to 353.84353.84 and 355.90355.90, supporting the value of feature weights for the algorithms.

WeightedShift uses the same d,k,κd,k,\kappa with T=4000T=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.28921.96\pm9.28 and 923.08±6.61923.08\pm6.61, versus 1742.10±9.331742.10\pm9.33 for weighted FTRL, about 4747% 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=60d=60, k=20k=20, T=6000T=6000) combines a rotating signal with stronger distractor noise. Weights encode inverse noise variance before normalization. Rounded Fantope achieves 229.93±2.86229.93\pm2.86, versus 255.50±2.86255.50\pm2.86 for weighted FTRL and 546.10±2.72546.10\pm2.72 when Fantope ignores weights, supporting reliability weighting under drift.

Air Quality (d=12d=12, k=2k=2, T=1512T=1512) uses chronological observations with observed-entry weight 11 and missing-entry weight 0.010.01. Fantope achieves weighted fitting loss 238.52238.52, versus 463.87463.87 and 462.48462.48 for weighted FTRL with 3 and 30 ALS iterations. This exploratory, dataset-specific comparison gives a 48.43%48.43\% reduction over the stronger baseline.

What cumulative loss does a fixed subspace spanned by the first kk SVD coordinates achieve with no updates?

Its MovieLens losses are 415.01415.01, 323.45323.45, and 254.98254.98 at k=10,15,20k=10,15,20, invariant to order and lower than Algorithms 4 and 5 and FTRL. We therefore no longer interpret proximity to SVD as discovery of unknown structure. The MNIST frozen value and calibration-only evaluation remain unreported. The old control has nonorthogonal columns, and we have removed its headline percentages in the revised copy. A random orthogonal projector would have expected loss T(1−k/d)T(1-k/d).

How does Theorem 3.1 compare with the (1+ε)(1+\varepsilon)-approximate regret guarantee of Cohen-Addad et al. (2021), given the additive O(εT)O(\varepsilon T) term here?

Their result gives stronger approximate regret at fixed accuracy, but has a higher exponential dependence in the runtime. Our tradeoff removes dd from the exponential routing class, with log⁡∣E∣=O~(k/ε2)\log|\mathcal E|=\widetilde O(k/\varepsilon^2), at the cost of O(εT)O(\varepsilon T) additional error. For fixed kk, choosing ε=T−1/4\varepsilon=T^{-1/4} gives O~(T3/4)\widetilde O(T^{3/4}) regret and exp⁡(O~(kT))\exp(\widetilde O(k\sqrt T)) experts.

Thank you for the response and for reporting the frozen SVD subspace. My concerns remain. Appendix G does not concern Theorem 3.1, and Corollary G.3 makes no claim about a fixed constant factor. Unweighted online PCA (Warmuth & Kuzmin, 2008; Nie et al., 2016) already gives polynomial-time rank-kk plays with expected loss at most κCWLRA\kappa C_{\mathrm{WLRA}} plus WW times its regret, which is better than the factor (k+1)2(κ+1)2/4(k+1)^2(\kappa+1)^2/4 relative to the anchored optimum that your new bounds give the rounded Fantope plays. On real data, Algorithms 4 and 5 do not beat FTRL, the frozen subspace beats all three on MovieLens, and η=1000\eta = 1000 is far above the prescribed 8log⁡N/T\sqrt{8 \log N / T}. I keep my score.

Reviewer_VbUQOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies online kk-means and online weighted low-rank approximation (WLRA). For kk-means, projected grid points determine assignments while empirical centers are maintained in the original space. A marginal Johnson--Lindenstrauss argument avoids a union bound over the horizon and gives an expected comparison with the true hindsight objective. At fixed ϵ\epsilon, the expert count has no dependence on dd or direct dependence on TT, but remains exponential in kk and 1/ϵ1/\epsilon.

For WLRA, the paper covers Gr⁡(k,d)\operatorname{Gr}(k,d) with bounded charts in k(d−k)k(d-k) coordinates. A second-order expansion at the cumulative optimum permits resolution T−1/4T^{-1/4} and gives sublinear regret against the exact rank-kk comparator. A second method runs a convex learner within each chart cell and obtains a (1+ϵ)(1+\epsilon) comparison with a number of cells independent of TT at fixed ϵ\epsilon. Both methods remain exponential in k(d−k)k(d-k).

An online-to-offline reduction connects this cost to the hardness of offline WLRA. The paper also gives a polynomial-time Fantope method, but it uses a fixed anchor, fractional projectors, and a weighted projection surrogate rather than standard WLRA. The experiments evaluate practical variants rather than the analyzed Grassmannian algorithms.

Critical strengths
  1. The paper uses the geometry of the decision spaces in a useful way. For kk-means, it projects the assignment rule while keeping the centers in the original space, which avoids reconstructing centers through a noninvertible projection. For WLRA, it works with subspaces rather than bases and uses the vanishing first derivative of the cumulative loss to reduce the required grid resolution from T−1/2T^{-1/2} to T−1/4T^{-1/4}. The two constructions share a useful idea: represent only the part of the decision that must be searched globally, and handle the rest with a local learner. In Section 3 this gives projected assignments with ambient means and in Section 4 it gives Grassmannian cells with a learner inside each cell.

  2. The paper is careful about the distinction between a strong comparator and an efficient algorithm. The Grassmannian methods use the standard WLRA loss but are exponential in k(d−k)k(d-k). The Fantope method is polynomial-time, but the paper states that it changes the anchor space, decision class, loss, and comparator. The online-to-offline reduction also explains why a uniform polynomial-time guarantee for standard WLRA would be difficult.

Critical weaknesses
  1. The experiments do not run either analyzed Grassmannian algorithm. The practical hierarchy uses data-dependent splits and has no stated connection to the regret bounds beyond the general geometric idea. The real-data experiments are unweighted, and their feature maps are fitted using all evaluated observations before the stream begins. The Fantope anchor is fitted from a prefix that is included in cumulative loss, while the synthetic plots evaluate a rank-kk eigenspace extracted from the fractional decision rather than the theorem's cumulative surrogate regret. The methods also use different feasible sets, and the fixed random control is generally not an orthogonal projector. No runtime or cell-count scaling is reported. The plots evaluate the heuristics, not Algorithms 4 and 5 or their regret bounds.

  2. The algorithms with the strongest comparators are not computationally usable. The kk-means method updates an expert class exponential in kk and 1/ϵ1/\epsilon, and both Grassmannian methods update exponentially many regions. The polynomial-time Fantope result does not solve this problem for standard WLRA: it competes with a fractional comparator in a fixed anchor space under a different loss. The hardness result rules out a uniform family with polynomial dependence at inverse-polynomial accuracy, but it does not rule out a polynomial-time method for an arbitrary fixed constant ϵ\epsilon.

Questions for authors
  1. Is there any condition on the anchor VV, the weights WtW_t, or the optimal subspace under which the best reduced-Fantope surrogate value provably controls CWLRAC_{\mathrm{WLRA}}?

  2. Can the authors run Algorithms 4 and 5 in a small-dimensional setting and report leaf or cell counts, runtime, and loss as TT, k(d−k)k(d-k), and ϵ\epsilon vary? The current hierarchy differs from both analyzed algorithms, so these experiments would show whether either analyzed discretization can be run even in small dimensions.

1 comment

Thank you for the helpful review. 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.

The experiments do not run either analyzed Grassmannian algorithm.

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\eta=1000 on real data. Across ten paired orders on MNIST and MovieLens at k=10,15,20k=10,15,20, both have slightly higher mean loss than FTRL, within 0.710.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=6d=6, k=2k=2, T=2000T=2000, κ=64\kappa=64) combines cyclic signal directions, a frequent low-importance distractor, and small Gaussian noise. Algorithms 4 and 5 achieve 209.25±4.66209.25\pm4.66 and 208.69±6.23208.69\pm6.23, versus 281.03±3.74281.03\pm3.74 for weighted FTRL, with lower loss on every seed. Ignoring weights raises their mean losses to 353.84353.84 and 355.90355.90, supporting the value of feature weights for the algorithms.

WeightedShift uses the same d,k,κd,k,\kappa with T=4000T=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.28921.96\pm9.28 and 923.08±6.61923.08\pm6.61, versus 1742.10±9.331742.10\pm9.33 for weighted FTRL, about 4747% 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=60d=60, k=20k=20, T=6000T=6000) combines a rotating signal with stronger distractor noise. Weights encode inverse noise variance before normalization. Rounded Fantope achieves 229.93±2.86229.93\pm2.86, versus 255.50±2.86255.50\pm2.86 for weighted FTRL and 546.10±2.72546.10\pm2.72 when Fantope ignores weights, supporting reliability weighting under drift.

Air Quality (d=12d=12, k=2k=2, T=1512T=1512) uses chronological observations with observed-entry weight 11 and missing-entry weight 0.010.01. Fantope achieves weighted fitting loss 238.52238.52, versus 463.87463.87 and 462.48462.48 for weighted FTRL with 3 and 30 ALS iterations. This exploratory, dataset-specific comparison gives a 48.43%48.43\% reduction over the stronger baseline.

The algorithms with the strongest comparators are not computationally usable.

The main contribution is an accuracy-computation tradeoff. Second-order analysis reduces the representative count from Tk(d−k)/2T^{k(d-k)/2} to Tk(d−k)/4T^{k(d-k)/4} without changing the regret order; local convexification makes the cell count independent of TT at fixed accuracy. Appendix G rules out the stated exact-comparator and uniform inverse-accuracy guarantees with polynomial parameter dependence unless NP⊆BPP\mathrm{NP}\subseteq\mathrm{BPP}. It does not rule out every fixed constant accuracy or prove optimality of our tradeoffs. The Fantope relaxation gives polynomial-time updates for its stated surrogate.

Is there any condition on the anchor VV, the weights WtW_t, or the optimal subspace under which the best reduced-Fantope surrogate value provably controls CWLRAC_{\text{WLRA}}?

Yes. Let SVS_V be the best reduced-Fantope surrogate value and CVC_V the best anchored rank-kk WLRA value. For μI⪯Wt⪯WI\mu I\preceq W_t\preceq WI and κ=W/μ\kappa=W/\mu, CVκ(k+1)≤SV≤(κ+1)24κCV.\frac{C_V}{\kappa(k+1)}\le S_V\le\frac{(\kappa+1)^2}{4\kappa}C_V. Thus CWLRA≤κ(k+1)SVC_{\mathrm{WLRA}}\le\kappa(k+1)S_V. If the anchor contains an optimum, CV=CWLRAC_V=C_{\mathrm{WLRA}}; scalar weights improve the upper factor to one. We also obtain SV≤κCWLRA+W∑t∥(I−VV⊤)xt∥22.S_V\le\kappa C_{\mathrm{WLRA}}+W\sum_t\|(I-VV^\top)x_t\|_2^2. These supplement Theorem 4.3 without changing its algorithm.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.