Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2501.14928 v1 pith:5LZTV6OG submitted 2025-01-24 cs.LG cs.AIcs.ITmath.ITmath.STstat.MLstat.TH

Fan Chen , Alexander Rakhlin This is my paper · ORCID
classification cs.LGcs.AIcs.ITmath.ITmath.STstat.MLstat.TH MSC 68Q3262C2068P27
keywords hybridDecision-EstimationCoefficientlocaldifferentialprivacystatisticalqueriesrobustdecisionmakingcontextualbanditsminimaxregretlearnabilitystrongdata-processinginequality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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?

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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ε.

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 (3)
  1. [Definition 3 / Lemma F.7 / Theorems 1 and 8] 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.
  2. [Theorem 10 / Assumption 3 (Eq. 18)] 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'.
  3. [Proposition 20 / Lemma E.6] 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.
minor comments (4)
  1. [Appendix F.4.2] 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.
  2. [Section 5.3, Example 7] 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,θ−θ⋆⟩².
  3. [Theorems 1–6] 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.
  4. [Eq. (17)] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the hybrid-DEC bounds and new instantiations (LDP regression, linear contextual bandits) are derived in the appendix via explicit calculations; self-citations to co-authored DEC literature exist but are not load-bearing; the moderate-decay caveat is a correctness limitation, not a circular step.

full rationale

The paper's central claim (Theorem 1: p-decH_epsilon(T)(P) approx <= minimax risk approx <= p-decH_epsilon-bar(T)(P)) is not circular. The hybrid DEC (Eq. 2) is defined independently of any algorithm, and both inequalities are proven in the appendix: the lower bound via a quantile-DEC reduction to stationary environments (Proposition E.1, Appendix E.1) and the upper bound via the ExO+ algorithm with an offset-DEC-to-DEC conversion (Theorems F.4-F.5 and Lemma F.7, Appendix F). No step assumes the target bound as an input; the DEC is a computable quantity and the algorithm is constructed to achieve it. The new instantiations are derived, not fitted: (i) the SQ-DEC/SQ-dimension equivalence is proven in both directions (Proposition 17, Appendix H.3) and is benchmarked against the external SQ-dimension characterization of Feldman [2017]; (ii) the LDP results rest on a strong data-processing inequality (Proposition 20) proven in Appendix I.1 and are compared against the external bounds of Duchi-Ruan [2024], Zheng et al. [2020], Han et al. [2021], and Li et al. [2024]; (iii) the linear contextual bandit bound r-decLDP(MLin-CB) <= O(d*epsilon) (Theorem 30, proved in Appendix I.6) is an explicit calculation, not a parameter fit; and (iv) the fractional covering number characterization is re-proven for LDP (Theorem 34, Appendix J.2) rather than merely imported from the authors' own Chen et al. [2024]. The paper does cite its co-authored prior work heavily (Foster et al. 2021/2023b; Chen et al. 2024), and it credits the information-set idea to co-authors' discussions, but those cited results are prior peer-reviewed theorems with stated assumptions that do not include the present claims, and the extensions are proven in-appendix rather than asserted by citation. The substantive caveat is the moderate-decay condition (Definition 3) required for Lemma F.7 and hence Theorem 8: a DEC growing as epsilon^2 (e.g., squared-error interactive estimation, which satisfies the metric-like inequality (50)) violates moderate decay, and Lemma F.7 degrades the offset-DEC conversion to O(epsilon) rather than O(epsilon^2), so Theorem 1's 'mild growth assumption' is less mild than claimed for such classes. This is a correctness/generality limitation, not circularity, and the paper honestly discloses other gaps (the exponential gap in Eq. (41) for fractional covering number and the openness of efficient algorithms).

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The framework rests on four explicit assumptions (realizability, compactness, moderate decay, observability) and the introduced mathematical constructs; no free parameters are fitted to data. The strong data-processing inequality and DEC reductions are proven in the appendices rather than assumed.

