論文の概要: A Distributional-Lifting Theorem for PAC Learning

• arxiv url: http://arxiv.org/abs/2506.16651v1
• Date: Thu, 19 Jun 2025 23:28:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:05.288442
• Title: A Distributional-Lifting Theorem for PAC Learning
• Title（参考訳）: PAC学習のための分散リフティング理論
• Authors: Guy Blanc, Jane Lange, Carmen Strassle, Li-Yang Tan,
• Abstract要約: 分散仮定は効率的なアルゴリズムの設計を促進するが、その到達範囲と妥当性は制限される。 ブラン、ランゲ、マリク、タンの最近の研究は、一様分布学習者を持ち上げる特別な事例であると考えた。 これらの手法は, ランダムな例にのみアクセスすることで, 情報論的に抽出可能であることを示す。 次に、$Dstar$を学ぶ必要性を助長する別のアプローチを取り、標準のPACモデルで動作するリフターを生成します。
• 参考スコア（独自算出の注目度）: 16.985620991607345
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the design of efficient algorithms but also limit their reach and relevance. Towards addressing this, we prove a distributional-lifting theorem: This upgrades a learner that succeeds with respect to a limited distribution family $\mathcal{D}$ to one that succeeds with respect to any distribution $D^\star$, with an efficiency overhead that scales with the complexity of expressing $D^\star$ as a mixture of distributions in $\mathcal{D}$. Recent work of Blanc, Lange, Malik, and Tan considered the special case of lifting uniform-distribution learners and designed a lifter that uses a conditional sample oracle for $D^\star$, a strong form of access not afforded by the standard PAC model. Their approach, which draws on ideas from semi-supervised learning, first learns $D^\star$ and then uses this information to lift. We show that their approach is information-theoretically intractable with access only to random examples, thereby giving formal justification for their use of the conditional sample oracle. We then take a different approach that sidesteps the need to learn $D^\star$, yielding a lifter that works in the standard PAC model and enjoys additional advantages: it works for all base distribution families, preserves the noise tolerance of learners, has better sample complexity, and is simpler.
• Abstract（参考訳）: 効率的な分散なしPAC学習の難しさは、分散特化学習に多大な貢献をもたらした。 分布仮定は効率的なアルゴリズムの設計を促進するが、その到達範囲と関連性も制限する。 これは、限定分布族 $\mathcal{D}$ に対して成功する学習者を、任意の分布に対して成功する学習者へアップグレードする。 ブラン、ランゲ、マリク、タンの最近の研究は、一様分布学習者を持ち上げる特別な場合を考え、標準PACモデルでは利用できない強力なアクセス形態であるD^\star$の条件付きサンプルオラクルを使用するリフターを設計した。 彼らのアプローチは、半教師付き学習からアイデアを引き出すもので、まずD^\star$を学び、その情報を使って持ち上げる。 これらの手法は, ランダムな例にのみアクセス可能な情報理論的に難解であることを示し, 条件付きサンプルオラクルの使用に対する公式な正当性を与える。 次に、D^\star$を学習し、標準のPACモデルで機能し、さらなる利点を享受するリフターを出力する別のアプローチを取ります。

関連論文リスト

• SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups [14.925722398371498]
  本稿では,S_n$以上の複雑な分布を学習するタスクを単純化する離散拡散モデルを提案する。 有限群上のランダムウォークの理論に基づいて拡散長を選択するための経験的ガイドラインを提供する。 本モデルでは,4桁画像のソート,ジグソーパズル,旅行セールスマン問題などの課題に対して,最先端ないし同等のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2024-10-03T19:37:40Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  条件分布は機械学習の中心的な問題です ペアデータとペアデータの両方を統合する新しいパラダイムを提案する。 提案手法は任意の誤差で理論上真の条件分布を復元可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-03T16:12:59Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Learning Algorithm Generalization Error Bounds via Auxiliary Distributions [16.44492672878356]
  一般化エラー境界は、機械学習モデルがどのように機能するかを理解するのに不可欠である。 そこで本研究では,Auxiliary Distribution Methodという新たな手法を提案する。
  論文  参考訳（メタデータ） (2022-10-02T10:37:04Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  ニューラルネットワークを用いて各戻り分布から統計量の有限集合を学習する手法を定式化する。 我々の手法は、戻り分布とベルマン目標の間のモーメントの全ての順序を暗黙的に一致させるものとして解釈できる。 Atariゲームスイートの実験により,本手法は標準分布RLベースラインよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-24T05:18:17Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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