論文の概要: An Optimal Agnostic PAC Algorithm

• arxiv url: http://arxiv.org/abs/2608.06363v1
• Date: Thu, 06 Aug 2026 17:57:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-07 15:25:20.997491
• Title: An Optimal Agnostic PAC Algorithm
• Title（参考訳）: 最適Agnostic PACアルゴリズム
• Authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy,
• Abstract要約: 2進リスクに対して$L$と$L*=min_hin HL(h)$を書き、統計的に最適なリスク境界を達成する学習者を構築する。 これにより、PACが任意の固定された$L*$で普遍定数まで学習する際の無知なサンプル複雑性が解決される。
• 参考スコア（独自算出の注目度）: 15.361702135159845
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<δ\le 1/2$, with probability at least $1-δ$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). \] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].
• Abstract（参考訳）: H\subseteq\{-1,+1\}^X$ を有限VC次元 $d\ge1$ の類とする。 L^*=\min_{h\in H}L(h)$と$L^*=\min_{h\in H}L(h)$と書くと、統計的に最適なリスク境界を達成する学習者を構成する: i.d.\ sample of size $n$, for every $0<δ\le 1/2$, with probability least $1-δ$, \[L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt {\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right)。 これは、Devroye, Györfi, and Lugosi の下位境界に一致する固定された$L^*$ の任意の定数まで学習する無知な PAC のサンプル複雑性(A Probabilistic Theory of Pattern Recognition, Springer, 1996)を解決した。

関連論文リスト

• The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences [4.588028371034407]
  我々は,データ分布の逆摂動が Cressie-Read divergence of order $k>1$ and radius $geq 0$ で制約されるような$0$--1$-lossのPAC学習について検討した。 VC次元が$d$の仮説クラスに対して、実現可能かつ非依存的なサンプル-複雑性は定数および対数的因子に密接な境界を定めている。
  論文  参考訳（メタデータ） (2026-08-05T10:53:13Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
  論文  参考訳（メタデータ） (2025-09-25T07:39:25Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。 本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
  論文  参考訳（メタデータ） (2022-09-06T23:37:31Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Memory-Sample Lower Bounds for Learning Parity with Noise [2.724141845301679]
  ノイズ下でのパリティ学習においてよく研究されている問題に対して、任意の学習アルゴリズムは、$Omega(n2/varepsilon)$または指数的なサンプル数を必要とすることを示す。 我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。
  論文  参考訳（メタデータ） (2021-07-05T23:34:39Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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