PaperlayerView exact revision on arXiv

Source-linked AI summary

Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction

Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi

arXiv:1812.11476v4cs.DScs.DMcs.ITcs.LGmath.ITmath.STstat.TH

TL;DR

Distributed learning and testing must be performed from channel-constrained messages rather than players’ raw samples. The paper characterizes chi-square contraction to derive lower bounds, finding a tight public/private sample-complexity separation for testing in the studied settings.

  • Problem

    The paper asks how many players are needed to learn or test a discrete distribution when each player can reveal only a locally information-constrained message about one sample.

    Source: §I · p. 3

  • Method

    It bounds chi-square contraction for perturbed distribution families after channels transform samples, using chi-square and decoupled chi-square fluctuations.

    Source: §IV · p. 23

  • Results

    For identity testing, ℓ=1 communication yields tight sample complexities Θ(k) for public-coin and Θ(k^(3/2)) for private-coin protocols, while the paper reports tight public/private separations for LDP testing as well.

    Source: B. Summary of our techniques · p. 11

  • Takeaways & Limitations

    Shared randomness does not help distribution learning under communication or LDP constraints, but it reduces sample complexity for identity testing in the reported settings.

    Source: B. Summary of our techniques · p. 11

Abstract

from arXiv · show

Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels $\mathcal{W}$, which can be instantiated to capture both the communication- and privacy-constrained settings and beyond. The referee uses the messages from players to solve an inference problem for the unknown distribution that generated the samples. We derive lower bounds for sample complexity of learning and testing discrete distributions in this information-constrained setting. Underlying our bounds is a characterization of the contraction in chi-square distances between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both public- and private-coin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.

I. INTRODUCTION

The paper studies learning and testing discrete distributions when each player sends a referee only a channel-constrained message about one sample. It frames private- and public-coin protocols and develops lower bounds for these tasks under communication, privacy, and more general information constraints.

I. INTRODUCTION

  • Each of n players sends a channel-transformed sample to a referee, with the allowed channel family W abstracting local information constraints.Communication limits and local differential privacy are two instantiations of this framework.Source: §I · p. 3

A. Information-constrained inference framework

  • The framework targets distribution estimation and identity testing for discrete distributions, with sample complexity equal to the number of players when each holds one sample.The stated objective is to characterize sample complexity under W for both private- and public-coin protocols.Source: §I · p. 4, A. Information-constrained inference… · pp. 6, 8

I. INTRODUCTION

  • The lower-bound approach quantifies how information constraints contract chi-square distances between input distributions and their output-message distributions.The paper introduces chi-square and decoupled chi-square fluctuations to characterize this contraction locally.Source: §I · p. 5

A. Information-constrained inference framework

  • Private-coin protocols select channels independently, whereas public-coin protocols use shared randomness to select channels jointly.In the SMP setting, player messages are simultaneous and there is no communication between players.Source: §I · p. 5, A. Information-constrained inference… · p. 7

B. Summary of our techniques

The paper derives distributed inference lower bounds by measuring chi-square fluctuations after channel outputs contract distances between perturbed input distributions. Its private-coin maxmin and public-coin minmax analyses yield tight bounds in the considered communication and privacy settings, with testing exhibiting a public/private separation.

