A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS

Dmitry B. Rokhlin

REVIEW 2 major objections 4 minor 18 references

A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that a hierarchical Vovk-Azoury-Warmuth forecaster with random features achieves expected dynamic regret $O(T^{2/3}P_T(f)^{1/3}+\sqrt{T}\ln T)$ for online regression in an RKHS, with per-iteration cost $O(T\ln T)$.

desk verdict A plausible first sublinear dynamic regret bound for RKHS online regression, with a real but repairable gap in the proof of Theorem 2. read the letter →

arxiv 2506.22631 v1 pith:XODPUIHC submitted 2025-06-27 cs.LG stat.ML

Dmitry B. Rokhlin This is my paper · ORCID

classification cs.LGstat.ML MSC 68Q3268W2768W20

keywords Vovk-Azoury-WarmuthalgorithmdynamicregretRKHSrandomfeatureshierarchicallearningonlineregressiondiscounting

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to show that online regression in a reproducing kernel Hilbert space can track a slowly changing comparator function with sublinear dynamic regret, while keeping computation feasible. It constructs H-VAW-D, a three-level Vovk-Azoury-Warmuth forecaster in which discounted VAW experts on random Fourier features are aggregated over a grid of discount factors and then over a grid of feature counts. The claimed expected dynamic regret is $O(T^{2/3}P_T(f)^{1/3}+\sqrt{T}\ln T)$, where $P_T(f)$ is the functional path length of the comparator sequence. If the proof is right, this is the first computationally tractable algorithm with sublinear dynamic regret for RKHS regression, and it requires no prior knowledge of the path length, discount, or feature dimension.

What carries the argument

The engine is the discounted Vovk-Azoury-Warmuth update over a random-feature space, in which a discount factor $\gamma$ down-weights older losses and the inverse covariance matrix is updated in $O(m^2)$ per step via the Woodbury identity. Around this base expert the paper places two VAW meta-aggregators: one learns $\gamma$ on a geometric grid for a fixed feature count $m$, and the top-level aggregate learns $m$ on a dyadic grid. The bridge from the finite-dimensional feature space to the RKHS comparator is Lemma 3, which bounds the expected change of the feature-space loss by $\rho_m\|f_{t+1}-f_t\|_H$ with $\rho_m=a(aR+Y)+4Ra^2/m$, converting the functional path length $P_T(f)$ into the comparator-variation term of the DVAW regret bound.

What would settle it

Take a bounded comparator sequence with total variation $P_T(f)=T^{-1}$, for example $f_t=(1/T)g$ for odd $t$ and $f_t=0$ for even $t$ with $\|g\|_H=1$, and compute the paper's optimal feature count $m_d$; it grows as $T^{2/3}$, which exceeds the dyadic grid's maximum $\Theta(\sqrt{T})$. Simulating H-VAW-D on this sequence would show whether the claimed bound still holds: if it does, the $P_T(f)=\Omega(1)$ step is a removable gap, and if it does not, that step is essential.

Watch

Extended reading notes

Core claim

The central claim is that H-VAW-D, built from the discounted VAW forecaster of Jacobsen and Cutkosky applied to $m$-dimensional random features and wrapped in two further VAW meta-aggregators, attains expected dynamic regret $O\bigl((1+b)^2(1+a^2)\rho_\infty R^2 P_T(f)\Delta^2_{1:T}T\bigr)^{1/3} + (Y+\tilde Y)^2\sqrt{T}\ln T + a^2R^2\sqrt{T}\bigr)$ against every comparator sequence $f_1,\dots,f_T$ with $\|f_t\|_H\le R$, where $P_T(f)=\sum_{t=1}^{T-1}\|f_{t+1}-f_t\|_H$ and $\rho_\infty = a(aR+Y)$. When $P_T(f)=O(T)$ and the hints are bounded, this simplifies to $O(T^{2/3}P_T(f)^{1/3}+\sqrt{T}\ln T)$, uniformly over the path length. The algorithm is fully adaptive: it learns the discounting level and the feature dimension online, and its per-iteration cost is $O(T\ln T)$.

Load-bearing premise

The proof assumes that whenever the target function changes at all, the total amount of change over the whole run never shrinks to zero as the run grows longer; if it does shrink, the optimal feature count falls outside the pre-set range and the written argument stops.

Editorial extensions

If this is right

