{"id":"1596b966-c6ae-472f-b999-691531165b23","arxiv_id":"2605.29148","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Horizon-free pure-DP algorithm achieves optimal gap-dependent regret bound 1000*(log K/Δ_min + log K/ε) for stochastic online learning with K actions.","lead":"The paper gives a horizon-free pure differentially private algorithm for stochastic decision-theoretic online learning that achieves regret at most 1000 times (log K over the minimum gap plus log K over the privacy parameter ε). This matches the known lower bound order and resolves a COLT open problem.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"Whether the entropy-potential argument bounds the summed softmax errors across exponentially growing blocks without log T factors","rationale":"The reader's weakest assumption directly identifies the same point in the argument (the random-prefix conversion and its control via the potential). No other internal inconsistency or hidden dependence on T appears in the stated construction, so the verdict does not change.","tokens_in":1792,"tokens_out":312,"duration_ms":48897,"concrete_test":"Extract the precise definition of the entropy potential, its per-block update, and the summation over prefix lengths from the proof of the regret bound; recompute the total accumulated cost over a sequence of 20 doubling blocks and verify whether it remains O(log K / ε) independent of the number of blocks.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the random prefix of the previous block converts each block's regret into a sum (over prefix lengths) of softmax selection errors, and that one entropy-potential argument then bounds the total contribution of all privacy-dominated actions by O(log K / ε) for the entire run. Because blocks double in size, there are Θ(log T) blocks and the sum is taken over an increasing number of prefix lengths; if the potential is reset or charged per block, the aggregate cost scales with log T, contradicting the stated T-independent bound. The abstract asserts a single argument suffices but supplies no definition of the potential, its update rule, or the telescoping argument that would prevent accumulation.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims to resolve the COLT open problem of Hu and Mehta by giving a horizon-free pure event-level DP algorithm for stochastic decision-theoretic online learning. For K actions and losses in [0,1] with unique best action separated by gap Δ_min, it proves the explicit T-independent regret bound Reg_T ≤ 1000 ⋅ (log K / Δ_min + log K / ε) that matches the known lower bound up to the universal constant 1000. The algorithm partitions time into exponentially growing blocks, plays a single action per block, and selects the next action via the exponential mechanism applied to a data-independent random prefix of the prior block; a single entropy-potential argument is asserted to bound the total contribution of privacy-dominated actions by O(log K / ε).","tokens_in":1943,"tokens_out":458,"duration_ms":17913,"significance":"If the central analysis holds, the result is significant: it supplies the first explicit horizon-free pure-DP algorithm achieving the optimal gap-dependent rate, directly answering the open question. The block-partitioning construction together with the random-prefix reduction and entropy-potential argument are technically notable for eliminating all log T factors while preserving pure DP.","major_comments":[{"comment":"Abstract (final paragraph describing the algorithm): the claim that 'a single entropy-potential argument controls all privacy-dominated large-gap actions at cost log K/ε' is load-bearing for the T-independent bound. With Θ(log T) blocks of exponentially increasing size, the random-prefix construction produces a sum over an increasing number of prefix lengths; without an explicit definition of the potential function, its update rule across blocks, and the telescoping argument that prevents accumulation of log T factors, it is impossible to verify that the total privacy cost remains O(log K / ε) rather than O(log T ⋅ log K / ε).","section":"Abstract"}],"minor_comments":[{"comment":"The constant 1000 is explicitly stated as unoptimized; a short remark on whether the analysis yields a concrete (even if large) improvement path would aid readers.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their thorough review and positive assessment of the significance of our work. We address the major comment regarding the entropy-potential argument below. We agree that additional details are needed for clarity and will revise the manuscript to include them.","responses":[{"response":"We acknowledge that the abstract's description is high-level and that the full details of the entropy-potential argument are crucial for verifying the bound. In the revised version of the paper, we will expand the relevant section to explicitly define the entropy potential function, describe its update rule after each block, and provide the telescoping argument showing that the total contribution from privacy-dominated actions sums to O(log K / ε) independent of T. The argument relies on the fact that the random prefix ensures the selection error is averaged over prefixes, and the potential decreases sufficiently to offset the privacy cost without accumulation over the log T blocks due to the exponential block sizes and the uniform control over large-gap actions.","revision_made":"yes","referee_comment":"[Abstract] Abstract (final paragraph describing the algorithm): the claim that 'a single entropy-potential argument controls all privacy-dominated large-gap actions at cost log K/ε' is load-bearing for the T-independent bound. With Θ(log T) blocks of exponentially increasing size, the random-prefix construction produces a sum over an increasing number of prefix lengths; without an explicit definition of the potential function, its update rule across blocks, and the telescoping argument that prevents accumulation of log T factors, it is impossible to verify that the total privacy cost remains O(log K / ε) rather than O(log T ⋅ log K / ε)."}],"tokens_in":1455,"tokens_out":357,"duration_ms":24082,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper supplies the first algorithm and matching upper bound for the Hu-Mehta open question on gap-dependent regret under pure event-level DP. For K actions and unique best arm with gap Delta_min, it achieves Reg_T <= 1000 (log K / Delta_min + log K / epsilon) for any T, using exponentially growing blocks, a single action per block, and the exponential mechanism on a random prefix of the prior block.\n\nThe construction is new: earlier work had the lower bound but left the horizon-free upper bound open. The random-prefix trick converts per-block regret into a sum of softmax errors, and one entropy-potential argument is claimed to bound the privacy-dominated terms at total cost log K / epsilon without T factors. That is the central technical step, and the abstract states it works via a single potential.\n\nThe bound is explicit and the constant, while large, is consistent with an order-optimal result that was not previously available. The analysis assumes losses in [0,1] and a unique best action separated by Delta_min; those are standard but worth noting.\n\nThe main soft spot is verification of the potential argument itself. The stress-test concern about possible log T accumulation from summing over prefixes across Theta(log T) blocks is reasonable to raise from the abstract alone. The paper asserts the argument telescopes or resets to avoid that, but without the full derivation of the potential update and charging, it is hard to confirm the bound stays T-independent. The large constant also leaves room for tightening, though that is secondary.\n\nThis is for researchers in private online learning who care about tight gap-dependent rates. A reader working on DP regret bounds or COLT-style open problems gets direct value from the construction. It deserves serious referee time because it claims to resolve a stated open problem with a concrete algorithm and proof sketch.","headline":"This paper closes the COLT open problem with the first explicit horizon-free pure-DP algorithm matching the gap-dependent lower bound order.","tokens_in":2414,"tokens_out":443,"would_cite":true,"duration_ms":23326,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"A horizon-free pure-DP algorithm achieves gap-dependent regret bounded by 1000 times (log K over Delta_min plus log K over epsilon) for all time horizons T in stochastic decision-theoretic online learning.","keywords":["differential privacy","online learning","regret bounds","gap-dependent regret","stochastic decision-theoretic learning","full information feedback","pure DP","event-level privacy"],"falsifier":"An explicit instance with unique gap Delta_min where the algorithm's realized regret exceeds 1000 times (log K / Delta_min + log K / epsilon) on some run of length T, or a matching lower bound construction showing a strictly smaller universal constant is impossible.","tokens_in":2687,"feed_emoji":"🔐","tokens_out":816,"duration_ms":18171,"temperature":0.7,"pith_summary":"The paper establishes that the optimal gap-dependent regret under pure event-level differential privacy matches a known lower bound of order log K over min(Delta_min, epsilon). It does so by constructing an algorithm whose total regret never exceeds 1000 times that quantity, independent of the horizon length. A sympathetic reader cares because the construction resolves an explicit open question on the precise rate achievable with privacy constraints. The bound separates the contribution from the action gap and from the privacy parameter into two additive terms, each multiplied by log K.","feed_headline":"Private online learner matches gap-dependent regret lower bound","feed_subtitle":"Horizon-free pure-DP algorithm keeps total regret at most 1000 times (log K/Delta_min + log K/epsilon) for every T","key_machinery":"Block partitioning with exponentially growing sizes combined with an exponential mechanism on a data-independent random prefix of the prior block; the prefix turns each block's regret into a controllable sum of softmax errors whose total is bounded by an entropy potential.","core_discovery":"We study stochastic decision-theoretic online learning with full information and event-level pure differential privacy. For K actions, losses in [0,1], and a unique best action separated from the second-best by gap Delta_min, the known lower bound is of order log K over min(Delta_min, epsilon). We give a horizon-free pure-DP algorithm and prove the explicit regret bound Reg_T <= 1000 * (log K / Delta_min + log K / epsilon) for every horizon T. The algorithm partitions time into blocks of exponentially increasing size, plays a single action throughout each block, and chooses the next action by an exponential mechanism applied to a data-independent random prefix of the previous block. The rand","pith_inferences":["The random-prefix technique may extend to other settings where one wants to decouple privacy noise from gap-dependent selection.","If the constant 1000 can be reduced, the same algorithmic skeleton would immediately improve the explicit bound.","The entropy-potential argument might apply to other full-information private online problems that admit a softmax error decomposition."],"forward_implications":["The achieved regret is independent of the time horizon T.","The privacy cost appears only as the additive term log K / epsilon and does not interact with the gap term.","The same block structure yields a pure-DP guarantee while preserving the non-private gap-dependent rate up to the constant factor.","The construction works for any sequence of loss vectors satisfying the unique-gap assumption."],"fun_headline_variants":["Pure DP algorithm matches optimal gap-dependent regret bound","Horizon-free pure DP attains optimal private regret rate","Gap-dependent regret lower bound achieved under pure event DP","Optimal regret for private stochastic online learning proven"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The analysis assumes a unique best action separated from the second-best by a fixed gap Delta_min, losses bounded in [0,1], and that the random-prefix exponential mechanism converts block regret into a sum of softmax errors that an entropy potential can control.","fun_headline_variants_meta":{"raw":{"variants":["Pure DP algorithm matches optimal gap-dependent regret bound","Horizon-free pure DP attains optimal private regret rate","Gap-dependent regret lower bound achieved under pure event DP","Optimal regret for private stochastic online learning proven"]},"model":"grok-4.3","cost_usd":0.005337,"raw_usage":{"total_tokens":2636,"prompt_tokens":787,"num_sources_used":0,"completion_tokens":58,"cost_in_usd_ticks":53374500,"prompt_tokens_details":{"text_tokens":787,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1791,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":787,"tokens_out":58,"duration_ms":15580,"temperature":1.0,"reasoning_tokens":1791,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T13:21:57.442227+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit instance with unique gap Delta_min where the algorithm's realized regret exceeds 1000 times (log K / Delta_min + log K / epsilon) on some run of length T, or a matching lower bound construction showing a strictly smaller universal constant is impossible.","supporting_citations":[],"review_version":1}