論文の概要: 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)を注意深く適応させることで,これらの条件がブール積分布の効率的な学習にも十分であることを示す。
関連論文リスト
- 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 [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (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) - On the Statistical Complexity of Sample Amplification [43.612884935666116]
未知の分布から引き出された$n$ i.i.d.サンプルが与えられたら、いつより大きな$n+m$ i.i.d.サンプルを生成することができるのか?
サンプル増幅問題を, 一般に適用可能な増幅手順, 低境界技術, 既存の統計的概念との関係を導出することにより, しっかりとした統計基盤に配置する。
論文 参考訳（メタデータ） (2022-01-12T05:45:27Z) - 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) - Learning Entangled Single-Sample Distributions via Iterative Trimming [28.839136703139225]
そこで本研究では, 反復トリミング標本に基づいて, 簡便かつ効率的な手法を解析し, トリミング標本集合上のパラメータを再推定する。
対数反復法では, 誤差が$lceil alpha n rceil$-th ノイズ点の雑音レベルにのみ依存する推定値が出力されることを示す。
論文 参考訳（メタデータ） (2020-04-20T18:37:43Z) - Distributed, partially collapsed MCMC for Bayesian Nonparametrics [68.5279360794418]
ディリクレ法やベータ・ベルヌーリ法のようなモデルでよく用いられる完全無作為測度は独立な部分測度に分解可能であるという事実を利用する。
この分解を用いて、潜在測度を、インスタンス化された成分のみを含む有限測度と、他のすべての成分を含む無限測度に分割する。
得られたハイブリッドアルゴリズムは、収束保証を犠牲にすることなくスケーラブルな推論を可能にすることができる。
論文 参考訳（メタデータ） (2020-01-15T23:10:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。