論文の概要: Tester-Learners for Halfspaces: Universal Algorithms

• arxiv url: http://arxiv.org/abs/2305.11765v1
• Date: Fri, 19 May 2023 15:52:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-22 13:38:56.200216
• Title: Tester-Learners for Halfspaces: Universal Algorithms
• Title（参考訳）: 半空間のためのテスタリーナー:ユニバーサルアルゴリズム
• Authors: Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
• Abstract要約: 広範に構造化された分布に対して普遍的に成功するハーフ空間に対して、最初のテスタ・ラーナーを与える。 学習者はラベル付きディストリビューションでエラー$mathrmopt + epsilon$を達成します。
• 参考スコア（独自算出の注目度）: 13.13131953359806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time and has the following guarantee: the learner achieves error $O(\mathrm{opt}) + \epsilon$ on any labeled distribution that the tester accepts, and moreover, the tester accepts whenever the marginal is any distribution that satisfies a Poincar\'e inequality. In contrast to prior work on testable learning, our tester is not tailored to any single target distribution but rather succeeds for an entire target class of distributions. The class of Poincar\'e distributions includes all strongly log-concave distributions, and, assuming the Kannan--L\'{o}vasz--Simonovits (KLS) conjecture, includes all log-concave distributions. In the special case where the label noise is known to be Massart, our tester-learner achieves error $\mathrm{opt} + \epsilon$ while accepting all log-concave distributions unconditionally (without assuming KLS). Our tests rely on checking hypercontractivity of the unknown distribution using a sum-of-squares (SOS) program, and crucially make use of the fact that Poincar\'e distributions are certifiably hypercontractive in the SOS framework.
• Abstract（参考訳）: 半空間に対する最初のテスタ・リーナーは、広く構成された分布のクラスで普遍的に成功する。 学習者は、テスト者が受け入れるラベル付き分布でエラー $o(\mathrm{opt}) + \epsilon$ を達成し、さらに、限界がポアンカル・ユイの不等式を満たす任意の分布であるとき、テスト者は受け入れる。 テスト可能な学習に関する以前の研究とは対照的に、テスターは単一ターゲットの分布に合わせたものではなく、ターゲットの分布全体に対して成功する。 Poincar\'e 分布のクラスは、全ての強い対数分布を含み、Kannan--L\'{o}vasz--Simonovits (KLS) 予想を仮定すると、全ての対数対数分布を含む。 ラベルノイズがマスアートであることが知られている特別なケースでは、テスト担当者は、すべてのログコンケーブ分布を無条件に(klsを仮定せずに)受け入れながら、エラー $\mathrm{opt} + \epsilon$ を達成する。 本テストでは,SOS(sum-of-squares)プログラムを用いて未知分布の超収縮度をチェックすることに頼るとともに,Poincar\'e分布がSOSフレームワークにおいて極めて過収縮的であるという事実を重要視する。

関連論文リスト

• Universal Batch Learning Under The Misspecification Setting [4.772817128620037]
  ログロスを伴う不特定設定において、普遍的なエムバッチ学習の問題を考察する。 我々は、最適普遍学習者、データ生成分布の集合上の混合を導出し、min-max後悔を表す閉形式表現を得る。
  論文  参考訳（メタデータ） (2024-05-12T11:16:05Z)
• Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
  Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。 それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
  論文  参考訳（メタデータ） (2024-04-02T23:34:39Z)
• SimPro: A Simple Probabilistic Framework Towards Realistic Long-Tailed Semi-Supervised Learning [49.94607673097326]
  ラベルなしデータの分散に関する前提を前提としない、高度に適応可能なフレームワークをSimProとして提案する。 我々のフレームワークは確率モデルに基づいており、期待最大化アルゴリズムを革新的に洗練する。 本手法は,様々なベンチマークやデータ分散シナリオにまたがる一貫した最先端性能を示す。
  論文  参考訳（メタデータ） (2024-02-21T03:39:04Z)
• Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective [42.85196869759168]
  a) テストランダムデータおよびトレーニングランダムデータの下で、ラベル$z$は、(x,y)$, (b) トレーニングディストリビューションは、別々に$x$と$y$の限界分布をカバーしているが、(c) テストディストリビューションは、トレーニングディストリビューションがカバーしていない製品ディストリビューションの例を含む。
  論文  参考訳（メタデータ） (2023-07-12T21:17:47Z)
• An Efficient Tester-Learner for Halfspaces [13.13131953359806]
  本稿では、Rubinfeld と Vasilyan が最近定義したテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを提案する(2023)。 このモデルでは、学習者は、トレーニングセットがテストに合格するたびに、その出力仮説の精度がほぼ最適であると認定する。
  論文  参考訳（メタデータ） (2023-02-28T18:51:55Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  ニューラルネットワークを用いて各戻り分布から統計量の有限集合を学習する手法を定式化する。 我々の手法は、戻り分布とベルマン目標の間のモーメントの全ての順序を暗黙的に一致させるものとして解釈できる。 Atariゲームスイートの実験により,本手法は標準分布RLベースラインよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-24T05:18:17Z)
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
  分布固有モデルにおいて,同種半空間の学習を代理する問題に対する解を示す。 任意の凸分布において、誤分類誤差は本質的にハーフスペースの誤分類誤差につながることを示す。
  論文  参考訳（メタデータ） (2020-06-11T18:55:59Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

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

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