Fugu-MT 論文翻訳(概要): On the complexity of PAC learning in Hilbert spaces

論文の概要: On the complexity of PAC learning in Hilbert spaces

arxiv url: http://arxiv.org/abs/2303.02047v1
Date: Fri, 3 Mar 2023 16:16:11 GMT
ステータス: 処理完了
システム内更新日: 2023-03-06 14:22:13.633894
Title: On the complexity of PAC learning in Hilbert spaces
Title（参考訳）: ヒルベルト空間におけるPAC学習の複雑さについて
Authors: Sergei Chubanov
Abstract要約: ヒルベルト空間における凸多面体学習の観点から二項分類の問題を考察する。本稿では,分布の少なくとも1-varepsilon$を正しく分類する多面体学習アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of binary classification from the point of view of learning convex polyhedra in Hilbert spaces, to which one can reduce any binary classification problem. The problem of learning convex polyhedra in finite-dimensional spaces is sufficiently well studied in the literature. We generalize this problem to that in a Hilbert space and propose an algorithm for learning a polyhedron which correctly classifies at least $1- \varepsilon$ of the distribution, with a probability of at least $1 - \delta,$ where $\varepsilon$ and $\delta$ are given parameters. Also, as a corollary, we improve some previous bounds for polyhedral classification in finite-dimensional spaces.
Abstract（参考訳）: ヒルベルト空間における凸多面体学習の観点から二項分類の問題を考察し、二項分類の問題を減らすことができる。有限次元空間における凸多面体学習の問題は文献で十分に研究されている。我々は、この問題をヒルベルト空間のそれと一般化し、少なくとも 1 〜 \varepsilon$ の分布を正しく分類する多面体学習アルゴリズムを提案し、ここで $\varepsilon$ と $\delta$ が与えられた確率を 1 - \delta とする。また、圏として、有限次元空間における多面的分類の以前の境界を改善する。

関連論文リスト

Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文参考訳（メタデータ） (2024-04-29T15:04:07Z)
Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文参考訳（メタデータ） (2023-01-04T04:15:40Z)
Sobolev Spaces, Kernels and Discrepancies over Hyperspheres [4.521119623956821]
この研究は超球面文脈におけるカーネルメソッドの理論基盤を提供する。超球面上で定義されたカーネルに付随するネイティブ空間(再生カーネルヒルベルト空間)とソボレフ空間を特徴付ける。その結果,カーネルキュウチュアの直接的影響,最悪のケースエラーの収束率の決定,およびキュウチュアアルゴリズムの適用性の向上が得られた。
論文参考訳（メタデータ） (2022-11-16T20:31:38Z)
On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms [10.66048003460524]
構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
論文参考訳（メタデータ） (2021-02-11T21:28:55Z)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文参考訳（メタデータ） (2020-12-14T18:14:08Z)
Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文参考訳（メタデータ） (2020-06-25T19:59:24Z)
Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文参考訳（メタデータ） (2020-06-11T14:25:02Z)
Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
論文参考訳（メタデータ） (2020-06-08T17:59:11Z)
Kolmogorov Width Decay and Poor Approximators in Machine Learning: Shallow Neural Networks, Random Feature Models and Neural Tangent Kernels [8.160343645537106]
与えられたバナッハ空間の部分空間間のコルモゴロフ幅型のスケール分離を確立する。再現されたカーネルヒルベルト空間は、高次元の2層ニューラルネットワークのクラスに対してL2$-approximatorが貧弱であることを示す。
論文参考訳（メタデータ） (2020-05-21T17:40:38Z)
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文参考訳（メタデータ） (2020-04-16T16:12:10Z)

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