{"id":"115b5a59-e62d-4119-832b-a78faa2b3912","arxiv_id":"2506.12856","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Online k-list learnability does not imply differentially private k-list learnability for k>1, disproving a natural extension of the multiclass equivalence.","lead":"This paper shows that the close equivalence between private and online learning breaks down for list learning: some classes that are learnable online with lists of k guesses are not learnable under differential privacy. It introduces a new combinatorial dimension, the k-monotone dimension, and gives two necessary conditions for private list learnability, leaving sufficiency open.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 17's five-summand bound is arithmetically false: the Lemma 18 term grows like n^{1-o(1)}, so the interior-point reduction for Theorem 2 does not go through.","rationale":"The reader's weakest assumption was the unproved extension of Lemma 8 from BNSV15 to list learning. That is a genuine missing justification, but it is not the most load-bearing issue. The paper's proof of the necessary condition PLL => finite k-Littlestone dimension (Theorem 2) relies on Lemma 14, whose proof depends on Proposition 17's utility bound. That bound contains a concrete arithmetic error: the first summand n·exp(-⌊log2 n⌋/(8(k+1))) is claimed to be <1/20 for large n, but it actually grows like a positive power of n. A simple calculation shows it exceeds 1 for all n≥2 when k≥1. Consequently, the reduction from the interior point problem is invalid as written. This does not necessarily refute the truth of the theorem, but it invalidates the provided proof. The separation result (online k-list learnable but not DP k-list learnable, Corollary B(iii)) may still survive through Theorem 4 and the class CL, but the paper's stronger claim that finite k-Littlestone dimension is necessary for DP k-list learnability is not established. Because the flaw is a false inequality rather than a missing detail, the appropriate verdict moves from CONDITIONAL to REJECT of the current version, pending substantial repair of the reduction.","tokens_in":32298,"tokens_out":13127,"duration_ms":140531,"concrete_test":"Recompute the first summand in the Proposition 17 bound for arbitrary n and k: show n·exp(-⌊log2 n⌋/(8(k+1))) = n^{1-1/(8(k+1)ln2)}·(1+o(1)), which exceeds 1/20 for all n≥2 and k≥1. Equivalently, instantiate k=1, n=2^32; if the summand is not <1/20, the claim in the proof is false and the reduction is invalid.","verdict_should_be":"REJECT","load_bearing_attack":"In the proof of Lemma 14 (Section 5.2), the utility analysis of Algorithm 1 (Proposition 17) claims that each of five summands bounding the failure probability is <1/20. The first summand comes from Lemma 18: n·exp(-⌊log2 n⌋/(8(k+1))). Since ⌊log2 n⌋≈ln n/ln2, this equals n^{1-1/(8(k+1)ln2)} up to subexponential factors, which tends to infinity for every fixed k≥1. For example, with k=1 and n=2^32 it is ≈2^30, not <1/20. Thus the success probability of the reduction is not bounded below by 3/4, and the proof of Lemma 14, Theorem 2, and Corollary B(i) is unsupported. This is independent of the reader's Lemma 8 concern: even granting the empirical-learner conversion, the reduction from the interior point problem fails.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies k-list PAC learning under differential privacy and compares it with online k-list learning. The main claims are: (i) finite k-Littlestone dimension is necessary for private k-list learnability (Theorem 2 and Corollary A(i)); (ii) finite k-monotone dimension, a newly introduced generalization of threshold dimension, is also necessary (Theorem 4 and Corollary A(ii)); and (iii) for every k>1 these two dimensions are independent, yielding a class that is online k-list learnable but not privately k-list learnable (Theorem 5 and Corollary B). The paper thus claims the first separation between private and online learnability in the list-learning setting. The conceptual framework is interesting, and the proof of Theorem 5 is clean, but the proof of the necessity of finite k-Littlestone dimension contains a concrete arithmetic error in the interior-point reduction that invalidates the proof of Theorem 2 as written.","tokens_in":32488,"tokens_out":19005,"duration_ms":238877,"significance":"If the technical gaps are repaired, the paper would make a notable contribution: it identifies a natural setting where the classical equivalence between private and online learnability breaks down, and it introduces a new combinatorial dimension that is necessary but not sufficient for private list learnability. The separation itself, Corollary B(iii), does not depend on the flawed interior-point argument for Theorem 2; it uses Theorem 4 and Theorem 5, whose proofs appear essentially sound conditional on the unproved Lemma 8. The generalization of the tree Ramsey theorem of FHM+24 to (k+1)-ary trees is a useful methodological contribution. The paper is clearly written, with detailed proofs and an honest statement of the open question whether finiteness of both dimensions is sufficient.","major_comments":[{"comment":"The claim that each of the five summands bounding the failure probability is smaller than 1/20 is arithmetically false for the first summand. With l = floor(log2 n), n * exp(-l/(8(k+1))) = exp(ln n - (log2 n + O(1))/(8(k+1))) = n^{1 - 1/(8(k+1) ln2) + o(1)}, which diverges for every fixed k >= 1; for k=1 it is roughly n^{0.91}. This is not a loose-constant artifact of the Chernoff bound: under the independence model used in the proof, the per-interval probability of an almost-correct interval below x_m is exp(-Theta(l/(k+1))), so the expected number of such intervals is n^{1 - Theta(1/(k+1))}, which is polynomial in n. Since Algorithm 1 outputs the deepest almost-correct interval, the presence of such intervals below x_m would place the output outside [d1, dm], so the utility guarantee of Proposition 17 fails. Consequently Lemma 14, Theorem 2, Corollary A(i), and Corollary B(i) are unsupported as written. A plausible repair is to take l = C(k) * floor(log2 n) with C(k) > 8(k+1) ln2 and to require, in Lemma 15, input spacing larger than l; the proof of Lemma 19 would then still find an interval inside S because consecutive inputs are spaced by more than l. This repair needs to be carried out in detail, including the constants in Lemmas 18 and 19 and the rescaling argument in Lemma 15.","section":"Section 5.2, Proposition 17 and Lemma 18"},{"comment":"The extension of Lemma 5.9 of BNSV15 from ordinary classification to k-list learning is asserted without proof: the paper says the proof 'also applies to more general settings, including the setting of list learning.' This step is load-bearing because both lower-bound proofs (Theorem 2 and Theorem 4) first convert a PAC learner into an empirical learner, and the impossibility results are then proved only for empirical learners. Please provide a proof, or a precise citation to a version of the subsampling argument that treats hypotheses mapping to k-element subsets. I expect a short appendix proof is feasible, since the standard subsampling-amplification argument does not appear to use the single-label nature of the output.","section":"Section 3.2, Lemma 8"}],"minor_comments":[{"comment":"The first sentence says 'we outline the proof of Theorem 4', but this section is about the k-Littlestone dimension lower bound and should refer to Theorem 2.","section":"Section 2.1"},{"comment":"In the paragraph defining the k-Littlestone dimension, 'Littlestione dimension' is a typo for 'Littlestone dimension'.","section":"Section 3.1"},{"comment":"The type set is written as {0,1}^{m+1}; since the tree has arity k+1, it should be {0,...,k}^{m+1}.","section":"Definition 12"},{"comment":"The accuracy parameter is written as 1/200k(k+), which appears to be a typo for 1/(200k(k+1)), matching the statement of Theorem 4.","section":"Lemma 22"},{"comment":"There are unresolved 'See ??' references in the proof of Theorem 11; these placeholders should be filled or removed.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The central conceptual claim is valuable and the separation result appears quite plausibly correct, but the proof of Theorem 2 has a genuine arithmetic gap in Proposition 17 that is load-bearing for the PLL => OLL direction. The gap seems repairable by using intervals of length C(k) log n and adjusting the input-separation assumption, so I do not recommend rejection at this stage. The authors should also supply the missing proof of Lemma 8 for list learners. If the repair cannot be made within a reasonable revision, the status of Theorem 2 and Corollary B(i) should be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the paper has a genuinely interesting central idea—list learning breaks the private/online equivalence—and the k-monotone dimension is a nice new combinatorial parameter. The example of a class that is online k-list learnable but not privately learnable is convincing. Unfortunately, the proof of the other main direction, Theorem 2 (private list learning implies finite k-Littlestone dimension), contains a serious arithmetic error in the reduction from the interior point problem. As written, the proof does not go through.\n\nThe problem is in Proposition 17. The utility bound decomposes the failure probability into five summands and claims each is below 1/20. The first summand is n·exp(-⌊log₂n⌋/(8(k+1))) from Lemma 18. That quantity grows roughly like n^{1-1/(8(k+1)ln2)}; for k=1 it is about n^0.91, so it tends to infinity with n, not to zero. The claim that it is small for 'large enough n' is backwards. This breaks the reduction: the constructed algorithm does not solve the interior point problem with the required success probability, so Lemma 14, and with it Theorem 2 and Corollary B(i), are unsupported. This is independent of the reader's concern about Lemma 8—even granting the empirical-learner conversion, the reduction fails.\n\nThe Lemma 8 concern is real but secondary. The paper asserts that BNSV15's PAC-to-empirical conversion extends to list learning without proving it. That needs a proof or a direct citation, since both lower-bound proofs rely on it.\n\nWhat the paper does well: the k-monotone dimension is well-defined and it appears to be genuinely necessary for private list learnability; the separation between k-LD and k-MD is crisp and the example classes are simple. The Ramsey-theoretic generalization to b-ary trees is a useful technical tool. Section 6 (k-MD) looks substantially correct to me, though I did not check every computation.\n\nWho this is for: theoretical computer scientists working on private learning and combinatorial dimensions. It deserves a serious referee—the conceptual contribution is important—but only with the expectation of major revision. The arithmetic error is likely fixable by modifying the reduction or the choice of parameters, but until then, the main claim should not be taken as established.","headline":"The separation result and k-monotone dimension are real contributions, but the proof of the k-Littlestone necessity theorem has an arithmetic error that invalidates the reduction; the main claim is unsupported as written.","tokens_in":32984,"tokens_out":4177,"would_cite":false,"duration_ms":40727,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05","05D10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that private PAC list learning is strictly weaker than online list learning for k>1: a finite k-Littlestone dimension is necessary but not sufficient, witnessed by the class of (k+1)-labeled monotone functions over N.","keywords":["k-list learning","differential privacy","online learning","PAC learning","k-Littlestone dimension","k-monotone dimension","monotone functions","Ramsey theory"],"falsifier":"A concrete DP PAC k-list learner for the (k+1)-labeled monotone functions over N for some k>1, for instance a 2-list learner for 3-labeled monotone functions with sample complexity o(log* n) on [n], would refute the main separation; alternatively, proving the PAC-to-empirical conversion fails for list learning would remove the lower bounds' reach over general PAC learners.","tokens_in":32109,"feed_emoji":"📋","tokens_out":4198,"duration_ms":47329,"temperature":0.7,"pith_summary":"The paper asks whether the known equivalence between differential privacy and online learning in multiclass PAC classification extends to k-list learning, where a learner outputs a list of k labels and errs only if the true label is absent. It establishes one direction: any differentially private k-list learner must have finite k-Littlestone dimension, hence is online k-list learnable. It then breaks the converse. For every k>1, the class of (k+1)-labeled monotone functions on the natural numbers is online k-list learnable with mistake bound 1 but is not DP PAC k-list learnable. The separation is certified by a new parameter, the k-monotone dimension, which is finite in the multiclass setting exactly when the threshold dimension is but becomes an independent barrier for lists. The upshot is that private list learnability needs at least two incomparable combinatorial conditions, and a single-parameter characterization may not exist.","feed_headline":"List predictions split private from online learning","feed_subtitle":"A monotone class with k+1 labels is online-learnable with one mistake yet impossible under differential privacy.","key_machinery":"Two combinatorial dimensions carry the argument. The k-Littlestone dimension is the depth of the deepest shattered (k+1)-ary mistake tree and characterizes online k-list learnability. The k-monotone dimension is the largest d such that the class restricted to d ordered points contains all monotone functions over k+1 ordered labels, generalizing the threshold dimension. The lower-bound proofs replace full comparison-based predictions with the weaker requirement of comparison-based loss, then reduce to the interior point problem; one reduction uses a Ramsey theorem for b-ary trees, the other uses classical hypergraph Ramsey to force approximately comparison-based marginal probabilities for the k+1 relevant labels.","core_discovery":"For list learning, the multiclass equivalence between private learnability and online learnability holds in only one direction. The paper proves that finite k-Littlestone dimension is necessary for DP PAC k-list learnability, and separately that finite k-monotone dimension is also necessary. It then constructs two separating classes for k>1: the class of all (k+1)-labeled monotone functions on N has k-Littlestone dimension 1 and infinite k-monotone dimension, while the class of concepts realizing a single branch of an infinite (k+1)-ary tree has infinite k-Littlestone dimension and k-monotone dimension 1. The first class is online k-list learnable with at most one mistake yet not privately list learnable, so online learnability does not imply private learnability. Whether finite k-Littlestone dimension together with finite k-monotone dimension is sufficient for private k-list learnability remains open.","pith_inferences":["The natural conjecture left by the paper is that finite k-Littlestone dimension plus finite k-monotone dimension is sufficient for DP k-list learnability; testing this on the two constructed separating classes would be a direct next step.","The separation uses the infinite domain N, so a finite-domain analogue would give a quantitative question: how large must the domain be before the sample-complexity gap between private and non-private list learning becomes visible.","The comparison-based loss relaxation may transfer to other structured prediction settings, such as partial concepts or list regression, where the full comparison-based prediction assumption is too strong.","The k-monotone dimension could interact with representation-based characterizations of pure differential privacy, suggesting that list learning may require a genuinely multi-parameter theory."],"forward_implications":["Every DP PAC k-list learnable class is online k-list learnable, since finite k-Littlestone dimension is necessary.","For k=1 the two notions coincide, recovering the known multiclass equivalence.","For k>1 there are classes online k-list learnable with mistake bound 1 that are not DP PAC k-list learnable.","Both finite k-Littlestone dimension and finite k-monotone dimension are necessary for private list learning, and neither alone is sufficient.","Any private k-list learner for a class with k-Littlestone dimension d requires a sample complexity of Omega(log* d), and similarly for k-monotone dimension d."],"supporting_citations":[{"why":"Introduces the k-Littlestone dimension and proves it characterizes online k-list learnability, giving the parameter whose necessity is established here.","marker":"[MSTY23]"},{"why":"Supplies the interior point problem lower bound and the private PAC-to-empirical learner conversion (Lemma 8) on which both lower-bound proofs rest.","marker":"[BNSV15]"},{"why":"Establishes multiclass private learnability implies finite Littlestone dimension via threshold dimension and Ramsey-theoretic lower bounds, the approach generalized in Section 6.","marker":"[ALMM19]"},{"why":"Provides the binary-tree Ramsey theorem and comparison-based reduction technique that the paper extends to b-ary trees and to comparison-based loss.","marker":"[FHM+24]"},{"why":"Supplies the k=1 converse (online learnable implies DP learnable), the base equivalence that the paper shows fails for k>1.","marker":"[BLM20]"},{"why":"Extends the private-online equivalence to finite multiclass label spaces, providing the benchmark setting the paper contrasts with list learning.","marker":"[JKT20]"}],"fun_headline_variants":["List learning: online learnable does not mean private","Monotone class breaks list privacy equivalence","k-Littlestone dimension not sufficient for DP lists","New k-monotone dimension for privacy necessary"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound proofs start from a differentially private empirical list learner, and the step that converts any private PAC list learner into a private empirical one with only a constant factor sample blow-up is asserted to carry over from the multiclass case without proof, so if that conversion fails the impossibility might only hold for empirical learners.","fun_headline_variants_meta":{"raw":{"variants":["List learning: online learnable does not mean private","Monotone class breaks list privacy equivalence","k-Littlestone dimension not sufficient for DP lists","New k-monotone dimension for privacy necessary"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000499,"raw_usage":{"total_tokens":2525,"prompt_tokens":1110,"completion_tokens":1415,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":726,"completion_tokens_details":{"reasoning_tokens":1354}},"tokens_in":726,"tokens_out":1415,"duration_ms":15153,"temperature":1.0,"reasoning_tokens":1354,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:37:38.377697+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete DP PAC k-list learner for the (k+1)-labeled monotone functions over N for some k>1, for instance a 2-list learner for 3-labeled monotone functions with sample complexity o(log* n) on [n], would refute the main separation; alternatively, proving the PAC-to-empirical conversion fails for list learning would remove the lower bounds' reach over general PAC learners.","supporting_citations":[],"review_version":1}