The Role of Interactivity in Structured Estimation

• URL: http://arxiv.org/abs/2203.06870v1
• Date: Mon, 14 Mar 2022 05:54:42 GMT
• Title: The Role of Interactivity in Structured Estimation
• Authors: Jayadev Acharya and Cl\'ement L. Canonne and Ziteng Sun and Himanshu Tyagi
• Abstract summary: We study high-dimensional estimation under three natural constraints. Without sparsity assumptions, interactivity cannot improve the minimax rates of estimation. We establish that the gap increases when we have more structured sparsity.
• Score: 44.068012503785475
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study high-dimensional sparse estimation under three natural constraints: communication constraints, local privacy constraints, and linear measurements (compressive sensing). Without sparsity assumptions, it has been established that interactivity cannot improve the minimax rates of estimation under these information constraints. The question of whether interactivity helps with natural inference tasks has been a topic of active research. We settle this question in the affirmative for the prototypical problems of high-dimensional sparse mean estimation and compressive sensing, by demonstrating a gap between interactive and noninteractive protocols. We further establish that the gap increases when we have more structured sparsity: for block sparsity this gap can be as large as polynomial in the dimensionality. Thus, the more structured the sparsity is, the greater is the advantage of interaction. Proving the lower bounds requires a careful breaking of a sum of correlated random variables into independent components using Baranyai's theorem on decomposition of hypergraphs, which might be of independent interest.

Related papers

• Nonparametric Partial Disentanglement via Mechanism Sparsity: Sparse Actions, Interventions and Sparse Temporal Dependencies [58.179981892921056]
  This work introduces a novel principle for disentanglement we call mechanism sparsity regularization. We propose a representation learning method that induces disentanglement by simultaneously learning the latent factors. We show that the latent factors can be recovered by regularizing the learned causal graph to be sparse.
  arXiv  Detail & Related papers  (2024-01-10T02:38:21Z)
• Approximate Causal Effect Identification under Weak Confounding [13.552959043816482]
  We propose an efficient linear program to derive the upper and lower bounds of the causal effect. We show that our bounds are consistent in the sense that as the entropy of unobserved confounders goes to zero, the gap between the upper and lower bound vanishes.
  arXiv  Detail & Related papers  (2023-06-22T23:35:49Z)
• Nonparametric Embeddings of Sparse High-Order Interaction Events [21.758306786651772]
  High-order interaction events are common in real-world applications. We propose Non Embeddings of Sparse High-order interaction events. We develop an efficient, scalable model inference algorithm.
  arXiv  Detail & Related papers  (2022-07-08T01:25:34Z)
• Weakly Supervised Representation Learning with Sparse Perturbations [82.39171485023276]
  We show that if one has weak supervision from observations generated by sparse perturbations of the latent variables, identification is achievable under unknown continuous latent distributions. We propose a natural estimation procedure based on this theory and illustrate it on low-dimensional synthetic and image-based experiments.
  arXiv  Detail & Related papers  (2022-06-02T15:30:07Z)
• Disentanglement and Generalization Under Correlation Shifts [22.499106910581958]
  Correlations between factors of variation are prevalent in real-world data. Machine learning algorithms may benefit from exploiting such correlations, as they can increase predictive performance on noisy data. We aim to learn representations which capture different factors of variation in latent subspaces.
  arXiv  Detail & Related papers  (2021-12-29T18:55:17Z)
• Pair-correlation ansatz for the ground state of interacting bosons in an arbitrary one-dimensional potential [0.0]
  We derive and describe a very accurate variational scheme for the ground state of the system of a few ultra-cold bosons confined in one-dimensional traps of arbitrary shapes. By construction, the proposed ansatz is exact in the noninteracting limit, exactly encodes boundary conditions forced by contact interactions, and gives full control on accuracy in the limit of infinite repulsions.
  arXiv  Detail & Related papers  (2021-04-16T08:10:43Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)
• Interactive Inference under Information Constraints [45.72264074254599]
  We study the role of interactivity in distributed statistical inference under information constraints. We focus on the tasks of goodness-of-fit testing and estimation of discrete distributions.
  arXiv  Detail & Related papers  (2020-07-21T17:51:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.