acceptodds
Under review as a conference paper at ICLR 2027

Randomization Is Necessary for Learning from Symmetric Equivalence Queries

Abstract

We resolve the dimension-only derandomization question for general symmetric equivalence queries posed in Learning from Equivalence Queries, Revisited at COLT 2026. Prior work gave a randomized proper learner with expected query complexity for every finite class of Littlestone dimension . We show that deterministic proper learners cannot match this dimension-only guarantee, even with a fixed target. Under target reselection, symmetric two-point generators can force deterministic complexity linear in the number of concepts even at Littlestone dimension one, while randomized learning uses fewer than three expected queries. For independently resampled distributions over total orders, the extremal deterministic complexity on the singleton class is . A uniform mixture of cyclic rotations has an exact value asymptotic to . A row lower-envelope inequality for the linear-order polytope yields the matching universal upper bound. For one fixed, known total order, a lexicographic projection of the standard optimal algorithm gives a version-consistent proper learner using at most queries. Complete classes attain this bound. With a fixed target, arbitrary symmetric generators have a tight worst-case hierarchy on singleton classes. Under the same fixed-target protocol, every finite class admits a generator-dependent deterministic upper bound. Randomized learning remains throughout. Dimension alone therefore cannot characterize deterministic EQ learning: the target protocol and feedback structure determine the cost of determinism.

Primary area:
learning theory
Keywords:
Learning theory, Equivalence queries, Query complexity, Randomization, Littlestone dimension, Proper 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_JkpuOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper asks whether randomization actually helps when a learner makes a guess and receives a counterexample if it is wrong. The authors show that it can help when compared to a deterministic learner. They provide a few different settings in this paper.

When the answer can change in between rounds, they give an example where the feedback rule picks a new random starting point on a circle for each guess and reports the first error it finds. With this rule, it forces every deterministic learner use about n\sqrt{n} queries , and another symmetric rule forces n/2n/2 queries. On the other hand, for both examples, a randomized learner needs about 3 queries on average.

When the answer stays fixed, the worst-case deterministic querey cost is log⁡n\log n, even for a class with Littlestone dimension 1 and again randomized learners need at most 3.

The paper also shows that if feedback follows a fixed, known order, then a deterministic learner can finish in at most d+1d+1 queries (where dd is Littlestone dimension).

Critical strengths

It answers the main part of the open question.\textbf{It answers the main part of the open question}. The COLT 2026 work asked two things: a) Is randomness needed against arbitrary symmetric adversaries, and b) is randomness needed for the case of order-induced adversaries. This paper answers the first part. Even for a very simple class (Littlestone dimension 1) and a fixed target, there is a symmetric feedback adversary that forces any deterministic learner to use log⁡n\log n queries, while a randomized learner needs at most 3. I followed this argument and it seems correct. I am not an expert in this area, but this seems like a meaningful contribution.

Critical weaknesses

The second part of the question is only partly answered.\textbf{The second part of the question is only partly answered.} For order-induced adversaries, the paper's n\sqrt{n} query bound holds only when the target can change in between rounds. The fixed-target case, which is the main setting of the COLT paper (to my understanding at least), is left open, as the authors state. There are hints the answer there could be positive: with a fixed target, the cyclic rule needs at most 4 deterministic queries (Prop 4.5.), and random counterexamples which is a special case of order-induced adversaries (taken from the COLT paper), already have deterministic learners. So while the paper shows randomization is necessary for some symmetric adversaries, it remains unclear whether it is needed for the order-induced adversaries.

The main result is technically simple, and the paper is hard to read.\textbf{The main result is technically simple, and the paper is hard to read.} The main negative result for symmetric adversaries follows quickly from known results on tournament domination (Thm 4.3.). Most of the paper is spent on introducing many protocol variants and exact constants and not on this main question. The main text is dense, it uses many similar notations, and it gives little intuition, which made the claims hard for me to verify beyond the main arguments. For an ICLR audience, this limits both the accessibility and the perceived significance of the contribution.

