acceptodds
Under review as a conference paper at ICLR 2027

Known-Subspace Rate Ladder for Streaming Low-Rank Regression with Fast Coefficient Drift

Abstract

We study streaming low-rank regression when the relevant subspace is fixed but its coefficients can change abruptly. This setting exposes a plasticity–stability tradeoff: decaying steps learn stationary segments well but recover slowly after jumps, while constant steps react quickly but retain a noise floor. We prove a known-subspace rate ladder for expected dynamic regret under the same linear-Gaussian sample feedback. Monotone decaying-step stochastic gradient suffers linear regret under coefficient jumps, whereas a clipped fixed-window estimator achieves regret when the number of jumps grows as . An adaptive estimator that combines generalized likelihood ratio (GLR) change-point detection with clipped least squares achieves on a well-spaced class with jumps, and a van Trees argument gives a matching lower bound on the same class. Charging each change by its own size, the ratio of the two bounds depends only on the condition number and the signal-to-noise ratio, uniformly in the minimum jump size, whereas a size-independent charge grows as the squared amplitude-to-jump ratio and is linear in for the smallest jumps the spacing admits. When the subspace is fixed but unknown, running the same detector on half of the samples projected onto a spectral-moment estimate built from the other half keeps the rate at an additive cost of order for learning the subspace when , and a matching lower bound shows that this cost is necessary up to the factor when ; a blockwise Fantope extension covers moving subspaces at the scale. In synthetic experiments, a fixed window cuts the regret of a theorem-class decaying-step learner -fold at ; the analyzed GLR rule, run exactly on equally spaced jumps of size at least with isotropic Gaussian covariates at high signal-to-noise ratio, grows at close to the oracle's rate and has lower regret at than every tuned baseline; and a suffix-retaining GLR variant has – lower regret than the preregistered tuned competitor with the lowest tuning regret at on equally and unequally spaced change paths with mixed jump sizes, three covariate designs and noise levels –.

Primary area:
learning theory
Keywords:
online learning, dynamic regret, low-rank regression, concept drift, change-point detection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_P8TYOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper analyses a low-rank linear model yt=(Utat)⊤xt+noisey_t= (U_t a_t)^\top x_t+ noise where observations (xt,yt)(x_t,y_t) are received online from t=1t=1 to TT, UtU_t is a low rank matrix and ata_t is assumed piecewise constant with bounded jumps in time. The main goal is to estimate coefficient UtatU_ta_t. The paper proposes a regret analysis for several type of estimators, assuming both Ut=UU_t=U known or UtU_t unknown that improve upon each other in a ladder type going from O(T)O(T) to O(T1/2log⁡(T))O(T^{1/2}\log(T)) for some class of paths ata_t 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 O(T)O(T) to O(T1/2log⁡T)O(T^{1/2}\log T) 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 UU case, rr is also unknown ? Could the algorithm be made adaptive w.r.t rr as well, i.e estimate an "adaptive optimal" rank kk ? Since the regret only cares about estimating UtatU_ta_t and not whether the middle dimension rr is known.