H-VAW-D is the first computationally tractable online RKHS regression algorithm with sublinear dynamic regret; its per-iteration cost is $O(T\ln T)$ and its expected regret is $O(T^{2/3}P_T(f)^{1/3}+\sqrt{T}\ln T)$.
No prior knowledge of the comparator path length, the discount factor, or the feature dimension is needed: the three-level hierarchy learns all of them online.
If the comparator sequence is constant ($P_T(f)=0$), the dynamic term disappears and the bound reduces to the static kernel-regression rate $O(\sqrt{T}\ln T)$.
The analysis uses the ordinary functional path length $P_T(f)$ rather than the more complex comparator-variation measure in the original DVAW bound, which simplifies the oracle trade-off between discounting and approximation error.
The total computational cost is $O(T^2\ln T)$, a large improvement over exact kernelization's $O(T^3)$, though still growing with $T$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same three-level aggregation is modular: any base expert that can be run on random features and indexed by a discount factor could be substituted for DVAW, potentially yielding dynamic-regret bounds for other non-parametric function classes.
The static $O(\sqrt{T})$ term in the bound depends on the feature-map bound $a$ and the comparator norm $R$; a data-dependent effective-dimension grid could sharpen this term on easy data, in analogy with static kernel VAW bounds.
The paper leaves open whether the $T^{2/3}P_T^{1/3}$ dynamic rate is minimax; if a matching lower bound exists, this algorithm would already be order-optimal in the dynamic component.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this is a legitimate extension of Jacobsen-Cutkosky's DVAW forecaster to RKHS via random features, with a three-level hierarchical aggregation that adaptively tunes the discount factor and the feature dimension. If the proof is fixed, it gives the first sublinear dynamic regret bound for online regression in RKHS with per-iteration cost O(T ln T), which matters. The abstract's O(T^{2/3} P_T^{1/3} + sqrt(T) ln T) is honestly derived, and the dependence on hint quality Delta^2 is clearly shown.

What I liked: the random-feature reduction is clean; Lemma 3 correctly bounds the variation of the finite-dimensional comparator loss by the functional path length; the oracle-plus-grid analysis in Lemma 4 is standard but competently executed; and the paper credits [8] heavily, which is appropriate since the DVAW bound is the workhorse. I also appreciate that the authors state their own complexity is O(T^2 ln T) overall, not hiding it.

The soft spot is exactly what the stress-test flagged. In Theorem 2, the proof needs m_d to lie on the grid S_m. The line 'Since P_T(f) > 0, we have P_T(f) = Omega(1)' is false: a comparator can drift by T^{-alpha-1} per step, giving P_T = T^{-alpha} and m_d as large as T^{1/2 + alpha/3}, which can exceed the grid maximum ~2 sqrt(T). That is load-bearing: without m_d on the grid, the O((P_T Delta^2 T)^{1/3}) evaluation is not attained by any instantiated expert. The good news is the fix is straightforward. When m_d exceeds the grid, the static term a^2 R^2 T/(2m) at m_max ~ sqrt(T) already gives O(sqrt(T)), which is dominated by the static regret, so the bound survives. But the paper does not supply that case split, and the same Omega(1) assertion reappears in bounding m_d ln T. This is a genuine gap that needs closing.

Minor things: no experiments, which is fine for a theory paper but limits immediate practical validation; the per-iteration O(T ln T) is not cheap, but it is a big improvement over O(T^3). The citation pattern looks fair: the self-citation [12] is contextual, not load-bearing.

Who it is for: researchers working on dynamic regret, kernel methods, and random features. They will get a clear template for lifting finite-dimensional adaptive algorithms to nonparametric settings. I would send it to a serious referee; the gap is repairable and the central claim is likely true. My verdict is conditional accept, with the Omega(1) step fixed.

Recommendation: engage with it, and require the repair.

Referee Report

2 major / 4 minor

Summary. The paper proposes H-VAW-D, a fully hierarchical online regression algorithm for RKHS-valued comparators. The algorithm uses random Fourier features, runs discounted Vovk-Azoury-Warmuth (DVAW) base experts over a grid of discount factors, aggregates them with a VAW meta-algorithm per feature dimension, and then aggregates all feature dimensions with a top-level VAW meta-algorithm. The main theoretical claim is an expected dynamic regret bound of order O(T^{2/3} P_T(f)^{1/3} + sqrt(T) log T), where P_T(f) is the RKHS path length of the comparator sequence, with per-iteration cost O(T log T). The analysis combines an oracle bound depending on the optimal discount factor and feature dimension with standard meta-regret decompositions; the random-feature approximation error is handled by Lemmas 2 and 3.

