論文の概要: The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning

• arxiv url: http://arxiv.org/abs/2010.11925v3
• Date: Thu, 24 Aug 2023 12:58:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-25 19:16:57.498353
• Title: The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
• Title（参考訳）: 分布自由相関型SQ学習のための多項式法
• Authors: Aravind Gollakota, Sushrut Karmalkar, Adam Klivans
• Abstract要約: Malach と Shalev-Shwartz (2022) を一般化し、学習公式に対する厳密な相関 SQ (CSQ) の下界を与えた。 任意の関数クラスのしきい値または近似次数に対する下限は、PACまたはDNF学習のためのCSQ下限を直接意味する。
• 参考スコア（独自算出の注目度）: 9.036124518750732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of distribution-free learning for Boolean function classes in the PAC and agnostic models. Generalizing a beautiful work of Malach and Shalev-Shwartz (2022) that gave tight correlational SQ (CSQ) lower bounds for learning DNF formulas, we give new proofs that lower bounds on the threshold or approximate degree of any function class directly imply CSQ lower bounds for PAC or agnostic learning respectively. While such bounds implicitly follow by combining prior results by Feldman (2008, 2012) and Sherstov (2008, 2011), to our knowledge the precise statements we give had not appeared in this form before. Moreover, our proofs are simple and largely self-contained. These lower bounds match corresponding positive results using upper bounds on the threshold or approximate degree in the SQ model for PAC or agnostic learning, and in this sense these results show that the polynomial method is a universal, best-possible approach for distribution-free CSQ learning.
• Abstract（参考訳）: PACおよび非依存モデルにおけるブール関数クラスに対する分布自由学習の問題点を考察する。 Malach と Shalev-Shwartz (2022) による DNF 式を学習するための厳密な相関 SQ (CSQ) 下界を与える美しい研究を一般化し、各関数クラスのしきい値あるいは近似次数に対する下界が、それぞれPAC あるいは無知学習のCSQ 下界を暗示する新しい証明を与える。 このような境界は、Feldman (2008, 2012) と Sherstov (2008, 2011) の事前の結果を組み合わせることで暗黙的に従うが、我々の知識では、我々がこれまでこの形式になかった正確な文が現れる。 さらに、我々の証明は単純で、ほとんど自己完結している。 これらの下界は、PACや非依存学習のためのSQモデルにおける閾値の上界や近似次数を用いて対応する正の値と一致し、この意味では、多項式法は分布のないCSQ学習において、普遍的で最も有望なアプローチであることを示す。

関連論文リスト

• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [7.443139252028032]
  非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。 近年の研究では、この問題をアクター批判の枠組みで研究している。 線形関数近似を用いた時間差分学習(TD)について検討した。
  論文  参考訳（メタデータ） (2024-10-29T03:40:53Z)
• Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability [71.82666334363174]
  我々は,統計的推定と対話的意思決定において,下位境界法のための統一的なフレームワークを開発する。 対話型意思決定のための新しい下位境界の複雑さを促進する新しい尺度である決定次元を導入する。
  論文  参考訳（メタデータ） (2024-10-07T15:14:58Z)
• Fine-grained analysis of non-parametric estimation for pairwise learning [9.676007573960383]
  ペアワイズ学習における非パラメトリック推定の一般化性能について検討する。 我々の結果は、ランキング、AUC、ペアワイズ回帰、メートル法、類似性学習など、幅広いペアワイズ学習問題に対処するために利用できる。
  論文  参考訳（メタデータ） (2023-05-31T08:13:14Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Fine-Grained Distribution-Dependent Learning Curves [27.09513298165498]
  学習曲線はラベル付き入力サンプル数の関数として学習アルゴリズムの予測誤差をプロットする。 本稿では,Bousquet et alの最近の成果を改良し,改良する,粒状PACと呼ばれる新しい次元特性について紹介する。 我々の特徴は、きめ細かい境界を提供することによって学習曲線の構造に新たな光を当てることである。
  論文  参考訳（メタデータ） (2022-08-31T03:29:21Z)
• Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks [21.687992445577226]
  標準(ノイズフリー)モデルにおけるガウス入力に対する2層ReLUネットワークを学習するために,指数関数的統計的クエリ(SQ)の下界を与える。 従来のSQの下限は、逆ノイズモデル(認識学習)や相関SQのような制限されたモデルに限られていた。 これらの手法を他の学習モデルに拡張する方法を示し、多くのよく研究されたケースにおいて、より効率的な還元が得られることを示す。
  論文  参考訳（メタデータ） (2022-02-10T18:59:14Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
  ガウスの下の半空間を不可知的に学習する問題を考察する。 我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
  論文  参考訳（メタデータ） (2021-02-10T18:40:44Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。 L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
  論文  参考訳（メタデータ） (2021-02-08T18:06:32Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。