3 comments
AuthorsOpenReview ↗

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:

  • Theorem 1, decaying steps, Ω(T)\Omega(T). Because the population gradient is affine, the mean iterate follows noiseless gradient descent exactly, so every jump is charged either by a slow recovery after it or by slow rounds before it. The bound covers the whole monotone-step class under any conditionally unbiased gradient feedback, which includes the sample gradients of the model of the upper bounds.
  • Theorem 2 and Proposition 16, fixed windows, Θ(T3/4)\Theta(T^{3/4}) for KT=Θ(T)K_T=\Theta(\sqrt T). The lower bound holds on isotropic streams for every window width, clipped or not. It makes this rung tight and gives Corollary 7: in the jump-rate regimes stated there (KT=⌊Tγ⌋K_T=\lfloor T^\gamma\rfloor, γ∈(0,1)\gamma\in(0,1)), a polynomial separation between the worst-case regret orders of the GLR rule and of the fixed-window family on its path class, even for a window tuned with knowledge of γ\gamma.
  • Theorems 4 and 5, GLR windows, O(Tlog⁡T)O(\sqrt T\log T) for KT=Θ(T)K_T=\Theta(\sqrt T) well-spaced jumps. With random designs the GLR noncentrality σ−2δ⊤(GL−1+GR−1)−1δ\sigma^{-2}\delta^\top(G_L^{-1}+G_R^{-1})^{-1}\delta is a random quadratic form. We give a detection event that is uniform over all tested triples and has a single-logarithm delay; a ghost estimator that controls the least-squares risk after restarts selected by the same responses; and a mixed-window bias bound that pairs the delay of each change with its own per-round cost, so that the cost per change does not depend on the jump size and, in the revision, carries κ\kappa in place of κ3\kappa^3. For the smallest admissible jumps the bound of Theorem 4 is linear in TT, while that of Theorem 5 stays O(Tlog⁡T)O(\sqrt T\log T).
  • Theorem 8, lower bound. A van Trees argument with a smooth, compactly supported prior gives a cost of order rσ2log⁡TKT+1r\sigma^2\log\frac{T}{K_T+1} per segment on the separated well-spaced class on which the upper bound holds, so the two match in TT (Corollary 6).
  • Theorem 10 and Proposition 11, fixed unknown subspace. Splitting the stream makes the regression rounds independent of the estimated subspace; this independence is what extends the detection analysis, and, within each epoch, the projection error enters as a noise level that changes only at coefficient change points. For isotropic designs under cumulative excitation, learning UU costs an additive O(rdlog⁡2(dT))O(rd\log^2(dT)) when d≥log⁡(dT)d\ge\log(dT), which does not grow with the number of changes. The lower bound of Proposition 11 contains the term rdσ22log⁡(1+J/cd)\frac{rd\sigma^2}{2}\log(1+J/c_d), with JJ the segment length and cd=160rdσ2/Amax⁡2c_d=160rd\sigma^2/A_{\max}^2; for fixed (r,σ,Amax⁡)(r,\sigma,A_{\max}), KT=Θ(T)K_T=\Theta(\sqrt T) and J≥cd2J\ge c_d^2, hence d=O(T1/4)d=O(T^{1/4}), it is of order rdlog⁡Trd\log T, so the two bounds agree in dd up to a factor log⁡(dT)\log(dT).
  • Theorem 12, moving subspace. Fantope online gradient descent against a moving comparator keeps the fixed-window order T3/4T^{3/4}.

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)log⁡T(K_T+1)\log T for isotropic designs with a known subspace. Our known-subspace results cover unknown anisotropic covariances with explicit rr and κ\kappa, 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).

AuthorsOpenReview ↗

Response to Reviewer P8TY (2/2): unknown rank

"What happens if in the unknown UU case, rr is also unknown? Could the algorithm be made adaptive w.r.t. rr 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 βj\beta_j be the matrix-Bernstein radius of the moment estimate M^j\hat M_j of epoch jj; it depends only on (σ,Amax⁡,d,T)(\sigma,A_{\max},d,T) and the epoch. Keep the k^j\hat k_j eigenvectors of M^j\hat M_j whose eigenvalues exceed βj\beta_j. On the moment-concentration event of the proof of Theorem 10, which has probability at least 1−1/(4T)1-1/(4T): (i) k^j≤r\hat k_j\le r in every epoch; (ii) k^j=r\hat k_j=r in every epoch after the warm-up charged by T⋆T_\star, where βj≤μa/(2r)<μa\beta_j\le\mu_a/(2\sqrt r)<\mu_a; this separation is what exact recovery needs, the nonzero population eigenvalues being at least 2μa2\mu_a under the excitation assumption. Thus Corollary 30 applies with kˉ=r\bar k=r, 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 rr as input and satisfies the expected-regret bound of Theorem 10.