Significance. If the advertised bound is correct, this is a meaningful advance: it would give the first computationally tractable algorithm with sublinear dynamic regret for online regression in an RKHS, lifting the finite-dimensional DVAW result of Jacobsen and Cutkosky to the nonparametric setting. The proof strategy is standard but nontrivial, and the paper correctly relies on the published external DVAW bound rather than circular reasoning; the oracle choices are analysis artifacts, not fitted parameters. The paper is also honest about limitations, including the large total complexity and the open question of lower bounds. However, the proof of Theorem 2 contains a false inference about positive path lengths, and that inference is load-bearing in the current write-up. Because the gap is localized and likely repairable, the appropriate decision is major revision rather than rejection.

major comments (2)

[Theorem 2, after Eq. (20)] The assertion 'Since P_T(f) > 0, we have P_T(f) = Omega(1)' is false. A comparator sequence with increments of size T^{-alpha-1} inside the R-ball has positive total path length P_T(f) = Theta(T^{-alpha}), which decays with T. This assertion is used to conclude that m_d = O(T^{1/2}/(log T)^{1/3}) and hence that a grid point m'_d approximating m_d lies in S_m. When P_T(f) decays, m_d can exceed the largest grid element 2^{ceil((1/2) log_2 T)}, and the advertised evaluation of the regret at m_d is not attained. The gap is likely repairable: if m_d lies above the grid, the regret at the largest grid point is dominated by the static O(sqrt(T)) terms, but the paper does not supply this case split. As written, the proof of the main theorem is incomplete.
[Theorem 2, after Eq. (20)] In the same paragraph, the claimed order bound 'm_d (Y + tilde Y)^2 log T + ... = (Y + tilde Y)^2 o(sqrt(T))' is not justified. Even accepting the preceding bound m_d = O(T^{1/2}/(log T)^{1/3}), the product is O(sqrt(T) (log T)^{2/3}), which is not o(sqrt(T)). It is o(sqrt(T) log T) and can be absorbed into the stated static term, so the final regret bound survives after correction, but the displayed order claim must be fixed for the proof to be rigorous.

minor comments (4)

[Theorem 2, Eq. (15)] The displayed O(...) expression has unbalanced parentheses; the intended term appears to be O( ((1+b)^2(1+a^2) rho_infty R^2 P_T(f) Delta^2_{1:T} T)^{1/3} ).
[Theorem 2, after Eq. (20)] The sentence 'This proves that m_d <= N_m' should compare m_d to the largest grid element 2^{ceil((1/2) log_2 T)}, since N_m was already defined as the cardinality |S_m|.
[Lemma 4, Step (1)] The sentence 'The expert k = 0 predicts z_{t,0} = ey2_t' appears to be a typo; it should read z_{t,0} = tilde y_t.
[Abstract and Section 4] The abstract states 'per-iteration computational complexity of O(T log T)', while the conclusion states 'overall complexity O(T^2 log T)'. Please clarify the distinction between per-iteration and total complexity in both places.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the regret bound is derived from an external DVAW theorem and standard random-feature estimates; the noted issue in Theorem 2 is a correctness gap, not a circular one.

full rationale

The central bound (15) is not circular. The H-VAW-D analysis imports Theorem 1 from Jacobsen and Cutkosky [8], an external published result by different authors, and combines it with elementary random-feature approximation lemmas (Lemmas 1-3) proved in the paper. The oracle quantities η* and m_d are analysis artifacts used to select grid points in the proof; they are not fitted parameters that are later relabeled as predictions. The meta-algorithm genuinely aggregates DV-AW experts and VAW meta-experts, and its regret decomposition is a standard oracle-expert argument, not an identity between input and output. The author's own reference [12] appears only as context for multikernel random-feature regression and is not load-bearing. The reviewer-flagged assertion in Theorem 2 that 'Since P_T(f) > 0, we have P_T(f) = Ω(1)' is indeed false and appears to be needed to place m_d on the predefined grid, but this is a mathematical correctness gap, not a circularity: the claimed regret bound is not defined in terms of that assertion, and the assertion is not a restatement of the theorem's conclusion. Because circularity requires a specific reduction of a claim to its own inputs or to a self-citation chain, and no such reduction is present, the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard RKHS and VAW theory, with the key external input being [8, Theorem 3.1]. The only ad hoc element is the unjustified P_T=Ω(1) bound in the proof of Theorem 2.