B. Summary of our techniques

  • The approach derives lower bounds by quantifying chi-square contraction from input distributions to channel-output distributions in a neighborhood of a nominal distribution.A carefully chosen perturbed family makes the inference task require distinguishing distributions in that neighborhood.Source: B. Summary of our techniques · pp. 8–9
  • Chi-square fluctuation measures average distance to the nominal distribution, while decoupled chi-square fluctuation measures distance from the average perturbed distribution.The decoupled quantity is the main new technical tool used to obtain lower bounds for distributed identity testing.Source: B. Summary of our techniques · p. 9
  • Private-coin lower bounds use a maxmin over channel choices and perturbation families, while public-coin lower bounds use a minmax; the maxmin can be significantly smaller for testing.For private coins, perturbations can be designed after channels are fixed; for public coins, a perturbation must work across channel choices.Source: B. Summary of our techniques · pp. 9–10
  • For distribution learning, both coin settings have lower bounds Ω(k^2/(ε^2 2^ℓ)) under communication limits and Ω(k^2/(ε^2ρ^2)) under LDP.The paper reports these bounds as tight and states that shared randomness does not help for distribution learning under either constraint.Source: B. Summary of our techniques · p. 11
  • For identity testing, ℓ=1 communication gives tight sample-complexity lower bounds Θ(k) for public-coin and Θ(k^(3/2)) for private-coin protocols.For LDP identity testing, the corresponding tight bounds are Ω(k/(ε^2ρ^2)) and Ω(k^(3/2)/(ε^2ρ^2)), respectively.Source: B. Summary of our techniques · p. 11

C. Prior and related work

Prior work covers distribution learning and testing, but the paper distinguishes its approach by extending lower bounds to identity testing under local information constraints and separating public- and private-coin performance. It develops this approach through perturbed families and chi-square fluctuations, first in the centralized setting.

C. Prior and related work

  • For discrete distributions, learning estimates p in total variation distance, while identity testing distinguishes a known reference q from p=q or alternatives ε-far from q.The paper focuses on sample complexity as a function of support size, including the large-support, small-sample regime.Source: C. Prior and related work · pp. 12–13
  • Earlier distributed-inference work often studied asymptotic error exponents or communication requirements, while this paper constrains information about individual samples.Related work also considered blackboard communication or multiple samples per player with restricted aggregation.Source: C. Prior and related work · pp. 12–13
  • The paper’s two distinguishing features are decoupled chi-square bounds that extend lower-bound methods to identity testing and a separation showing shared public randomness reduces sample complexity.The paper contrasts this with, which found no benefit from shared randomness for simple hypothesis testing.Source: C. Prior and related work · p. 13

D. Organization

  • The paper organizes its analysis by introducing notation, developing centralized lower bounds, extending them to information constraints, and specializing them to communication and privacy constraints.The framework is developed for discrete distributions, with pointers to matching schemes reported in a subsequent paper in the series.Source: D. Organization · p. 14, §II · p. 14

III. PERTURBED FAMILIES, CHI-SQUARE FLUCTUATIONS, AND CENTRALIZED LOWER BOUNDS

  • Section III recasts centralized learning and testing lower bounds using perturbed families around a nominal distribution and chi-square fluctuation measures.A perturbed family consists of distributions at least ε in total variation distance from the nominal distribution.Source: §III · pp. 15–16
  • Chi-square fluctuation measures the average distance from the nominal distribution, while decoupled chi-square fluctuation supports testing lower bounds based on a mixture of product distributions.The paper presents these quantities as a geometric view that extends to local information constraints.Source: §III · pp. 16–17

A. Chi-square fluctuation and the centralized learning lower bound

The section derives centralized distribution-learning lower bounds using perturbed families and chi-square fluctuation. Its general bound specializes to the familiar Ω(k/ε^2) sample lower bound.

A. Chi-square fluctuation and the centralized learning lower bound

  • For (k, ε)-distribution learning, any (n, ε)-estimator requires n = Ω(k/ε^2) samples.The result follows by applying the general lower bound to Paninski’s perturbed family.Source: A. Chi-square fluctuation and the… · pp. 18, 20
  • The proof relates estimation accuracy to identifying a perturbed-family hypothesis, then applies a modified Fano argument to avoid requiring well-separated hypotheses.The ordinary route uses a Hamming-space packing, but that construction would complicate later public-coin bounds.Source: A. Chi-square fluctuation and the… · pp. 18–19
  • A general learning lower bound follows when an ε-perturbed family satisfies the stated pairwise-distance condition, with its sample requirement controlled by the family’s size and chi-square fluctuation.The supplied passage states this bound in Lemma III.5 without exposing its formula.Source: A. Chi-square fluctuation and the… · p. 20

