論文の概要: Optimistic Rates for Multiclass PAC Learning

• arxiv url: http://arxiv.org/abs/2608.10869v1
• Date: Tue, 11 Aug 2026 12:46:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-12 19:14:46.042089
• Title: Optimistic Rates for Multiclass PAC Learning
• Title（参考訳）: マルチクラスPAC学習における最適率
• Abstract要約: 最悪のマルチクラス境界は、最高の分類器が既にほぼ正しいときに小さくならない。 ナタラジャン次元のクラス $d_N$ と Daniely-Shalev-Shwartz 次元 $d_DS$ に対して、最適余剰リスクは2つのエンドポイントで知られている。 固定オラクルリスクが$Lstar$であれば、最適な過剰リスクは$widetilde(sqrtLstar d_N/n+d_DS/n)$で、アルファベットサイズは一様である。
• 参考スコア（独自算出の注目度）: 39.91890433860882
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk is known at the two endpoints ($d_{DS}/n$ realizable, $\sqrt{d_N/n}+d_{DS}/n$ agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk $L^\star$, the optimal excess risk is $\widetildeΘ(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size, attained by a learner that knows neither $L^\star$ nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-$k$ compression rule that empirically dominates a comparator $h$ has population risk at most $L(h)+O(\sqrt{L(h)Γ}+Γ)$ with $Γ=(k\log n+\log(1/δ))/n$, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed $L^\star$, by a pair-Assouad scheme calibrated to $L^\star$ and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best $r$-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor $r$ from the known realizable list lower bound.
• Abstract（参考訳）: 最良分類器が既にほぼ正しければ、最悪のマルチクラス境界は小さくならない。 ナタラジャン次元のクラス $d_N$ と Daniely-Shalev-Shwartz 次元 $d_{DS}$ に対して、最適余剰リスクは、2つの終点 (d_{DS}/n$ realizable, $\sqrt{d_N/n}+d_{DS}/n$ agnostic [HMZ24, CEH+26, Pab26]) で知られ、その間に開いている。 すべての固定オラクルリスク$L^\star$において、最適余剰リスクは$\widetildee(\sqrt{L^\star d_N/n}+d_{DS}/n)$、アルファベットサイズが一様であり、L^\star$も自信レベルも知らない学習者によって達成される。 上界は [CEH+26] のカバー-メニュー-圧縮アーキテクチャを、[Pab26] の縮約可能な速度で構成する: 新しいコンパレータ対応の相対圧縮定理: サイズ-$k$ 圧縮則は、比較器を経験的に支配するが、$h$ は、最大$L(h)+O(\sqrt{L(h)>)+O(\sqrt{L(h)>}+n$ の集団リスクを持ち、安定性のない$=(k\log n+\log(1/δ)/n$ を持つ。 下界は、固定されたすべての$L^\star$で、ペア・アスードスキームを$L^\star$に校正し、[BCD+22]のナタラジャン-ヴァース-DS分離の根底にある擬キューブ上のファイバー引数によって、1つのクラスと1つの分布の両項を強制する。 両方の定理はリスト学習にまで拡張される: 最高の$r$-tupleの仮説に対して、同じアーキテクチャと同じ2つのエンジンは楽観的な速度と同じ形状の下限を生じさせ、[Pab26] がリストのコンパレータに対して必要と期待する揺らぎ項を強制し、既知の実現可能なリストの下限から$r$を除去する。

関連論文リスト

• Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting [20.06940271479014]
  クラスごとの分解$I(X;Y)=sum_i_i D_mathrmKL(P_Y|i|P_Y)$を介して、Side-Channel Existence Theoremを$k$クラスに拡張します。 以下の3つの結果が従う: (1) 活性クラス全体の和形式 MI の下限、(2) カスケード臨界コスト定理と、一様予算境界が消滅する非ゼロ、(3) 精度 $mathrmAcc*
  論文  参考訳（メタデータ） (2026-09-06T00:48:40Z)
• Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
  2026年のエルツの単位距離予想とサウィンの量的洗練の反証は、固定正の$varepsilon$に対して、n$平面点の間の単位距離の最大値$u(n)$が$n1+varepsilon$を超えることを示す。 本稿では、Sawinのパラメータ選択を非線形整数最適化問題として扱い、素集合$T$と$S_Q$を含む証明書のためのオープンソースのPythonパイプラインを開発する。
  論文  参考訳（メタデータ） (2026-06-02T10:05:23Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals [38.241216472571786]
  標準的なマルチクラスパーセプトロンは,クリーンなラベルやガウスの限界を持つ場合でも,スーパーポリノミカルな多くのサンプルと更新を必要とすることを示す。 そこで我々は,誤差$O(mathrmopt)+$ for $k=3,エラー$mathrmpoly(k)mathrmopt+$ for geometryally regulark-class linear classifiersを開発した。
  論文  参考訳（メタデータ） (2026-05-20T17:19:30Z)
• Generalized $\mathbb{Z}_p$ toric codes as qudit low-density parity-check codes [5.692499671837265]
  ツイスト境界条件下での正方格子上の素次元四重項上の2次元変換不変CSS安定化符号について検討した。 最もよく観察された$k d2$は$p$で増加し、相互作用範囲がシステムサイズで大きくなると、$k d2 = 0.0541, n2ln p + 3.84, n$がBravyi--Poulin--Terhal型トレードオフと互換性を持つ。
  論文  参考訳（メタデータ） (2026-02-23T18:59:31Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• (Locally) Differentially Private Combinatorial Semi-Bandits [26.462686161971803]
  我々は,従来のマルチアーマッド・バンド(MAB)の拡張であるコンビニアル・セミバンド(CSB)と,より強力なローカル・ディファレンシャル・プライバシ(LDP)設定について検討した。
  論文  参考訳（メタデータ） (2020-06-01T04:23:27Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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