acceptodds
Under review as a conference paper at ICLR 2027

Online learning under relative entropy: sharp rates and the price of reference access

Abstract

We study online binary classification when each input law, conditional on the full preceding feedback history, has KL divergence at most one from a fixed reference measure. When the reference is known, we prove the sharp worst-case minimax expected regret at every fixed positive VC dimension bound , improving the previous guarantee. The upper uses one KL budget across all cover resolutions; a matching threshold lower bound shows that the logarithm is necessary. When the reference is unknown, we determine the sharp dependence on reference samples and total-variation approximation accuracy. Even thresholds can require expected regret of order despite polynomially many samples and inverse-polynomial approximation error. A bounded forward Rényi divergence of fixed order greater than one recovers the known-reference order. For every fixed , online inputs alone recover this horizon order uniformly over all unknown full-dimensional log-concave references on . The general upper bounds use proper statistical strategies that choose a hypothesis before the current input; the lower bounds allow arbitrary predictions after the input and adaptive reference-sample requests.

Primary area:
learning theory
Keywords:
online learning, smoothed online learning, minimax regret, KL and Rényi divergences, VC dimension, reference distributions

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_AexSOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors study an online prediction problem where the conditional probability given past observed realizations stays close (in terms of KL divergence) to a fixed distribution about which the learner has full or limited knowledge. They provide upper and lower regret bounds for some scenarios which match order-wise.

Critical strengths

S1) Theorem 2 establishes a sharp upper bound that matches the corresponding lower bound up to a constant factor. The resulting improvement in the convergence rate is significant, providing a strong theoretical contribution.

S2) Theorem 4.1 considers a practical case where the true reference is unknown and the learner only has limited information about it. The result exhibits an interesting insight: the regret is controlled by the known-reference regret and the additional cost arising from the incomplete knowledge of the reference. Notably, the latter term may dominate the former when the available reference information is inadequate.

Critical weaknesses

W1) My biggest concern is with respect to the presentation. The main text is poorly structured and hard to follow. The theoretical results seem scattered and insufficiently connected, making it challenging to identify the central contribution of this paper. The authors should make substantial efforts to improve the readability of the paper.

W2) From reading the paper, it seems that it may be (at best) lightly edited LLM output, which also matches the authors' disclosures in the AI statement. There seems to be no effort to make the paper fit for human consumption. It is unclear what value to readers publishing such a paper at a conference would have.

W3) The length of the paper including appendix exceeds 140 pages, and almost all of it is dense mathematical/technical material which by the authors' own disclosure is all AI generated. There is no discussion of why such an unusual amount of technical material is necessary to establish the technical results, and what value publishing it would bring to the theoretical understanding of online learning. After all, the publications at ICLR are still intended mainly for human reading. If the value is just establishing the technical validity itself with no insight into methodology or technique (at least for humans), it stands to reason that the proofs should also be published in a machine-friendly form (e.g., a theorem checker language). In any case, the 2.5 weeks review process of ICLR is in my view not remotely suitable to determine if a paper of this length should be published.

Questions for authors

Q1) Why is the problem important? It seems that the KL condition means that the underlying distribution is in some way "close to i.i.d.". I think the authors should at least give examples of practical problems that exhibit such properties.

Q2) If you can come up with an example for a practical problem regarding Q1, can you do numerical evaluations? If not, why not? (discuss as limitations!)

2 comments
AuthorsOpenReview ↗

Response to Reviewer AexS

Thank you for the comments on presentation. I have reduced the paper from 141 to 64 pages, with ten pages of main text. Section 3 now presents the learner, its stability proof and the shared KL estimate together. Most secondary extensions have been removed.

You asked why the KL model is useful and whether the inputs are close to i.i.d. The condition still allows strong dependence: a single fair bit repeated forever has conditional KL at most log⁡2\log2 relative to the fair-bit reference. It also allows online inputs to visit rare regions much more often than reference samples do.

To make the model concrete, Section 2 gives a controlled adaptive-testing example whose sampling rule enforces the KL constraint. Section 7 now explicitly states that I have not validated the KL assumption in a practical application. The paper is theoretical and does not include numerical evaluations.

Thank you for your response. I think it is good that the paper is more focused on the main results now (although it still is very long, it is just not quite as extreme as it was before). I am not fully clear from the response what exactly has been done to improve the readability of the paper (and there is also no highlighting in the revised version to help me find the changes). Also, while I respect that the focus of the paper is theoretical, I still think that if it is possible to evaluate numerically, there should at least be some numerical evaluation and if it is not possible there needs to be a discussion of why it is not possible and what additional research will be needed to close that gap. This is important so readers can get an idea of what exactly the nature of the gap between theory and practice is here.

