論文の概要: Optimal SQ Lower Bounds for Robustly Learning Discrete Product
Distributions and Ising Models
- arxiv url: http://arxiv.org/abs/2206.04589v1
- Date: Thu, 9 Jun 2022 16:10:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-10 14:09:41.061948
- Title: Optimal SQ Lower Bounds for Robustly Learning Discrete Product
Distributions and Ising Models
- Title（参考訳）: 離散的製品分布とイジングモデルのロバスト学習のための最適SQ下界
- Authors: Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
- Abstract要約: 我々は、離散的な高次元分布の特定の族をしっかりと学習するために、最適な統計的クエリー(SQ)の下位境界を確立する。
我々のSQローバウンドは、これらの問題に対する既知のアルゴリズムのエラー保証と一致し、これらのタスクの現在の上限が最善であることを示す。
- 参考スコア（独自算出の注目度）: 45.14286976373306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We establish optimal Statistical Query (SQ) lower bounds for robustly
learning certain families of discrete high-dimensional distributions. In
particular, we show that no efficient SQ algorithm with access to an
$\epsilon$-corrupted binary product distribution can learn its mean within
$\ell_2$-error $o(\epsilon \sqrt{\log(1/\epsilon)})$. Similarly, we show that
no efficient SQ algorithm with access to an $\epsilon$-corrupted ferromagnetic
high-temperature Ising model can learn the model to total variation distance
$o(\epsilon \log(1/\epsilon))$. Our SQ lower bounds match the error guarantees
of known algorithms for these problems, providing evidence that current upper
bounds for these tasks are best possible. At the technical level, we develop a
generic SQ lower bound for discrete high-dimensional distributions starting
from low dimensional moment matching constructions that we believe will find
other applications. Additionally, we introduce new ideas to analyze these
moment-matching constructions for discrete univariate distributions.
- Abstract（参考訳）: 離散高次元分布の族をロバストに学習するための最適統計クエリ(sq)下限を確立する。
特に、$\epsilon$-corrupted binary product distributionにアクセスできる効率的なSQアルゴリズムは、$\ell_2$-error $o(\epsilon \sqrt{\log(1/\epsilon)})$で学習できない。
同様に、$\epsilon$-corrupted ferromagnetic high-temperature Isingモデルにアクセスできる効率的なSQアルゴリズムが存在しないことを示し、このモデルから総変動距離$o(\epsilon \log(1/\epsilon))$.
我々のSQローバウンドは、これらの問題に対する既知のアルゴリズムのエラー保証と一致し、これらのタスクの現在の上限が最善であることを示す。
技術的なレベルでは、我々が他の応用を見出すと信じている低次元モーメントマッチング構成から始まり、離散高次元分布に対する一般的なsq下限を開発する。
さらに、離散一変量分布のモーメントマッチング構造を解析するための新しいアイデアを提案する。
関連論文リスト
- Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。
一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
論文 参考訳（メタデータ） (2023-05-28T19:40:46Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳（メタデータ） (2023-01-09T18:36:49Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。