論文の概要: Iterative Chow Filtering for Learning with Distribution Shift

• arxiv url: http://arxiv.org/abs/2605.17251v1
• Date: Sun, 17 May 2026 04:18:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-19 17:57:47.80854
• Title: Iterative Chow Filtering for Learning with Distribution Shift
• Title（参考訳）: 分布シフトによる学習のための反復的ショーフィルタリング
• Authors: Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan,
• Abstract要約: 効率的なPQ学習のために,$cal L$サンドイッチサフィスというより弱い概念が示された。 そこで我々は,DNFの準多項式時間PQ学習アルゴリズムを一様分布下で実現した。
• 参考スコア（独自算出の注目度）: 25.270503886184795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled training examples, unlabeled test examples, and must make correct predictions on the test set but is allowed to abstain from predicting on out-of-distribution points. Their results rely on ${\cal L}_2$ sandwiching approximations, a strong requirement that leads to poor bounds for several basic function classes such as DNF formulas. Here, we show that the weaker notion of ${\cal L}_1$ sandwiching suffices for efficient PQ learning. As a consequence, we obtain the first quasipolynomial-time PQ learning algorithm for DNFs under the uniform distribution and essentially match the guarantees known for ordinary PAC learning. More broadly, our bounds provide exponential improvements for several classes including constant depth circuits and constant degree polynomial threshold functions. Our main technical ingredient is Iterative Chow Filtering, a new procedure that uses low-degree Chow parameters to identify and remove test points incompatible with the training distribution.
• Abstract（参考訳）: Goel氏らによる最近の作業は、挑戦的なPQフレームワークにおける分散シフトによる学習のための、最初の効率的なアルゴリズムを提供した。 この設定では、学習者はラベル付きトレーニング例、ラベル付きテスト例を受け取り、テストセット上で正確な予測をしなければならないが、配布外ポイントでの予測は禁じられる。 それらの結果は、DNF式のようないくつかの基本関数クラスの境界が不足する強い要件である、${\cal L}_2$ sandwiching approximationsに依存している。 ここでは、効率的なPQ学習のために、より弱い${\cal L}_1$サンドイッチサフィスの概念を示す。 その結果,DNF に対する準多項式時間 PQ 学習アルゴリズムを一様分布で実現し,通常の PAC 学習で知られている保証と本質的に一致した。 より広範に、我々の境界は、定数深度回路や定数次多項式しきい値関数を含むいくつかのクラスに対して指数関数的に改善する。 これは、低度のChowパラメータを使用して、トレーニングディストリビューションと互換性のないテストポイントを特定し、削除する新しい手順です。

関連論文リスト

• Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift [21.679363840452087]
  ブール概念クラスに対して,PQ学習からTDS学習までの効率的なブラックボックス削減を行う。 この同値性は、ハーフ空間のような基本クラスの分布自由なTDS学習における最初の硬度結果を意味する。 また、学習者がメンバーシップクエリーにアクセスできるようにすることは、これらの難易度の結果を横取りし、ハーフスペースの効率よく分布のないPQ学習を可能にすることを示す。
  論文  参考訳（メタデータ） (2026-05-07T22:37:29Z)
• On the Learning Curves of Revenue Maximization [62.087200798198786]
  学習曲線は、トレーニングサンプル数の関数として、固定された基礎分布に対するアルゴリズムの誤差の減衰をプロットする。 収益を最大化する学習アルゴリズムに関する先行研究は、学習理論におけるPAC学習フレームワークと並行して、分散のない視点を採用する。 ベイズ一貫性アルゴリズムが存在し、任意の評価分布に対して学習曲線が0に収束することを示す。
  論文  参考訳（メタデータ） (2026-04-29T17:38:25Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。 適切なアクションにクレジットを割り当てるには? 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
  論文  参考訳（メタデータ） (2025-05-26T17:44:08Z)
• 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)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。 すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
  論文  参考訳（メタデータ） (2022-05-12T14:40:18Z)
• Transformers Can Do Bayesian Inference [56.99390658880008]
  我々はPFN(Presideed Data Fitted Networks)を提案する。 PFNは、大規模機械学習技術におけるインコンテキスト学習を活用して、大規模な後部集合を近似する。 我々は、PFNがガウス過程をほぼ完璧に模倣し、難解問題に対する効率的なベイズ推定を可能にすることを示した。
  論文  参考訳（メタデータ） (2021-12-20T13:07:39Z)
• Efficient Learning with Arbitrary Covariate Shift [19.230859892728784]
  境界のあるVC次元のクラスCで2進関数を学習するための効率的なアルゴリズムを提供し、トレーニングデータはPに従って分散し、テストデータはQに従って分散する。 本研究では,信頼できる学習が片面ノイズによる学習のモデルであるCの"信頼できる学習者"に,オーラクルを用いた時間PQ学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-02-15T19:14:25Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)

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

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