- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper analyses a low-rank linear model where observations are received online from to , is a low rank matrix and is assumed piecewise constant with bounded jumps in time. The main goal is to estimate coefficient . The paper proposes a regret analysis for several type of estimators, assuming both known or unknown that improve upon each other in a ladder type going from to for some class of paths and complement analysis with corresponding lower bounds that match in their T-dependency. Some synthetic experiments are further proposed.
Critical strengths
The proposed ladder and its exhaustive list of results are generally significant with a clear improvement from to through various techniques by differentiating between a monotone learner like GD to a classic OLS but with well chosen adaptive time windows for their regression, that use a GLR test to detect change points.
The mathematical quality of the paper is good, every result is clearly stated, and while I did not fully read the appendix, it seems correct to me.
Critical weaknesses
My only concern that does not make this paper a clear acceptance for me is the lack of unpacking, discussion of the proposed results given their large amount especially as the paper sometimes lacks narrative. While the related work does propose some insights, it would have been good to discuss the novelty of these results individually.
Questions for authors
What happens if in the unknown case, is also unknown ? Could the algorithm be made adaptive w.r.t as well, i.e estimate an "adaptive optimal" rank ? Since the regret only cares about estimating and not whether the middle dimension is known.
3 comments
Response to Reviewer P8TY (2/2): unknown rank
"What happens if in the unknown case, is also unknown? Could the algorithm be made adaptive w.r.t. as well?" The revision adds three statements, each with its conditions (§6, "Unknown rank"; proofs in Appendix L), and an experiment. They cover recovering the true rank and working ranks above and below it.
1. A certified rank rule (Corollary 31). Under Theorem 10's assumptions and Definition 28's rank-rule protocol, let be the matrix-Bernstein radius of the moment estimate of epoch ; it depends only on and the epoch. Keep the eigenvectors of whose eigenvalues exceed . On the moment-concentration event of the proof of Theorem 10, which has probability at least : (i) in every epoch; (ii) in every epoch after the warm-up charged by , where ; this separation is what exact recovery needs, the nonzero population eigenvalues being at least under the excitation assumption. Thus Corollary 30 applies with , using the same threshold function and cadence as the true-rank learner; clipping covers the earlier rounds and the complement of the event. This rank rule does not take as input and satisfies the expected-regret bound of Theorem 10.
2. A working rank above (Corollary 30). Under the same assumptions and protocol, if, on that event, after the warm-up (in particular for a fixed working rank ) and the spacing condition of Theorem 10 holds with in place of , the bound of Theorem 10 holds with in place of in the tracking terms of its first line, while the constants , and of the cost of learning keep the true rank. The proof uses a perturbation lemma for the top- eigenspace and repeats the detection, burn-in and ghost-estimator steps in dimension .
3. A working rank below (Proposition 32, Corollary 33). For isotropic designs, if the predictions on a set of rounds lie in the range of one projector of rank , their regret on is at least , with the average of over . For GLR-U with a fixed working rank this applies epoch by epoch, and the regret is at least , linear in , when the spectral tail is at least a constant on epochs covering at least rounds.
Experiment (Appendix L.7): sensitivity to the working rank and a practical threshold. The data-selected arm keeps the eigenvalues above , at most 12, with selected among , , and on five tuning streams. It is a practical threshold of the form covered by Corollary 30. We ran GLR-U on the streams of Study A19 (true rank , a change every rounds, , , 20 test streams), unchanged except for the number of eigenvectors kept; with eigenvectors the results agree with the earlier runs on all 60 pairs (relative difference at most ). Mean regret, with the change relative to the true rank:
| working rank | |||
|---|---|---|---|
| 3 | 27,765 (+74.5%) | 32,026 (+48.7%) | 38,072 (+24.8%) |
| 4, the true rank | 15,914 | 21,532 | 30,497 |
| 5 | 16,689 (+4.9%) | 22,590 (+4.9%) | 31,828 (+4.4%) |
| 6 | 17,398 (+9.3%) | 23,565 (+9.4%) | 33,182 (+8.8%) |
| 8 | 18,810 (+18.2%) | 25,408 (+18.0%) | 35,669 (+17.0%) |
| 12 | 21,439 (+34.7%) | 28,771 (+33.6%) | 39,735 (+30.3%) |
| data-selected, | 16,317 (+2.5%) | 21,779 (+1.1%) | 31,018 (+1.7%) |
| tuned full-dimensional comparator | 23,529 | 33,554 | 41,214 |
One additional dimension raises the mean regret by –% and one missing dimension by –%. With each tested rank GLR-U has lower regret than the comparator on 20 of 20 streams for every . The data-selected arm is –% above the known rank in mean regret and keeps eigenvectors in the last epoch on 20 of 20 streams; on the tuning streams the other three constants have higher mean regret. Applied without retuning to the nine other cells of Study A19, it is –% above the known rank. These runs measure rank sensitivity and a practical threshold; the guarantees are statements 1–3.
Thank you for the rebuttal which I find satisfying. I will keep my positive assessment.
Response to Reviewer P8TY (1/2): what is new in each result
Thank you for the constructive assessment. The revised PDF unpacks the results as you suggest. Your question on the rank led to three new statements, each with its conditions, and to a new experiment; they are described in the next comment.
"lack of unpacking, discussion of the proposed results ... discuss the novelty of these results individually" The revision adds Figure 1, a map of the results; a Roadmap paragraph in §3 that orders them by one question, which past samples enter the estimate; and a "Practical reading" paragraph at the end of §4. The top-rung learner combines a GLR test with clipped least squares; the contributions of the paper are the rate comparison under one feedback model, the jump-resolved regret accounting, and the quantified cost of learning the representation, each under the assumptions of its statement. Result by result:
Relative to the closest analysis: Gafni et al. (2026) track a directly observed mean, and the coordinatewise reduction derived in Appendix J brings their guarantee to order (KT+1)logT for isotropic designs with a known subspace. Our known-subspace results cover unknown anisotropic covariances with explicit r and κ, a lower bound for the regression class, and separation from the fixed-window family and decaying steps; for isotropic designs we also quantify the cost of an unknown subspace and give its lower bound (Appendix J).