論文の概要: Testably Learning Polynomial Threshold Functions
- arxiv url: http://arxiv.org/abs/2406.06106v1
- Date: Mon, 10 Jun 2024 08:42:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-11 14:37:02.494275
- Title: Testably Learning Polynomial Threshold Functions
- Title（参考訳）: 検証可能な多項閾値関数の学習
- Authors: Lucas Slot, Stefan Tiegel, Manuel Wiedmer,
- Abstract要約: 本稿では,古典的不可知モデルの拡張として,テスト可能な学習の枠組みを紹介する。
特に、ハーフスペースを自然に一般化するしきい値関数(PTF)を考える。
私たちの結果は、テスト可能な学習と愚かさの関連の上に構築されます。
- 参考スコア（独自算出の注目度）: 1.6112718683989882
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Rubinfeld & Vasilyan recently introduced the framework of testable learning as an extension of the classical agnostic model. It relaxes distributional assumptions which are difficult to verify by conditions that can be checked efficiently by a tester. The tester has to accept whenever the data truly satisfies the original assumptions, and the learner has to succeed whenever the tester accepts. We focus on the setting where the tester has to accept standard Gaussian data. There, it is known that basic concept classes such as halfspaces can be learned testably with the same time complexity as in the (distribution-specific) agnostic model. In this work, we ask whether there is a price to pay for testably learning more complex concept classes. In particular, we consider polynomial threshold functions (PTFs), which naturally generalize halfspaces. We show that PTFs of arbitrary constant degree can be testably learned up to excess error $\varepsilon > 0$ in time $n^{\mathrm{poly}(1/\varepsilon)}$. This qualitatively matches the best known guarantees in the agnostic model. Our results build on a connection between testable learning and fooling. In particular, we show that distributions that approximately match at least $\mathrm{poly}(1/\varepsilon)$ moments of the standard Gaussian fool constant-degree PTFs (up to error $\varepsilon$). As a secondary result, we prove that a direct approach to show testable learning (without fooling), which was successfully used for halfspaces, cannot work for PTFs.
- Abstract（参考訳）: Rubinfeld & Vasilyan氏は最近、古典的不可知モデルの拡張として、テスト可能な学習のフレームワークを紹介した。
テスターが効率的にチェックできる条件によって検証が難しい分布仮定を緩和する。
テスタは、データが元の仮定を真に満足するたびに受け入れ、学習者は、テスタが受け入れるたびに成功する必要がある。
我々は、テスターが標準のガウスデータを受け入れる必要がある設定に焦点を当てる。
そこでは、ハーフスペースのような基本的な概念クラスは、(分布固有の)非依存モデルと同様の時間的複雑さで検証可能であることが知られている。
本研究では、より複雑な概念クラスを実証的に学習する費用がかかるかどうかを問う。
特に、半空間を自然に一般化する多項式しきい値関数(PTF)を考える。
任意の定数次数の PTF が過剰な誤差$\varepsilon > 0$ in time $n^{\mathrm{poly}(1/\varepsilon)}$ まで証明できることを示す。
これは無知モデルにおける最もよく知られた保証と定性的に一致する。
私たちの結果は、テスト可能な学習と愚かさの関連の上に構築されます。
特に、少なくとも$\mathrm{poly}(1/\varepsilon)$モーメントにほぼ一致する分布は、標準ガウスの愚かな等級 PTF のモーメントである(誤差$\varepsilon$まで)。
二次的な結果として、ハーフスペースでうまく使われたテスト可能な学習(愚かさを伴わない)の直接的アプローチは、PTFでは働けないことが証明された。
関連論文リスト
- Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。
それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
論文 参考訳（メタデータ） (2024-04-02T23:34:39Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - An Efficient Tester-Learner for Halfspaces [13.13131953359806]
本稿では、Rubinfeld と Vasilyan が最近定義したテスト可能な学習モデルにおいて、ハーフスペースを学習するための最初の効率的なアルゴリズムを提案する(2023)。
このモデルでは、学習者は、トレーニングセットがテストに合格するたびに、その出力仮説の精度がほぼ最適であると認定する。
論文 参考訳（メタデータ） (2023-02-28T18:51:55Z) - Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳（メタデータ） (2022-06-21T20:43:53Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。
テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。
以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-22T21:12:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。