acceptodds
Under review as a conference paper at ICLR 2027

Fast Dynamic Regret with Logarithmic State for Online Least Squares

Abstract

Online least squares in a non-stationary environment admits fast dynamic regret under Euclidean comparator path length . The continuous fixed-share implementation used for this rate keeps one Gaussian component for every possible start time, so its per-round cost grows with the horizon. We study which state is needed for the guarantee. The exact fixed-share posterior may require positive Gaussian components even on a scalar stream; we instead retain only the state used by the analysis. Our learner applies sleeping Gaussian exponential weights to dyadic interval lifetimes. It also builds a causal, lossy orthonormal representation of the feature stream under a summable budget . The learner uses only the label bound, a reference point, and (for the lossy variant) ; it does not use , , the feature scale, or the comparator radius. The analysis combines an interval regret bound valid for every real parameter with an exact identity: weighted birth variation is the minimum weighted segment-start cost over all couplings with prescribed Gaussian marginals. This yields \widetilde{O}\\left( m_T + m_T^{2/3}T^{1/3}(P_T^{\mathrm{obs}})^{2/3} \right) with worst-case per-round time and space \widetilde{O}\\left(d(1+m_t)+(1+m_t^2)\log(t+1)\right). Here the retained dimension satisfies , so the dynamic term scales as , and is the shortest path preserving every comparator prediction. We also give a scalar lower bound matching the - and -exponents, a stream of feature rank whose gate retains one direction, an instance showing that the representation cross-term is unavoidable, and numerical checks of the reference implementation.

Primary area:
learning theory
Keywords:
online least squares, dynamic regret, non-stationary online learning

Reviews

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

This paper considers an online learning problem with square loss (hence called online least squares) in the “deterministic” setup where the learner is compared to a linear comparator class. A learning algorithm based on dyadic Gaussian exponential weighting is proposed and an upper bound on the regret is obtained. There is also a matching lower bound for the scalar case.

Critical strengths

The paper studies an interesting problem. An upper and a lower bound (though only matching for the scalar case) are proposed, and the proposed algorithm seems to be quite efficient.

Critical weaknesses

My biggest concern is that this paper is quite hard to follow, I give a few examples below

  1. the paper discusses "segment-start cost" several times in prominent places (abstract/contribution section), but I failed to find a proper definition of this quantity and I don’t believe this is a well-known term. For me, it is only implicitly mentioned in Theorem A.2 and some other places in the Appendix.

  2. in Section 4 where the algorithm is described. Three main parts (“lifetime schedule”, “conjugate core”, “representation gates”) are introduced. But these terms are not properly defined and explained. From the algorithm and other parts of section 4 I can partially infer what they mean. But the presentation overall is very confusing.

  3. before Theorem 1, the parameter \sigma is introduced (which is later used in Theorem 1) in the sentence “set …. \sigma^2 I_d in the transfer theorem”. What is the transfer theorem? I can’t find it.

some other questions

  • when defining the regret, the comparator sequence takes the form u_t^Ta_t. How much do the results depend on the fact that the output of the comparator is a linear function of a?

  • I’m not sure if the paper has substantial novelty. It seems that the dyadic Gaussian EW is not new, and it has already been applied to the online learning problem. So it seems that the novelty mainly comes from the fact that the fast regret can be achieved with a more efficient algorithm (demonstrated in the numerical part)? I think it would be more useful to articulate the contribution more clearly, in the context of existing literature.

Questions for authors

see the weakness section

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

This paper studies online least-squares regression in non-stationary environments. It aims to reduce computation and memory costs while maintaining fast dynamic regret guarantees. The method runs Gaussian exponential-weight learners over dyadic intervals and uses a weighted birth variation coupling argument to convert interval regret bounds into a dynamic regret bound based on Euclidean path length. It achieves $ \widetilde O \left(d+d^{2/3}T^{1/3}P_T^{2/3}\right) $ regret with O(d2log⁡(t+1))O(d^2\log(t+1)) worst-case time and memory per round. The paper also introduces an online lossy feature representation with an explicit error budget and an observation-equivalent path length to obtain tighter guarantees. Synthetic experiments illustrate these mechanisms.