2. A working rank above rr (Corollary 30). Under the same assumptions and protocol, if, on that event, r≤k^j≤kˉr\le\hat k_j\le\bar k after the warm-up (in particular for a fixed working rank k≥rk\ge r) and the spacing condition of Theorem 10 holds with kˉ\bar k in place of rr, the bound of Theorem 10 holds with kˉ\bar k in place of rr in the tracking terms of its first line, while the constants CUC_U, RUR_U and T⋆T_\star of the cost of learning UU keep the true rank. The proof uses a perturbation lemma for the top-kk eigenspace and repeats the detection, burn-in and ghost-estimator steps in dimension k^j\hat k_j.

3. A working rank below rr (Proposition 32, Corollary 33). For isotropic designs, if the predictions on a set SS of rounds lie in the range of one projector of rank k<rk < r, their regret on SS is at least ∣S∣2∑i>kλi(AˉS)\frac{|S|}{2}\sum_{i>k}\lambda_i(\bar A_S), with AˉS\bar A_S the average of atat⊤a_ta_t^\top over SS. For GLR-U with a fixed working rank k<rk < r this applies epoch by epoch, and the regret is at least αγT/2\alpha\gamma T/2, linear in TT, when the spectral tail ∑i>kλi(AˉSj)\sum_{i>k}\lambda_i(\bar A_{S_j}) is at least a constant γ>0\gamma>0 on epochs covering at least αT\alpha T rounds.

Experiment (Appendix L.7): sensitivity to the working rank and a practical threshold. The data-selected arm keeps the eigenvalues above c∣λmin⁡(M^j)∣c|\lambda_{\min}(\hat M_j)|, at most 12, with c=1.5c=1.5 selected among 11, 1.51.5, 22 and 33 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 44, a change every 150150 rounds, T=100,000T=100{,}000, σ=0.1\sigma=0.1, 20 test streams), unchanged except for the number of eigenvectors kept; with 44 eigenvectors the results agree with the earlier runs on all 60 pairs (relative difference at most 1.4×10−151.4\times10^{-15}). Mean regret, with the change relative to the true rank:

working rankd=50d=50d=100d=100d=200d=200
327,765 (+74.5%)32,026 (+48.7%)38,072 (+24.8%)
4, the true rank15,91421,53230,497
516,689 (+4.9%)22,590 (+4.9%)31,828 (+4.4%)
617,398 (+9.3%)23,565 (+9.4%)33,182 (+8.8%)
818,810 (+18.2%)25,408 (+18.0%)35,669 (+17.0%)
1221,439 (+34.7%)28,771 (+33.6%)39,735 (+30.3%)
data-selected, c=1.5c=1.516,317 (+2.5%)21,779 (+1.1%)31,018 (+1.7%)
tuned full-dimensional comparator23,52933,55441,214

One additional dimension raises the mean regret by 4.44.4–4.94.9% and one missing dimension by 24.824.8–74.574.5%. With each tested rank k=4,5,6,8,12k=4,5,6,8,12 GLR-U has lower regret than the comparator on 20 of 20 streams for every dd. The data-selected arm is 1.11.1–2.52.5% above the known rank in mean regret and keeps 44 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 0.40.4–5.35.3% 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.

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

This paper studies streaming low-rank regression problems when the relevant subspace is fixed while coefficients change abruptly. For problems with known subspace, a rate ladder for expected dynamic regret is proven. The authors additionally extend their analysis to unknown fixed subspace and moving subspaces. Numerical experiments with synthetic data corroborate their theoretical findings.

Critical strengths

Clear presentation. The paper is well-written and well-organized. The problem formulation is clean, assumptions are cleanly stated, and the theoretical results are presented cleanly. The rate ladder provides a useful framework for understanding the relative performance of various approaches and scenarios of the problem.

Comprehensive theoretical analysis. The paper provides a thorough theoretical analysis covering a broad range of settings. Rigorous regret bounds are established under relevant assumptions. For certain scenarios, matching upper and lower bounds are also provided. The analysis is further extended to unknow and moving subspaces.

Critical weaknesses

None

Questions for authors

Minor issue: consider citing the original papers of Adam and AdaGrad.

2 comments
AuthorsOpenReview ↗

Response to Reviewer RBcj

Thank you for the positive assessment and for the suggestion.