B. Decoupled chi-square fluctuation and the centralized testing lower bound

The section derives centralized testing lower bounds by comparing the uniform product distribution with a mixture of perturbed product distributions. Decoupled chi-square fluctuation captures the mixture’s closeness more effectively than ordinary chi-square fluctuation.

B. Decoupled chi-square fluctuation and the centralized testing lower bound

  • Testing is reduced to distinguishing u^n from a uniform mixture of n-fold product distributions drawn from an ε-perturbed family.The section uses the distance between the product distribution and this mixture to bound testing difficulty.Source: B. Decoupled chi-square fluctuation… · p. 20
  • Using decoupled chi-square fluctuation χ(2)(Pn), the authors obtain the desired improvement in the lower bound; ordinary chi-square fluctuation alone yields only a sample-complexity lower bound of Ω(1/ε²), described as much lower.Source: B. Decoupled chi-square fluctuation… · p. 21
  • The testing argument uses an Ingster-style bound on the chi-square distance between a mixture of product distributions and a product distribution.The cited proof relies on a product-distribution lemma.Source: B. Decoupled chi-square fluctuation… · p. 21
  • For the perturbed family, chi-square fluctuation is O(nε^2), whereas decoupled chi-square fluctuation is O(n^2ε^4/k).The section says the mixture’s total variation distance from u^n is much smaller than the average total variation distance.Source: B. Decoupled chi-square fluctuation… · p. 22

IV. RESULTS: THE CHI-SQUARE CONTRACTION BOUNDS WITH INFORMATION CONSTRAINTS

The section extends chi-square contraction and lower-bound tools to channels drawn from a family W. It distinguishes public-coin minmax bounds from private-coin maxmin bounds, with the latter yielding tighter testing lower bounds.

IV. RESULTS: THE CHI-SQUARE CONTRACTION BOUNDS WITH INFORMATION CONSTRAINTS

  • Information constraints contract chi-square fluctuations because channel-output distributions are closer than the corresponding input distributions, yielding lower bounds for learning and testing.The lower bounds combine this contraction with the relationship between inference difficulty and induced fluctuations.Source: §IV · p. 23
  • For public-coin protocols, the bottleneck is captured by a minmax chi-square fluctuation, and the analysis can restrict attention to a smaller channel family.The broader framework applies to arbitrary channel families W.Source: §IV · pp. 23, 26
  • For private-coin protocols, a perturbation can be chosen for each channel selection, giving a maxmin bound that is tighter than the public-coin minmax bound.This tighter bound leads to a public-/private-coin separation for communication- and privacy-constrained testing.Source: §IV · p. 23
  • The framework induces output-distribution families by applying channels to each member of an input perturbed family, then evaluates their chi-square fluctuations.The definitions allow the perturbation index to follow a general distribution rather than only the uniform distribution.Source: §IV · pp. 24–25
  • Approximate perturbations are required for the private-coin results and for establishing the public-/private-coin testing separation.The section introduces minmax and maxmin evaluations of decoupled chi-square fluctuation for the respective protocol settings.Source: §IV · pp. 25–26

A. General chi-square fluctuation bounds

The section derives learning and testing sample-complexity lower bounds from chi-square fluctuations under channel constraints. For testing, public- and private-coin protocols have bounds governed by different decoupled fluctuations and optimization orders.