assumptions (4)
  • domain assumption Assumption 1 (Constraint realizability): the learner's constraint class P contains the true P⋆.
    Section 2.1, Assumption 1. Standard realizability; if violated, the minimax bounds do not apply.
  • standard math Assumption 2 (Compactness): the model class has finite ε-covering for every ε > 0.
    Section 3, Assumption 2. Needed to apply Ky Fan's minimax theorem (Thm D.2) in the ExO+ analysis.
  • ad hoc to paper Definition 3 (Moderate decay): the DEC d(ε) satisfies c d(ε)/ε ≥ d(ε')/ε' for all ε' ≥ ε.
    Section 3, Def 3. This regularity condition is assumed for the upper bounds (Thm 8, 10, 21, 28); it is not proven for all problem classes, though it holds for power-law DECs.
  • domain assumption Assumption 3 (Observability): value function is linear over MP and Lipschitz w.r.t. Hellinger distance of observations (Eq. 18).
    Section 3.2, Assumption 3. Used for regret lower and upper bounds; shown to hold for reward-based (CV=√2) and LDP (CV=O(1/α)), but must be verified for each new application.
invented entities (2)
  • Hybrid DMSO framework (structured observation constraints and adversary constraints)
    purpose: To interpolate between stochastic and adversarial decision making and to unify SQ, LDP, robust, and smooth settings.
    Mathematical modeling construct; its validity is judged by the theorems it yields, not by external measurement.
  • Information set structure (Type 1 and Type 2)
    purpose: Enables ExO+ to exploit decision-space structure and achieve bounds scaling with fractional covering numbers instead of log|Π|.
    Technical device introduced in Appendix F.1; it sharpens bounds but is not independently falsifiable.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy." pith.science (2026). https://pith.science/paper/5LZTV6OG

@misc{pith2026250114928,
  author       = {Pith},
  title        = {Pith review of: Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5LZTV6OG}},
  note         = {Machine review of arXiv:2501.14928}
}
read the original abstract

We study the problem of interactive decision making in which the underlying environment changes over time subject to given constraints. We propose a framework, which we call \textit{hybrid Decision Making with Structured Observations} (hybrid DMSO), that provides an interpolation between the stochastic and adversarial settings of decision making. Within this framework, we can analyze local differentially private (LDP) decision making, query-based learning (in particular, SQ learning), and robust and smooth decision making under the same umbrella, deriving upper and lower bounds based on variants of the Decision-Estimation Coefficient (DEC). We further establish strong connections between the DEC's behavior, the SQ dimension, local minimax complexity, learnability, and joint differential privacy. To showcase the framework's power, we provide new results for contextual bandits under the LDP constraint.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Decision Making in Hybrid Environments: A Model Aggregation Approach

    cs.LG 2025-02 conditional novelty 7.0 of 10

    An aggregation-based extension of the DEC complexity measure yields new regret bounds for hybrid stochastic-adversarial RL and the first square-root-T regret for linear Q-star/V-star MDPs.

Reference graph

Works this paper leans on

83 extracted references · 66 canonical work pages · cited by 1 Pith paper

  1. [1]

    N. Alon, M. Bun, R. Livni, M. Malliaris, and S. Moran. Private and online learnability are equivalent. ACM Journal of the ACM (JACM), 69 0 (4): 0 1--34, 2022

    2022

  2. [2]

    H. Asi, V. Feldman, and K. Talwar. Optimal algorithms for mean estimation under local differential privacy. In International Conference on Machine Learning, pages 1046--1056. PMLR, 2022

    2022

  3. [3]

    H. Asi, J. Ullman, and L. Zakynthinou. From robustness to privacy and back. In International Conference on Machine Learning, pages 1121--1146. PMLR, 2023

    2023

  4. [4]

    H. Asi, V. Feldman, J. Nelson, H. Nguyen, and K. Talwar. Fast optimal locally private mean estimation via random projections. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  5. [5]

    Beimel, K

    A. Beimel, K. Nissim, and U. Stemmer. Characterizing the sample complexity of private learners. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 97--110, 2013 a

    work page 2013

  6. [6]

    Beimel, K

    A. Beimel, K. Nissim, and U. Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 363--378. Springer, 2013 b

    work page 2013

  7. [7]

    Ben-David, D

    S. Ben-David, D. Pal, and S. Shalev-Shwartz. Agnostic online learning. In Proceedings of the 22th Annual Conference on Learning Theory, 2009

    work page 2009

  8. [8]

    Berrett and C

    T. Berrett and C. Butucea. Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms. Advances in Neural Information Processing Systems, 33: 0 3164--3173, 2020

    work page 2020