Since a significant part of my main concerns seems to not be addressed, I have decided to keep my current score.

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

This paper studies online binary classification under a relative-entropy constraint, where the conditional input distribution (P_t) at each round satisfies KL(Pt∣μ)≤1\mathrm{KL}(P_t|\mu)\le 1 for a fixed reference distribution μ\mu. The authors investigate the minimax regret under different assumptions about the learner's access to the reference distribution.

The main result establishes a sharp minimax regret bound of Θ(dTlog⁡(eT/d))\Theta(\sqrt{dT\log(eT/d)}) when the reference distribution is known, improving the previously known Od(T2/3)O_d(T^{2/3}) upper bound. The key technical contribution is a multiscale covering argument that shares a single KL budget across different resolutions, avoiding the weaker tradeoff arising from a single approximation scale. A matching lower bound establishes the necessity of the logarithmic factor, even for threshold functions.

The paper further studies the unknown-reference setting and characterizes the minimax regret in terms of the number of reference samples mm and the total-variation approximation accuracy δ\delta. For fixed VC dimension, the authors obtain the sharp rate $ \Theta_d\left(\sqrt{T\log(eT)}+ \frac{T}{\log(eT(m+1)/\delta)}\right). $ The results demonstrate that polynomially many reference samples may be insufficient to recover the known-reference regret rate. Additional results consider Rényi-divergence constraints and structured reference distributions, including Gaussian and log-concave families.

Critical strengths

The improved known-reference regret bound resolves a quantitative gap in prior work. Establishing matching upper and lower bounds, with explicit dependence on the VC dimension and KL budget, is a meaningful advance. The multiscale covering analysis with shared KL accounting is an appealing idea. In particular, controlling the contributions of multiple covering resolutions without repeatedly charging the full KL budget appears to be the main technical insight behind the improved regret rate. The unknown-reference results provide an interesting information-theoretic perspective on smoothed online learning. The lower bounds are particularly notable because they hold even for realizable threshold functions and allow unrestricted post-input predictions and adaptive reference-sample requests.

Critical weaknesses
  1. The paper is extremely long and includes many additional results beyond the two main minimax characterizations. Although the main theorems are clearly stated, it is difficult to identify the essential technical contributions and understand how the different proof components fit together. A more focused presentation of the central arguments, with a clearer separation between the main results and supplementary extensions, would substantially improve readability.

  2. Most general upper bounds rely on statistical strategies with exact mathematical access to the hypothesis class or reference distribution. While the authors provide computational implementations for certain special cases, particularly thresholds, the applicability of the main techniques to computationally efficient learning for more general hypothesis classes remains unclear.

  3. Several components, including the Cover-based unknown-reference upper bounds and hidden-path lower-bound constructions, build on ideas from previous literature. Although the paper obtains sharper quantitative characterizations, I would appreciate a more explicit discussion of which technical ingredients are fundamentally new and which are refinements or combinations of existing approaches

Questions for authors

Is there a natural way to extend the proposed learning strategies to computationally efficient algorithms for broader hypothesis classes, such as halfspaces?

1 comment
AuthorsOpenReview ↗

Response to Reviewer B3Ti

Thank you for the constructive suggestions. In response to your halfspace question, I obtained a proper algorithm for all real affine halfspaces in every fixed dimension kk. It chooses a halfspace with rational coefficients before seeing the current input. For every unknown full-dimensional log-concave reference μ\mu, its expected regret is at most CkTlog⁡(eT)C_k\sqrt{T\log(eT)}, with CkC_k independent of μ\mu.

For this algorithm, expected total bit work is polynomial in TT, with degree depending only on kk and a constant that may depend on μ\mu. The access assumptions are explicit: the learner reads each input coordinate one binary digit at a time and retains a fixed initial group of online inputs for further digit reads; every read is charged. It receives no reference parameters or independent reference samples. Section 6 states the result and access assumptions; Theorem S12.7 and Lemma S12.8 give the construction and bit-complexity analysis.

I have reduced the paper from 141 to 64 pages, with ten pages of main text presenting the learner, its stability proof and the reference-access bounds together. Most secondary extensions have been removed, and the appendix guide identifies the estimates needed for each main result.