Questions for authors
  1. Do you have any evidence on if a deterministic learner can achieve constant queries for order-induced adversaries with a fixed target? This is the part of the COLT question left open.

  2. The answer for symmetric adversaries follows quickly from known tournament results. Which results do you consider the main technical contribution of the paper, and what makes them difficult?

4 comments
AuthorsOpenReview ↗

The fixed-target case and the complete resolution of the open problem

Thank you very much for the careful review, and for pointing to the fixed-target case, which is indeed the main setting of the COLT paper.

The revised version, now uploaded, completely resolves the open problem posed by Braverman et al. at COLT 2026.

It settles the fixed-target case left open in the submitted version, carries over all theorems of the submitted version with their proofs, and improves the presentation. The paper is now titled "Randomization in Learning from Symmetric Equivalence Queries"; the general response gives a result-by-result correspondence. Theorem and section numbers refer to the revised version unless we say otherwise.

1. Order-induced adversaries with a fixed target

As the review anticipated, the answer is positive. Theorem 4.1 gives a deterministic learner that uses at most 12815Ldim(H)+1\frac{128}{15}\mathrm{Ldim}(\mathcal H)+1 queries in expectation against every known order-induced generator, for every finite class and every fixed target; up to the constant this is optimal. It extends the deterministic learner for random counterexamples (Braverman et al., Section 3.1.1) to every known distribution of checking orders. On singleton classes it needs at most 143/15<10143/15 < 10 queries for every nn, not only for the cyclic rule mentioned in the review but for every known order mixture.

Part of the questionSubmitted versionRevised version
General symmetric feedbackNoNo (Theorem 3.1)
Order-induced, fixed targetOne known order: Yes; order mixtures: OpenYes for every known order-induced generator (new Theorem 4.1)
Order-induced, target reselectionOne known order: Yes; order mixtures: NoUnchanged (Corollary 4.2; Theorems 5.1-5.2)

How the proof closes the question, in four steps:

  1. Each random checking order acts as a voter. With the version space and its SOA predictions frozen for a phase, each order ranks the hypotheses lexicographically by where they disagree with these predictions. If the query is ranked above the target, it is accepted or the Littlestone dimension drops (Lemma C.2).
  2. A recent theorem from social choice (Song, Nguyen and Lin, SODA 2026) gives two hypotheses such that every target outside the pair is ranked below one of them with probability at least 1/4.
  3. Within a phase the learner alternates between these two. Since the target is fixed and each query draws a fresh order, a phase costs at most 128/15 queries in expectation.
  4. Each phase that does not end in acceptance lowers the dimension, so there are at most Ldim(H)\mathrm{Ldim}(\mathcal H) phases, plus one final query.

The argument needs the target to stay fixed; under reselection, order mixtures behave differently (Section 5).

2. The presentation

We also agree that the main text of the submitted version was dense and gave too much space to protocol variants and exact constants. The revised main text follows the main question: an opening example (Figure 1), a phase diagram of all main results (Table 1), then the negative answer (Section 3), the positive answer (Section 4) and target reselection (Section 5). Exact constants and specialized variants are in the appendices, with a proof index and dependency diagrams in Appendix A.

Submitted versionRevised version
§1-2 Introduction, model§1-2 (now with an example; phase diagram updated)
§3 Randomization is necessary§5; App. D, E.2
§4 Fixed targets, logarithmic theory§3; App. B, E
§5 A single known orderCor. 4.2; App. C.2-C.3, G.5-G.8
§6 Consistent-only protocolApp. G.1-G.4
§7-8 Related work, conclusion; App. H§6-7; Prop. B.5; Thm 4.1 settles the open case
Not in the submitted versionThms 4.1, 4.3, 4.5, Prop 4.4; App. C.4-C.8; App. A diagrams

Thank you again for this valuable feedback. We hope the revised version gives a much clearer picture, and we would be glad to clarify anything further.

AuthorsOpenReview ↗

A brief note before the discussion closes

Dear Reviewer Jkpu:

We are grateful for your review, and especially for the hints you pointed out on the fixed-target case.

The answer there is indeed positive, as your hints suggested. Both the cyclic rule and random counterexamples are special cases of Theorem 4.1 in the revised version we have uploaded: for every known order-induced adversary, a deterministic learner facing a fixed target needs an expected number of queries that grows only linearly with the Littlestone dimension. With this result, the open problem of Braverman et al. (COLT 2026) is now completely resolved. It also answers your first question in the affirmative: on every finite class of Littlestone dimension one, a constant expected number of queries suffices. We also tried to answer your second question, on the main technical contribution, as clearly as we could in our response.

If anything is unclear, or if other questions come up, we would be glad to hear from you.

With many thanks, and best regards.

Thank you for your response! Theorem 4.1 addresses my fixed-target concern. Although my second question is only partly addressed, I maintain my positive rating.

AuthorsOpenReview ↗

Thank you so much!

Dear Reviewer Jkpu:

Thank you very much for reading our response and the revised version, and for your continued support. The hints in your review on the fixed-target case encouraged us to develop our techniques further, check every proof line by line, and improve the writing.

Thank you for your time and support.

Reviewer_ncnhOpenReview ↗
Rating
1(−1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
1(−2)
Read review
Paper summary

The paper studies learning from equivalence queries, where the learner proposes a hypothesis and receives either acceptance or a counterexample. Braverman et al. (COLT 2026) gave a randomized proper learner that needs only O(Ldim)O(\mathrm{Ldim}) expected queries against symmetric counterexample generators, and asked whether a deterministic learner can do the same. The paper shows that, in general, deterministic proper learners cannot, even when the Littlestone dimension is 1. It also studies the cost of determinism across several settings, with bounds that are tight or nearly tight in most of them.

Critical strengths
  1. It answers a clearly posed open question from COLT 2026.
Critical weaknesses
  1. The paper is very hard to follow, even at a high level (admittedly I am not an expert). Even after a careful read, I could not get a clear picture of the main message or of how the many results fit together. The main text is a dense list of theorems across many settings (changing vs. fixed target, known order vs. order mixtures etc.), with heavy notation and little intuition or examples. It might be that important ideas were pushed into the appendix. I believe that the paper will greatly benefit from a substantial rewrite focusing on clarity.
Questions for authors

None

1 comment
AuthorsOpenReview ↗

The revised paper and the complete resolution of the open problem

Thank you very much for the careful reading and the candid assessment. We agree that the submitted version could have been written better, and we have revised the paper accordingly and uploaded the revised version (now titled "Randomization in Learning from Symmetric Equivalence Queries"). Theorem and section numbers refer to the revised version unless we say otherwise.

1. What we changed for each point

  • The main message. It is now stated early in the abstract and the introduction: with a fixed target, general symmetric feedback does not allow a deterministic learner a bound depending only on the Littlestone dimension, but a known distribution of checking orders, resampled at each query, does. Table 1 in Section 2 summarizes all main results in one phase diagram.
  • How the results fit together. Each setting now has a stated role: Section 3 gives the negative answer (general symmetric feedback), Section 4 the positive answer (order-induced feedback), and Section 5 the boundary of the positive answer (target reselection).
  • A dense list of theorems. The main text now has 10 numbered results instead of 17. Results specific to particular protocols or generators (the consistent-only protocol, exact constants, and the comparison with transductive learning) are now in the appendices.
  • Heavy notation. Quantities used only by these specialized results, such as the frontier dimension and the consistent-only and transductive values, are now introduced only in the appendices, so the main argument can be followed without this additional notation.
  • Little intuition or examples. The main text now has three concrete examples: the box example (Figure 1), a four-hypothesis example showing why two queries succeed where one cannot (Section 4.2), and the cyclic example (Section 5). Each main theorem comes with a proof idea or an intuition paragraph, and Figure 2 shows the new algorithm step by step.
  • Important ideas in the appendix. We agree that this was the case. The arguments behind the main results are now explained in the main text: the tournament reduction and the likelihood-halving argument (Section 3), the ranking and committee argument with its cost calculation (Sections 4.1-4.2), and the strategies behind the reselection bounds (Section 5). The appendices keep the complete proofs, and Appendix A gives a proof index and dependency diagrams.

The sections of the submitted version now appear as follows (the general response gives a result-by-result table):

Submitted versionRevised version
§1-2 Introduction, model§1-2 (now with an example; phase diagram updated)
§3 Randomization is necessary§5; App. D, E.2
§4 Fixed targets, logarithmic theory§3; App. B, E
§5 A single known orderCor. 4.2; App. C.2-C.3, G.5-G.8
§6 Consistent-only protocolApp. G.1-G.4
§7-8 Related work, conclusion; App. H§6-7; Prop. B.5; Thm 4.1 settles the open case
Not in the submitted versionThms 4.1, 4.3, 4.5, Prop 4.4; App. C.4-C.8; App. A diagrams

2. The open problem is now resolved

The submitted version answered only part of the open problem posed by Braverman et al. at COLT 2026. The revised version carries over all theorems of the submitted version with their proofs and adds the missing part, so that it now resolves this open problem completely. Here Yes/No indicates whether a deterministic learner can have a bound depending only on the Littlestone dimension.

Part of the questionSubmitted versionRevised version
General symmetric feedbackNoNo (Theorem 3.1)
Order-induced, fixed targetOne known order: Yes; order mixtures: OpenYes for every known order-induced generator (new Theorem 4.1)
Order-induced, target reselectionOne known order: Yes; order mixtures: NoUnchanged (Corollary 4.2; Theorems 5.1-5.2)

Theorem 4.1 gives a deterministic learner with at most 12815Ldim(H)+1\frac{128}{15}\mathrm{Ldim}(\mathcal H)+1 expected queries. Each random checking order acts as a voter that ranks the hypotheses, and a recent theorem from social choice (Song, Nguyen and Lin, SODA 2026) supplies two hypotheses that together cover every target; alternating between them lowers the dimension at constant expected cost.

We would be very grateful if you could take another look at the revised version. For a first reading, Section 1, Table 1, and Sections 4.1-4.2 with Figure 2 give the main message and the new mechanism without the appendix. Thank you again for this valuable feedback; we sincerely hope the revised version gives a much clearer picture, and we would be glad to clarify anything further.

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

This paper answers the open derandomization question posed in the paper "Learning from Equivalence Queries, Revisited" that was recently published at COLT 2026. This is about whether randomization is strictly necessary for learning from symmetric equivalence queries. In the standard equivalence-query model, a learner iteratively proposes hypotheses from a concept class and receives counterexamples until the target concept is identified. While that prior COLT 2026 publication established that a proper randomized learner can learn any finite concept class in an expected number of queries linear in its Littlestone dimension against any symmetric counterexample generator (whose disagreement distribution is invariant under swapping the query and target), it left open whether a deterministic learner could also achieve a query bound depending only on the Littlestone dimension against arbitrary symmetric adversaries or the restricted class of order-induced adversaries. This submission resolves that question negatively, proving that Littlestone dimension alone cannot bound deterministic equivalence-query complexity and mapping out a comprehensive complexity phase diagram across target protocols and generator structures.

First, when the adversary can adaptively reselect the target from the current version space on each round, the paper shows that even on a singleton concept class of Littlestone dimension one, general symmetric two-point generators can force a number of deterministic queries linear in the number of concepts, while independently resampled distributions over total orders ("order mixtures") have an extremal deterministic complexity that scales with the square root of the number of concepts.

Second, under a fixed-target protocol, the submission establishes a tight worst-case logarithmic deterministic hierarchy on singleton classes via a likelihood-halving strategy and a reduction from tournament domination, alongside a general logarithmic upper bound (in the size of the concept class) for arbitrary finite classes against known conditionally symmetric generators.

Third, for a single fixed, known total order, the paper introduces a lexicographic projection of the standard optimal algorithm onto the version space to achieve an optimal version-consistent proper learner whose query count exceeds the Littlestone dimension by at most one (including for multiclass labels and under target reselection), while demonstrating a linear separation between reselected first-disagreement equivalence queries and transductive online learning.

Critical strengths

The paper directly answers the COLT 2026 derandomization open problem by demonstrating sharp asymptotic separations on singleton classes of Littlestone dimension one. Specifically, while randomized learners require fewer than three expected queries, deterministic proper learners can be forced to make a logarithmic number of queries for fixed targets, a square-root number of queries for resampled order mixtures, and a linear number of queries for general symmetric kernels under target reselection. Beyond asymptotic rates, the paper derives exact minimax recurrences and sharp constants across its protocols. Notable examples include an exact asymptotic expansion for the Stackelberg game value of the cyclic generator, an exact instance-wise frontier dimension for fixed orders, and an explicit nine-concept order mixture that proves a strict numerical gap between version-consistent and unrestricted proper probes.

Critical weaknesses

The constructive deterministic upper bounds in the submission require the learner to have full prior knowledge of the counterexample generator or order distribution. Although the submission justifies this theoretically by showing that an unknown generator forces a deterministic learner to exhaustively query the entire singleton class, this assumption limits practical applicability in motivating domains where the oracle's exact tie-breaking distribution is unknown. While the paper resolves the COLT 2026 question for general symmetric adversaries with a fixed target and for order mixtures under target reselection, the dimension-only question for independently resampled order mixtures under a fixed target remains open. Even on the singleton class, it remains undetermined whether the worst-case deterministic complexity across order mixtures with a fixed target is bounded by a universal constant or grows up to logarithmically with the number of concepts.

Questions for authors

None

2 comments
AuthorsOpenReview ↗

Full solution of the COLT 2026 open problem

Thank you very much for your careful summary and for your positive assessment. We have uploaded a revised version of the paper (now titled "Randomization in Learning from Symmetric Equivalence Queries"), which completely resolves the open problem posed by Braverman et al. at COLT 2026. The revision carries over all theorems and technical findings of the submitted version, adds a new positive result, and improves the presentation; the general response gives details and a correspondence table. Theorem and section numbers refer to the revised version unless we say otherwise.

1. The COLT 2026 question is fully solved by the revised version of the paper

Braverman et al. (COLT 2026, Section 5) ask: "is there always a deterministic learning rule for learning against arbitrary symmetric adversaries? What about the restricted but natural class of order-induced adversaries?" The table compares the two versions.

Part of the questionSubmitted versionRevised version
General symmetric feedbackNoNo (Theorem 3.1)
Order-induced, fixed targetOne known order: Yes; order mixtures: OpenYes for every known order-induced generator (new Theorem 4.1)
Order-induced, target reselectionOne known order: Yes; order mixtures: NoUnchanged (Corollary 4.2; Theorems 5.1-5.2)

Theorem 4.1 gives a deterministic learner that uses at most 12815Ldim(H)+1\frac{128}{15}\mathrm{Ldim}(\mathcal H)+1 queries in expectation against every known order-induced generator, for every finite class and every fixed target. Up to the constant, this cannot be improved. On singleton classes it needs at most 143/15<10143/15 < 10 queries whatever nn is, so the answer to the constant-versus-logarithmic question is "constant". General symmetric adversaries behave very differently: already in dimension one, a deterministic learner may need about log⁡2n\log_2 n queries (Theorem 3.1), while a randomized one needs at most 3. Under bandit feedback, the negative answers still hold because our lower-bound constructions use binary labels, and Theorem 4.5 gives a deterministic bound of (34k)Ldim(H)(34k)^{\mathrm{Ldim}(\mathcal H)} when at most kk labels occur at each point.

The idea behind Theorem 4.1 can be summarized in four steps.

  1. Each random checking order acts as a voter. The learner works in phases; at the start of a phase it freezes the current version space and its SOA predictions, and each order ranks the hypotheses lexicographically by where, along the order, they disagree with these predictions. Whenever the order ranks the query above the target, the query is either accepted or receives a counterexample that lowers the Littlestone dimension (Lemma C.2).
  2. Two hypotheses are enough to cover every target. By a recent result of Song, Nguyen and Lin (SODA 2026), there are two hypotheses such that, for every target outside the pair, a random order ranks at least one of them above it with probability at least 1/4. A target inside the pair is found by querying it.
  3. Each phase has constant expected cost. Within a phase, the learner alternates between these two hypotheses and keeps them fixed after each counterexample. Since the target does not move and every query draws a fresh order, each round of two queries ends the phase with probability at least 15/64, so a phase costs at most 128/15 queries in expectation.
  4. These costs add up over the dimension. Every phase that does not end in acceptance lowers the dimension by at least one, so there are at most Ldim(H)\mathrm{Ldim}(\mathcal H) phases, plus one final query once the dimension reaches zero (Section 4.2; full proof in Appendix C.5).

The argument needs the target to stay fixed, which is also why order mixtures behave differently once the target may be reselected.

2. On the known-generator assumption

We agree that this is a real limitation for applications. The assumption comes from the setting of the original question: Braverman et al. assume a fully known adversary and list learning with only sampling access as a separate direction (their Section 5). Proposition B.5 shows that this information cannot simply be dropped: a learner that does not use the generator can be forced to make nn queries on singleton classes, or (n+1)/2(n+1)/2 if it is randomized. This does not rule out algorithms with weaker information. The learner uses the generator only to choose a two-member committee in each phase, and the analysis needs only that this pair cover every target with probability bounded away from zero. These finitely many coverage probabilities can be estimated from sampled checking orders, so learning a committee from samples is a natural next step, which we now mention in Section 7.

We hope the new result settles the open case you pointed out, and we would be glad to clarify anything further.

AuthorsOpenReview ↗

A short follow-up before the discussion closes

Dear Reviewer vitf,

Thank you very much for your careful summary and your positive assessment of our work.

We wanted to follow up briefly as the discussion period draws to a close. Following your comments, the revised version settles the fixed-target case for order mixtures with a deterministic bound linear in the Littlestone dimension (Theorem 4.1), which completely resolves the open problem of Braverman et al. (COLT 2026). In particular, on singleton classes the deterministic cost is bounded by a universal constant. Our response also discusses the known-generator assumption that you raised.

Please let us know if you have any further questions or comments on our response or the revised version. We would be very happy to answer them.

Thank you again for your time and support.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response: guide to the revised PDF

We thank all reviewers and the area chair for their time and constructive comments. We have uploaded a revised PDF. To make reviewing the revision efficient, this note summarizes what it contains, what has changed, and how it corresponds to the submitted version. Theorem and section numbers refer to the revised PDF unless marked otherwise.

1. All theorems and proofs of the submitted version are retained. Every theorem, lemma and proposition of the submitted version appears in the revised PDF with its proof; some are merged or restated (for example, the tournament reduction and the logarithmic bound now form Theorem 3.1). The more specialized results that were in the main text (the consistent-only protocol, exact constants for particular generators, and the comparison with transductive learning) now appear in the appendices, so that the main text can focus on the main question. Part 4 lists where each result now appears.

2. The COLT 2026 open problem is now completely resolved. Braverman et al. (COLT 2026, Section 5) ask: "is there always a deterministic learning rule for learning against arbitrary symmetric adversaries? What about the restricted but natural class of order-induced adversaries?" The submitted version answered the first part and left one case of the second open. The revised PDF closes it:

Part of the questionSubmitted versionRevised version
General symmetric feedbackNoNo (Theorem 3.1)
Order-induced, fixed targetOne known order: Yes; order mixtures: OpenYes for every known order-induced generator (new Theorem 4.1)
Order-induced, target reselectionOne known order: Yes; order mixtures: NoUnchanged (Corollary 4.2; Theorems 5.1-5.2)

By the new Theorem 4.1, against every known order-induced generator with a fixed target, a deterministic learner needs at most 12815Ldim(H)+1\frac{128}{15}\mathrm{Ldim}(\mathcal H)+1 queries in expectation, which is optimal up to the constant.

3. What has changed, and how the revised PDF is organized. The title is now "Randomization in Learning from Symmetric Equivalence Queries" (previously "Randomization Is Necessary for Learning from Symmetric Equivalence Queries"), so that it reflects both the negative results we keep and the new positive result. The abstract and introduction state the complete answer. The new results are in Section 4 and Appendix C. Appendix A is a new proof guide with a proof index (Table 2) and two dependency diagrams that mark imported theorems separately: Figure 3 traces the positive result from the voting lemma and the committee theorem to Theorems 4.1 and 4.5, and Figure 4 shows the two negative mechanisms. The supplementary material now contains two verification scripts that match the revised PDF. The main text stays within 10 pages and follows the structure of the answer:

  • §1: a small example (Figure 1) and the answer in brief.
  • §2: the model, and a phase diagram of all main results (Table 1).
  • §3: general symmetric feedback: the negative answer and matching logarithmic bounds (Theorems 3.1-3.2).
  • §4: order-induced feedback, the positive answer (Theorem 4.1) with the algorithm (Figure 2), its proof idea, the single-order case (Corollary 4.2) and extensions (Theorem 4.3, Proposition 4.4, Theorem 4.5).
  • §5: why target reselection changes the answer (Theorems 5.1-5.3).
  • §6-7: related work and discussion.

The appendices:

  • App. A: proof guide and dependency diagrams.
  • App. B: complete proofs for §3.
  • App. C: complete proofs for §4, including the new results.
  • App. D: complete proofs for §5.
  • App. E: exact kernel calculations.
  • App. F: order-mixture constants.
  • App. G: consistent queries, the exact game for one known order, transduction and properization.

4. Correspondence with the submitted version.

Submitted PDFRevised PDF
§1-2 (introduction, model); App. A§1-2; App. G.7
§3: Thm 3.1, Lemmas 3.2-3.3, Prop 3.4; App. B§5: Thms 5.1-5.3; App. D, E.2
§4: Prop 4.1, Thms 4.2-4.4; App. F§3: Thms 3.1-3.2; App. B
§4: Prop 4.5; App. C (kernels, cyclic constants)App. E
§5: Lemma 5.1, Thm 5.2 (one known order)Cor. 4.2; App. C.2-C.3, G.8
§5: Props 5.3, 5.5, Thm 5.6; App. EApp. G.5-G.8
§6: Thms 6.1-6.2, Prop 6.3; App. GApp. G.1-G.4
App. D (order-mixture constants)App. D.4, F
App. F: Prop F.1 (Bellman recursion)Prop. D.1
App. H: Prop H.1 (unknown generator)Prop. B.5
App. H: open problem O-FThm 4.1; App. C.4-C.5 (new)
§7-8, App. I (related work, conclusion)§6-7
(none)Thm 4.3, Prop 4.4, Thm 4.5; App. A, C.6-C.8 (new)

We thank the reviewers again and would be glad to clarify anything further.

AuthorsOpenReview ↗

Solution of the open problem at COLT 2026

We are pleased to report that, following the reviewers’ constructive suggestions, the revised manuscript resolves the open problem posed by Braverman et al. at COLT 2026.

We sincerely thank all reviewers for their careful reading and constructive comments.

A central concern was that the submission had only partially resolved the COLT 2026 full-information derandomization question, leaving open whether deterministic proper learners can achieve expected query bounds depending only on the Littlestone dimension against known, independently resampled order-induced generators with a fixed target.

We have uploaded a revised manuscript that resolves this remaining case and thereby fully settles both parts of the question for finite concept classes with known generators and a fixed target. The comments below explain the new result and the corresponding revisions.

Thank you again for your time and thoughtful feedback. We would be grateful if you could take another look at the revised manuscript, and we would warmly welcome any further comments or questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.