{"id":"1a610d48-f524-41d6-958f-46f9e0b5f4c5","arxiv_id":"2501.14928","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new 'hybrid DEC' complexity measure gives matching (up to logs) lower and upper bounds for decision-making under constrained adversaries, unifying SQ, LDP, robust, and smooth learning, with new LDP contextual bandit regret guarantees.","lead":"This paper introduces a unified framework, hybrid DMSO, for interactive decision making when the environment changes under constraints, and shows it covers statistical-query learning, local differential privacy, robust learning, and smooth adversaries. It derives regret and PAC bounds from a common complexity measure (the Decision-Estimation Coefficient), with a new near-optimal square-root-T regret bound for LDP linear contextual bandits.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Moderate decay is not a mild condition: a quadratic DEC (ε²) violates Definition 3 and makes Lemma F.7 convert the offset DEC to O(ε) instead of O(ε²), so Theorem 1's upper bound can degrade by a square root.","rationale":"The reader identified moderate decay as a key regularity assumption, and I agree that it is the most load-bearing issue among the listed assumptions. The contribution sharpens the concern: moderate decay is not merely unproven for some exotic class; there is a natural squared-error interactive estimation problem whose DEC is ε², which directly violates Definition 3. In that regime the offset-to-DEC conversion in Lemma F.7 provably loses the quadratic dependence, so the clean upper bound p-decH_{ε̄(T)} does not follow from the stated machinery. The informal Theorem 1 therefore overstates the generality of the characterization unless the 'mild growth assumption' is made explicit, and the abstract's blanket claim should be qualified. This does not invalidate the paper's main lower bounds or the E2D-based bounds in Sections 5--6, which do not rely on moderate decay; hence a conditional acceptance remains the right disposition, with the abstract and Theorem 1 statements requiring tightening.","tokens_in":66511,"tokens_out":31772,"duration_ms":313147,"concrete_test":"Take hybrid DMSO with Θ=[−1,1], noisy observations satisfying D_H²(θ,θ′)≍(θ−θ′)², squared-error loss L(P,π)=(π_P−π)², and a finite ε-cover Pε of the single-model family P. Compute p-decH_ε(Pε) exactly; it should be Θ(ε²). Then instantiate ExO+ as in Theorem F.5 with the offset DEC conversion from Lemma F.7 and determine whether the T-round PAC risk is Θ(log|P|/T) or only Θ(√(log|P|/T)). If the latter, the informal Theorem 1 upper bound fails for this class, and the statement must either explicitly exclude super-linear DEC growth or prove a sharper offset-to-DEC conversion.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The formal upper bounds (Theorems 8 and 10) assume the DEC has moderate decay (Definition 3). This is not a harmless regularity condition. Consider scalar interactive estimation with squared-error loss L(P,π)=|π_P−π|², which satisfies the 'metric-like' inequality (50) with C1=C2=2. The hybrid PAC DEC is d(ε)=Θ(ε²): for a reference model, the models within Hellinger radius ε form a parameter interval of width ε, and the worst squared error over that interval is ε². For this d, d(ε)/ε=ε, so as ε→0 the quantity d(ε′)/ε′ grows without bound for ε′≥ε; no constant c can satisfy Definition 3. Lemma F.7 controls the offset DEC via sup_{ε′∈[ε,1]} d(ε′)/ε′, which for d=ε² equals 1, yielding an O(ε) bound rather than O(d(ε))=O(ε²). Plugging this into Theorem F.5 gives an ExO+ risk bound of order ε̄(T)=√(log|P|/T), whereas the claimed upper bound is p-decH_{ε̄(T)} = log|P|/T, while the lower bound is 1/T. Thus the informal equivalence in Theorem 1 — that the hybrid DEC gives matching upper and lower bounds up to polylog factors — is not established for this natural squared-error class. Since squared loss appears in the paper's own regression applications (Section 5.2), this is a load-bearing gap, not merely a proof artifact.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a hybrid Decision Making with Structured Observations (DMSO) framework interposing between stochastic and adversarial decision making, with constraints both on the environment's evolution and on the learner's observations. It defines hybrid PAC and regret Decision-Estimation Coefficients (DECs) and claims matching lower and upper bounds on minimax risk and regret, achieved by a generalized Exploration-by-Optimization algorithm (ExO+) and an Estimation-to-Decision variant. The framework is instantiated for Statistical Query learning, local differential privacy, robust (Huber-contaminated) decision making, smooth adversaries, and contextual bandits. The headline application is a near-optimal O(√(d³T log(T/δ))/α) regret bound for linear contextual bandits under LDP, derived from the private regret-DEC bound r-decLDP_ε(MLin-CB) ≲ dε.","tokens_in":66889,"tokens_out":8211,"duration_ms":75401,"significance":"If the main equivalence holds, the paper provides a genuinely unifying complexity characterization for several otherwise disparate settings, and it would settle or nearly settle an open problem on LDP linear contextual bandits. The reductions between hybrid DEC and SQ DEC (Lemma E.5) and between hybrid DEC and LDP DEC (Lemma E.6) are clearly delineated, and the linear-bandit DEC calculation is an explicit computation rather than a curve-fit. The paper also connects DEC to SQ dimension, local minimax complexity, and joint differential privacy, which broadens the framework's impact. The appendices are extensive and contain detailed proofs of the main reductions. However, the central upper-bound statement depends on a 'moderate decay' condition whose scope is more restrictive than the informal theorems suggest, and this affects the claimed PAC equivalence for natural loss classes.","major_comments":[{"comment":"Definition 3 (moderate decay) is not a harmless regularity condition, and it is load-bearing for the main upper bound. Consider scalar interactive estimation with squared-error loss L(P,π)=|π_P−π|². This loss satisfies the metric-like inequality (50) with C1=C2=2, but for a one-dimensional location family the hybrid PAC DEC scales as d(ε)=Θ(ε²): a Hellinger ball of radius ε corresponds to a parameter interval of width Θ(ε), and the worst squared error over that interval is Θ(ε²). This d violates Definition 3, because d(ε)/ε=ε while sup_{ε'≥ε} d(ε')/ε' = 1 for ε→0, so no constant c can satisfy c·d(ε)/ε ≥ d(ε')/ε' for all ε'≥ε. Consequently Lemma F.7 gives inf_γ(p-deco,H_γ(P)+γε²) ≤ 8ε·sup_{ε'∈[ε,1]} d(ε')/ε' = O(ε), not O(d(ε))=O(ε²). Plugging this into Theorem F.5 yields an ExO+ risk bound of order √(log|P|/T), whereas the claimed upper bound in Theorem 1 is p-decH_{ε̄(T)}(P) = log|P|/T, with a lower bound of 1/T. Since squared loss is explicitly one of the losses in the paper's regression applications (Example 6 and Section 5.2), this is not a proof artifact: the informal equivalence stated in Theorem 1 is not established for a natural class inside the paper's own scope. The statements should be corrected either by restricting the upper bound to DECs whose growth is 'linear' (ρ ≤ 1) or by replacing the upper bound with the sup-over-ε' expression and quantifying the resulting loss.","section":"Definition 3 / Lemma F.7 / Theorems 1 and 8"},{"comment":"The formal regret upper bound requires Assumption 3 (observability, Eq. (18)) in addition to moderate decay, but the informal Theorem 5 does not list this assumption. The paper verifies Assumption 3 for reward-based learning (Example 1 with CV=√2) and for LDP reward-based learning (Appendix E.3.2 with CV=O(1/α)), but it does not show that the assumption holds for every constraint class P covered by the hybrid DMSO framework. For the advertised general characterization, the theorem statement should either prove Assumption 3 for a broad class of value functions or explicitly state that the regret upper bound is conditional on an assumption that may fail for natural hybrid problems. As written, the gap between the informal claim and the formal hypothesis is too large to be called 'mild'.","section":"Theorem 10 / Assumption 3 (Eq. 18)"},{"comment":"The LDP instantiations rest on Proposition 20, the strong data-processing inequality, which asserts that for every α-LDP channel Q there exists a distribution q_Q over binary functions such that the two-sided inequality (29) holds uniformly for all pairs (P1,P2). This is a delicate statement: the same q_Q must work for all pairs, and the constants must be dimension-free for the later DEC equivalences (Lemma E.6) to have the claimed form. The proof is deferred to Appendix I.1, and I could not fully verify it from the main text. Please confirm explicitly that the absolute constants in Eq. (29) do not depend on the observation space, the latent space, or the model class, and that the same q_Q indeed serves both the upper and lower bounds uniformly; otherwise the private DEC equivalence and the resulting LDP bounds inherit an unquantified dependence.","section":"Proposition 20 / Lemma E.6"}],"minor_comments":[{"comment":"The section heading 'Proof of Theorem 9' appears to be a mismatch: the section proves the no-regret upper bound, which is Theorem 10, not the lower bound of Theorem 9.","section":"Appendix F.4.2"},{"comment":"The definition of L2(M,θ) appears to be missing the square on the inner product: it should read E_{x∼M}(⟨x,θ−θ⋆⟩)² rather than E_{x∼M}⟨x,θ−θ⋆⟩².","section":"Section 5.3, Example 7"},{"comment":"The phrase 'under certain growth conditions' or 'under assumptions on the value function' is used in the informal theorems without pointing to Definition 3 and Assumption 3. Please add forward references and state the exact hypotheses in each informal theorem statement.","section":"Theorems 1–6"},{"comment":"The notation ε̄(∆T) in Eq. (17) is confusing because ∆ appears inside the logarithm and also as an additive slack; please define the argument of ε̄ explicitly.","section":"Eq. (17)"}],"recommendation":"major_revision","confidential_remarks":"The moderate-decay issue is the main obstacle to acceptance: it affects the headline PAC equivalence and the squared-loss regression applications. I believe it is fixable by restating the upper bounds in the sup_{ε'} form and by being explicit about which instantiations enjoy linear DEC growth. The linear contextual bandit result (Theorem 30) has r-decLDP_ε ≈ dε and should survive the correction, but the paper's broad informal claims need to be aligned with the formal hypotheses. I was not able to verify every deferred calculation in Appendices I and J from the manuscript text provided; those proofs should be checked carefully during revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a serious framework paper with several new results that will be cited. The hybrid DMSO formulation is a genuine interpolation between stochastic and adversarial DMSO, and the paper shows convincingly that SQ, LDP, robust, and smooth decision making fit under one umbrella with DEC-based upper and lower bounds. The concrete payoffs are real: the LDP linear contextual bandit bound of O(sqrt(d^3 T log(T/delta))/alpha) improves on previous T^{3/4} and log(T) sqrt(T) rates and removes well-conditioning assumptions; the SQ-dimension equivalence in Proposition 17 and the LDP learnability characterization via fractional covering number in Theorem 36 go beyond what was known. The strong data-processing inequality (Proposition 20) is a nice technical tool, and the proof structure is coherent. This deserves a serious referee.\n\nThe main soft spot is the moderate-decay assumption (Definition 3), and the stress-test note is on target. A DEC like d(eps)=eps^2 is natural for squared-error interactive estimation, but it violates Definition 3 in a strong sense. Consequently, Lemma F.7 converts the offset DEC to O(eps) instead of O(eps^2), so the upper bound in Theorem 8 becomes O(sqrt(log|P|/T)) rather than the O(log|P|/T) that the informal Theorem 1 suggests. That is a genuine gap for exactly the kind of squared-loss applications the paper itself discusses in Section 5.2. I do not think it sinks the paper: the formal theorems are correctly qualified, and the headline LDP bandit result uses a linear DEC where the assumption holds. But the abstract and informal statements overstate the tightness, and the authors should either prove the upper bound under a weaker condition (e.g., bounding the sup over eps' directly) or explicitly flag that moderate decay is needed for the polylog-tight equivalence.\n\nMinor points: many proofs are deferred to appendices, but the appendices appear substantively present; the dimension-free strong data-processing inequality is proven but delicate, so I would ask a referee to verify that carefully. The related-work and citation pattern look fine; the framework extends prior work by the same group without hiding dependence on it.\n\nWho is this for? Anyone working on decision-making frameworks, LDP online learning, or query-based learning. I would bring it to a reading group and would cite it. Recommendation: send to peer review. It will likely need a revision that tightens the informal claims and discusses the moderate-decay limitation, but the core contributions are solid and timely.","headline":"Substantial hybrid-DMSO framework with real payoffs in LDP bandits, but the advertised near-tight characterization is limited by a moderate-decay assumption that can cost a square root.","tokens_in":67444,"tokens_out":4178,"would_cite":true,"duration_ms":40835,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62C20","68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a single complexity measure, the hybrid Decision-Estimation Coefficient, controls both PAC risk and regret for interactive decision making where the environment can change under constraints, and that instantiating…","keywords":["hybrid Decision-Estimation Coefficient","local differential privacy","statistical queries","robust decision making","contextual bandits","minimax regret","learnability","strong data-processing inequality"],"falsifier":"Give a finite LDP instance such as a two-armed bandit with known binary rewards, compute the private regret-DEC exactly as a function of $\\varepsilon$, and check whether it has moderate decay on $[1/(\\alpha\\sqrt{T}),1]$; if not, ExO+'s offset-to-DEC conversion can fail, so running LDP-ExO and finding regret outside the predicted $O(\\sqrt{d^3T\\log(T/\\delta)}/\\alpha)$ would settle that the claimed bound is not reached.","tokens_in":66266,"feed_emoji":"🎯","tokens_out":8780,"duration_ms":76692,"temperature":0.7,"pith_summary":"This paper claims that one complexity measure, the hybrid Decision-Estimation Coefficient (DEC), controls how hard it is to learn by interacting with an environment that may change over time, as long as the changes respect a constraint set. The hybrid DEC is shown to sandwich the minimax PAC risk and regret between two evaluations of the same quantity, up to logarithmic factors, with stationary adversaries giving the lower bound and an exploration-by-optimization algorithm giving the upper bound. Because local differential privacy, statistical-query learning, Huber-style contamination, and smooth adversaries all become constraint sets in this formulation, the paper obtains DEC bounds for all four settings under one umbrella. The flagship application is a near-optimal $\\sqrt{T}$ regret for linear contextual bandits under local differential privacy, without the well-conditioning assumptions that earlier results required. If the framework is right, DEC becomes the default first question to ask about any new interactive learning problem: what does the DEC do as $\\varepsilon$ shrinks?","feed_headline":"One complexity measure sets learning rates under privacy and change","feed_subtitle":"Brackets minimax risk and regret, giving near-optimal √T regret for private linear bandits.","key_machinery":"The workhorse is the hybrid Decision-Estimation Coefficient (DEC), a minimax value defined as the smallest risk a learner can guarantee while holding Hellinger divergence from every compatible model to a reference model at most $\\varepsilon^2$. The constraint class $\\mathcal{P}$ encodes how the environment may change, and the measurement class $\\Phi$ encodes what the learner may observe; both enter only through this quantity. Upper bounds are carried by ExO+, which solves a minimax exploration-by-optimization objective and updates weights over information sets; for query-based and private settings, an estimation-to-decision variant (E2D) supplies upper bounds with weaker assumptions. The private instantiation rests on a strong data-processing inequality (Prop. 20) showing that an $\\alpha$-DP channel's Hellinger distance equals (up to constants) an $\\ell$-divergence average with factor $\\alpha^2$, which is what turns privacy into a DEC over binary channels.","core_discovery":"The central claim is that the hybrid DEC of a constraint class $\\mathcal{P}$ simultaneously lower- and upper-bounds the minimax PAC risk (Theorem 1) and regret (Theorem 5): $$p\\text{-dec}^{\\mathrm{H}}_{\\varepsilon(T)}(\\mathcal{P}) \\lesssim \\inf_{\\mathrm{Alg}}\\sup_{\\mathrm{Env}}\\mathbb{E}[\\mathrm{Risk}] \\lesssim p\\text{-dec}^{\\mathrm{H}}_{\\bar\\varepsilon(T)}(\\mathcal{P}),$$ with $\\varepsilon(T)\\asymp 1/\\sqrt{T}$ and $\\bar\\varepsilon(T)\\asymp \\sqrt{\\log|\\mathcal{P}|/T}$. The lower bound only needs stationary constrained environments; the upper bound is attained by ExO+, a generalization of exploration-by-optimization. For local privacy, a strong data-processing inequality converts the hybrid DEC into a private DEC based on $\\ell$-divergences, and the regret-DEC of the linear contextual bandit class is bounded by $d\\varepsilon$, yielding $\\mathrm{Reg}(T)\\le O(\\sqrt{d^3T\\log(T/\\delta)}/\\alpha)$. The same machinery recovers the SQ-dimension characterization of Statistical Query learning, the TV modulus-of-continuity characterization of local-minimax LDP estimation, and the fractional-covering characterization of LDP and joint-DP learnability.","pith_inferences":["The linear contextual bandit analysis suggests an analogous treatment of linear mixture RL under LDP, where the DEC would be the natural object to compute for adversarial contexts and no explorability assumption.","The gap between the $\\log|\\mathcal{P}|$ term in Theorem 8 and the fractional-covering-number refinements in Proposition 13 indicates that data-dependent information sets can tighten DEC upper bounds beyond the paper's examples, likely for non-convex sequential estimation.","The strong data-processing inequality in Prop. 20 is dimension-free only for pure $\\alpha$-DP channels; extending the DEC equivalence to approximate $(\\alpha,\\beta)$-DP channels would be a direct test of whether the LDP rates survive approximate privacy.","The structural equivalence between the robust DEC and the hybrid DEC with contamination constraints suggests a broader duality between robustness and privacy in interactive decision making, mirroring known robustness-privacy connections in statistical estimation."],"forward_implications":["Linear contextual bandits under $\\alpha$-local differential privacy admit regret $O(\\sqrt{d^3T\\log(T/\\delta)}/\\alpha)$, a near-optimal $\\sqrt{T}$ rate that needs no well-conditioned covariance assumption.","For Statistical Query learning, the SQ DEC gives both lower and upper bounds on query complexity and recovers the SQ-dimension characterization for distributional search problems.","The fractional covering number characterizes finite-time learnability under LDP, and equivalently under pure joint differential privacy, for reward-based losses.","Huber-type $\\beta$-contaminated decision making has a robust DEC whose PAC and regret guarantees follow directly from the general hybrid-DEC theorems.","Local-minimax LDP complexity is captured by a local DEC, which reduces to the TV modulus of continuity for functional estimation.","A similar DEC-instantiating recipe applies to smooth adversaries, where the regret-DEC of the smoothed model class plays the role of the complexity measure."],"supporting_citations":[{"why":"Defines the DMSO protocol and the original DEC that this paper extends to hybrid environments.","marker":"[Foster et al., 2021]"},{"why":"Introduces adversarial DMSO and the Exploration-by-Optimization algorithm that ExO+ generalizes for hybrid upper bounds.","marker":"[Foster et al., 2022b]"},{"why":"Provides constrained PAC-DEC and regret-DEC theory and the E2D algorithm whose guarantees are adapted to SQ and LDP settings.","marker":"[Foster et al., 2023b]"},{"why":"Contributes the fractional covering number and interaction-aware lower bounds used for learnability and tighter regret bounds.","marker":"[Chen et al., 2024]"},{"why":"Frames sequential locally private channels and strong data-processing inequalities that back the LDP-DEC instantiation.","marker":"[Duchi et al., 2018]"},{"why":"Defines the SQ dimension that the paper shows is quantitatively equivalent to its SQ DEC.","marker":"[Feldman, 2017]"},{"why":"Gives the TV modulus-of-continuity characterization of local-minimax LDP complexity that the local DEC recovers.","marker":"[Duchi and Ruan, 2024]"},{"why":"Develops the exploration-by-optimization technique that underlies the ExO+ algorithm.","marker":"[Lattimore and Szepesvári, 2020]"}],"fun_headline_variants":["One complexity measure now controls learning under privacy and change","Unified framework ties privacy, robustness, and query learning to one DEC","Better regret bounds for private bandits via a unified decision metric","A single coefficient sets minimax rates for dynamic and private decision making","How one number predicts learning performance in changing, private environments"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bounds require the DEC to be of moderate decay (Definition 3) and, for regret, the value function to satisfy observability (Assumption 3); the paper does not prove either for every problem class, and the private rates also rely on the dimension-free strong data-processing inequality of Proposition 20.","fun_headline_variants_meta":{"raw":{"variants":["One complexity measure now controls learning under privacy and change","Unified framework ties privacy, robustness, and query learning to one DEC","Better regret bounds for private bandits via a unified decision metric","A single coefficient sets minimax rates for dynamic and private decision making","How one number predicts learning performance in changing, private environments"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000694,"raw_usage":{"total_tokens":3145,"prompt_tokens":954,"completion_tokens":2191,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2105}},"tokens_in":570,"tokens_out":2191,"duration_ms":15088,"temperature":1.0,"reasoning_tokens":2105,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:46:43.595888+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Give a finite LDP instance such as a two-armed bandit with known binary rewards, compute the private regret-DEC exactly as a function of $\\varepsilon$, and check whether it has moderate decay on $[1/(\\alpha\\sqrt{T}),1]$; if not, ExO+'s offset-to-DEC conversion can fail, so running LDP-ExO and finding regret outside the predicted $O(\\sqrt{d^3T\\log(T/\\delta)}/\\alpha)$ would settle that the claimed bound is not reached.","supporting_citations":[],"review_version":1}