A. General chi-square fluctuation bounds

  • The bounds relate channel chi-square fluctuations to average distances in a probability-simplex neighborhood and can extend beyond learning and testing.The section next evaluates them for Paninski perturbed families and variants.Source: A. General chi-square fluctuation bounds · p. 26
  • The learning bound replaces the centralized packing argument’s denominator with induced chi-square fluctuation and applies to public-coin protocols, hence also private-coin protocols.The numerator remains the logarithm of a total-variation packing.Source: A. General chi-square fluctuation bounds · p. 27
  • Public-coin testing has a lower bound in terms of minmax decoupled chi-square fluctuation.The bound applies to identity testing for a k-ary reference distribution.Source: A. General chi-square fluctuation bounds · p. 27
  • Private-coin testing has a lower bound in terms of maxmin decoupled chi-square fluctuation.The bound applies to identity testing for a k-ary reference distribution.Source: A. General chi-square fluctuation bounds · pp. 27–28

B. Chi-square contraction bounds for learning and testing discrete distributions

The paper converts chi-square fluctuation bounds into sample-complexity lower bounds by quantifying how channel families contract chi-square distances. Its learning and testing bounds distinguish public-coin and private-coin protocols, with testing especially sensitive to that distinction.

B. Chi-square contraction bounds for learning and testing discrete distributions

  • The framework uses channel-dependent matrices H(W) to translate perturbation fluctuations into concrete learning and testing lower bounds for arbitrary channel families.The paper evaluates these bounds for Paninski’s perturbed family and a related almost ε-perturbation.Source: B. Chi-square contraction bounds for… · p. 28
  • The chi-square fluctuation contracts by at least a factor of 4 max_W∈W ∥H(W)∥_* / k under the local information constraints.The contraction bound is stated for the ε-perturbed family and any channel W.Source: B. Chi-square contraction bounds for… · p. 28
  • Combining the learning fluctuation bound with chi-square contraction yields a sample-complexity lower bound for public-coin distribution learning.The learning bound also applies to private-coin protocols, as established in the preceding section.Source: B. Chi-square contraction bounds for… · p. 29
  • For public-coin testing, the minmax fluctuation bound yields a uniformity-testing lower bound, with the channel matrix’s Frobenius norm entering its analysis.The paper notes that the bound leads to tight lower bounds for communication-constrained testing.Source: B. Chi-square contraction bounds for… · pp. 29–31
  • Private-coin testing has worse chi-square contraction than public-coin testing, with the comparison expressed through nuclear-norm versus Frobenius-norm bounds.The paper relates the difference to the rank of H(W), which is O(k).Source: B. Chi-square contraction bounds for… · pp. 32, 36
  • For private-coin protocols, the maxmin bound chooses a perturbation after the channels are fixed, using the spectrum of the channel matrix to find a least-favorable direction.The construction selects directions associated with the smallest eigenvalues to avoid the directions in which the channel family is most informative.Source: B. Chi-square contraction bounds for… · pp. 33–34

V. EXAMPLES AND APPLICATIONS

The section instantiates the general bounds for communication-limited and locally differentially private inference by bounding norms of channel-associated matrices.

V. EXAMPLES AND APPLICATIONS

  • Bounds for the matrix Frobenius and trace norms yield lower bounds for learning and testing under communication and local privacy constraints.The section summarizes its results in Table I.Source: §V · p. 36
  • The paper reports that these lower bounds are tight for the communication-limited and LDP settings.It delegates matching upper bounds to subsequent papers in the series.Source: §V · p. 36
  • The section presents lower bounds only, leaving matching upper bounds to subsequent papers in the series.Source: §V · p. 36

A. Communication-constrained inference

For communication-limited inference, the paper derives learning and testing lower bounds by bounding norms of channel matrices. The resulting bounds are reported as tight and show different communication penalties across public- and private-coin testing.

A. Communication-constrained inference

B. Local differential privacy constraints

The section treats local differential privacy through a family of ρ-LDP channels and derives lower bounds for learning and testing. It reports a public- versus private-coin separation for testing under LDP.