I have also made the distinction you asked for between inherited tools and new estimates. Chaining and exponential weights are inherited. The new known-reference estimate controls contributions from large density ratios at every cover resolution using one KL budget. For unknown references, the upper bound sharpens the dimension dependence in Blanchard's (2025) analysis of the Cover algorithm. The lower bound refines the hidden-path construction from the same paper. The bounds now match in VC dimension, reference samples and total-variation error. Section 7 explains this distinction.

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

This paper studies online binary classification when the reference distribution is not fully known. The learner may receive at most m i.i.d. samples from the true reference μ\mu, ora known approximation ν\nu with TV(μ,ν)≤δTV(\mu,\nu)\le \delta. The sharp worst-case minimax expected regret bound is established. The core message—that the “sample barrier” for unknown references is not universal but depends on the regularity of the reference—is well motivated and, in my view, interesting.

Critical strengths
  1. The joint sample/TV law is clean and the lower bound is strong: it allows adaptive post-input reference requests and unrestricted post-input prediction.
  2. The multiscale KL accounting in Lemma 3.1 is a good technical idea. The standard single-resolution cover argument gives T2/3T^{2/3}, charging all high-density contributions to one shared KL budget is what yields the sharp T/log(eT) information term.
  3. The forward-moment condition removing the sample penalty entirely is a crisp and conceptually important observation, and the paper is careful to emphasize that the direction of the divergence matters.
Critical weaknesses
  1. My main concern is the dependence on the VC dimension. The constants C_d in the sample/TV law are allowed to depend strongly on d, and the paper explicitly leaves sharp dimension dependence open. This is a legitimate limitation, but it would help to be more explicit about what the current proof actually gives—for instance, whether C_d is polynomial or exponential in d, and which steps (cover cardinalities, terminal disagreement bounds) drive the dependence.
  2. The finite-bit guarantees are restricted to threshold classes in one dimension, with known uniform or unknown one-dimensional log-concave references. The general VC upper bounds are statistical existence results, and the paper says so. Still, Section 6 could more clearly state what additional assumptions (ERM oracle, computable cover enumeration, etc.) would be needed for a general-class finite-bit implementation. This would prevent readers from over-interpreting the “finite-bit” label.
  3. I think some of the calibration constants are somewhat loose. The Cauchy-reference calibration for log-concave measures gives CtAd,TC\sqrt{t}A_{d,T}, but the k-dependence is not optimized. the O(k2+log⁡T)O(k^2 +\log T) prefix for Gaussian case is also not claimed to be necessary. A discussion of whether k2k^2 is an artifact of the Gaussian-fitting argument or a genereal requirement would be helpful.
Questions for authors

please refer to weaknesses

2 comments
AuthorsOpenReview ↗

Response to Reviewer p1Vn

Thank you for the constructive questions. Your question about dimension dependence led me to remove the unspecified CdC_d. Theorem 4.1 now gives matching statistical upper and lower bounds with universal constants: dTlog⁡(eT/d)+Tlog⁡(e(T/d)(1+m/d)/δ),\sqrt{dT\log(eT/d)}+\frac{T}{\log(e(T/d)(1+m/d)/\delta)}, for T≥max⁡{512,d}T\ge\max\{512,d\} and 0<δ≤10<\delta\le1. The old proof lost an exponential factor when it converted covers into a partition. The revised proof works directly with the covers.

I agree that the finite-bit claims needed explicit access assumptions. Under its stated resource bounds, Proposition S12.1 now gives sufficient conditions for polynomial work in computing and sampling from the cover tree: a polynomial-size representation, with efficient access to losses, child counts and child selection. Evaluating the selected hypothesis has its separately stated cost.

I also checked which of the calibration costs you raised can be avoided. For Cauchy calibration in ambient dimension kk, the linear dependence on kk is necessary within that family: the KL divergence from a known uniform distribution on a cube to its best Cauchy approximation is of order kk, even after optimizing the center and scatter matrix (Proposition S11.5).

Fitting a Gaussian reference to the accuracy and confidence used in the proof requires order k2+log⁡Tk^2+\log T initial online inputs (Theorem S11.10). That many initial inputs are not necessary for the fixed-dimensional regret rate: Cauchy calibration achieves the same dependence on TT from O(klog⁡(ek))O(k\log(ek)) initial online inputs, with a larger k\sqrt{k} regret coefficient. Section 5 now explains this distinction. Optimal regret dependence on kk for arbitrary learners remains open.

Reviewer_p1VnOpenReview ↗

Response to authors

Thank you for the clarifications. Since the author has addressed my concerns and made the requested revisions, I would like to maintain my positive score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.