論文の概要: The Complexity of Finding Local Optima in Contrastive Learning

• arxiv url: http://arxiv.org/abs/2509.16898v1
• Date: Sun, 21 Sep 2025 03:21:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-23 18:58:16.027657
• Title: The Complexity of Finding Local Optima in Contrastive Learning
• Title（参考訳）: コントラスト学習における局所最適点探索の複雑さ
• Authors: Jingming Yan, Yiyuan Luo, Vaggos Chatziafratis, Ioannis Panageas, Parnian Shahkar, Stelios Stavroulakis,
• Abstract要約: 個別設定で$mathsfPLS$-hardness、連続設定で$mathsfPLS$-hardnessを証明します。 この結果から,アルゴリズムが様々なコントラスト学習問題の局所的最適解を見つけることは不可能であることが示唆された。
• 参考スコア（独自算出の注目度）: 18.910128965812124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Contrastive learning is a powerful technique for discovering meaningful data representations by optimizing objectives based on $\textit{contrastive information}$, often given as a set of weighted triplets $\{(x_i, y_i^+, z_{i}^-)\}_{i = 1}^m$ indicating that an "anchor" $x_i$ is more similar to a "positive" example $y_i$ than to a "negative" example $z_i$. The goal is to find representations (e.g., embeddings in $\mathbb{R}^d$ or a tree metric) where anchors are placed closer to positive than to negative examples. While finding $\textit{global}$ optima of contrastive objectives is $\mathsf{NP}$-hard, the complexity of finding $\textit{local}$ optima -- representations that do not improve by local search algorithms such as gradient-based methods -- remains open. Our work settles the complexity of finding local optima in various contrastive learning problems by proving $\mathsf{PLS}$-hardness in discrete settings (e.g., maximize satisfied triplets) and $\mathsf{CLS}$-hardness in continuous settings (e.g., minimize Triplet Loss), where $\mathsf{PLS}$ (Polynomial Local Search) and $\mathsf{CLS}$ (Continuous Local Search) are well-studied complexity classes capturing local search dynamics in discrete and continuous optimization, respectively. Our results imply that no polynomial time algorithm (local search or otherwise) can find a local optimum for various contrastive learning problems, unless $\mathsf{PLS}\subseteq\mathsf{P}$ (or $\mathsf{CLS}\subseteq \mathsf{P}$ for continuous problems). Even in the unlikely scenario that $\mathsf{PLS}\subseteq\mathsf{P}$ (or $\mathsf{CLS}\subseteq \mathsf{P}$), our reductions imply that there exist instances where local search algorithms need exponential time to reach a local optimum, even for $d=1$ (embeddings on a line).
• Abstract（参考訳）: コントラスト学習(Contrastive learning)は、$\textit{contrastive information}$に基づいて目的を最適化することで有意義なデータ表現を発見する強力なテクニックであり、しばしば重み付き三重項の集合として与えられる$\{(x_i, y_i^+, z_{i}^-)\}_{i = 1}^m$は、"正"の例よりも"負"の例である$y_i$に近いことを示す。 目的は、表現(例えば $\mathbb{R}^d$ または木計量への埋め込み)を見つけることであり、アンカーは負の例よりも正に近い位置に置かれる。 対照的に、$\textit{global}$ optima は $\mathsf{NP}$-hard であるが、$\textit{local}$ optima を見つける複雑さは、勾配ベースのメソッドのような局所的な検索アルゴリズムによって改善されない。 我々の研究は、離散的な設定(例えば、満足度の高い三重項)における$-hardnessと連続的な設定(例えば、トリプレット損失を最小化する)における$\mathsf{PLS}と$\mathsf{CLS}と$\mathsf{CLS}は、それぞれ離散的および連続的な最適化における局所的な探索ダイナミクスをよく研究した複雑性クラスである。 我々の結果は, 多項式時間アルゴリズム(局所探索等)が, 連続問題に対して$\mathsf{PLS}\subseteq\mathsf{P}$ (または$\mathsf{CLS}\subseteq \mathsf{P}$) でない限り, 様々なコントラスト学習問題に対して局所的な最適解を求めることができないことを示唆している。 不可能なシナリオでは、$\mathsf{PLS}\subseteq\mathsf{P}$ (または$\mathsf{CLS}\subseteq \mathsf{P}$) であっても、我々の減少は、局所探索アルゴリズムが局所最適点に到達するのに指数時間を必要とするインスタンスが存在することを意味する。

関連論文リスト

• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
  シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。 適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
  論文  参考訳（メタデータ） (2024-11-08T17:10:38Z)
• 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)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization [11.523746174066702]
  我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。 この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
  論文  参考訳（メタデータ） (2022-09-20T11:57:13Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)

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

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