論文の概要: The Role of Interactivity in Structured Estimation
- arxiv url: http://arxiv.org/abs/2203.06870v1
- Date: Mon, 14 Mar 2022 05:54:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-15 17:40:24.955137
- Title: The Role of Interactivity in Structured Estimation
- Title(参考訳): 構造的推定における相互作用の役割
- Authors: Jayadev Acharya and Cl\'ement L. Canonne and Ziteng Sun and Himanshu
Tyagi
- Abstract要約: 3つの自然制約下での高次元推定について検討する。
空間性仮定がなければ、相互作用性は推定の最小値率を改善することはできない。
より構造化された空間を持つと、ギャップは増大する。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): 本研究では,通信制約,局所プライバシー制約,線形計測(圧縮センシング)という3つの自然な制約下での高次元スパース推定について検討する。
空間性仮定がなければ、これらの情報制約の下での最小推定率を改善することはできないことが確立されている。
相互作用性が自然推論タスクに役立つかどうかという問題は、活発な研究のトピックである。
我々は,対話型プロトコルと非対話型プロトコルのギャップを示すことにより,高次元スパース平均推定と圧縮センシングの原型的問題に対する肯定論において,この問題を解決した。
さらに、より構造化された空間性を持つ場合、このギャップは増大し、ブロック空間性については、このギャップは次元の多項式に匹敵する大きさである。
したがって、疎度がより構造化されるほど、相互作用の利点が大きくなる。
下界の証明には、相関確率変数の和を独立成分に慎重に割る必要があるが、これは独立な関心を持つかもしれないハイパーグラフの分解に関するバラニーの定理を用いている。
関連論文リスト
- Nonparametric Partial Disentanglement via Mechanism Sparsity: Sparse
Actions, Interventions and Sparse Temporal Dependencies [58.179981892921056]
この研究は、メカニズムのスパーシティ正則化(英語版)と呼ばれる、アンタングルメントの新たな原理を導入する。
本稿では,潜在要因を同時に学習することで,絡み合いを誘発する表現学習手法を提案する。
学習した因果グラフをスパースに規則化することにより、潜伏因子を復元できることを示す。
論文 参考訳(メタデータ) (2024-01-10T02:38:21Z) - Approximate Causal Effect Identification under Weak Confounding [13.552959043816482]
因果効果の上下境界を導出する効率的な線形プログラムを提案する。
我々の境界は、観測されていない共同設立者のエントロピーがゼロになるにつれて、上界と下界の間のギャップが消えるという意味で一貫していることが示される。
論文 参考訳(メタデータ) (2023-06-22T23:35:49Z) - Nonparametric Embeddings of Sparse High-Order Interaction Events [21.758306786651772]
高次相互作用イベントは現実世界のアプリケーションでは一般的である。
スパース高次相互作用イベントの非埋め込みを提案する。
我々は効率的でスケーラブルなモデル推論アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-07-08T01:25:34Z) - Weakly Supervised Representation Learning with Sparse Perturbations [82.39171485023276]
潜伏変数のスパース摂動によって生じる観測の監督が弱い場合、未知の連続潜伏分布の下で識別が達成可能であることを示す。
本稿では,この理論に基づく自然な推定手法を提案し,それを低次元の合成および画像に基づく実験で説明する。
論文 参考訳(メタデータ) (2022-06-02T15:30:07Z) - Disentanglement and Generalization Under Correlation Shifts [22.499106910581958]
実世界のデータでは、変動要因間の相関が一般的である。
機械学習アルゴリズムは、ノイズの多いデータに対する予測性能を高めることができるため、そのような相関を利用する利点がある。
潜在部分空間の様々な要因を捉える表現を学習することを目的としている。
論文 参考訳(メタデータ) (2021-12-29T18:55:17Z) - Pair-correlation ansatz for the ground state of interacting bosons in an
arbitrary one-dimensional potential [0.0]
任意の形状の1次元トラップに閉じ込められたいくつかの超低温ボソン系の基底状態の非常に正確な変分スキームを導出し、記述する。
構築により、提案されたアンザッツは、非相互作用極限において正確なものであり、接触相互作用によって強制される境界条件を正確に符号化し、無限反発の極限における精度を完全に制御する。
論文 参考訳(メタデータ) (2021-04-16T08:10:43Z) - Disentangling Observed Causal Effects from Latent Confounders using
Method of Moments [67.27068846108047]
我々は、軽度の仮定の下で、識別性と学習可能性に関する保証を提供する。
我々は,線形制約付き結合テンソル分解に基づく効率的なアルゴリズムを開発し,スケーラブルで保証可能な解を得る。
論文 参考訳(メタデータ) (2021-01-17T07:48:45Z) - Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
多くの機械学習アプリケーションは、2つの競合する目標を達成する表現を学習する。
ミニマックスゲーム理論の定式化は、精度と不変性の基本的なトレードオフを表す。
分類と回帰の双方において,この一般的かつ重要な問題を情報論的に解析する。
論文 参考訳(メタデータ) (2020-12-19T15:24:04Z) - Interactive Inference under Information Constraints [45.72264074254599]
情報制約下での分散統計的推論における相互作用性の役割について検討する。
適合度テストの課題と離散分布の推定に焦点をあてる。
論文 参考訳(メタデータ) (2020-07-21T17:51:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。