B. Local differential privacy constraints

  • For ρ ∈ (0, 1], the allowed channels Wρ are ρ-LDP channels, and the section derives lower bounds for learning and testing under these constraints.The cited theorem passages identify public-coin learning and public- and private-coin testing results, but do not provide their bound expressions.Source: B. Local differential privacy… · pp. 38–39
  • The family Wρ is convex, so the analysis can restrict to bounds on the trace and Frobenius norms of H(W) for W ∈ Wρ.The section states this restriction after establishing convexity.Source: B. Local differential privacy… · p. 38
  • Shared randomness strictly reduces sample complexity for testing under LDP, and the public- and private-coin testing protocols match the corresponding lower bounds.Public-coin learning protocols also match the lower bounds.Source: B. Local differential privacy… · p. 40

VI. FUTURE DIRECTIONS AND UPCOMING RESULTS

The section distinguishes upcoming matching protocols from this paper’s focus on lower bounds. It also identifies high-dimensional and continuous settings as future applications of the framework.

VI. FUTURE DIRECTIONS AND UPCOMING RESULTS

  • This paper focuses on lower bounds; matching distributed inference schemes are reserved for two upcoming papers in the series.The authors say the papers are separated to present their related ideas distinctly.Source: §VI · p. 40
  • The second paper presents communication-constrained protocols matching this paper’s lower bounds, using simulate-and-infer for learning and private-coin testing and random input partitions for public-coin testing.The public-coin scheme’s efficacy is described as closely tied to the geometric view developed here.Source: §VI · p. 40
  • The third paper presents LDP testing schemes: existing mechanisms for private-coin tests and a new public-coin protocol that achieves the lower bounds.The authors state that existing LDP mechanisms, all private-coin, cannot attain the public-coin lower bound.Source: §VI · p. 40
  • The framework extends to high-dimensional and continuous settings, including Gaussian mean testing and testing product distributions under information constraints, which the authors defer to future work.Source: §VI · p. 40

APPENDIX A

Appendix A gives proof strategies for a matrix claim and chi-square fluctuation bounds. The arguments use concentration tools and reductions to testing error and total variation.

PROOF OF CLAIM IV.17

  • Claim IV.17 considers independent uniform sign vectors and a positive semidefinite matrix; the appendix defines the Frobenius norm and spectral radius used in its statement.Source: PROOF OF CLAIM IV.17 · p. 41
  • The proof of Claim IV.17 follows a moment-generating-function approach to tail bounds for a homogeneous order-2 Rademacher chaos.It uses sub-Gaussianity and a decoupling inequality; the claim’s displayed bound is not stated in the supplied passage.Source: PROOF OF CLAIM IV.17 · p. 41

APPENDIX B PROOFS OF CHI-SQUARE FLUCTUATION BOUNDS

  • The chi-square fluctuation proof uses Le Cam’s two-point method and connects testing error to the total variation distance between the mixture and reference distributions.Source: Appendix B · p. 42
  • The fluctuation argument also simplifies an expectation using an independent copy of θ and independence among the ∆θ_j terms.Source: Appendix B · p. 43

APPENDIX C PROOFS OF INDUCED CHI-SQUARE FLUCTUATION BOUNDS

The appendix handles public- and private-coin protocols differently when deriving induced chi-square bounds. Public-coin arguments fix shared randomness, while private-coin arguments use convex combinations of allowed channels.

APPENDIX C PROOFS OF INDUCED CHI-SQUARE FLUCTUATION BOUNDS

  • For public-coin protocols, the proof represents the protocol with shared randomness U and fixes a realization u, which may depend on the perturbation family.Source: Appendix C · pp. 43–44
  • The public-coin testing argument considers alternatives in an almost ε-perturbation with probability at least 1/10 and uses the test’s success probabilities to derive its bound.Source: Appendix C · p. 44
  • For private-coin protocols, each player’s effective channel is a convex combination of channels from W and therefore remains in W.This lets the proof consider arbitrary almost ε-perturbations while retaining an allowed channel.Source: Appendix C · p. 44
Loading 1812.11476v4…