Show all 83 references
  1. [9]

    T. B. Berrett, L. Gy \"o rfi, and H. Walk. Strongly universally consistent nonparametric regression and classification with privatised data. 2021

    2021

  2. [10]

    A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 253--262, 1994

    1994

  3. [11]

    Brennan, G

    M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T. Schramm. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.06107, 2020

    2009 arXiv

  4. [12]

    N. H. Bshouty and V. Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research, 2 0 (Feb): 0 359--395, 2002

    2002

  5. [13]

    Bubeck, J

    S. Bubeck, J. Ding, R. Eldan, and M. Z. R \'a cz. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, 49 0 (3): 0 503--532, 2016

    2016

  6. [14]

    M. Bun, R. Livni, and S. Moran. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 389--402. IEEE, 2020

    2020

  7. [15]

    Butucea and Y

    C. Butucea and Y. Issartel. Locally differentially private estimation of functionals of discrete distributions. Advances in Neural Information Processing Systems, 34: 0 24753--24764, 2021

    2021

  8. [16]

    Butucea, A

    C. Butucea, A. Rohde, and L. Steinberger. Interactive versus noninteractive locally differentially private estimation: Two elbows for the quadratic functional. The Annals of Statistics, 51 0 (2): 0 464--486, 2023

    2023

  9. [17]

    Canonne, S

    C. Canonne, S. B. Hopkins, J. Li, A. Liu, and S. Narayanan. The full landscape of robust mean testing: Sharp separations between oblivious and adaptive contamination. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2159--2168. IEEE, 2023

    2023

  10. [18]

    Casella and R

    G. Casella and R. Berger. Statistical Inference. Duxbury advanced series in statistics and decision sciences. Thomson Learning, 2002

    2002

  11. [19]

    F. Chen, S. Mei, and Y. Bai. Unified algorithms for rl with decision-estimation coefficients: pac, reward-free, preference-based learning, and beyond. arXiv preprint arXiv:2209.11745, 2022

    2022 arXiv

  12. [20]

    F. Chen, D. J. Foster, Y. Han, J. Qian, A. Rakhlin, and Y. Xu. Assouad, fano, and le cam with interaction: A unifying lower bound framework and characterization for bandit learnability. arXiv preprint arXiv:2410.05117, 2024

    2024 arXiv

  13. [21]

    Diakonikolas and D

    I. Diakonikolas and D. M. Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911, 2019

    1911 arXiv

  14. [22]

    Diakonikolas and D

    I. Diakonikolas and D. M. Kane. Algorithmic high-dimensional robust statistics. Cambridge university press, 2023

    2023

  15. [23]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73--84. IEEE, 2017

    2017

  16. [24]

    Diakonikolas, G

    I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48 0 (2): 0 742--864, 2019

    2019

  17. [25]

    D. L. Donoho and R. C. Liu. Geometrizing rates of convergence, II . The Annals of Statistics, pages 633--667, 1991

    1991

  18. [26]

    Duchi and R

    J. Duchi and R. Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory, pages 1161--1191. PMLR, 2019

    2019

  19. [27]

    J. C. Duchi. Lecture notes on statistics and information theory. 2023

    2023

  20. [28]

    J. C. Duchi and F. Ruan. The right complexity measure in locally private estimation: It is not the fisher information. The Annals of Statistics, 52 0 (1): 0 1--51, 2024

    2024

  21. [29]

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th annual symposium on foundations of computer science, pages 429--438. IEEE, 2013

    2013

  22. [30]

    J. C. Duchi, J. Lafferty, Y. Zhu, et al. Local minimax complexity of stochastic convex optimization. Advances in Neural Information Processing Systems, 29, 2016

    2016

  23. [31]

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113 0 (521): 0 182--201, 2018

    2018

  24. [32]

    Dwork, F

    C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265--284. Springer, 2006

    2006

  25. [33]

    K. Fan. Minimax theorems. Proceedings of the National Academy of Sciences, 39 0 (1): 0 42--47, 1953

    1953

  26. [34]

    V. Feldman. A general characterization of the statistical query complexity. In Conference on learning theory, pages 785--830. PMLR, 2017

    2017

  27. [35]

    Feldman and D

    V. Feldman and D. Xiao. Sample complexity bounds on differentially private learning via communication complexity. In Conference on Learning Theory, pages 1000--1019. PMLR, 2014

    2014

  28. [36]

    Feldman, W

    V. Feldman, W. Perkins, and S. Vempala. On the complexity of random satisfiability problems with planted solutions. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 77--86, 2015

    2015

  29. [37]

    Feldman, E

    V. Feldman, E. Grigorescu, L. Reyzin, S. S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64 0 (2): 0 1--37, 2017

    2017

  30. [38]

    Foster, D

    D. Foster, D. J. Foster, N. Golowich, and A. Rakhlin. On the complexity of multi-agent decision making: From learning in games to partial monitoring. In The Thirty Sixth Annual Conference on Learning Theory, pages 2678--2792. PMLR, 2023 a

    2023

  31. [39]

    D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021

    2021 arXiv

  32. [40]

    D. J. Foster, N. Golowich, J. Qian, A. Rakhlin, and A. Sekhari. A note on model-free reinforcement learning with the decision-estimation coefficient. arXiv preprint arXiv:2211.14250, 2022 a

    2022 arXiv

  33. [41]

    D. J. Foster, A. Rakhlin, A. Sekhari, and K. Sridharan. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 35: 0 35404--35417, 2022 b

    2022

  34. [42]

    D. J. Foster, N. Golowich, and Y. Han. Tight guarantees for interactive decision making with the decision-estimation coefficient. In The Thirty Sixth Annual Conference on Learning Theory, pages 3969--4043. PMLR, 2023 b

    2023

  35. [43]

    D. J. Foster, Y. Han, J. Qian, and A. Rakhlin. Online estimation via offline estimation: An information-theoretic framework. arXiv preprint arXiv:2404.10122, 2024

    2024 arXiv

  36. [44]

    Garcelon, V

    E. Garcelon, V. Perchet, C. Pike-Burke, and M. Pirotta. Local differential privacy for regret minimization in reinforcement learning. Advances in Neural Information Processing Systems, 34: 0 10561--10573, 2021

    2021

  37. [45]

    Georgiev and S

    K. Georgiev and S. Hopkins. Privacy induces robustness: Information-computation gaps and sparse mean estimation. Advances in neural information processing systems, 35: 0 6829--6842, 2022

    2022

  38. [46]

    Glasgow and A

    M. Glasgow and A. Rakhlin. Tight bounds for -regret via the decision-estimation coefficient. arXiv preprint arXiv:2303.03327, 2023

    2023 arXiv

  39. [47]

    Golowich

    N. Golowich. Differentially private nonparametric regression under a growth condition. In Conference on Learning Theory, pages 2149--2192. PMLR, 2021

    2021

  40. [48]

    S. Gopi, G. Kamath, J. Kulkarni, A. Nikolov, Z. S. Wu, and H. Zhang. Locally private hypothesis selection. In Conference on Learning Theory, pages 1785--1816. PMLR, 2020

    2020

  41. [49]

    Y. Han, Z. Liang, Y. Wang, and J. Zhang. Generalized linear bandits with local differential privacy. Advances in Neural Information Processing Systems, 34: 0 26511--26522, 2021

    2021

  42. [50]

    Hanneke, R

    S. Hanneke, R. Livni, and S. Moran. Online learning with simple predictors and a combinatorial characterization of minimax in 0/1 games. In Conference on Learning Theory, pages 2289--2314. PMLR, 2021

    2021

  43. [51]

    Hazan, T

    E. Hazan, T. Koren, R. Livni, and Y. Mansour. Online learning with low rank experts. In 29th Annual Conference on Learning Theory, pages 1096--1114, 2016

    2016

  44. [52]

    J. He, J. Zhang, and R. Q. Zhang. A reduction from linear contextual bandits lower bounds to estimations lower bounds. In International Conference on Machine Learning, pages 8660--8677. PMLR, 2022

    2022

  45. [53]

    S. B. Hopkins, G. Kamath, M. Majid, and S. Narayanan. Robustness implies privacy in statistical estimation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 497--506, 2023

    2023

  46. [54]

    P. J. Huber. A robust version of the probability ratio test. The Annals of Mathematical Statistics, pages 1753--1758, 1965

    1965

  47. [55]

    P. J. Huber. Robust estimation of a location parameter. In Breakthroughs in statistics: Methodology and distribution, pages 492--518. Springer, 1992

    1992

  48. [56]

    P. J. Huber and E. M. Ronchetti. Robust statistics. John Wiley & Sons, 2011

    2011

  49. [57]

    T. Jayram. Hellinger strikes back: A note on the multi-party information complexity of and. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 562--573. Springer, 2009

    2009

  50. [58]

    Joshi, T

    N. Joshi, T. Misiakiewicz, and N. Srebro. On the complexity of learning sparse functions with statistical and gradient queries. arXiv preprint arXiv:2407.05622, 2024

    2024 arXiv

  51. [59]

    A. B. Juditsky and A. S. Nemirovski. Nonparametric estimation by convex programming . The Annals of Statistics, 37 0 (5A): 0 2278 -- 2300, 2009. doi:10.1214/08-AOS654. URL https://doi.org/10.1214/08-AOS654

    2009 doi

  52. [60]

    S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SIAM Journal on Computing, 40 0 (3): 0 793--826, 2011

    2011

  53. [61]

    M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45 0 (6): 0 983--1006, 1998

    1998

  54. [62]

    Lattimore

    T. Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathematical Statistics and Learning, 2 0 (3): 0 311--334, 2020

    2020

  55. [63]

    Lattimore and A

    T. Lattimore and A. Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pages 2965--2992. PMLR, 2021

    2021

  56. [64]

    Lattimore and C

    T. Lattimore and C. Szepesv \'a ri. Exploration by optimisation in partial monitoring. In Conference on Learning Theory, pages 2488--2515. PMLR, 2020

    2020

  57. [65]

    G. Li, P. Kamath, D. J. Foster, and N. Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35: 0 23737--23750, 2022

    2022

  58. [66]

    J. Li, D. Simchi-Levi, and Y. Wang. On the optimal regret of locally private linear contextual bandit. arXiv preprint arXiv:2404.09413, 2024

    2024 arXiv

  59. [67]

    M. Li, T. B. Berrett, and Y. Yu. On robustness and local differential privacy. The Annals of Statistics, 51 0 (2): 0 717--737, 2023

    2023

  60. [68]

    C. Liao, J. He, and Q. Gu. Locally differentially private reinforcement learning for linear mixture markov decision processes. In Asian Conference on Machine Learning, pages 627--642. PMLR, 2023

    2023

  61. [69]

    Littlestone

    N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2 0 (4): 0 285--318, 1988

    1988

  62. [70]

    Liu and A

    A. Liu and A. Moitra. Settling the robust learnability of mixtures of gaussians. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 518--531, 2021

    2021

  63. [71]

    M. J. Osborne and A. Rubinstein. A course in game theory. MIT press, 1994

    1994

  64. [72]

    Polyanskiy and Y

    Y. Polyanskiy and Y. Wu. Dualizing le cam's method for functional estimation, with applications to estimating the unseens. arXiv preprint arXiv:1902.05616, 2019

    1902 arXiv

  65. [73]

    A. F. Pour, H. Ashtiani, and S. Asoodeh. Sample-optimal locally private hypothesis selection and the provable benefits of interactivity. In The Thirty Seventh Annual Conference on Learning Theory, pages 4240--4275. PMLR, 2024

    2024

  66. [74]

    Rakhlin and K

    A. Rakhlin and K. Sridharan. Online nonparametric regression. In Conference on Learning Theory, 2014

    2014

  67. [75]

    Rakhlin, K

    A. Rakhlin, K. Sridharan, and A. Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011

    2011

  68. [76]

    Rohde and L

    A. Rohde and L. Steinberger. Geometrizing rates of convergence under local differential privacy constraints. The Annals of Statistics, 48 0 (5): 0 2646--2670, 2020

    2020

  69. [77]

    Russo and B

    D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39 0 (4): 0 1221--1243, 2014

    2014

  70. [78]

    Russo and B

    D. Russo and B. Van Roy. Learning to optimize via information-directed sampling. Operations Research, 66 0 (1): 0 230--252, 2018

    2018

  71. [79]

    Shariff and O

    R. Shariff and O. Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018

    2018

  72. [80]

    Vietri, B

    G. Vietri, B. Balle, A. Krishnamurthy, and S. Wu. Private reinforcement learning with pac and regret guarantees. In International Conference on Machine Learning, pages 9754--9764. PMLR, 2020

    2020

  73. [81]

    Wang and J

    D. Wang and J. Xu. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, pages 6628--6637. PMLR, 2019

    2019

  74. [82]

    S. L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60 0 (309): 0 63--69, 1965

    1965

  75. [83]

    Zheng, T

    K. Zheng, T. Cai, W. Huang, Z. Li, and L. Wang. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33: 0 12300--12310, 2020

    2020

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.