論文の概要: Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes

• arxiv url: http://arxiv.org/abs/2211.09101v1
• Date: Wed, 16 Nov 2022 18:38:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 14:37:08.181390
• Title: Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
• Title（参考訳）: 比較学習:2つの仮説クラスのためのサンプル複雑性理論
• Authors: Lunjia Hu, Charlotte Peale
• Abstract要約: 比較学習は、PAC学習における実現可能な設定と不可知な設定の組み合わせとして導入する。 たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。 比較学習のサンプルの複雑さは、相互VC次元$mathsfVC(S,B)$によって特徴づけられる。
• 参考スコア（独自算出の注目度）: 5.194264506657145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many learning theory problems, a central role is played by a hypothesis class: we might assume that the data is labeled according to a hypothesis in the class (usually referred to as the realizable setting), or we might evaluate the learned model by comparing it with the best hypothesis in the class (the agnostic setting). Taking a step beyond these classic setups that involve only a single hypothesis class, we introduce comparative learning as a combination of the realizable and agnostic settings in PAC learning: given two binary hypothesis classes $S$ and $B$, we assume that the data is labeled according to a hypothesis in the source class $S$ and require the learned model to achieve an accuracy comparable to the best hypothesis in the benchmark class $B$. Even when both $S$ and $B$ have infinite VC dimensions, comparative learning can still have a small sample complexity. We show that the sample complexity of comparative learning is characterized by the mutual VC dimension $\mathsf{VC}(S,B)$ which we define to be the maximum size of a subset shattered by both $S$ and $B$. We also show a similar result in the online setting, where we give a regret characterization in terms of the mutual Littlestone dimension $\mathsf{Ldim}(S,B)$. These results also hold for partial hypotheses. We additionally show that the insights necessary to characterize the sample complexity of comparative learning can be applied to characterize the sample complexity of realizable multiaccuracy and multicalibration using the mutual fat-shattering dimension, an analogue of the mutual VC dimension for real-valued hypotheses. This not only solves an open problem proposed by Hu, Peale, Reingold (2022), but also leads to independently interesting results extending classic ones about regression, boosting, and covering number to our two-hypothesis-class setting.
• Abstract（参考訳）: 多くの学習理論問題において、中心的な役割は仮説クラスによって演じられる: データはクラス内の仮説(通常、実現可能な設定と呼ばれる)に従ってラベル付けされていると仮定するか、あるいはクラス内の最良の仮説(不可知的な設定)と比較することによって学習モデルを評価することができる。 2つの二項仮説クラス$s$と$b$が与えられた場合、データはソースクラス$s$の仮説に従ってラベル付けされ、ベンチマーククラス$b$のベスト仮説に匹敵する精度を達成するために学習モデルが必要であると仮定します。 たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。 比較学習のサンプルの複雑さは、相互VC次元$\mathsf{VC}(S,B)$によって特徴づけられ、これは、$S$と$B$によって破られた部分集合の最大サイズであると定義する。 また、オンライン設定でも同様の結果を示し、ここでは相互のLittlestone次元$\mathsf{Ldim}(S,B)$の観点から、後悔の意を表す。 これらの結果は部分仮説にも当てはまる。 さらに, 比較学習のサンプル複雑性を特徴付けるために必要な知見を, 実数値仮説に対するvc次元の類似である相互脂肪散布次元を用いて, 実現可能な多重精度と多重化のサンプル複雑性を特徴付けるために応用できることを示した。 これは、Hu, Peale, Reingold (2022) によって提案されたオープンな問題を解くだけでなく、回帰、ブースティング、および2つの仮説クラスの設定へのカバーに関する古典的な結果も、独立に興味深い結果をもたらす。

関連論文リスト

• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• On Learning Latent Models with Multi-Instance Weak Supervision [57.18649648182171]
  本稿では,複数の入力インスタンスに関連付けられた遷移関数$sigma$ラベルによって,教師信号が生成される弱い教師付き学習シナリオについて考察する。 我々の問題は、潜在的な構造学習やニューロシンボリックな統合など、さまざまな分野で満たされている。
  論文  参考訳（メタデータ） (2023-06-23T22:05:08Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。 提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。 これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
  論文  参考訳（メタデータ） (2023-03-28T15:59:12Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。 すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
  論文  参考訳（メタデータ） (2022-05-12T14:40:18Z)
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap [66.75488143823337]
  また, 指数的標本複雑度は, 一定の準最適ギャップを仮定しても, 未だに保持していることを示した。 おそらく驚くことに、これはオンラインrl設定と生成モデル設定の指数関数的な分離を意味する。
  論文  参考訳（メタデータ） (2021-03-23T17:05:54Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)
• L2R2: Leveraging Ranking for Abductive Reasoning [65.40375542988416]
  学習システムの帰納的推論能力を評価するために,帰納的自然言語推論タスク(alpha$NLI)を提案する。 新たな$L2R2$アプローチは、Learning-to-rankフレームワークの下で提案されている。 ARTデータセットの実験は、公開リーダボードの最先端に到達します。
  論文  参考訳（メタデータ） (2020-05-22T15:01:23Z)

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

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