論文の概要: Efficient Parameter Estimation of Truncated Boolean Product
Distributions
- arxiv url: http://arxiv.org/abs/2007.02392v2
- Date: Sun, 24 Apr 2022 08:44:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-13 08:13:04.909340
- Title: Efficient Parameter Estimation of Truncated Boolean Product
Distributions
- Title（参考訳）: 断続ブール積分布の効率的なパラメータ推定
- Authors: Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
- Abstract要約: 切り離されたサンプルからの学習の計算的および統計的複雑さが離散的な設定で検討されたのはこれが初めてである。
トラニケート集合が十分に太った場合, トラニケートされた試料から真の分布から試料を生成できることが示される。
- 参考スコア（独自算出の注目度）: 26.396901523831534
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of estimating the parameters of a Boolean product
distribution in $d$ dimensions, when the samples are truncated by a set $S
\subset \{0, 1\}^d$ accessible through a membership oracle. This is the first
time that the computational and statistical complexity of learning from
truncated samples is considered in a discrete setting.
We introduce a natural notion of fatness of the truncation set $S$, under
which truncated samples reveal enough information about the true distribution.
We show that if the truncation set is sufficiently fat, samples from the true
distribution can be generated from truncated samples. A stunning consequence is
that virtually any statistical task (e.g., learning in total variation
distance, parameter estimation, uniformity or identity testing) that can be
performed efficiently for Boolean product distributions, can also be performed
from truncated samples, with a small increase in sample complexity. We
generalize our approach to ranking distributions over $d$ alternatives, where
we show how fatness implies efficient parameter estimation of Mallows models
from truncated samples.
Exploring the limits of learning discrete models from truncated samples, we
identify three natural conditions that are necessary for efficient
identifiability: (i) the truncation set $S$ should be rich enough; (ii) $S$
should be accessible through membership queries; and (iii) the truncation by
$S$ should leave enough randomness in all directions. By carefully adapting the
Stochastic Gradient Descent approach of (Daskalakis et al., FOCS 2018), we show
that these conditions are also sufficient for efficient learning of truncated
Boolean product distributions.
- Abstract（参考訳）: 我々は、会員オラクルを通してアクセス可能な$s \subset \{0, 1\}^d$ によってサンプルが切り離されるとき、ブール積分布のパラメータを$d$次元で推定する問題を研究した。
切断標本からの学習の計算と統計の複雑さが離散的な設定で考慮されるのはこれが初めてである。
そこで本研究では, 実分布に関する十分な情報を明らかにするために, 減価償却セット$s$ の太さという自然概念を導入する。
切断集合が十分に太っている場合、真の分布からのサンプルは切断されたサンプルから生成できることを示す。
驚くべき結果として、ブール積分布に対して効率的に実行できる事実上あらゆる統計タスク(例えば、総変動距離、パラメータ推定、一様性、同一性テスト)も、縮小されたサンプルから実行でき、サンプル複雑性がわずかに増加する。
我々は,d$ の代替品に対して分布をランク付けするアプローチを一般化し,停止したサンプルからmallowsモデルの効率的なパラメータ推定を実現する方法を示す。
切り刻まれたサンプルから離散モデルを学習する限界を探索し、効率的な識別に必要となる3つの自然条件を同定する。
(i)truncation set $S$ は十分にリッチであるべきである。
(ii)$s$は会員問合せを通じてアクセス可能でなければならない。
(iii)$s$の切り下げは、すべての方向に十分なランダム性を残すべきである。
確率的勾配降下アプローチ(daskalakis et al., focs 2018)を注意深く適応させることで,これらの条件がブール積分布の効率的な学習にも十分であることを示す。
関連論文リスト
- Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。
マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
論文 参考訳（メタデータ） (2024-11-14T01:37:02Z) - Controllable Generation via Locally Constrained Resampling [77.48624621592523]
本研究では, ベイズ条件付けを行い, 制約条件下でサンプルを描画する, トラクタブルな確率的手法を提案する。
提案手法はシーケンス全体を考慮し,現行のグリード法よりも大域的に最適に制約された生成を導出する。
提案手法は, 有害な世代からモデル出力を分離し, 脱毒化に対する同様のアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2024-10-17T00:49:53Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Weighted Sparse Partial Least Squares for Joint Sample and Feature
Selection [7.219077740523681]
本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。
我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
論文 参考訳（メタデータ） (2023-08-13T10:09:25Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions [42.6763105645717]
少数の破損したサンプルが与えられた場合、ゴールは確率の高い$mu$を正確に近似する仮説を効率的に計算することである。
本アルゴリズムは, 周辺次元と対数的にスケーリングするサンプルを多数使用して, 最適誤差を実現する。
我々の分析は、ある空間特性を満たす正の半定値に対する(非スペクトル)分解の繊細な設計を含む、独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2022-11-29T16:13:50Z) - On counterfactual inference with unobserved confounding [36.18241676876348]
独立だが不均一な単位を持つ観測的研究を前提として、各単位の反実分布を学習することが目的である。
我々は、すべての$n$サンプルをプールして、すべての$n$パラメータベクトルを共同で学習する凸目的を導入する。
対数的ソボレフ不等式を満たすためにコンパクトに支持された分布に対して十分な条件を導出する。
論文 参考訳（メタデータ） (2022-11-14T04:14:37Z) - Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
まず確率分布をモデル化し,そのモデルからサンプリングする。
これらのモデルでは, 少数の評価値を用いて, 高精度に多数の密度を近似することが可能であることが示され, それらのモデルから効果的にサンプルする簡単なアルゴリズムが提示される。
論文 参考訳（メタデータ） (2021-10-20T12:25:22Z) - Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
粒子フィルタリングは複素系の優れた非線形推定を計算するために用いられる。
粒子フィルタは様々なシナリオにおいて良好な推定値が得られることを示す。
論文 参考訳（メタデータ） (2021-10-06T16:58:34Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。