論文の概要: Optimal Sample Complexity of Contrastive Learning
- arxiv url: http://arxiv.org/abs/2312.00379v1
- Date: Fri, 1 Dec 2023 06:57:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-04 15:30:04.480669
- Title: Optimal Sample Complexity of Contrastive Learning
- Title（参考訳）: コントラスト学習の最適サンプル複雑性
- Authors: Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, Grigory
Yaroslavtsev
- Abstract要約: 比較学習の複雑さ、すなわち、高い精度を得るのに十分なラベル付き一般化の最小数について研究する。
我々は、任意の距離関数に焦点をあてて、様々な設定でサンプルの複雑さに厳密な境界を与える。
本稿では,VC/ナタラジャンによる試料の複雑さに関する理論的境界が,実験結果に強い予測力を持つことを示す。
- 参考スコア（独自算出の注目度）: 12.108926584457736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Contrastive learning is a highly successful technique for learning
representations of data from labeled tuples, specifying the distance relations
within the tuple. We study the sample complexity of contrastive learning, i.e.
the minimum number of labeled tuples sufficient for getting high generalization
accuracy. We give tight bounds on the sample complexity in a variety of
settings, focusing on arbitrary distance functions, both general
$\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal
bound on the sample complexity of learning $\ell_p$-distances for integer $p$.
For any $p \ge 1$ we show that $\tilde \Theta(\min(nd,n^2))$ labeled tuples are
necessary and sufficient for learning $d$-dimensional representations of
$n$-point datasets. Our results hold for an arbitrary distribution of the input
samples and are based on giving the corresponding bounds on the
Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further
show that the theoretical bounds on sample complexity obtained via VC/Natarajan
dimension can have strong predictive power for experimental results, in
contrast with the folklore belief about a substantial gap between the
statistical learning theory and the practice of deep learning.
- Abstract（参考訳）: コントラスト学習はラベル付きタプルからデータ表現を学習し、タプル内の距離関係を特定する、非常に成功した手法である。
コントラスト学習のサンプル複雑性,すなわち,高い一般化精度を得るのに十分なラベル付きタプルの最小数について検討する。
我々は、任意の距離関数、一般の$\ell_p$- distancesとツリーメトリクスに焦点を当てて、様々な設定でサンプル複雑性の厳密な境界を与える。
主な結果は、整数$p$に対して$\ell_p$- distancesを学習するサンプル複雑性の(ほぼ)最適境界です。
任意の$p \ge 1$に対して、$\tilde \Theta(\min(nd,n^2))$ラベル付きタプルは、$n$ポイントデータセットの$d$次元表現を学ぶのに十分であることを示す。
この結果は,入力サンプルの任意の分布を保ち,関連する問題のVapnik-Chervonenkis/Natarajan次元に対応する境界を与える。
さらに,VC/ナタラジャン次元を用いて得られたサンプルの複雑さに関する理論的境界は,統計的学習理論と深層学習の実践との実質的なギャップに関する民間伝承と対照的に,実験結果に対して強い予測力を持つことを示す。
関連論文リスト
- Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Sharper Bounds for $\ell_p$ Sensitivity Sampling [56.45770306797584]
まず, $ell_p$ 部分空間埋め込みを $p に対して高感度サンプリングする。
また、ルートレバレッジスコアサンプリングアルゴリズムは1leq p2$に対して約$d$を達成し、レバレッジスコアと感度サンプリングの組み合わせにより、約$d2/pmathfrak S2-4/p$を2pinftyで改善することを示した。
論文 参考訳（メタデータ） (2023-06-01T14:27:28Z) - The Sample Complexity of Approximate Rejection Sampling with
Applications to Smoothed Online Learning [29.44582058149344]
n$ の関数としての最適総変分距離が $tildeTheta(fracDf'(n))$ によって与えられることを示す。
次に、スムーズなオンライン学習という非常に異なる分野のアプリケーションを検討します。
論文 参考訳（メタデータ） (2023-02-09T14:20:14Z) - Tree Learning: Optimal Algorithms and Sample Complexity [10.638365461509]
任意の分布から抽出したラベル付きサンプルから,データの階層木表現を学習する問題について検討する。
本稿では,この問題に対する最適なサンプル境界を,学習やオンライン学習など,いくつかの学習環境において提示する。
論文 参考訳（メタデータ） (2023-02-09T08:35:17Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Sample Complexity of Adversarially Robust Linear Classification on
Separated Data [41.30425613353595]
対向的堅牢性を伴う学習の複雑さについて考察する。
非常に分離されたデータの場合、$o(frac1n)$の収束率は達成可能である。
論文 参考訳（メタデータ） (2020-12-19T22:04:59Z) - 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 the mapping $\mathbf{x}\mapsto \sum_{i=1}^d x_i^2$: the cost of
finding the needle in a haystack [6.436049723896002]
干し草の山で針を見つけるコストは,その関数のバロンノルムと関係があることが示される。
一般化ギャップのサイズを制御するために、d$が増加するにつれて、明示的な正規化の使用がますます重要になる。
論文 参考訳（メタデータ） (2020-02-24T21:58:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。