論文の概要: Learning Structured Distributions From Untrusted Batches: Faster and
Simpler
- arxiv url: http://arxiv.org/abs/2002.10435v2
- Date: Sun, 7 Jun 2020 17:50:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 03:38:52.456482
- Title: Learning Structured Distributions From Untrusted Batches: Faster and
Simpler
- Title（参考訳）: 信頼できないバッチから構造化分布を学ぶ:より速く、よりシンプルに
- Authors: Sitan Chen, Jerry Li, Ankur Moitra
- Abstract要約: 本稿では,Qiao と Valiant [QV17] が導入した信頼できないバッチから学ぶことの問題点を再考する。
我々は,[JO19] と [CLM19] の技法を合成して両世界の長所を与える,魅力的な方法を見出した。
- 参考スコア（独自算出の注目度）: 26.57313255285721
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the problem of learning from untrusted batches introduced by Qiao
and Valiant [QV17]. Recently, Jain and Orlitsky [JO19] gave a simple
semidefinite programming approach based on the cut-norm that achieves
essentially information-theoretically optimal error in polynomial time.
Concurrently, Chen et al. [CLM19] considered a variant of the problem where
$\mu$ is assumed to be structured, e.g. log-concave, monotone hazard rate,
$t$-modal, etc. In this case, it is possible to achieve the same error with
sample complexity sublinear in $n$, and they exhibited a quasi-polynomial time
algorithm for doing so using Haar wavelets.
In this paper, we find an appealing way to synthesize the techniques of
[JO19] and [CLM19] to give the best of both worlds: an algorithm which runs in
polynomial time and can exploit structure in the underlying distribution to
achieve sublinear sample complexity. Along the way, we simplify the approach of
[JO19] by avoiding the need for SDP rounding and giving a more direct
interpretation of it through the lens of soft filtering, a powerful recent
technique in high-dimensional robust estimation. We validate the usefulness of
our algorithms in preliminary experimental evaluations.
- Abstract（参考訳）: Qiao と Valiant [QV17] が導入した信頼できないバッチから学ぶ問題を再考する。
最近 jain と orlitsky [jo19] は、多項式時間で本質的に情報理論上最適誤差を達成するカットノルムに基づく単純な半定義型プログラミングアプローチを提唱した。
とChenらは言う。
[CLM19]は、$\mu$がロジコンケーブ、モノトンハザードレート、$t$-modalなど、構造化されると仮定される問題の変種であると考えた。
この場合、サンプル複雑性サブリニアを$n$で同じ誤差を達成でき、Haarウェーブレットを用いてそれを行うための準多項式時間アルゴリズムを示した。
本稿では, [jo19] と [clm19] の手法を合成し,両世界の最善を尽くす方法を見出した。
その過程で,sdp丸めの必要性を回避し,高次元ロバスト推定の強力な手法であるソフトフィルタリングのレンズを通して,より直接的な解釈を行うことで,jo19のアプローチを単純化する。
予備実験評価におけるアルゴリズムの有用性を検証する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。
本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
論文 参考訳（メタデータ） (2021-07-12T17:00:59Z) - Rejection sampling from shape-constrained distributions in sublinear
time [14.18847457501901]
離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。
本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-29T01:00:42Z) - Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear
Time [13.617081331738056]
我々は、サンプルの$epsilon$-fractionが逆転して破損するベイズネットワークを学習する問題を研究する。
本稿では,この問題に対する線形時間アルゴリズムを,次元に依存しない誤差保証で提示する。
論文 参考訳（メタデータ） (2021-05-12T10:11:32Z) - Faster Differentially Private Samplers via R\'enyi Divergence Analysis
of Discretized Langevin MCMC [35.050135428062795]
ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。
我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
論文 参考訳（メタデータ） (2020-10-27T22:52:45Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。
本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
論文 参考訳（メタデータ） (2020-04-09T01:45:05Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。