assumptions (4)

domain assumption The kernel admits a random feature representation k(x,y)=∫ φ(x;θ)φ(y;θ)P(dθ) with |φ(x;θ)| ≤ a.
Used throughout: Lemma 1 (representation), Lemma 2 (variance bound), Lemma 3 (loss variation bound). Standard for random feature kernels such as Gaussian with shift-invariant features.
domain assumption Comparator functions are uniformly bounded in norm: ||f_t||_H ≤ R, and labels and hints are bounded: |y_t| ≤ Y, |ỹ_t| ≤ Ỹ.
Assumed in Theorem 2 and used in every bound to control losses, regret terms, and the path length P_T. Needed for the boundedness of ρ_m and the grid analysis.
standard math Theorem 3.1 of Jacobsen-Cutkosky (2024) bounds the regret of the discounted VAW forecaster.
Used as a black box in equation (9) and in Lemma 4. This is an external published result, not derived in the paper.
ad hoc to paper If P_T(f) > 0 then P_T(f) = Ω(1).
Stated in the proof of Theorem 2 to conclude m_d = O(T^{1/2}/(ln T)^{1/3}) and hence that a grid expert approximates m_d. This is mathematically false: a positive sequence can converge to 0. It is load-bearing for the grid approximation argument.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS." pith.science (2026). https://pith.science/paper/XODPUIHC

@misc{pith2026250622631,
  author       = {Pith},
  title        = {Pith review of: A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XODPUIHC}},
  note         = {Machine review of arXiv:2506.22631}
}

abstract

We study the problem of online regression with the unconstrained quadratic loss against a time-varying sequence of functions from a Reproducing Kernel Hilbert Space (RKHS). Recently, Jacobsen and Cutkosky (2024) introduced a discounted Vovk-Azoury-Warmuth (DVAW) forecaster that achieves optimal dynamic regret in the finite-dimensional case. In this work, we lift their approach to the non-parametric domain by synthesizing the DVAW framework with a random feature approximation. We propose a fully adaptive, hierarchical algorithm, which we call H-VAW-D (Hierarchical Vovk-Azoury-Warmuth with Discounting), that learns both the discount factor and the number of random features. We prove that this algorithm, which has a per-iteration computational complexity of $O(T\ln T)$, achieves an expected dynamic regret of $O(T^{2/3}P_T^{1/3} + \sqrt{T}\ln T)$, where $P_T$ is the functional path length of a comparator sequence.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[8]

Online linear regression in dynamic environments via discounting

A. Jacobsen and A. Cutkosky. “Online linear regression in dynamic environments via discounting”. In: Proceedings of the 41st International Conference on Machine Learning. Vol. 235. Proceedings of Machine Learning Research. 2024, pp. 21083–21120

work page 2024
[12]

Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning

D.B. Rokhlin and O.V. Gurtovaya. Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning. 2025. arXiv: 2503.20087 [cs.LG]

work page Pith review arXiv 2025
[1]

Theory of reproducing kernels

N. Aronszajn. “Theory of reproducing kernels”. In: Transactions of the American mathematical society 68.3 (1950), pp. 337–404

work page 1950
[2]

Relative loss bounds for on-line density estimation with the expo- nential family of distributions

K.S. Azoury and M.K. Warmuth. “Relative loss bounds for on-line density estimation with the expo- nential family of distributions”. In: Machine Learning 43.3 (2001), pp. 211–246

work page 2001
[3]

Cesa-Bianchi and G

N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006

work page 2006
[4]

Uniform regret bounds over Rd for the sequential linear regression problem with the square loss

P. Gaillard et al. “Uniform regret bounds over Rd for the sequential linear regression problem with the square loss”. In: Proceedings of the 30th International Conference on Algorithmic Learning Theory. Vol. 98. Proceedings of Machine Learning Research. 2019, pp. 404–432

work page 2019
[5]

Updating the inverse of a matrix

W.W. Hager. “Updating the inverse of a matrix”. In: SIAM review 31.2 (1989), pp. 221–239

work page 1989
[6]

Efficient learning algorithms for changing environments

E. Hazan and C. Seshadhri. “Efficient learning algorithms for changing environments”. In: Proceedings of the 26th annual international conference on machine learning. 2009, pp. 393–400