"consider citing the original papers of Adam and AdaGrad" The revised PDF cites both original papers, Kingma and Ba (ICLR 2015) for Adam and Duchi, Hazan and Singer (JMLR 2011) for AdaGrad, in the definition of the monotone-step class in §3.1 and in the table of learners in Appendix A, where both are baselines of the lower-rung robustness check.

Thank you for addressing my concern. I will keep the original scores.

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

This paper studies streaming linear regression and establishes regret bounds for different SGD settings, including fixed-window least squares and GLR-based adaptive windows. On a well-spaced jump class, the adaptive method achieves O(Tlog⁡T)O(\sqrt{T}\log T) regret. The paper also studies learning an unknown subspace and tracking blockwise-moving subspaces.

Critical strengths

The paper establishes matching regret rates in TT under a common model. The jump size-resolved analysis and careful handling of data-dependent resets are useful contributions. The experiments are thorough, with separate test streams and detailed detection measurements.

Critical weaknesses

My main concern is about the logic and presentation of the paper. The current main text contains too many theorems and technical terms. The relationship between these different parts of the content should be clarified, and the readability should be significantly improved. Please see the questions for details.

Questions for authors
  1. It is recommended to clarify the randomness in the expectation in regret function and the randomness in the regret function. Because in Theorem 1, there is also term E[RegT]\mathbb{E}[\text{Reg}_T], which implies that Reg_T is a random variable.

  2. In a monotone-step learner, why is the update rule for θt+1\theta_{t+1} based on data from time tt, rather than using the data at time t+1t+1 (i.e., (xt,yt)(x_t, y_t)) to compute the gradient?

  3. In the theorem, the eigenvalues ​​Σ\Sigma are stated to fall within the range [μ,L][\mu, L]. Does this refer to the same parameters as those mentioned in Assumptions 1 and 2? Where does the coefficient 8192 in Theorem 1 come from?

  4. Corollary 6 still leaves an upper/lower-bound gap involving κ3+LAmax⁡2/σ2\kappa^3+LA_{\max}^2/\sigma^2. Could a different reset strategy reduce them?

  5. The results in this paper are solid and sound. However, a large portion of the main text is dedicated to describing theorems, e.g., regret bounds across various settings, such as scenarios with known or unknown factors, or different parameter estimation methods. Unfortunately, this obscures the paper's core focus. From a reader's perspective, it would be beneficial to clarify the logical relationships between these different theorems and setting. Furthermore, the motivations behind the various settings, for instance, the use of sliding window approaches, the design of window lengths, or the implementation of decaying learning rates, are not clearly articulated. This gives the impression that the paper is a collection of results—akin to a series of mathematical exercises across different settings, rather than a focused exploration of a specific, compelling problem or phenomenon. The reviewer suggests establishing a clear logical connection between the various theorems and their interrelationships; a comprehensive flowchart could be helpful in this regard. Additionally, following the presentation of the main theoretical results, the paper should discuss their implications and provide insights relevant to practical machine learning applications. Without this, the paper’s readability remains quite poor. Although the reviewer believe the quality of the mathematics meet the standard of ICLR, the presentation and organization require significant improvement.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Zrdj (1/2): notation, protocol, constants and presentation

Thank you for the careful reading and the concrete suggestions; the revised PDF addresses each of them. The gap in Corollary 6 is answered in the next comment.

"clarify the randomness in the expectation in regret function" The revision defines RegT=∑t≤T(Lt(θt)−Lt(θt⋆))\mathrm{Reg_T}=\sum_{t\le T}\bigl(L_t(\theta_t)-L_t(\theta_t^\star)\bigr), the realized sum of population excess losses. Each LtL_t averages over the fresh sample (xt,yt)(x_t,y_t), so RegT\mathrm{Reg_T} is random only through the iterates θt\theta_t, which depend on earlier observations and on any internal randomization of the learner; the coefficient paths are deterministic. The regret bounds are stated for E[RegT]\mathbb E[\mathrm{Reg_T}] (§3 and the notation table).

