論文の概要: Faster PAC Learning and Smaller Coresets via Smoothed Analysis
- arxiv url: http://arxiv.org/abs/2006.05441v1
- Date: Tue, 9 Jun 2020 18:25:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-23 14:10:44.055000
- Title: Faster PAC Learning and Smaller Coresets via Smoothed Analysis
- Title（参考訳）: 平滑解析による高速PAC学習と小型コアセット
- Authors: Alaa Maalouf and Ibrahim Jubran and Murad Tukan and Dan Feldman
- Abstract要約: PAC学習は通常、$n$アイテムから小さなサブセット(varepsilon$-sample/net)を計算することを目的としています。
スムーズな解析から着想を得て、クエリに対する強調誤差(最悪のケースではなく)を近似する自然な一般化を提案する。
- 参考スコア（独自算出の注目度）: 25.358415142404752
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: PAC-learning usually aims to compute a small subset
($\varepsilon$-sample/net) from $n$ items, that provably approximates a given
loss function for every query (model, classifier, hypothesis) from a given set
of queries, up to an additive error $\varepsilon\in(0,1)$. Coresets generalize
this idea to support multiplicative error $1\pm\varepsilon$.
Inspired by smoothed analysis, we suggest a natural generalization:
approximate the \emph{average} (instead of the worst-case) error over the
queries, in the hope of getting smaller subsets. The dependency between errors
of different queries implies that we may no longer apply the Chernoff-Hoeffding
inequality for a fixed query, and then use the VC-dimension or union bound.
This paper provides deterministic and randomized algorithms for computing
such coresets and $\varepsilon$-samples of size independent of $n$, for any
finite set of queries and loss function. Example applications include new and
improved coreset constructions for e.g. streaming vector summarization
[ICML'17] and $k$-PCA [NIPS'16]. Experimental results with open source code are
provided.
- Abstract（参考訳）: pac-learningは通常、$n$項目から小さなサブセット (\varepsilon$-sample/net) を計算することを目的としている。これは、与えられたクエリセットから与えられたクエリ(モデル、分類器、仮説)ごとに与えられた損失関数を近似し、付加的なエラー$\varepsilon\in(0,1)$となる。
coresetsはこのアイデアを一般化し、乗算誤差 1\pm\varepsilon$ をサポートする。
スムーズな解析から着想を得て、より小さな部分集合を得ることを期待して、クエリ上での(最悪のケースの代わりに)emph{average} の誤差を近似する自然な一般化を提案する。
異なるクエリのエラー間の依存関係は、Chernoff-Hoeffdingの不等式を固定クエリに適用しなくなり、VC-dimensionあるいはUnionboundを使用することを意味する。
本稿では,このようなコアセットと$\varepsilon$-samplesを,任意の有限個のクエリと損失関数に対して決定論的かつランダムに計算するアルゴリズムを提供する。
例えば、ストリーミングベクトル要約 [ICML'17] や$k$-PCA [NIPS'16] のための新しい改良されたコアセット構成がある。
オープンソースコードによる実験結果が提供される。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。