論文の概要: An Efficient Tester-Learner for Halfspaces

• arxiv url: http://arxiv.org/abs/2302.14853v1
• Date: Tue, 28 Feb 2023 18:51:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-01 14:54:06.989738
• Title: An Efficient Tester-Learner for Halfspaces
• Title（参考訳）: ハーフスペースのための効率的なテスタリーナー
• Authors: Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
• Abstract要約: 本稿では、Rubinfeld と Vasilyan が最近定義したテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを提案する(2023)。 このモデルでは、学習者は、トレーニングセットがテストに合格するたびに、その出力仮説の精度がほぼ最適であると認定する。
• 参考スコア（独自算出の注目度）: 13.13131953359806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023). In this model, a learner certifies that the accuracy of its output hypothesis is near optimal whenever the training set passes an associated test, and training sets drawn from some target distribution -- e.g., the Gaussian -- must pass the test. This model is more challenging than distribution-specific agnostic or Massart noise models where the learner is allowed to fail arbitrarily if the distributional assumption does not hold. We consider the setting where the target distribution is Gaussian (or more generally any strongly log-concave distribution) in $d$ dimensions and the noise model is either Massart or adversarial (agnostic). For Massart noise our tester-learner runs in polynomial time and outputs a hypothesis with error $\mathsf{opt} + \epsilon$, which is information-theoretically optimal. For adversarial noise our tester-learner has error $\tilde{O}(\mathsf{opt}) + \epsilon$ and runs in quasipolynomial time. Prior work on testable learning ignores the labels in the training set and checks that the empirical moments of the covariates are close to the moments of the base distribution. Here we develop new tests of independent interest that make critical use of the labels and combine them with the moment-matching approach of Gollakota et al. (2023). This enables us to simulate a variant of the algorithm of Diakonikolas et al. (2020) for learning noisy halfspaces using nonconvex SGD but in the testable learning setting.
• Abstract（参考訳）: 最近rubinfeld と vasilyan (2023) によって定義されたテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを与える。 このモデルでは、学習者は、トレーニングセットが関連するテストに合格すると、その出力仮説の精度がほぼ最適であると確認し、目標分布(例えばガウス分布)から引き出されたトレーニングセットがテストに合格しなければならない。 このモデルは分布固有の非依存ノイズモデルやマッサートノイズモデルよりも困難であり、分布仮説が成立しない場合には学習者が任意に失敗することが許される。 対象分布がガウス分布(あるいはより一般的には強対流分布)であるような設定をd$次元で考慮し、ノイズモデルはマスアートまたは逆(非依存)である。 マッサートノイズに対して、テストレーナーは多項式時間で実行し、情報理論上最適である誤差 $\mathsf{opt} + \epsilon$ で仮説を出力する。 反対のノイズに対して、テスト担当者はエラー$\tilde{o}(\mathsf{opt}) + \epsilon$ を持ち、準多項時間で実行します。 テスト可能な学習に関する先行研究は、トレーニングセットのラベルを無視して、共変量の経験的モーメントがベース分布のモーメントに近いことをチェックする。 ここでは,ラベルを批判的に利用し,gollakotaらによるモーメントマッチングアプローチ(2023年)と組み合わせた,独立した関心の新たなテストを開発する。 これにより、非凸SGDを用いてノイズの多いハーフスペースを学習するために、Diakonikolas et al. (2020) のアルゴリズムの変種をシミュレートすることができる。

関連論文リスト

• Tolerant Algorithms for Learning with Arbitrary Covariate Shift [18.37181965815327]
  学習者は,ある分布からラベル付き集合を学習するが,異なる,潜在的に逆向きに生成されたテスト分布で評価する。 我々は,PQ学習 (Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS 2020) とTDS学習 (Klivans, Stavropoulos, Vasilyan COLT 2024) の2つのフレームワークに注目した。
  論文  参考訳（メタデータ） (2024-06-04T19:50:05Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• Efficient Testable Learning of Halfspaces with Adversarial Label Noise [44.32410859776227]
  最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。 テストラナーは、時間$poly(d/eps)$を実行し、ミス分類エラー$O(opt)+eps$でハーフスペースを出力します。
  論文  参考訳（メタデータ） (2023-03-09T18:38:46Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  本稿ではランダム行列理論の手法を用いて、単純な線形回帰に対して理想的なトレーニング-テストデータ分割を求める。 それは「理想」を整合性計量を満たすものとして定義し、すなわち経験的モデル誤差は実際の測定ノイズである。 本論文は,任意のモデルのトレーニングとテストサイズを,真に最適な方法で解決した最初の論文である。
  論文  参考訳（メタデータ） (2021-12-11T13:18:33Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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