"why is the update rule for θt+1\theta_{t+1} based on data from time tt" This is the online protocol of §3: in round tt the learner commits to θt\theta_t using rounds 1,…,t−11,\dots,t-1 and then observes (xt,yt)(x_t,y_t). The step θt+1=θt−ηtgt(θt)\theta_{t+1}=\theta_t-\eta_tg_t(\theta_t) uses the sample just observed; forming θt+1\theta_{t+1} from (xt+1,yt+1)(x_{t+1},y_{t+1}) would reveal the response before it is predicted. The definition of the monotone-step learner now says so.

"the same parameters as those mentioned in Assumptions 1 and 2? Where does the coefficient 8192 in Theorem 1 come from?" Yes: for the squared loss ∇2Lt=Σ\nabla^2L_t=\Sigma, so μI⪯Σ⪯LI\mu I\preceq\Sigma\preceq LI is equivalent to Assumptions 1–2 with the same μ\mu and LL. The constant is a product of four factors in Step 3 of the proof, none optimized: at least KT/2K_T/2 jumps are each charged at least μΔ02/32\mu\Delta_0^2/32 per round, on a window of at least 364T/(KT+1)\frac3{64}T/(K_T+1) rounds, and KT/(KT+1)≥12K_T/(K_T+1)\ge\frac12; hence 12⋅132⋅364⋅12=38192\frac12\cdot\frac1{32}\cdot\frac3{64}\cdot\frac12=\frac3{8192}. Both remarks now follow Theorem 1.

"a clear logical connection between the various theorems ... a comprehensive flowchart" Figure 1 of the revision is a map of the results organized by one question: which past samples enter the estimate. For KT=Θ(T)K_T=\Theta(\sqrt T) jumps it shows the three rungs of the known-subspace ladder with their rates, a labelled arrow from each rung to the next, a double arrow between the top rung and the lower bound on the same class, and, kept apart below, the two unknown-subspace extensions. A Roadmap paragraph in §3 follows the same order and motivates each design:

  • a decaying step, the standard schedule for stationary streams, gives new observations ever smaller weight; Theorem 1 shows regret linear in TT on a path with repeated jumps;
  • a sliding window forgets: it trades an estimation error of order κσ2r/w\kappa\sigma^2r/w per clean round against up to ww contaminated rounds per change, which gives w≍T/(KT+1)w\asymp\sqrt{T/(K_T+1)} and regret O(T3/4)O(T^{3/4}) for KT=Θ(T)K_T=\Theta(\sqrt T) (Theorem 2); on isotropic streams no width does better in order (Proposition 16);
  • a GLR test lets the window grow until a change is declared (Theorems 4–5): O(Tlog⁡T)O(\sqrt T\log T) for KT=Θ(T)K_T=\Theta(\sqrt T) well-spaced jumps, matched in TT by the lower bound of Theorem 8 on the same class (Corollary 6); Corollary 7 separates its worst-case regret order polynomially from that of the fixed-window family, in the jump-rate regimes and on the path class stated there;
  • §6, under isotropic design and excitation: Theorem 10 and Proposition 11 give the cost of learning a fixed unknown subspace, and Theorem 12 covers blockwise moving subspaces at the fixed-window order.

"implications ... practical machine learning applications" A "Practical reading" paragraph now closes §4. With the measurements of §7, its message is:

  • with a decaying step, every jump is paid either by a slow recovery after it or by slow rounds before it (Theorem 1); in §7 the best of 12 decaying-step settings has 11.311.3 times the regret of a fixed window at T=50,000T=50{,}000;
  • a fixed window must be tuned to the unknown change rate and, even when tuned, is polynomially worse in the worst case over the class of Corollary 7;
  • a window that grows until a declaration needs neither the change rate nor the jump size. In the setting of Table 1 (equally spaced jumps of size at least 0.50.5, isotropic Gaussian covariates, σ=0.1\sigma=0.1) the exact rule has lower mean regret than every tuned baseline at both reported horizons, T=50,000T=50{,}000 and 100,000100{,}000.
AuthorsOpenReview ↗

