論文の概要: Optimal VC Dimension of Contrastive Learning with Margin

• arxiv url: http://arxiv.org/abs/2609.38834v1
• Date: Wed, 30 Sep 2026 02:54:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.059065
• Title: Optimal VC Dimension of Contrastive Learning with Margin
• Title（参考訳）: Marginを用いたコントラスト学習のためのVCの最適次元
• Abstract要約: コントラスト学習は$d$次元幾何表現を学ぶための成功パラダイムである。 コントラスト学習が高テクスト一般化品質の表現につながる理由を示す。
• 参考スコア（独自算出の注目度）: 11.677234237476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Contrastive learning is a successful paradigm for learning $d$-dimensional geometric representations from a collection of ``anchor--positive--negative'' triplets $(i,j^{+},k^{-})$, indicating that ``item $i$ is closer to $j$ than to $k$.'' Despite its success, understanding why contrastive learning leads to representations of high \textit{generalization} quality---beyond the often pessimistic predictions from PAC-learning---remains a central question. Recently, \citet*{alon2024optimal} proved that, for PAC-learning $d$-dimensional Euclidean representations of $n$-point datasets, $Θ(\min(nd, n^2))$ triplets are necessary and sufficient, while they posed as an open question whether their VC dimension bounds for the more realistic setting of \textit{contrastive learning with a margin} can be improved. For a margin parameter $α>0$, a triplet $(i,j^{+},k^{-})_α$ is satisfied by the embedding $φ:[n]\rightarrow \mathbb{R}^{d}$, if $\|φ(i)-φ(k)\|_2>(1+α)\cdot\|φ(i)-φ(j)\|_2$. In this work, we resolve their question by proving that the VC dimension of contrastive learning under any margin $α\in(0,1)$ is in fact $O(n/α^2)$, improving on the previous bound of $O(n\log(n)/α^2)$. We also establish that the bounds are optimal up to constant factors, by providing a matching lower bound of $Ω(\frac{n}{α^2})$ (the previously known lower bound was $Ω(\frac{n}α)$), for $α\geq \max(n^{-1/2},d^{-1/2})$.
• Abstract（参考訳）: 対照的な学習は、$d$の幾何学的表現を ``anchor-- positive-- negative'' の三重項 $(i,j^{+},k^{-})$ の集合から学習するための成功パラダイムであり、 ``item $i$ が $k$ よりも$j$ に近いことを示す。 「'その成功にもかかわらず、なぜコントラスト学習が高い「textit{ Generalization>」品質の表現につながるのかを理解することは、PAC学習からしばしば悲観的な予測に加えて、中心的な疑問を残している。 近ごろ \citet*{alon2024optimal} は PAC-learning $d$-dimensional Euclidean representations of $n$-point datasets に対して、$(\min(nd, n^2))$ triplet は必要かつ十分であることを示した。 マージンパラメータ $α>0$ に対して、三重項 $(i,j^{+},k^{-})_α$ は埋め込み $φ:[n]\rightarrow \mathbb{R}^{d}$, if $\|φ で満たされる。 (i)-φ(k)\|_2>(1+α)\cdot\|φ (i)-φ (j)\|_2$。 本研究では,任意のマージン$α\in(0,1)$のVC次元が実際に$O(n/α^2)$であることを証明することにより,従来の$O(n\log(n)/α^2)$の限界を改善した。 また、この境界が定数因子まで最適であるとも証明し、$α\geq \max(n^{-1/2},d^{-1/2})$に対して$Ω(\frac{n}{α^2})$(これまで知られていた下限は$Ω(\frac{n}α)$)$)の一致する下限を与える。

関連論文リスト

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。 我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
  論文  参考訳（メタデータ） (2026-05-22T12:22:20Z)
• 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)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning [6.416429054645991]
  近似の理論と応用は、最適化と強化学習の応用により、ますます関連性が高まっている。 本稿では, ステップサイズ$alpha>0$のSAを再帰で定義し, $$theta_n+1 = theta_n+ alpha f(theta_n,Phi_n+1)$$$, $theta_ninmathbbRd$と$Phi_n$をマルコフ連鎖とする。
  論文  参考訳（メタデータ） (2023-09-06T12:22:32Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• 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)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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