Critical strengths
  • The paper addresses a well-defined research problem. It preserves the fast O~(T1/3PT2/3)\widetilde{O}(T^{1/3}P_T^{2/3}) dependence while reducing the worst-case per-round computational cost to O(d2log⁡(t+1))O(d^2\log(t+1)), avoiding a number of experts that grows linearly with time.

  • The paper is clearly written and well organized.

Critical weaknesses
  • The technical novelty needs further clarification. Theorem A.2 appears to follow directly from the classical residual-mass decomposition of maximal coupling, with simultaneous optimality for all nonnegative weight functions following naturally. The authors should distinguish this standard fact from the new technical contributions in the regret analysis and identify the nontrivial steps that yield the improved dimension dependence and computational guarantees.

  • The empirical evidence is limited. The experiments cover only three synthetic data streams, with no evaluation on real-world data. In Table 2, the proposed method and OGD with the theoretical step size achieve regret of 909±16909\pm16 and 935±64935\pm64, respectively, while their per-round runtimes are 36.1 and 6.3 microseconds. These results do not yet establish a consistent practical advantage for the proposed method.

Questions for authors

See Weaknesses

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

This paper studies dynamic regret for online least-squares prediction against a comparator sequence with bounded Euclidean path length. Its main objective is to preserve the fast T1/3PT2/3T^{1/3}P_T^{2/3} dependence while reducing the growing computational cost of continuous fixed-share implementations. The proposed algorithm maintains Gaussian exponential-weights learners on dyadic lifetimes, keeping only O(log⁡t)O(\log t) components active at round tt. Its analysis combines a whole-space interval-regret guarantee with a coupling argument that characterizes the minimum weighted cost of starting new comparator segments.

For fixed boundedness parameters, the uncompressed method achieves $ \widetilde O\left(d+d^{2/3}T^{1/3}P_T^{2/3}\right) $ regret with O(d2log⁡(t+1))O(d^2\log(t+1)) worst-case time and space per round.

Critical strengths
  1. The paper improves the dimension dependence of the closest continuous fixed-share least-squares bound while reducing the number of maintained Gaussian components from linear to logarithmic in time. The resulting combination of d2/3d^{2/3} dependence in the dynamic term, O(log⁡t)O(\log t) active components, and limited required side information is meaningful.

  2. The weighted birth-variation formulation provides a useful bridge from interval regret to dynamic regret. In particular, the argument controls both the number of comparator switches and the second moments of the parameters at segment starts. This matters because switch events and parameter norms are dependent, and the auxiliary Gaussian comparators are unbounded. The whole-space interval guarantee and explicit Gaussian moment calculations address these issues directly. The resulting transfer theorem is a useful analytical contribution beyond this particular implementation.

Critical weaknesses

The presentation does not adequately distinguish the paper’s contribution from earlier methods that already combine fast dynamic-regret exponents with logarithmic computational overhead. Baby and Wang (2021, Appendix B, Proposition 20) explain that replacing FLH by AFLH yields O(ρlog⁡T)O(\rho\log T) per-round runtime, where ρ\rho is the base-learner cost, while adding only a logarithmic factor to interval regret. Their fast temporal and path-length exponents therefore remain available with an efficient implementation. Zhang et al. (2025) also explicitly acknowledge this possibility. Table 1’s description of Baby–Wang as “partitions / restarts” obscures this important comparison. Earlier guarantees have worse dimension dependence and stronger side-information requirements, so they do not subsume the present result. Nevertheless, the contribution should be positioned around the simultaneous improvement in dimension dependence, parameter requirements, and computational cost. This distinction is consequential because logarithmic state is central to the paper’s motivation and title.

Questions for authors

See Weaknesses

Comments on the paper

1 comment
Area_Chair_NFU3OpenReview ↗

Author–Reviewer Discussion reminder

Dear reviewers,

Thank you all for your service to ICLR 2027. The author–reviewer discussion period is coming to an end. Could you please confirm if the authors' replies have resolved your questions?

Best regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.