Response to Reviewer Zrdj (2/2): the gap in Corollary 6

"Corollary 6 still leaves an upper/lower-bound gap involving κ3+LAmax⁡2/σ2\kappa^3+LA_{\max}^2/\sigma^2. Could a different reset strategy reduce them?" The two terms arise from different parts of the analysis, and the answer differs for each. Your question led us to tighten the conditioning term from κ3\kappa^3 to κ\kappa (point 1). For the second term, retaining a clean post-change suffix reduces its burn-in component under a stated condition (point 3). Corollary 6 is a statement about the order in TT.

1. Conditioning: κ3\kappa^3 becomes κ\kappa for the same algorithm. The earlier proof bounded the bias of a window that mixes two coefficients by 9κΔk9\kappa\Delta_k in the Euclidean norm. The same concentration step compares Gram matrices with Σz\Sigma_z itself, 14∣I∣Σz⪯GI⪯94∣I∣Σz\frac14|I|\Sigma_z\preceq G_I\preceq\frac94|I|\Sigma_z. In the design norm ∥v∥Σ=(v⊤Σzv)1/2\Vert v\Vert_\Sigma=(v^\top\Sigma_zv)^{1/2} the bias is then at most 9∥δk∥Σ9\Vert\delta_k\Vert_\Sigma, and the signal-dependent part of the detection delay is of order σ2rlog⁡T/∥δk∥Σ2\sigma^2r\log T/\Vert\delta_k\Vert_\Sigma^2. The squared bias multiplied by the signal-dependent part of the delay is independent of the jump size and of the conditioning; the delay floor and the cadence are controlled separately by clipping, and one factor κ\kappa enters through the Euclidean clipping step. Theorem 5 now gives E[RegT]≤C(KT+1)(κσ2rlog⁡T+LAmax⁡2(n0+Δc))\mathbb E[\mathrm{Reg_T}]\le C(K_T+1)\bigl(\kappa\sigma^2r\log T+LA_{\max}^2(n_0+\Delta_c)\bigr) under the assumptions of Theorem 4, which include ∥at∥≤Amax⁡\Vert a_t\Vert\le A_{\max}; under the hypotheses of Corollary 6 the ratio to the lower bound is O(κ+LAmax⁡2/σ2)O(\kappa+LA_{\max}^2/\sigma^2) (proof in Appendix L.2). This sharpens the upper bound.

2. A new experiment measures the cost per change of the exact rule (Appendix L.6). GLR-1 is run untuned on streams with r=4r=4, σ=0.1\sigma=0.1, T=40,000T=40{,}000, a change every 2,0002{,}000 rounds and a design covariance with geometric spectrum of trace rr and condition number κ\kappa; 20 streams per cell. Excess regret over the change-time oracle, per change:

jumpsκ=1\kappa=1κ=4\kappa=4κ=16\kappa=16κ=64\kappa=64log–log slope in κ\kappa [95% CI]
unit-sphere coefficients, size ≥0.5\ge0.52.232.372.262.270.000.00 [−0.03,0.03][-0.03, 0.03]
size 0.40.4, random direction0.840.810.800.80−0.01-0.01 [−0.02,0.00][-0.02, 0.00]
size 0.40.4, smallest-eigenvalue direction0.830.760.710.69−0.04-0.04 [−0.06,−0.03][-0.06, -0.03]

All 4,5604{,}560 changes are declared, each exactly once. Across the tested trace-normalized spectra (μ\mu from 11 to 0.0470.047, LL from 11 to 3.0123.012) the fitted slopes over the four displayed condition numbers show no clear positive trend in mean excess per change. In the last row the median delay increases from 1010 to 202.5202.5 rounds while the median of the delay times ∥δ∥Σ2/σ2\Vert\delta\Vert_\Sigma^2/\sigma^2 remains between 148148 and 160160. A second set of runs extends the first two rows to κ=256\kappa=256 and 1,0241{,}024: 2.222.22 and 2.052.05 in the first row, 0.830.83 and 0.910.91 in the second, with slopes over κ∈[1,1024]\kappa\in[1,1024] of −0.01-0.01 [−0.03,0.00][-0.03,0.00] and 0.010.01 [0.00,0.02][0.00,0.02]. These measurements are consistent with the pairing of delay and per-round cost used in the proof.

