論文の概要: Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
- arxiv url: http://arxiv.org/abs/2609.10886v1
- Date: Wed, 09 Sep 2026 22:45:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.15965
- Title: Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
- Title（参考訳）: 相対的スマートII:トラクタブルまたは半スーパービジョンのインスタンス最適化学習
- Abstract要約: Dughmi and Pour (2026) は、教師付き学習者に対して、ラベルのないデータから確実に証明可能なすべての分散固定エラー保証と、限界差による競合を要請した。
その結果,1-Inclusion Graph (OIG) 学習者は2次的なサンプル・複雑さの爆発で比較的賢いことがわかった。
半教師付き比較的スマートな学習は、ラベル付けされていないサンプルの複雑さでのみ二次的な爆発によって情報理論的に可能であることを示す。
- 参考スコア（独自算出の注目度）: 3.545082819007165
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We continue the study of relatively smart learning, introduced by Dughmi and Pour (2026), which asks a supervised learner to compete, marginal by marginal, with every distribution-fixed error guarantee soundly certifiable from unlabeled data. They showed that the One-Inclusion Graph (OIG) learner is relatively smart with a quadratic sample-complexity blowup, and that no relatively smart learner can do better, leaving open whether ERM or another natural or tractable learner achieves comparable guarantees. They also left open whether the blowup can be restricted to unlabeled data. Our firs results shows that ERM---and in fact any proper consistent learner---is relatively smart for binary classification in the distribution-free setting. We show that a small certifiable error with $m$ samples implies a similarly small error on the uniform distribution over a random sample of size $O(m^2)$, yielding a cover of size at most $2^{m+1}$ on that sample. This suffices to control the error of proper consistent learners with $O(m^2)$ samples. We then show that semi-supervised relatively smart learning is information-theoretically possible with a quadratic blowup only in unlabeled sample complexity and no blowup in labeled sample complexity. The learner uses a natural generalization of OIG to a leave-most-out transductive problem, where labels of part of a finite pool are revealed and the remaining labels are predicted. Finally, this label efficiency comes at a cost in simplicity and tractability. If the hypothesis class is accessed only through an agnostic ERM oracle, any semi-supervised relatively smart learner with substantially sub-quadratic labeled-sample blowup requires super-polynomially many oracle calls. This holds even when the marginal is given explicitly, and thus also yields an intractability result for distribution-fixed learning that may be of independent interest.
- Abstract（参考訳）: 我々は、Dughmi and Pour (2026) が導入した比較的スマートな学習の研究を継続し、教師付き学習者に対して、ラベルのないデータから確実に証明できる全ての分布固定誤差保証を用いて、限界差で競合するよう求めている。
彼らは、One-Inclusion Graph (OIG)学習者は、二次的なサンプル複雑さの爆発で比較的賢く、比較的スマートな学習者は、EMMまたは他の自然または学習可能な学習者が同等の保証を達成できるかを放置して、より良くすることができないことを示した。
彼らはまた、ブローアップがラベルのないデータに制限できるかどうかも公表した。
この結果から,ERM-- と実のところ, 適切な一貫した学習者-- は, 分布自由環境における二項分類において比較的賢明であることが示唆された。
検定値が$m$の小さな検定誤差は、検定値が$O(m^2)$のランダムな検定値に対して同様に小さい検定誤差を示し、検定値が$2^{m+1}$の検定値であることを示す。
これは、$O(m^2)$サンプルで適切な一貫した学習者のエラーを制御するのに十分である。
次に、半教師付き比較的スマートな学習は、ラベル付けされていないサンプルの複雑さとラベル付けされたサンプルの複雑さにのみ、二次的な爆破によって情報理論的に可能であることを示す。
学習者は、有限プールの一部のラベルが明らかにされ、残りのラベルが予測される残余変換問題に対して、OIGの自然な一般化を用いる。
最後に、このラベルの効率性は単純さとトラクタビリティを犠牲にします。
仮説クラスが無知のERMオラクルを通してのみアクセスされる場合、実質的に準四重項ラベル付きサンプルのブローアップを持つ半教師付きの比較的スマートな学習者は、超ポリノミカルに多くのオラクル呼び出しを必要とする。
これは、境界が明示的に与えられるときでも成り立ち、したがって、独立した関心を持つかもしれない分布固定学習の難易度がもたらされる。
関連論文リスト
- Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
モノトン対向は、i.i.d.ラベル付きサンプルを観察し、その選択の有限個の例を付加する。
すべてのサンプルは正しくラベル付けされているが、挿入はクリーンサンプルに依存するため、組み合わせたサンプルは交換できない。
このモデルを導入したLarsen、Pabbaraju、およびShettyは、VC次元$d$のクラスに対して、経験的リスク最小化が予測誤差$O((d/n)log(n/d))$に達することを示した。
論文 参考訳（メタデータ） (2026-08-06T17:45:32Z) - Refereed Learning [4.024083217094761]
提案手法では,精度のレベルが同等のコストで得られるものよりもはるかに高い参照学習プロトコルを示す。
for all $varepsilon>0$ and ambient dimension $d$, our learner makes only one query to the ground truth function。
学習者は,まず,効率よくサンプリングできない分布から,プローバーを用いて,学習者がサンプルを採取できる技術を開発した。
論文 参考訳（メタデータ） (2025-10-06T23:07:31Z) - On the sample complexity of semi-supervised multi-objective learning [17.947890912560162]
多目的学習では、競合する可能性のある予測タスクを1つのモデルで共同で解決する必要がある。
Bregman の損失で定義された目的に対して、$mathcalG$ の複雑さはラベルのないデータでのみ有効であることが証明される。
これらのレートは擬似ラベルによる単純な半教師付きアルゴリズムによって達成される。
論文 参考訳（メタデータ） (2025-08-23T22:15:36Z) - Weak to Strong Learning from Aggregate Labels [9.804335415337071]
本研究では,そのような学習袋にアグリゲートラベルを付けた弱い学習者を用いて,強力な学習者を得るという課題について検討する。
弱い学習者はトレーニングバッグに一定精度1を有し、強い学習者の精度は任意に1に近づくことができる。
我々の研究は、LLPで同じことを達成するアルゴリズムを用いて、アグリゲーションラベルから弱いから強い学習を理論的に研究した最初のものである。
論文 参考訳（メタデータ） (2024-11-09T14:56:09Z) - Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [72.69498649272347]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しいパラダイムを提案する。
提案手法は任意の誤差で理論上真の条件分布を復元可能であることを示す。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning [57.18649648182171]
我々は、MI-PLLの文脈において、これまで研究されていない問題に対処するためのコントリビューションを行っている。
最小限の仮定をしながら、クラス固有のMI-PLLのリスク境界を導出する。
我々の理論は、$sigma$が学習の不均衡に大きな影響を及ぼすというユニークな現象を明らかにしている。
論文 参考訳（メタデータ） (2024-07-13T20:56:34Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Out-Of-Domain Unlabeled Data Improves Generalization [0.7589678255312519]
本稿では,ラベルなしデータを半教師付き分類問題に組み込む新しい枠組みを提案する。
ラベルのないサンプルは一般化ギャップを狭めるために利用できることを示す。
我々は、さまざまな合成および実世界のデータセットで実施された実験を通じて、我々の主張を検証する。
論文 参考訳（メタデータ） (2023-09-29T02:00:03Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - How Does Pseudo-Labeling Affect the Generalization Error of the
Semi-Supervised Gibbs Algorithm? [73.80001705134147]
擬似ラベル付き半教師付き学習(SSL)におけるGibsアルゴリズムによる予測一般化誤差(ゲンエラー)を正確に評価する。
ゲンエラーは、出力仮説、擬ラベルデータセット、ラベル付きデータセットの間の対称性付きKL情報によって表現される。
論文 参考訳（メタデータ） (2022-10-15T04:11:56Z) - A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。
最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
論文 参考訳（メタデータ） (2022-02-11T03:01:45Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。