work page 2009

Show all 18 references

[7]

Online learning: A comprehensive survey

S.C.H. Hoi et al. “Online learning: A comprehensive survey”. In: Neurocomputing 459 (2021), pp. 249– 289

2021
[9]

Efficient online learning with kernels for adversarial large scale problems

R. J´ ez´ equel, P. Gaillard, and A. Rudi. “Efficient online learning with kernels for adversarial large scale problems”. In: Advances in Neural Information Processing Systems32 (2019)

2019
[10]

Random features for large-scale kernel machines

A. Rahimi and B. Recht. “Random features for large-scale kernel machines”. In: Advances in neural information processing systems. Vol. 20. 2007, pp. 1177–1184

2007
[11]

Online non-parametric regression

A. Rakhlin and K. Sridharan. “Online non-parametric regression”. In: Proceedings of The 27th Con- ference on Learning Theory. Vol. 35. Proceedings of Machine Learning Research. 2014, pp. 1232–1264

2014
[13]

Large scale online multiple kernel regression with application to time- series prediction

D. Sahoo, S.C.H. Hoi, and B. Li. “Large scale online multiple kernel regression with application to time- series prediction”. In: ACM Transactions on Knowledge Discovery from Data (TKDD)13.1 (2019), pp. 1–33

2019
[14]

Random feature-based online multi-kernel learning in envi- ronments with unknown dynamics

Y. Shen, T. Chen, and G.B. Giannakis. “Random feature-based online multi-kernel learning in envi- ronments with unknown dynamics”. In: Journal of Machine Learning Research20.22 (2019), pp. 1– 36

2019
[15]

Competitive on-line statistics

V. Vovk. “Competitive on-line statistics”. In: International Statistical Review69.2 (2001), pp. 213–248

2001
[16]

On-line regression competitive with reproducing kernel Hilbert spaces

V. Vovk. “On-line regression competitive with reproducing kernel Hilbert spaces”. In: International Conference on Theory and Applications of Models of Computation. Springer. 2006, pp. 452–463

2006
[17]

Adaptive online learning in dynamic environments

L. Zhang, S. Lu, and Z.-H. Zhou. “Adaptive online learning in dynamic environments”. In: Advances in neural information processing systems31 (2018). 14

2018
[18]

Online convex programming and generalized infinitesimal gradient ascent

M. Zinkevich. “Online convex programming and generalized infinitesimal gradient ascent”. In: Pro- ceedings of the 20th international conference on machine learning (icml-03). 2003, pp. 928–936. 15

2003

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [8]

Online linear regression in dynamic environments via discounting

A. Jacobsen and A. Cutkosky. “Online linear regression in dynamic environments via discounting”. In: Proceedings of the 41st International Conference on Machine Learning. Vol. 235. Proceedings of Machine Learning Research. 2024, pp. 21083–21120

work page 2024

[2] [12]

Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning

D.B. Rokhlin and O.V. Gurtovaya. Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning. 2025. arXiv: 2503.20087 [cs.LG]

work page Pith review arXiv 2025

[3] [1]

Theory of reproducing kernels

N. Aronszajn. “Theory of reproducing kernels”. In: Transactions of the American mathematical society 68.3 (1950), pp. 337–404

work page 1950

[4] [2]

Relative loss bounds for on-line density estimation with the expo- nential family of distributions

K.S. Azoury and M.K. Warmuth. “Relative loss bounds for on-line density estimation with the expo- nential family of distributions”. In: Machine Learning 43.3 (2001), pp. 211–246

work page 2001

[5] [3]

Cesa-Bianchi and G

N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006

work page 2006

[6] [4]

Uniform regret bounds over Rd for the sequential linear regression problem with the square loss

P. Gaillard et al. “Uniform regret bounds over Rd for the sequential linear regression problem with the square loss”. In: Proceedings of the 30th International Conference on Algorithmic Learning Theory. Vol. 98. Proceedings of Machine Learning Research. 2019, pp. 404–432

work page 2019

[7] [5]

Updating the inverse of a matrix

W.W. Hager. “Updating the inverse of a matrix”. In: SIAM review 31.2 (1989), pp. 221–239

work page 1989

[8] [6]

Efficient learning algorithms for changing environments

E. Hazan and C. Seshadhri. “Efficient learning algorithms for changing environments”. In: Proceedings of the 26th annual international conference on machine learning. 2009, pp. 393–400

work page 2009