3. The factor LAmax⁡2/σ2LA_{\max}^2/\sigma^2 is where the reset rule matters. It collects the noise-independent costs around a change: the burn-in after a discard-all reset, the detection floor and the cadence. A different reset acts on the first. Under the clean-suffix condition of Proposition 19, keeping the post-change samples at a declaration changes the burn-in charge of a run from n0n_0 to max⁡(n0−Bj,0)\max(n_0-B_j,0), where BjB_j is the length of the retained clean suffix; Corollary 20 gives sufficient localization, ordering and covariance conditions. Measured at an equal threshold and scan set in the 28 conditions of Appendix A.2 (Tables 6–7), retention lowers the zero-prediction burn-in from 388388–963963 to 77–287287 rounds per stream and the regret by 4.84.8–61.361.3%, with every paired 95% interval below zero. The benefit holds for the variant as run, which retains from the estimated split, beyond the condition of Proposition 19.

Reviewer_ZrdjOpenReview ↗

Reply to Author Response

Thank you for the detailed reply and response. After reading, most of my previous comments are properly addressed. In particular, I believe Fig. 1 will greatly improve the readability and quality of the work. Therefore, I keep my positive score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of changes in the revised PDF

We thank the three reviewers. The revised PDF keeps every theorem, proposition and table number of the submission; new statements and tables are numbered after the existing ones, in a new Appendix L. The main text uses the tenth page allowed in the discussion phase. Changes, with the review that prompted each:

  1. Map of the results (Figure 1) and Roadmap paragraph in §3 (Zrdj, P8TY). The figure shows the three rungs of the known-subspace ladder, the lower bound and the two unknown-subspace extensions, and how they relate; the paragraph orders the results by which past samples enter the estimate and gives the reason for each design.
  2. Regret notation (Zrdj). RegT\mathrm{Reg_T} is the realized sum of population excess losses and the regret bounds are stated for E[RegT]\mathbb E[\mathrm{Reg_T}]; the appendices and the notation table use the same convention.
  3. Protocol and constants of Theorem 1 (Zrdj). The definition of the monotone-step learner states the order of prediction and update; two remarks after the theorem relate μ\mu and LL to Assumptions 1–2 and derive the constant 3/81923/8192.
  4. Theorem 5 and Corollary 6 sharpened (Zrdj). The conditioning enters the per-change transient as κ\kappa in place of κ3\kappa^3, for the same algorithm (proof in Appendix L.2). Theorem 4 now states the condition ∥at∥≤Amax⁡\Vert a_t\Vert\le A_{\max} that its proof uses, and n0n_0 and the delay bounds are written as integers. Appendix L.6 measures the cost per change of the exact rule for condition numbers from 11 to 1,0241{,}024.
  5. Practical reading paragraph in §4 (Zrdj).
  6. Unknown rank (P8TY). A paragraph in §6 and Appendix L.3–L.5 add three statements with their conditions: a certified rank rule read from the spectral moment, which on the concentration event of Theorem 10 does not exceed rr and equals rr after the warm-up, and therefore satisfies the expected-regret bound of Theorem 10 (Corollary 31); any working rank between rr and an upper bound kˉ\bar k, with kˉ\bar k in the tracking terms and the spacing condition (Corollary 30); and a working rank below rr, with a lower bound that is linear in TT under a quantitative spectral-tail condition (Proposition 32, Corollary 33). Appendix L.7 measures the regret as a function of the working rank and evaluates a practical data-dependent threshold.
  7. Citations of Adam and AdaGrad (RBcj) in §3.1 and in the table of learners.

To stay within ten pages, three passages of the main text are shortened: the comparison with follow-the-leading-history guarantees after Corollary 6, the proof idea in §5, and one clause on learned-discount forecasters in §7. Their content remains in Appendices F.1, G and A.2.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.