The Complexity of Finding Local Optima in Contrastive Learning
Authors: Jingming Yan
Yiyuan Luo
Vaggos Chatziafratis
Ioannis Panageas
Parnian Shahkar
Stelios Andrew Stavroulakis
Venue: NeurIPS 2025 poster ()
Keywords: contrastive learning
computational complexity
local search
PLS
CLS
reductions
Primary area: theory
TL;DR: We investigate the computational complexity of finding local solutions for many contrastive learning settings based on triplet constraints (anchor-positive-negative paradigm), and we prove that reaching local optima cannot be done in polynomial time.

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 $\text{\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).

The Complexity of Finding Local Optima in Contrastive Learning
Jingming Yan"!, Yiyuan Luo"?, Vaggos Chatziafratis loannis Panageas
Parnian Shahkar', and Stelios Stavroulakis'
University of California, Irvine
2 University of California, Santa Cruz Archimedes AI
Abstract
Contrastive learning powerful technique for discovering meaningful data representations by optimizing objectives based contrastive information, often given as a set of weighted triplets {(x,, y." 2, )}m indicating that an "anchor" æ is more similar to a "positive" example y; than to "negative" example 2.. The goal is to find representations (e.g., embeddings in IR or tree metric) where anchors placed closer to positive than negative examples. While finding global optima of contrastive objectives is NP-hard, the complexity finding local aptima--rprrssentaiion that do not improve by local search algorithms such gradient-based -reannsss open. Our work settles the complexity of finding local optima in various contrastive learning problems by proving PLS-hardness in discrete settings (e.g.. maximize satisfied triplets) and CLS-hardness in continuous settings (e.g., minimize Triplet Loss), where PLS (Polynomial Local Search) and 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 PLS for continuous problems). Even in the unlikely scenario that PLS C P (or CLS S P), our reductions imply that there exist instances where local search algorithms need exponential time to reach a local optimum, even for d (embeddings on a line).
(or CLS P
Introduction
Extracting meaningful representations from complicated datasets is a cornerstone of machine learning. For the past decades, algorithmic questions of how to find convenient representations (Euclidean space, tree metrics, etc.) faithfully capturing distance relationships have been at the forefront of metric embeddings and multidimensional scaling [Kruskal, 1964a, Borg and Groenen, 2007, Indyk et al., 2017], yielding by now vast literature with both practical successes and deep mathematical insights.
Due to the high cost of labeling datasets and obtaining accurate distances, many communities focus instead on learning representations based on easier-to-obtain contrastive information, i.e., distance comparisons [Agarwal et al., 2007, Tamuz al., 2011, Jamieson and Nowak, 2011, Van Der Maaten and Weinberger, 2012, Terada and Luxburg, 2014, Jain et al., 2016, Kleindessner and von Luxburg, 2017]. Contrastive information, like "item & is closer to item y than z" or "among 2r, y, items x, are farthest apart" is much easier to obtain than numerical values ("how similar is to y"",, essentially creating pseudo-labels with little learning, c.g., the popular "anchor- "anchor-positive positive-neaatiiee paradigm (I, yt, [Schroff et al., 2015],
supervision. Indeed, such triplets are standard in contrastive
"Equal contribution. Corresponding authors jingmyl @uci.edu, yluo uesc.edu.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

since image transformations (cropping, rotations) or nearby words produce anchor-positive pairs, and random images/words yield unchor-negative pairs (see also "hard negatives" [Robinson et al., 2020]).
Contrastive Information
Types of Representations Types of Local Moves
"c is closer to than x"
x0, are farthest apart"
Rd embedding
move point in IR
LCA v,
of
"2r closer to than 2"
rooted binary tree
relocate leaf in the tree
Figure 1: An overview of contrastive learning problems studied here (LCA: lowest common ancestor).
Interestingly, even though contrastive information lies at the heart of contrastive learning pipelines, the history of using ordinal information, i.e., comparisons instead of absolute numerical values, dates back to the 1960s psychometries and (non-metric Thurstone, 1954, Kruskal, 1964b]. Since then, ordinal embeddings (also monotone or contrastive embeddings [Bilu and Linial, 2005, Avdiukhin et al., 2024, Chen et al., 2022, Chatziafratis and Indyk, 2024]) are widely-studics in computer science, because important applications (nearest-neighbor, recommendation, ranking, crowdsourcing) only care to preserve the relative ordering of distances (not lengths) [Agarwal et al., 2007, Bădoiu et al., 2008, Tamuz et al., 2011, Vankadara et al., 2019, Ghosh et al., 2019].
multi-dimensional scaling [TToreesonn, 1952,
Despite empirical successes, various aspects of contrastive learning are not well-understood. To address this, works on theoretical foundations have focused on generalization [Alon et al., 2023], inductive bias [Saunshi et al., 2022, HaoChen and Ma, 2022], latent classes [Saunshi et al., 2019]. hard negatives [Robinson al., 2020, Kalantidis et al., 2020, Awasthi et al., 2022], multi-view redundancy ['oss et al.. 2021], mutual information [Oord et al., 2018, Hjelm et al., 2018] and more.
Optimization of contrastive objectives. Our paper focuses on optimization aspects of contrastive learning with widely-used objectives, both in discrete and continuous settings (Figure 1). The input set C of m triplets ((1a, v/= 2; } importance of each constraint (see [Robinson et al., 2020, Kalantidis al., 2020] for benefits "hard negatives" which are difficult to distinguish from anchor points). The task is to find representation f(.) respecting the given constraints as much as possible by optimizing Objectives 2, below:
dataset S, with non-negative weights w; 2 0 indicating the
1. Triplet Maximization in Rdd Many algorithmic works in contrastive embeddings, aim maximizing the weight of satisfied triplets. We say that a triplet (z,, y," 2, is satisfied by the embedding f(-). if (x:) fl,)) [.f));) (21)]l2 Even the case of d = 1 (line embedding ranking) is well-motivated and non-trivial [Arora et al., 1995, 2002, Guruswami et al., 2011 Fan et al., 2020].
2. Triplet Maximization trees: Here, we map data onto leaves of tree T maximizing the weight of satisfied triplets (distr(x,, y4) S dist (æ,, 2,), or equivalently, has a subtree containing xy. Vi- but not 2;). Such hierarchical clustering problems known as triplet reconstruction consistency naturally appear across areas [Aho et al., 1981, Byrka et al., 2010, Vikram and Dasgupta, 2016, Bodirsky et al., 2017, Chatziafratis et al., 2018, Emanjomeh-Zadee and Kempe, 2018].
Minimize Triplet Loss in Rd: The influential FaceNet paper [Schroff et al., 2015] introduced the Triplet Loss, which has since evolved into one of the most prominent contrastive losses:
C(C, = Σ WrL,, where L, == (1xxfl) - f(v))l1 llf(x)) - +
+ a3
The margin a specifies the minimum gap of distance (I;, y/) and (a,, 2,) and wy the importance of triplet. This loss "pushes" positive pairs close together while keeping negative pairs far apart.

---

Our primary motivation is to understand the complexity of finding representations based on con- trastive information. Unfortunately. NP- NP-hardness results prevent us from finding globally optimum representations in the worst-case, and so in practice, local search algorithms are deployed. Local search is general algorithmic approach that examines improving moves from a set of allowable nearby configurations to the current solution (most notably gradient-based methods and various heuristics in discrete optimization [Orlin et al., 2004)). We ask the following basic questions:
Motivating Questions:
How hard is it find a locally optimum representation for contrastive learning? Can we find a local optimum in polynomial time? How efficient is local search?
In this context, a locally optimum representation is one that cannot be improved by taking further steps of gradient-based methods, or generally any type of local search algorithm.
1.1 Our contributions
Our main contribution is to formally study the above questions from the lens of computational complexity, and give strong evidence that for many problems with contrastive objectives, even finding a locally optimum solution for the objectives is intractable in specific formal sense. Local search is a widely-used heuristic for many NP-hard problems [Lawler, 1985, Schäffer and Yannakakis, 1991, Abuja et al., 2002, Orlin et al., 2004], wherein we iteratively perform local moves (e.g., gradient step or reassignment of points) that get better objective value, terminating at solution with no improving move, i.c., local optimum. Of course, local optimum need not be a global optimum, and since there are more local optima than global optima in general, local optima may appear easier to find. Nevertheless, there is currently of the contrastive objectives 1, 2, 3; indeed, it is not even clear whether there is a polynomial -ime algorithm for computing local optimum. Our main result is to show that no such polynomial-tin algorithm exists (unless there is an unlikely collapse of complexity classes, see below). Moreover, an unconditional consequence of our reductions, is that there exist contrastive learning instances where local search algorithms (including gradient-base methods) require exponential time before reaching local optimum. To the best of our knowledge, we the first to formally investigate the complexity of local solutions in contrastive learning objectives.
overall lack of theoretical guarantees regarding local optimization
Proving hardness of local optima. The remarkable theory of NP-hardness was developed to understand the difficulty of computing the value of global optimum in optimization problems. Hence, NP-hardness is not suitable to describe local optimality, which corresponds to fixed points of local search algorithms. Johnson, Papadimitriou, and Yannakakis [1988] initiated the complexity-theorete study of discrete local search problems by defining the complexity class PLS (Polynomial Local Search), and later, Daskalakis and Papadimitriou [2011 1] defined the class CLS (Continuous Local Search) for continuous local search problems. Due to the significance of computing fixed points, both PLS and CLS have played prominent role in optimization and algorithmic game theory. For example, computing a pure Nash equilibrium in congestion games is PLS-hard [Fabrikant et al., 2004], and it was recently shown that computing a Marrsh-Kuhn-Tuckeee point (fixed points of gradient-descent of a quadratic program is CLS-hard [Fearnley et al., 2024]. Surprisingly, even though PLS and CLS were originally defined with very different problems in mind, recent breakthrough [Fearnley. Goldberg, Hollender, and Savani, 2023] established a deep connection between them. i.c.. that CLS PLS n PPAD. Building on it, Babichenko and Rubinstein [2021]. Anagnostides et al. [2023], Ghosh and Hollender [2024], Anagnostides et al. [2025] have shown that broad classes of games, including congestion games and adversarial team games, are captured by CLS. Beyond games, for connections of PLS and CLS to cryptography, see Bitansky and Gerichter [2020]. Hubácek and Yogev [2020]. Our work provides formal evidence of computational intractability of finding local optima in contrastive learning:
Theorem (Abridged; see Theorems 3.2, 3.3, 3.4, 4.1). Triplet maximization problems 1, 2 are PLS-hard, i.e., every problem in PLS efficiently reduces to them. The Triplet Loss minimization problem 3 is CLS-hard, i.e., every problem in CLS efficiently reduces to it. As corollary. assuming the widely-believen PLS & P and CLS & P, no polynomial time algorithm (local search or otherwise) can find local optimum of objectives 1, 2. 3. Even PLS C P or CLS C P. there exist instances where local search (including crudient-methodd
require exponential time to reach a local optimum.
*PPAD captures computation of mixed Nash equilibria, see celebrated work of Daskalakis et al. [2009].
3

---

In this sense, one Formal statements are in Section 3, 4. As is common in complexity, polynomial time refers to algorithms whose runtime polynomial in the imput size (provided in binary representation). Our results also extend to approximate local optima (solutions within a small O from local optimum).
Challenges and proof ideas. The consequence of proving that problem is PLS-hard (or CLS-hard) is that in certain precise sense, such problems are as hard as any other local search problem where the goal find local optimum. Here, local optimality is defined with respect to a generic definition of a local search algorithm [Johnson et al.. 1988, Daskalakis and Papadimitriou, 2011]. The main technical challenge in all works establishing hardness results is how to do PLS-reductions (or CLS (LS-reduciions). Roughly speaking, these are special type of efficient transformations between problems, that preserve local optimality: the intuition is that starting from an already-know hard problem, and using a PLS-reduction to another problem, e.g., the contrastive objectives above, then any efficient algorithm that purportedly finds a local optimum of the latter, would in fact compute a local optimum of the original knowwn-t--e-hardd problem. Contrast this with the common NP-reductions that are only required to preserve the value of global optima, ignoring how local solutions are being altered.
Our results provide PLS-reductions from the LOCALMAXCUT problem [Schäffer and Yannakakis, 1991] (see Section 2 for definitions) the maximization of satisfied triplets (Obj. 1, 2). and a CLS-reduction from QUAdRATICPROGRAA KKT [Fearnley et al., 2024] to the Triplet Loss (Obj. 3). Our PLS-reductions rely on novel gadgets that allow us to encode graph cuts and local (vertex) moves via triplet constraints and embeddings in Euclidean space, trees or even the line (for the case of rankings). Our gadgets impose a series of "heavy" contrastive triplet constraints on a special set of "boundary" points, thus ensuring they are not allowed to move back and forth, otherwise the objective value would drift away from any local optimum. After an embedding is performed, the two sides of the graph cut can be formed by looking at which nodes were placed to the "left" or "right" of the boundary points. Regarding our CLS-reductions, we encode and recover KKT stationary points of quadratic programs min x Qx + b x, by finding local minima of Triplet Loss, even if the representation f()) comes from simple linear embedding model parameterized by 0 E [0, 1) such that fx( = 0 x. Towards this, we first break the quadratic form into triples of variables t, = E [0, 1] and we generate a specially crafted collection T of contrastive triplets (I;, 27. ) where Fe, Jj Th are coordinates of However, contrastive constraints introduce dependencies among their shared variables and to deal with the interacting terms, we introduce groups of contrastive triplets with carefully chosen weights that depend on the coefficients of the quadratic form.
2 Preliminaries
2.1 Discrete objectives in contrastive learning and PLS
Johnson al. [1988] defined PLS to describe local search problems. A problem IT is in PLS if the following three polynomial-time algorithms exist: (i) the first algorithm, given an instance of II. it outputs an arbitrary feasible solution S, (ii) the second, given S. it returns a number which is the objective value of the feasible solution, and (iii) the third, given S, it either reports "locally optimal" or produces better solution. Implicit in the definition the fact that feasible solutions have polynomially many neighboring solutions (the third algorithm is polynomial-time can think of PLS as problems with efficient verification of local optimality.
Definition 2.1 (PLS-reduction), A PLS-reduction from problem 11, to problem 1lg is two polynomial- time algorithms: (i) the first algorithm A maps every instance x of 11, to an instance A(x) of 11g, and (ii) the second algorithm B maps every local optimum of A(x) to local optimum of z.
PLS-reduction ensures that if we find a local optimum for II2 in polynomial time then, we could also find a local optimum for 11, in polynomial time. A problem is PLS-hard if every problem in PLS can be reduced to it. In complexity, it is widely-believed that PLS & P. hence there is no polynomial-time algorithm for computing local optimum of a PLS-hard problem. Interestingly, Schäffer and Yannakakis [1991] proved many natural problems are PLS-hard, including LOCALMAXCUT:
MAcAL Problem.
INPUT: : A weighted undirected graph G(V, E) with a non-negative weight w. 2 0 for each edge.
Both PLS and CLS can be equivalently defined with arithmetic circuits [Fearnley al., 2023]

---

OUTPUT: A partition () of the vertices V in two nonempty sets, such that no vertex v can increase the value of the cut, i.e., the sum of weighted edges cut, by switching sides.
We now define widely-used (discrete) objectives of maximizing satisfied contrastive constraints. To simplify notation, from
drop the signs and simply write (2,, V/s 2,) for contrastive triplets.
All embeddings here map a set of n items to non-overlapping points of a metric space of dimension d S
DOCAA.COTRRATTVV-EECC...
Problem.
Set V of n vertices, together with m contrastive triplets { Vs. } ) where 2i, Ds. E V (we dropped the +/- signs for lighter notation), and target dimension Each triplet has non- negative weight wi 2 0.
INPUT:
OUTPUT: An embedding f V - Rd such that" no vertex e can increase the value of the embedding by switching its location in Rd. We say triplet (2;, Vi. 25) is satisfied by f()), ), if xx is placed closer to y, than to 2,, i.e., (x,, f(w))l2 S (x,) - [(=,)le The embedding's 's objective value is
-== Wy (x.. where 1 (2),)))))) 1 if the constraint satisfied by f(-), and 0 otherwise.
m
"The output embedding is computable in polynomial time in [V] and the description of weights.
LOCAA.CONTAASTIVE-TII
Problem.
INPUT: : As above, set V with contrastive triplets ((z,, Mi, xx) Jmm (non-negative weights w, 2 0). OUTPUT: A hierarchical clustering, i..,, a binary rooted tree T with [V] leaves, and 1-to-1 mapping from V to the leaves of T, such that vertex
increase the value of the tree by switching to another location in the tree T (for each v in T. there are exactly | 3 other candidate locations). We say triplet (31,, Ut, 24) is satisfied by T, if 2; is placed closer to yi than to 2,, i.e., if there is subtree in T containing 24, Vr but not 2; (this is equivalent to dist (2;, Ui) S distr((s, zi) for an ultrametric distance on T). The tree's objective value is Em W 1 (x..01))))
Moreover, we examine scenarios where provided contrastive information is of the form "among x. y, 2, items v, are farthest apart" (instead of indicating that "item x is closer to y than to z²). Already for I-dimensional embeddings, such constraints give rise to BETWEENNESS, a well-studied ranking problem in approximation algorithms [Arora et al., 2002, Charikar et al., 2009, Austrin et al., 2015]. Problem.
INPUT: : Set V with betweenness triplets {(,,, Ui ) each with non-negative weight uy 2 0. and target dimension d.
OUTPUT An embedding f V + Rd such that no vertex e can increase the value of the embedding by switching location in IRd, We say triplet (Ia, Vis zi) satisfied by f()). if 25 and are placed the farthest apart (equivalently,
is "between" z; and 2,), i.e., [f(zz) f(z))l 2 max (1.f f(::) f(2))f(())lll lla)) The embedding" objective value is >/= w 1 (mpan)))))
"The output embedding is computable in polynomial time in [V] and the description of weights.
Even though we defined problems in their general form, our PLS-hardness results also hold for interesting special cases: we show
in dimension d' [Bädoiu et al., 2008, Alon et al., 2008, Fan et al., 2020] and LOCAL BEwCEAEeEEEEEESSEEEEL...
with d = [Arora et al., 2002, Charikar et al., 2009, Austrin et al., 2015] are PLS-hard. For trees, COCALLONTRASTIVEEES [Byrka et al., 2010, Chatziafratis and Makarychev,
is also known as triplet reconstruction/consistere 2023], and in terms of approximating the globally optimum solution several results and connections to other hierarchical clustering objectives are known [Chatziafratis et al., 2021, Naumov et al., 2021, Charikar al., 2019, Chami al., 2020, Moseley and Wang. 2023, Vainstein et al., 2021]. For other extensions, see Appendix C.
2.2 Continuous objectives in contrastive learning and CLS
Daskalakis and Papadimitriou [2011] proposed CLS study local search for continuous objective functions, most notably search problems that can be solved by performing Gradient Descent. CLS has played an important role in game theory and optimization, and a recent breakthrough showed that CLS = PPAD n PLS [Fearnley et al., 2023]. The natural problem of finding KKT points in quadratic programs was recently shown be CLS-hard [Fearnley al., 2024] and we will reduce finding local minima of the Triplet Loss [Schroff et al., 2015J.
5

---

SMADRATTCPROGRAM-KKE Problem.
INPUT: : A symmetric matrix Q E _gax= and vector E R"
OUTPUT:
Compute a local optimum (i.e., KKT point) for the quadratic mingeeuu.1 T Q bTa
Problem.
INPUT Set V (A, B of points in R set of triplets (æz, y, 2) of weight w 0, margin 0.
OUTPUT Find an embedding f V - [o, 1]d that is first-order stationary point for the minimization objective given by the triplet-loss:
Σ w max {11((z) ( [I]()) s(=) 0,,0-
(m.y==)CC
'The output embedding f' is computable in polynomial time the description of the input set V and the weights.
Recall, first-order stationary points are fixed points of gradient descent: x" X' is first-order stationary point of g(x), Vo E X' we have (x x², Vag(x*)) 2 (X:: convex, compact domain).
We emphasize the role of the two pivot points A, B in the definition. Notice that if we did not have pivot points, then the embedding that maps all points from V the all-zeros vector would be trivial first-order stationary point. Moreover, if we had only I pivot A, then again mapping every point in V to A would result in a first-order stationary point of the Triplet Loss. Thus having two pivot points are necessary and sufficient to make the problem non-trivial.
3 PLS-hardness for discrete objectives in contrastive learning
LOCAL..OTTASTIVEETR... where the goal is to find local solutions for maximizing weight of satisfied triplets. We start with Euclidean embeddings, then have results on trees.
In this section we present our results for SaAA..oORRSSTIV-EUUUUII Bww..BerwEENNNSs-BBi..
3.1 The case of embeddings in Rd with d =
To set some notation and convey the key ideas for our later proofs, start by presenting reductions for the case of I-dimensional embeddings, since our reductions for the general case are more involved.
Theorem 3.1. LocALCCoNRASTIVS--ECCUUD... even for embedding dimension 1, is PLS-hard.
with == 1. Let G (V, be an undirected graph with edge-weights w 2 0. Let W == Σ (u,)) Wae be the total weight. Moreover, let M = W + and M' = (2]V) + 1)M denote two heavy weights. For our reduction, we introduce three special vertices X, Y. (we use capital letters to distinguish them from the vertices of G). Eventually, the input to the LOCALCoNTER CONAAACSOTTAAAAVEEEACCCC EUCCLDEAN problem will be V U { (X, Y, 2} together with collection m = |E] + 2| [|+|+ contrastive triplets. Our goal is show how our constructed instance.
Proof. We present PLS-reduction from LOCAl
recover locally maximum cut for G, from locally maximum embedding of
We add the following two types of contrastive triplet constraints:
Type A ("edge" triplets). For every edge (u, v) E E' with weight Wwe. add single triplet (u, X x +.))) with weight Wan. This incentivizes embeddings put closer X than e.
Type ("boundary" triplets). We add the following:
For every vertex v E add (X, y+ 2,277 with weight M.
For every vertex a E V, add (X, ** Z with weight M.
Finally, add (Y, z X with weight M', and (X, ++ --) also with weight M''
In total, this creates m E + 2 contrastive triplets on V U Y,
First, observe that because of the heavy- weight triplets (X, y+ 2-) and (Y, 7+ X-), any locally maximum embedding must satisfy those two triplets: any of those two triplets was violated, we can always satisfy both simultancously by moving Z and forcing either the order X < Y Z or

---

2<Y < X, with distances |X - Y| Y 2), thus gaining at least M' while losing at most 2 + E(u,o)E Wan M', which would contradict local optimality.
Next, we show that in any locally maximum embedding, all (X, ,+, and (X, u². Z are satisfied, meaning that each V must lie on one of two line segments YZ Y Z', where Y and Z' are the reflections of Y and Z with respect to X respectively (see Figure 2). Note that Y Z' are only used for the analysis and they not part of the reduction. If any (X, y 0T) or (X, (X,"t, --) violated, we can always satisfy both by moving to segment Y or to Y'z', thus gaining at least M while losing most D(..)EE Way M
((,
Wue 1.
Z'
Y
Z
Figure 2:
Reduction (d = 1): Any local optimum places v E V in segment Y or its reflection Y'Z'.
Finally, it is clear that (2, -) is satisfied if and only if u and v are placed on different sides of X. This encodes solution to the LOCALMAXCUT instance, by defining one side of the cut (S,3) to be all vertices placed segment Y Z and the other side to be the remaining vertices.
3.2 Hardness for general d-dimensional embeddings
Extending the above proof, our two results for general Euclidean embeddings are: Theorem 3.2. For every fixed dimension d 2 1, LoCA..COTE.SSIVEEEUCcum is PLS-hard.
Theorem 3.3. For every fixed dimension d 2 1, Bww.BBerwEENNSS-EEUUIEEEE is PLS-hard.
All proofs can be found in the Appendix A. Due to space constraints, we give the proof for BEL.LEETEENNESS-UUULDEDEEEE for the case d = 2. Similar gadgets are used to prove Theorem 3.2.
Proof of Theorem 3.3 (d 2). Our PLS-reduction is from LOCALMAXCUT. As previously, let G (V, F.) be undirected graph with edge-weights 2 O. Let W = E(Cw,)E Ways and let M W + denote heavy weight. For our reduction, we introduce two special vertices X1, X2. Our goal is to show how we can recover a locally maximum cut for G, from a locally maximum embedding of our constructed instance. We add the following two types of contrastive triplet constraints:
Type A ("edge" triplets). For each edge (u, v) E E with weight Wa.. add a single triplet (u, X1, v) with weight Wae- Geometrically, the semantics of the triplet in is that the pair is the farthest distance apart, i.e., the largest edge in the triangle formed by u, X1, U is the edge v).
Type ("isosceles" triplets). For each v E V, add two triplets (X1, X2, v) and (X2, X1, , v). each with weight M. Intuitively, because of the heavy weight, this forces X1.X2, form an isosceles triangle, such that ||v X1lla |/ - X2lla 2 2 ||X Xall2, where we overload the notation v, X1. X2 to also denote the vertex embeddings the 2D-plane.
Observe that in any local optimum, all "isosceles" triplets must be satisfied. If any "isosceles" triplet involving v is unsatisfied, we can always satisfy it by moving v to form the corresponding isosceles triangle, thus gaining at least M while losing at most Σ Wne < M, which would strictly increase the objective value. This effectively forces every vertex to lie on one of two rays (see Figure 3).
X1
X1
X
X2
Figure 3: Reduction (d (d=2) 2) for LLCN.BBEEEENENs-EECL.DD... onto two opposing rays. Left: (u, X1, v) is not satisfied when u and v lie on the same ray. Right: (u, X1, v) is satisfied when u and v lie on different rays.
Type B triplets force all v E V

---

Next, we show that in any locally maximum embedding for LOCALBEETEEENESS-EEUUCCC an "edge" triplet (u, x,,) u) is satisfied if and only if and v are on opposite rays. To see this, let us analyze the triangle AuX1u:
u and v are on the same ray, we have ZuX1e v < 30 Basic trigonometry tells us uv cannot be the longest side of the triangle, thus (u, X1, v) is satisfied.
If u and v are on opposite rays, we have LuX,v 120%. Basic trigonometry tells us we must be the longest side of the triangle, thus (u, X1, v) is satisfied.
Therefore, the configuration of a locally maximum embedding encodes a local max cut for G. We can easily recover the cut (S, 5) by checking whether each "edge" triplet (u, X1, is satisfied the configuration, c.g., S can be all vertices in one ray.
3.3 Hardness of tree embeddings
Theorem 3.4. The LoCA.CoNTRAATIIVETTEE problem is PLS-hard.
We do PLS-reduction from LOCALMAXCUT. Given graph G(V, E), construct triplets over nodes V U XX, Y, 2} for special nodes XX, ZJ. The triplets are as follows:
Proof Sketch. Sketch.
Type A triplets: XX' XX') ZZ, and XX' for v V, each with weight EeEF We.
Type B triplets: XY 2 with a large weight V EeEE We + |V| +
Type C triplets: Yu|X and Zu|X for all v V, each with weight EeEF We +
Type D triplets:
uX|r and eX/u whenever (u, v) E E, each with weight 12.
The purpose of the special vertices and the constraints that they force the tree to look as in Figure 4: X, X' are siblings, and any other vertex E V is either in subtree Ty containing Y or subtree Tz containing Z (because of heavy Type C triplets). Then, the solution to LoCALMAXCUT can be formed by all nodes that fell in Ty one side of the cut, and Tz the other side. The proof proceeds by a case analysis showing that this is indeed a local max cut, and that no vertex can increase the weight of the edges by moving to the other subtree (for full proof, see Appendix B).
Z
YY
X
X"
Figure 4: Reduction for LOCALLONNTASSTIVE-TREES
4 CLS-hardness for continuous objectives in contrastive learning
Theorem 4.1. For every dimension d 2 1, LocasTRrrLarLLs-EEcccme is CLS-hard.
Proof Sketch. We present the key idea for the case = with two pivot points A and B = 1/2. The full proof is in Appendix D. We give CLS-reduction from DUADRATICCROOGANN-KKK The key idea is that we can use triplets of the form (x. y. 2) to simulate the quadratic function. For now, imagine we had as representation function f(-) the identity function. Then, given triplet constraint (x, y, 2) with weight w will contribute the following term to the overall Triplet Loss:
C(x, 2) w mmx - y)² (x 2)² + +a, 0}.
8

---

Our proof first breaks the given quadratic program into smaller quadratics on three variables at a time:
q 3. = cı + c2y² + c3z² + c4zy + Czaz + cayz + Cy + c&y + Cg
We then show how to generate a set of m carefully chosen triplets [(r;, yi, ) with appropriate weights wy so that the total triplet loss L is the same as the quadratic program. It easy
that for terms depending only on one variable such as cj=² or Cgty, we can easily generate them by using a triplet (for example, triplet (0, z; ( allows us generate the quadratic term x² and triplet (y, 0, +) generates the linear term y). However, the main obstacle is that for the cross-terms like xy we need to use triplct (z, 0, y). and this introduces dependencies among the different triplets since there are shared variables. To overcome the difficulty of interacting terms, we need to introduce total of 12 contrastive triplets on 2, y, 2, whose corresponding weights depend on the coefficients of the given quadratic. By solving a linear system for the weights, we obtain loss [(z, 2) that equals g( y, 2).
Using these ideas, we can prove hardness under the framework of contrastive learning [Schroff et al., 2015], even for the case where the representation f(.) is a linear model parameterized by E [0, 1)" such that fo = 0 x. Here a is the sampled input to the linear model, f(x) is the output of the linear model. For any input o;. denote a, (0) = e x; to be the output of the linear model. We aim to find local solutions of the triplet loss problem:
min [E
Σ (5.1.)
Wiij max ((as (0) - a0)) (a:(0) au (0))² + a,
We set and let Φ; e, be the 7th standard basis, then (0) = 0 [0, 1]. The result follows from the case with d = 1.
5 Experimental verification: hard examples for local search
Our theoretical results establish worst-case hardness for finding local optima in several contrastive objectives. Here, we provide an experimental illustration that this indeed can happen by constructing instances where local search takes exponential time. By using our reductions from LOCALMAXCUT, we create hard instances for various other contrastive problems, namely DOCALCONTRASTIVE-ITT
and LOCALBETTEENNESS SENNEEEEENNNSSEEELDDEEAS and we measure the runtime of
local search.
Our starting point a hard instance for the LOCALMAXXUT problem due Monien and Tscheuschner [2010]. This instance is bounded-degree graph with maximum vertex degree 4, where any flip-based local search algorithm (initialized from a specific initial cut) will require exponentially many iterations to reach a local optimum. Flip-based local search algorithms attempt to move one vertex at time from its current position to another position, while trying to improve the objective. Our reductions transform this instance to the various contrastive objectives mentioned previously. In fact, reductions when applied to the hard instance LOCALMAXXUT preserve the local search structure and the changes in the objectives exactly. As we verify, the same exponentially-slon path towards a local optimum exists in all of the transformed instances. In particular, to validate our findings, we implemented local search for LOCALMAXCUT, LocaL BETWENNSSS -ECLLIDEE and LONAA observed exactly the same local search dynamics (i.e., the same improving moves were performed). As consequence the iteration counts on the corresponding instances are identical. We summarize the results in Figure 5 and provide the detailed statisties in Appendix E.
well as for the three problems LOCAL EUCLLIDAN Interestingly, in all four cases, we
Finally, we observed that we start from a random configuration, local search usually converges quickly, suggesting that the hard instances of Monien and Tscheuschner [2010] are sensitive to the choice of the starting point. However, understanding whether random initialization (or other strategies) is generally sufficient to avoid such worst-case dynamics remains open question.
Conclusion
In this work, we provided strong evidence that computing local optima for various contrastive learning objectives computationally intractable the worst case. To do so we relied on the well-studied complexity classes PLS and CLS and we presented series of reductions from difficult problems

---

100000
80000
itrations
60000
40000
20000
0
50
100
150
200
250
300
vertices
Figure 5: Comparison of instance sizes and number iterations of local search for the sequence of hard instances created by our reductions.
of those classes to our contrastive objectives (even for relatively simple settings). There are many exciting questions for future consideration. The main interesting future direction is to examine whether our negative results are persistent the average case. In particular, understanding the effects of initialization is exciting direction. Another interesting perspective to study for contrastive objectives, so-called smoothed analysis [Spielman and Teng, 2009], where the input data are slightly perturbed by random noise, and many algorithms (including linear programming with the Simplex, which is local search algorithm) seem to get much better guarantees compared to worst-case inputs. Finally, work studied the question of how fast can we reach local optimum, but an important future direction is to argue about the quality of local solutions.
Acknowledgements
Ioannis Panageas and Jingming Yan were supported by NSF grant CCF-2454115. Vaggos Chatziafratis is supported by Hellman Fellowship and a startup grant from UC Santa Cruz. This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program. Part of this work was done while J. J.Y., Y.L., V.C., and I.P. were visiting Archimedes Al Research Center, Athens, Greece.
10

---

References
S. Agarwal, J. Wills, L. Cayton, G. Lanckriet, D. Kriegman, and S. Belongie. Generalized non-metric multidimensional scaling. In Artificial Intelligence and Statistics, pages 11-18. PMLR, 2007.
A. V. Aho, Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from lowest common ancestors with application to the optimization of relational expressions. SIAM Journal Computing, 10(3):005 421, 1981.
R. K. Ahuja, Ô. Ergun, J. B. Orlin, and A. P. Punnen. A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123(1-3):5--10,, 2002.
N. Alon, M. Bădoiu, E. D. Demaine, M. Farach-Colton, M. Hajiaghayi, and A. Sidiropoulos. Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. ACM Transactions on Algorithms (TALG), 4(4):1-21, 2008.
N. Alon, D. Avdiukhin, D. Elboim, O. Fischer, and Yaroslavtsev. Optimal sample complexity of contrastive learning. arXiv preprint arXiv:2312.003: 2023.
I. Anagnostides. F. Kalogiannis, I. Panageas, E. Vlatakis Vlatakis-Gkaragha Gkaragkounis, and S. McAleer. Algorithms and complexity for computing nash equilibria in adversarial team games. In Conference on Economics and Computation (EC), 2023.
I. Anagnostides, I. Panageas, T. Sandholm, and J. Yan. The complexity of symmetric equilibria in min-max optimization and team zero-sum games, 2025, URL httpp::/aaxxvvorrg/eeee. org.///25022 08519.
S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of np-hard problems. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 284-293, 1995.
S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Mathematical programming, 92(1):1-36, 2002.
Austrin, R. Manokaran, and C. Wenner. On the up-hardness of approximating ordering-constrain satisfaction problems. Theory of Computing, 11(1):257-283, 2015.
D. Avdiukhin, Chatziafratis, O. Fischer, and G. Yaroslavtsev. Embedding dimension of contrastive learning and k-nearest neighbors. Advances in Neural Information Processing Systems, 37: 13359-41393, 2024.
P. Awasthi, N. Dikkala, and P. Kamath. Do more negative samples necessarily hurt in contrastive learning? International conference on machine learning, pages 1101-1116. PMLR, 2022.
Y. Babichenko and A. Rubinstein. Settling the complexity of nash equilibrium in congestion games. In S. Khuller and V. V. Williams, editors, Symposium on Theory of Computing (STOC), 2021.
M. Bădoiu, F. D. Demaine, M. Hajiaghayi, A. Sidiropoulos, and M. Zadimoghaddam. Ordinal embed- ding: Approximation algorithms and dimensionality reduction. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 21-34. Springer, 2008.
Y. Bilu and N. Linial. Monotone maps, sphericity and bounded second eigenvalue. Journal of Combinatorial Theory, Series B, 95(2):283-22 2005.
N. Bitansky and I. Gerichter. On the cryptographic hardness of local search. In 11th Innovations in l'heoretical Computer Science Conference (ITCS 2020), pages 6-1. Schloss Dagstuhl-Leibniz- Zentrum für Informatik, 2020.
M. Bodirsky, P. Jonsson, and T. V. Pham. The complexity of phylogeny constraint satisfaction problems. ACM Transactions Computational Logic (TOCL), 18(3):1-42, 2017.
Borg and Groenen. Modern multidimensional scaling: Theory and applications. Springer Science & Business Media, 2007.
11

---

J. Byrka, S. Guillemot, and J. Jansson. New results on optimizing rooted triplets consistency. Discrete Applied Mathematics, 156(11): 2010.
I. Chami, A. Gu, V. Chatziafratis, and C. Ré. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering. Advances in Neural Information Processing Systems, 33: 15065-15078 2020.
M. Charikar, V. Guruswami, and R. Manokaran. Every permutation esp of arity 3 is approximation resistant. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 62-73.
IEEE, 2009.
M. Charikar, V. Chatziafratis, and Niazadeh. Hierarchical clustering better than average-linkage. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2291-2304. SIAM, 2019.
V. Chatziafratis and P. Indyk. Dimension-accuracy tradeoff's in contrastive embeddings for triplets, terminals & top-k nearest neighbors. In 2024 Symposium Simplicity in Algorithmss (SOSA), pages 230-243. SIAM, 2024.
V. Chatziafratis and K. Makarychev. Triplet reconstruction and all other phylogenetic csps are approximation resistant. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 253-284, IEEE, 2023.
V. Chatziafratis, R. Niazadeh, and M. Charikar. Hierarchical clustering with structural constraints. In International conference machine learning, pages 774-783. PMLR, 2018.
V. Chatziafratis, M. Mahdian, and S. Ahmadian. Maximizing agreements for ranking, clustering and hierarchical clustering via max-cut. International Conference on Artificial Intelligence and Statistics, pages 1657-1665. PMLR, 2021.
S. Chen, C. Gong, J. Li, J. Yang, G. Niu, and M. Sugiyama. Learning contrastive embedding in Now-dimensional space. Advances Neural Information Processing Systems, 05:6345-6357, 2022.
C. Daskalakis and C. Papadimitriou. Continuous local search. In Proceedings of the twenty-second anmual ACM-SIAM symposium on Discrete Algorithms, pages 790-804. SIAM, 2011.
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing nash equilibrium. Communications of the ACM, 52(2):99-97, 2009.
E. Emamjomeh-Zaadee and Kempe. Adaptive hierarchical clustering using ordinal queries. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 415-429. SIAM, 2018
A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure nash equilibria. In Proceedings of the thirty-sixih annual ACM symposium Theory of computing, pages 604-612, 2004.
B. Fan, D. I. Centurion, N. Mohammadi, F. Sgherzi, A. Sidiropoulos, and M. Valizadeh. Learning lines with ordinal constraints. arXiv preprint Xiv:20044.3300, 2020.
Fearnley, P. Goldberg, Hollender, and R. Savani. The complexity of gradient descent: CLS PPAD n PLS. J. ACM, 70(1):7:1-7:74, 2023.
J. Fearnley, P. W. Goldberg, A. Hollender, and R. Savani. The complexity of computing kkt solutions of quadratic programs. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 892-903, 2024.
A. Ghosh and A. Hollender. The complexity of symmetric bimatrix games with common payoffs. In International Workshop On Internet And Network Economics (WINE), 2024.
N. Ghosh, Y. Chen, and Yue. Landmark ordinal embedding. Advances Neural Information Processing Systems, 32, 2019.
V. Guruswami, R. Manokaran, and P. Raghavendra. Beating the random ordering is hard: Inapprox- imability of maximum acyelic subgraph. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 573-582. IEEE, 2008.
12

---

V. Guruswami, J. Håstad, R. Manokaran, P. Raghavendra, and M. Charikar. Beating the random ordering hard: Every ordering esp upproximation resistant. SIAM Journal on Computing, 40 (3):878-914, 2011.
J. Z. HaoChen and T. Ma. A theoretical study of inductive biases in contrastive learning. arXiv preprint arXiv: 22..2221,.,499, 14699, 2022.
R. D. Hjelm, A. Fedorov, S. Lavoie-Marchildon, K. Grewal, P. Bachman, A. Trischler, and Y. Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint 1808. 06670, 2018.
Hubácck and E. Yogev. Hardness of continuous local search: Query complexity and cryptographic lower bounds. SIAM Journal Computing, (996):112--1172 2020.
P. Indyk, J. Matoušek, and A. Sidiropoulos. 8: low-distortion embeddings of finite metric spaces. In Handbook of discrete and computational geometry, pages 21 211-231. Chapman and Hall/CRC, 2017.
L. Jain, K. G. Jamieson, and R. Nowak. Finite sample prediction and recovery bounds for ordinal embedding. Advances in nearal information processing systems, 29, 2016.
K. G. Jamieson and R. D. Nowak. Low-dimensional embedding using adaptively selected ordinal data. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1077-1084, IEEE, 2011.
D. S. Johnson, C. Papadimitriou, and M. Yannakakis. How easy is local search? Journal of computer and system sciences, 37(1):79-100, 1988.
Y. Kalantidis, M. B. Sariyildiz, N. Pion, P. Weinzaepfel, and D. Larlus. Hard negative mixing for contrastive learning. Advances in neural information processing systems, 33:21798-2188 -2989,, 2020.
M. Kleindessner and U. von Luxburg. Kernel functions based on triplet comparisons. Advances in neural information processing systems, 30, 2017.
J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to nonmetric hypothesis. Psychometrika, 29(1): 1964a.
B. Kruskal. Nonmetric multidimensional scaling: numerical method. Psychometrika, 29(2): 115-129, 1964b.
E. L. Lawler. The traveling salesman problem: guided tour of combinatorial optimization. Wiley-Interscienee Series in Discrete Mathematics, 1985.
B. Monien and Tscheuschner. On the power of nodes of degree four in the local max-cut problem. In Algorithms and Complexity: 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings 7, pages 264-275. Springer, 2010.
B. Moseley and J. R. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. Journal of Machine Learning Research, 24(1):1-36, 2023.
S. Naumov, G. Yaroslavtsev, and D. Avdiukhin. Objective-based hierarchical clustering of deep embedding vectors. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9055-9063, 2021.
A. v. d. Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. arXiv preprint frXiv:/807.03740 2018.
J. B. Orlin, A. P. Punnen, and A. S. Schulz. Approximate local search in combinatorial optimization. SIAM Journal on Computing, 33(5): 2004.
Robinson, C.-Y. Chuang, Sra, and S. Jegelka. Contrastive learning with hard negative samples. arXiv preprint 1xXi:2011000459.. 2020.
N. Saunshi, O. Plevrakis, S. Arora, M. Khodak, and H. Khandeparkar. A theoretical analysis of contrastive unsupervised representation leanniinn In International Conference on Machine Learning, pages 5628-5637 PMLR, 2019.
13

---

N. Saunshi, J. Ash, S. Goel, D. Misra, C. Zhang, S. Arora, S. Kakade, and A. Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. In International Conference Machine Learning, pages 19250-19286. PMLR, 2022.
A. A. Schäffer and M. Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing. 20(1):56-88) 87, 1991.
Schroff, D. Kalenichenko, and J. Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 815-823, 2015.
D. A. Spielman and S.-H. Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM, 52(10):76-84, 2009.
O. Tamuz, Liu, Belongie, Shamir, and T. Kalai. Adaptively learning the crowd kernel. 28th International Conference on Machine Learning (ICML), 2011.
Y. Terada and U. Luxburg. Local ordinal embedding. In International Conference Machine Learning, pages 855. PMLR, 2014.
L. L. Thurstone. The measurement of values. Psychological review, 61(1):47, 1954.
W. S. Torgerson. Multidimensional scaling: I. theory and method. Psychometrika, 17(4):001441, 1952.
C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theeor, pages 1179-1206. PMLR, 2021.
D. Vainstein, V. Chatziafratis, G. Citovsky, A. Rajagopalan, M. Mahdian, and Y. Azar. Hierarchical clustering via sketches and hierarchical correlation clustering. International Conference on Artificial Intelligence and Statistics, pages 559-567. PMLR, 2021.
L. Van Der Maaten and K. Weinberger. Stochastic triplet embedding. In 2012 IEEE International Workshop on Machine Learning for Signal Processing, pages 1-6. IEEE, 2012.
L. C. Vankadara, S. Haghiri, M. Lohaus, F. U. Wahab, and U. von Luxburg. Insights into ordinal embedding algorithms: A systematic evaluation. arXiv preprint arXiv:1912.00 1912.01666, 2019.
Vikram and S. Dasgupta. Interactive bayesian hierarchical clustering. In International Conference on Machine Learning, pages 2081 2091-2090. PMLR, 2016.
14

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
Our main contributions and results are summarized the abstract and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our results are about the computational complexity of local solutions in contrastive learning. These are worst case guarantees and practice the running time can be much faster.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: All the proofs of our claims can be found in the appendix. Moreover, we have provided proof sketches to give intuition to the reader about our proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments, it includes simulations that do not affect the main claims.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access the model is limited in some way (e.g.. to registered users), but should be possible for other researchers to have some path reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code. with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
We have included the code for the simulations in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
wsisssolicyyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips. cc/ htc//uulicggguiiieeeeeeeee
for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include such type of experiments. It includes simulations of hard instances that verify our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments of this nature.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include experiments of this nature.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics https://neure: https//cc..cpppcc/hhhccccecdelld
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g.. if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is on the computational complexity of local optima for contrastive learning and is theoretical. The authors do not believe there is any social impact from this work.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address socictal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re- ee-pakagedd both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/codemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components. www.rrpps..c/oooeeeeeeeee.ccceee
Please refer to LLM policy for what should or should not be described.
21

---

A Omitted proofs for Section 3.2
Theorem A.I (Theorem 3.3, restated), For every fixed dimension 2 1, LOCA.BETWEENNESS- EUCLIDEAN is PLS-hard.
Proof. We reduce from LOCALMAXCUT. Let = (V, E, w) be a weighted undirected graph.
Reduction Construction. We define instance of LoCAL BETWEENNESS- EUCLIDDAN in R called Tatu as follows. We introduce special vertices X1, XI,..., Xa and choose a hierarchy of weights
M3 > M4 > > Ma M
Wavi
(a,v)EE
such that for each & 2 3,
Mr >
Σ 1>k
3(
+ 2
+
Σ Wuv
(u,N)E all "odge" triplets
all "isosceles" triplets
lower layer "cquilatoral" uiplets
Now we add constraints as follows:
Type A ("edge" triplets). For each edge (u, v) E E, we add triplet (u, X1, v) with weight Wav-
Type B ("isosceles" triplets). For each v E V and every pair (Xg, Xe) with 1 < < < d, we add triplets (Xx, Xe, v) and (Xe, v), each with weight M. Intuitively, this will force XR, Xx, e to form an isosceles triangle such that || - Xxll2 = ||e- Xella 2 ||X -Xel2-
Type C ("equilateral" triplets). For every triple (X,, XR, Xe) with 1 S J < k < E d. we add three triplets (X,, Xk; Xt), (Xk, Xe, Xz). 3) (Xe, Xj.Xa) each with weight Me (E is the largest index among j. k. E). Intuitively, this will force X,, Xx, X₂ to form an equilateral triangle.
Lemma A.2. any local optimum of Istus all "equilateral" triplets are satisfied, therefore form (d - 1)-dimensional regular simplex.
Proof of Lemma A.2. We prove (X Xx} form a regular simplex for each k = ......, d. We do this by induction on k.
Base Case (k- = 3). If any "equilateral" triplets over {X1, X2, X3} is unsatisfied, moving any of them to form equilateral triangle with the other two will satisfy least new triplet of weight M3. while losing at most Ej>3 3(2²²) Mj ( M E(u,)E Wuv < M3, which contradicts local optimality.
Inductive Step. Suppose (XI.... X form regular simplex but {X Xx) ) do not. Similar to the above, moving X to form regular simplex with (X1...., Xx-13 will satisfy at least one new triplet of weight Mg. while losing a total strictly less than Mg. Hence, ( must also form regular simplex.
Lemma A.3. Let C be the centroid of the simplex XI...., Xa and C= 1|1, X2ll2 be its edge length. Then any local optimum, all "isosceles" triplets are satisfied, therefore each E must lie on the line through C perpendicular to the hyperplane spanned by the Xi, and moreover at distance at least from every Xz. Formally, each & E V lies on one of two opposing rays:
R+ =CCtuut
R = cCC tu: to)
where u is the unit vector along that line and = l
d+1
2d
Proof of Lemma A.3. Without loss of generality, assume the simplex in the standard position:
X = 0... (1, X2 = (0,1..... (0, Xa = (0.0....,1)
In geometry, regular simplex is the d'dimensional generalization of an equilateral triangle (2-simplex) or regular tetrahedron (3-simplex), consisting of + points with all pairwise distances equal.
22

---

with centroid C' = (3: d: .) The edge length is = v2.
2).
We denote the i-th coordinate v as vz. The equidistant condition ||0 - -xx1l112 110 -Xell2 simplifies to:
u 20 = of 20, Vi Vi
The only solutions are = (a, , a) for some a E R.
For a1, the distance to any vertex X is:
|/U -xxll2 = (a 1)2 (d 1)aa da² -20 + 12 l =
Solving da² 2a + gives:
a $ 1-v
or a² 1+vd+
d
d
Expressing relative to the centroid C²= f:=
u = C+uu u u= 1/Vd, t= Vd (a-
Substituting the bounds for a yields t <
d+1
or t 2
1+1
For arbitrary > 0, scale the canonical simplex by X = f/v2.
The threshold to scales as:
to X d+1 = E
d+1
2d
The standard basis assumption is justified because any regular simplex can be mapped this form via a similarity transformation, which preserves the distance relationships.
Since M > E( Waes any configuration of that violates the "isosceles" triplets can be improved by moving v to either R+ or R
Lemma A.4. In any local optimum, the "edge" triplet (u, X1, v) is satisfied if and only if and lie on opposite rays R and R.
Proof of Lemma A.4. Let C + f,u and u C ttu. Since u, v lie on the line through C perpendicular to the hyperplane spanned by the X,, we have
|| X1112 = V 6 ||X1
CI2 1|
||u - X1112 = e3 ||X ClI2
dd11 We can also verify that ||x, Cll = ev
2d
Case 1: If and are the same ray (e.g., Rt), then:
I|u 1||2 = It, - t, S max(t;, t2) < max([Iu - X1ll2. 11v -x,ll))
Thus (u, X1, v) satisfied.
Case 2: If u and are on opposite rays R+ and R=, then:
|u X1ll2 Ve3 + ||X| CII / 1 + (d 1)
2d
- 10-X1112 = V + ||, - -
1 13 + (d 1)
2d
2112 = |4al + 1tyl-
We need to show that ||u -1112 > max( |/u X1 [|2 1|00 100-xXi0 X1ll2).
23

---

To show I|u 2|12 2 l|u X1 X1l need (141 + |1/1)2 2 12
(d-1)e² Expanding:
2d
t + 2 1 12 (d 1)62
(d
1)
2/44 + 15
2d
2d
Since [t.l. ltyl 2 to. substitute
|t:] = |tyl to (worst case for the inequality):
(d (d-13 1)e2
20 + to =t 2
2d
Substitute to = =VV
d+1. 2d
(d + 1)
(d - (d
3
3(d+ 1) 2 d d-1.
2d
2d
This holds for all d 2 2.
Symmetrically we can show 1|u- 2||2 2 110 X1ll2-
Thus (u, X1, v) is satisfied.
Special Case d 1. We note that in the case of 1, this construction degenerates into only one special vertex X1, with only "'egge" triplcts. We claim that this construction is still correct, as the vertices on different sides of Xı encode cut. Since "no local moves can improve the objective function" is stronger condition than "no local moves of vertices except X1 can improve the objective function", any local optimum of Totw is also a local max cut.
This concludes the proof of Theorem 3.3.
Proof of Theorem 3.2. We extend the reduction for LOCAL to higher dimen- sions by modifying the
construction.
Recall that in the L opposing rays. We can encode the same isosceles and equilateral gadgets using contrastive triplets, for example, replacing betweenness triplet (x. y, 2) with two contrastive triplets (I, 2-) and (2, y² x ). We then use the same idea for the d = 1 case we considered in Section 3.1, to turn the rays into segments. Let Y be
construction, all u E V are forced onto two
special vertex forming regular simplex with X X1,...p Xd. and Z be a new special vertex on one of the rays. We add a contrastive triplet (Y, 2+ xT) to ensure that ||x 2 > |Y 2 Y is the segment "cut" the ray.
For each v E V, we add two contrastive triplets (X1, Si,Y+tu" x)) and (X1, -- to ensure that is on ZZ or on its mirror Z' with respect to the hyperplane spanned by XI....; Xa.
We can always choose a hierarchy of weights so that these newly added triplets are satisfied in any local optimum. The rest of the proof follows similarly to Theorem 3.3.
B Omitted proofs for Section 3.3
Proof of Theorem 3.4. We reduce from LOCALMAXCUT. For a given graph G(V, E, w), we construct the triplets over vertices V U (X,X', X', ZJ. We denote W E(,,)) Wao be the of edge weights. The triplets are constructed
Type A triplets: XX'IY, XX' and XX'lv lo for all vertex E V, each with weight W;
Type B triplets:
XY Z with a large weight nW +n+1;
Type C triplets:
Yu X and Zu|X for all v E V, each with weight W + 1;
Type D triplets: For every edge (u, v)) E F,, we add uX j and eX u, each with weight Wan/2.
Assume that T is a local solution of the above triplets instance. Since T is an rooted binary tree, there exists a unique path P starting from the leave node X to the root. All other leave nodes [X', Y, Z} would be on branches of this path Firstly observe that X' should share the same parent node with X. In other words, X', and only X', should be on the lowest branch on the path P. If this is not the case, X' can simply move to a location such that X and X' share the same parent and this would only increase the satisfied triplets by satisfying all triplets of Type A.
24

---

Since in any local solution T. Type A triplets are always satisfied as argued above. For nodes Y and Z, Type B triplet XY Z has dominating weight (the weight of XY|Z is greater than the sum of weights of other triplets that Y or Z is involved). Formally, we have
Wy and WXYIZ > BEV
Σ
Σ
W
BEV
Thus any local solution T needs to satisfy Type B triplet. We note that the triplet XY|Z can only be satisfied when Y is lower branch of Z on the path P.
Similarly for each vertex v V, it holds that
E uEN(v)
(Waxlu + wox|u)
WYo
where (v)) denotes the set of neighbors of v. Thus in any local solution T, vertex e would try to satisfy Yu|X and Zu| X first. Since Y and Z are on different branch, only one of Yu|X and Ze|X could be satisfied in a local solution T. Notice that in order to satisfy Yu|X or Zu| vertex should be on the branch of Y or the branch of Z respectively. We conclude that in local solution T, any v E should be on either the branch with Y or the branch with Z.
We proceed to show that for any pair of vertices and if u and v are on the same branch (either the branch with Y or the branch with 2), then neither of x (u or u. would be satisfied. u and v are on different branches, e.g., is on the branch of Y and u is on the branch of Z, then exactly one of u.X u or u.X y would be satisfied. Since any vertex v E can only reside in either the branch with Y or the branch with Z, we conclude that in any local solution T, the configuration of all vertices will introduce a solution of LoCALMAXCUT on the original graph. That is, all vertices v E on the branch with Y form one side of the cut and those on the branch with Z form the other side.
C Hardness of Non-Betweeness embeddings
We start this section by giving formal definition of LLCALNONBEEEEEEEEEEEEEEELDLDE problem.
Problem.
INPUT Set V with non-betweenness triplets { Ui, hm each with non-negative weight W; 2 O, and target dimension d.
OUTPUT An embedding" f V + Rd such that no vertex e can increase the value of the embedding by switching its location Rd. We say a triplet (2i,,), 2.) satisfied by f()), 24 and 2 not placed the farthest apart (equivalently, y: is not "between" 2; and 2,), ie.. [lf( - f(x)ll2 S max(1lf(z,) - f()))22 lf(z)) f(y))l2) The embedding's objective value is Σm Wi [(x.0)))))
"The output embedding f' is computable in polynomial time in the description of the input set V and the weights.
The problem embeddings (d 1), is the well-studied problem called non-Betweenness |Guruswami et al., 2008, Charikar et al., 2009, Austrin et al., 2015]. Here we show that it is PLS-hard.
problem, even in the case of 1-dimensional
Theorem C.1. LocALNoNBETwEENNEES DEAENEEBBBWEEEEEEEEECLLDDDA for embedding dimension d = 1 is PLS-hard.
Proof. We give a polynomial time reduction from LOCALMAXCUT to Le EUCLIDEAN with d = 1. Given an undirected graph G (V, E)) with edge-weight, w 2 0. Denote
W = E(,viE Wee to be the sum of all edge weights. We introduce two special vertices X and Y
and the input to the Loc SSSrTWEEENISS--ULLLDDANN EUCLIDEAN will be vertices from V U
V (X,Y) with
|V| E|E non-betweenness triplets. The triplets can be classified into two types:
Type A triplets. For every vertex v E V, we add triplet (X, Y) with weight W.
Type B triplets. For every edge (u, v) E E, we add (u, X) and (v, u, X) with weight Wan-
We now argue that in any local optimal embedding over IR, there must no point between X and Y. To see this, given embedding where vertex is in between X and Y, the corresponding triplet
25

---

consider an (X, v, Y) is not satisfied. By moving Y to the location such that there is no point between X and Y (X and Y are next to each other), triplet (X, v, Y) becomes satisfied and previous satisfied triplets remain unchanged. Thus one can simply change the location of Y and increase the sum of weighted satisfied triplets.
We proceed to analyze Type B triplcts. For any edge (u, v) E E, we have the following three cases.
Case 1 Vertices and u to the left of X, that is, u and v are both smaller than X. Without loss of generality, we assume that u < v. Notice that this case v is in between u and X. Thus triplet (v, u, X) is satisfied but (u, v, X) is not satisfied.
Case 2 Both u and v are greater than X. Assume that < v, it follows that triplet (u, v, X) is satisfied but (v, X) is not satisfied.
Case 3 Vertices and are different side of X. In this case it holds that
X S Iu - 2/, and 2 X S Ju v/.
Thus both triplets (u, v, X) and (v, u, X) are satisfied.
We conclude that for any edge (u, v) E F, if vertices u and e are on the same side of X (either to the left or the right), then one of triplets (u, v, X) or (v, u, X) would be satisfied. If and are on different side of X, both (u, X) and (u, u, X) would be satisfied. Thus type B triplets essentially induce a cut over the original graph G-any vertex v to the left of X is on one side of the cut and vertices to the right of X is the other side of the cut. Any local optimal embedding over the above BENNBeEEEENNNS-BBBS
instance with total weight W would induce a LOCALMAXXUT over G' with weight W" -IVI + 1)W.
D Omitted proofs for Section 4
Proof of Theorem 4.1. We first study the case where the embedding dimension d = 1 with pivot points A = 0 and B 1/2. In order to show the hardness result, we reduce QUADeATICPROGRAM- KKT problem to the local solution of LocAl TRILLERIPLLLLOS LosSFELLoS-- The former has been shown to be CLS-complete [Fearnley et al., 2024]. Formally, we consider the following optimization problem
min Tox bT..
To show that QUADRATIcPROGRAMM KKT reduces to DocA.TTRPLELLLS--UcUu.. arbitrary quadratic function of 3 variables x, y, 2 E [0, 1]
( y, =) x + c2y² + 2z2² + caay + C5az + coyz + 67 + C&l + Cg
(2)
For a LOCAl.
problem with points from [0, 1], we set the margin Notice that for any triplet of points (a;, Oj, 04) [0, 1 we have
1.
(a, a2)² (a; ax))² - 1 120. 0.
Thus for any triplet constraint (a;, 0g. 0x) with weight w. the loss function is
L= w ((a: a,,² 2 (a; axx² +1) +
For any triplet (a,, aj, ax), denote triplet (a., aks az) as its dual. Notice if (a,, aj, as) has weight w and the dual triplet (a,, ag, a,) has weight w', we have the following objective function
C= w²) ((a: - az - (as )x) - w + w'.
Now consider a LLccA.TRiPLELLLos-EEEc..... instance on (x, 2) E [0, 1Js. Triplets with weights wi are given
Triplet f = (z, 0, y) with weight wi: L1 = wi ((x 0)2 (x y) + 1): triplet 1/ = (y, 0, .) with weight w2: L2 w2 ((y 0)2 (y x)² + 1) triplet t3 (x, 0, 2) with weight Wy: L3 Wa ((x 0)2 (x 2)² + 1);
26

---

triplet f (z, 0, 2) with weight wa: L1 W1 ((2 - -) (z x)² + +1);
triplet 45 (y, 0, =) with weight wy: Ls = wi ((v - 0)² (y 2)² + +1)
triplet tg (z, 0, y) with weight wa: La we ((2 - 0)2 2 y)² +1);
triplet f = (x, 0, () with weight wy: L = wy (z² - (z 1)² +1+1));
triplet is = (y, 0, }) with weight ws: Ls = ws (1²² (y - 1)3 + 1);
triplet to (z, 0, ! with weight wy: Ly Wy (2² -(2 2)2 + +1];
triplet /10 (0, s; 2) with weight wiot L wio ((0 x)² - 1 +1);
triplet 11 (0, y. 2) with weight w11: L1 W11 ((0 - y)² 1
1 +1);
triplet (12 (0, ( with weight w12: L12 w12 ((0 =)² 1 +1)
The duals of above constraints are defined similarly with weight w/. Summing up all the objectives we get
L = (wi wi) (2xy - y²) + (w2 - -w2) (2ry - 2²) + (w3 w/)) (2 z²2 + (wa - w'') (2xz - z²) + (wy w//) (2yz x²2 + (we - w//) (2yz - y²)
+ (w7 - w²)xx + (wa w//y + (wo wg)=
+ (w1o w/o )r? + (wn - "'1)v'' + (W12 x11) - C.
We note that the last constant term C' wouldn't change the first-order stationary point of the above program. By setting
W1 w1 C2
U12 w/2 02 c4.
W/ w/g -33 4
W/ 4/ C3 + 2 + 2
W/5 S/m CB.
W/6 m/ 0;
W7 1n 07
W8 S/m C8:
W/g m/ 0g:
W10 w/o C1 +
02
+
C3
+
61
2
+
5o 2
W11 w 0:
W12 W/2 = O.
we have L = g(x,, y, 2). This means that from any first-order stationary point (x", ,"",,* ) of the objective L, we have [x=, yy" = [0, 1J3 is a KKT the quadratic program defined in (2).
As shown above, L has the power to represent any quadratic polynomials q(x, z). For the general form as in (1), one group variables into groups of three (M), My v2) and repeat the construction shown above. Since most have O(n?) interacting terms Ug2y where U; and By different variables, it requires Onn²) triplets to represent the quadratic program in (1). From the CLS-hardness of QUADRATICPROGRAM-KER we conclude that LOCAI.TRIPLA. www.erLL.Ss.... oosoooss-ee IDEAN with embedding dimension d is CLS-hard.
27

---

To extend above result to higher dimensions, we construct reduction similar to the one-dimension case. Since lla; aاlر | + ||احاا 2| 2a, aj, by using the same constraints and coefficients as the one-dimensional case and setting a = d, we can construct a quadratic program of the form
min x: Qu: + b x. (0
Where is dn dn matrix with blocks, the (i,j)tt block is of form Cij I. b Rdd is concatenation of n vectors (V1,..., Un), where each Id is of form d; 1 Now for any first-order stationary point a' = (aj, (aj,a...... a2..... a,)) each ai1 a e1, one can verify that aj = (ai,1.... on,1) E [0, 1]4 forms a KKT point of the following program
[0, 1]dn, we consider the first coordinate for
min x² T Car d'x. =E[0,]]
Where C E R and Cij is the coefficient for the (i,j)th block of Q defined in (3) and d; is the coefficient of the 8th vector of b in (3). From the CLS-hardness of QUADRATICPROGRRMMKK conclude that LRcAL.TRPL -ESULLDD is CLS-hard.
E Detailed experimental statistics
Table 1: Experimental statistics for the hard instances H1 to His used in Section 5. The second and the third columns show the number of vertices and edges in the original LOCALMAXCUT instance. The next 6 columns show the number of vertices and constraints in the reduced LOCALBETTEENNISS EUCLIDEAN- ID, LOCAL.COTTRACE TERAATIVE-EELLDDEAA ID and LocAICoNTRASTIVE T instances. The last column shows the number of iterations needed to reach a local optimum.
MaxCut
Berweenness-
Contrastive-
Contrastive
Instance
#iterations
H1
37
45
38
45
40
121
204
63
H2
65
81
66
81
68
213
69
360
167
Ha
93
117
94
117
96
305
97
516
375
Ha
121
153
122
153
124
397
125
672
791
Ha
149
189
489
153
828
1623
Ha
177
225
178
225
180
581
181
984
3287
205
261
206
261
208
673
209
1 1140
6615
H&
233
297
234
297
236
765
237
1296
13,271
Ha
261
333
262
333
264
857
265
1452
26,583
H10
289
369
290
369
292
949
293
1608
53,207
HI
405
320
1041
321
1764
106,455
H12
345
441
346
441
348
1133
349
1920
212,951
H13
373
477
374
477
376
1225
377
2076
425,943
H1A
401
513
402
513
404
1317
405
2232
851,927
H15
429
549
430
549
432
1409
433
2388
1,703,895
28


Reviews:
[{"review_id": "kEw1Ptr4ng", "reviewer": "Reviewer_Fqic", "summary": "The paper studies the computational complexity of finding local optima in contrastive learning problems, a gap previously unexplored compared to global optimization.\nThey prove that finding local optima for both discrete and continuous contrastive objectives is PLS-hard or CLS-hard, respectively, even in low-dimensional settings.\nThis establishes that no polynomial-time algorithm can guarantee finding such optima unless major complexity class collapses (PLS ⊆ P or CLS ⊆ P) occur.\nThe authors establish PLS- and CLS-hardness of contrastive learning objectives by reducing from well-known hard problems such as LocalMaxCut (for discrete settings) and QuadraticProgram-KKT (for continuous settings). These reductions are designed to preserve local optimality, using specialized constraint gadgets that encode the structure of the original problems within the contrastive framework.\n\nThe authors used a synthetic graph from Monien and Tscheuschner (2010), known to be hard for local search, and transformed it into instances of contrastive learning problems via their reductions.\nTheir goal was to test whether local search behaves similarly across problems; the result showed identical exponential-time convergence, validating that worst-case hardness transfers empirically.", "questions": "1. In lines 118--121, you state that the PLS/CLS-hardness results extend to $\\varepsilon$-approximate local optima. Could you clarify for what values of $\\varepsilon = \\varepsilon(n, m)$---where $n = |V|$ (number of data points) and $m = |C|$ (number of triplet constraints)---the reductions remain valid? \n\n2.  Can you explicitly define the geometric configuration of points X, Y, Z in the 1D embedding?\n\n3. In lines 223--228, the proof shows that violating a boundary constraint results in a net loss, but it assumes that the total loss is upper bounded by $\\sum w_{uv}$. Why this upper bound always dominates the gain from violating any single boundary constraint? Including a concrete inequality to justify this would help formalize the argument and strengthen the correctness of the reduction.\n\n4. Theorem 4.1, It would be very helpful if you could list the 12 triplets used to encode a quadratic over $x, y, z$, and share a simple example (either symbolic or numeric) of the corresponding weights. This would really clarify how cross-terms like $xy$ are handled in the reduction.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Novelty: First formal study of the complexity of local optima in contrastive learning.\nTechnical depth: Strong PLS and CLS reductions from canonical problems (LocalMaxCut, QuadraticProgram-KKT).\n- Generality: Hardness holds even in low dimensions (e.g., $d=1$), and across Euclidean, tree, and loss-based settings.\n- Theoretical rigor: Reductions are clean, constructions are well-motivated, and results are sharp.\n\nWeaknesses\n- Clarity: Some sections (especially CLS reductions) are dense; The paper assumes background in PLS/CLS; adding more intuition and context would help make it easier to follow for the broader ML community.\n- Empirical scope: Experiments are limited to synthetic worst-case instances. This is acceptable since the paper was submitted under Theory as the primary area, though broader empirical validation could strengthen future versions.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their suggestions and positive feedbacks.\n\n> \"Some sections are dense; The paper assumes background in PLS/CLS; adding more intuition and context would help make it easier to follow for the broader ML community.\"\n\nDue to the space constraint, we are unable to include full details in the main paper. For the CLS reduction, the intuition is provided in section 4 and the formal mathematical proof is presented in section D of the Appendix. In the proof, we firstly present a reduction to quadratic programs with three variables, which we believe is more intuitive, and then we extend the result to higher dimension settings. We also refer the reviewer to our discussion with Reviewer XHnj regarding the intuition and technicality of our reductions. If space allows, we will include more background information regarding PLS/CLS in the revised version.\n\n> \"Experiments are limited to synthetic worst-case instances.\"\n\nThe main focus of this paper deals with worst-case runtime analysis of local search methods in various contrastive settings and the purpose of our experiments is only to validate our theoretical findings. As we point out in the Conclusion section (line 334 - 338), we deem other theoretical frameworks such as average-case analysis, smoothed analysis, beyond worst-case analysis, and the corresponding empirical validations interesting but go well beyond the scope of our work. For more details regarding the significance of worst-case analysis along with other theoretical models that captures more practical settings, we refer the reviewer to our discussion with Reviewer VGp6 and Reviewer XHnj.\n\n> \"Could you clarify for what values of $\\epsilon = \\epsilon(n, m)$—where $n = |V |$ (number of data points) and $m = |C|$ (number of triplet constraints)—the reductions remain valid?\"\n\nThanks for asking for clarifications on the accuracy parameter. Firstly, our PLS-hardness results hold for embeddings with discrete objectives ($\\sum_{i = 1}^m w_i \\cdot \\mathbf{1}_{(x_i, y_i, z_i)}$),  and due to the discrete nature of the objective functions, approximating with small additive error $\\epsilon$ is equivalent to computing an exact local optimum. Regarding our CLS-hardness results for the triplet loss objective, [1] showed $2^{\\Omega(n)}$ query complexity in black-box model and further provided strong evidence that CLS is hard for polynomial-time algorithms when $\\epsilon$ is inverse exponential ($1/exp(m, n)).$ Thus our results indicate that it is highly unlikely to find an $\\epsilon$-approximate local optimal embedding in polynomial time when the error is inverse exponential.\n\n> \"Can you explicitly define the geometric configuration of points $X$, $Y$, $Z$ in the 1D embedding?\"\n\nThanks for asking for clarifications on the geometric configuration. Since the question is a bit unclear to us, we address potential concerns in three different ways:\n\n1. Regrading the triplet notation $(X, Y, Z)$, the formal definition can be found at the top of page 5, where $X$ is required to be closer to $Y$ than to $Z$ in the embedding space.\n\n2. For the relative positions of the special vertices $X$, $Y$, $Z$ in any local optimal embedding, this is stated in lines 220-221: \"either the order $X < Y < Z$ or $Z < Y < X$, with distances $|X - Y| \\geq |Y - Z|$\"; we also illustrated this in Figure 2.\n\n3. Finally, to clarify \"how the specific triplet constraints listed in the proof enforce this configuration\", we provide the following case analysis covering all $6$ possible orderings of $X, Y, Z$ on the line: \n\n* If $X < Y < Z$, both constraints $(X, Y^+, Z^-)$ and $(Y, Z^+, X^-)$ are satisfied if and only if $|X-Y| \\geq |Y-Z|$. \n\n* If $X < Z < Y$, $(X, Y^+, Z^-)$ cannot be satisfied. \n\n* If $Y < X < Z$, $(Y, Z^+, X^-)$ cannot be satisfied. \n\n* If $Y < Z < X$, $(X, Y^+, Z^-)$ cannot be satisfied. \n\n* If $Z < X < Y$, $(Y, Z^+, X^-)$ cannot be satisfied. \n\n* If $Z < Y < X$, both constraints are satisfied if and only if $|X-Y| \\geq |Y-Z|$.\n\n> \"In lines 223--228, the proof shows that violating a boundary constraint results in a net loss, but it assumes that the total loss is upper bounded by $\\sum w_{uv}$. Why does this upper bound always dominate the gain from violating any single boundary constraint?\"\n\nThis property holds because we specifically set $M := \\sum_{(u,v) \\in E} w_{uv} + 1$ in our construction (lines 203--204). We would like to justify this argument as follows:\n\nConsider the consequences of moving $v$ in this way. (1) The boundary constraints $(X, Y^+, v^-)$ and $(X, v^+, Z^-)$ become satisfied, yielding gain $M$ (if one was previously unsatisfied) or $2M$ (if both were previously unsatisfied). (2) Edge constraints involving $v$, which in the worst case all become violated, yielding maximum loss $\\sum_{(u,v) \\in E} w_{uv}$.\n\nTherefore,\n$\n    \\text{gain} \\geq M, \\text{loss} \\leq \\sum_{(u,v) \\in E} w_{uv} \\Rightarrow \\text{gain} - \\text{loss} \\geq M - \\sum_{(u,v) \\in E} w_{uv} = 1 > 0.\n$\nThis inequality shows that fixing a boundary constraint always improve the solution, thus any local optimum must satisfy all boundary constraints. We will make the inequality explicit in the revised version.\n\n> \"Theorem 4.1, it would be very helpful if you could list the 12 triplets used to encode a quadratic over $x$, $y$, $z$, and share a simple example (either symbolic or numeric) of the corresponding weights. This would really clarify how cross-terms like $xy$ are handled in the reduction.\"\n\nWe listed the 12 triplets in the Appendix section (line 645-656) due to the space constraint of the main paper. In our reduction, two triplets $(t_1 = (x, 0, y)$  and $t_2 = (y, 0, x))$ contribute to the cross-term $xy.$ We will add detailed illustrations regarding the triplet constructions to the main paper in the revised version if space allows.\n\nWe would like to thank the reviewer again for their valuable time and supportive comments.\n\nBest regards, \n\nThe authors.\n_____________\nReferences:\n\n[1] Pavel Huáček and Eylon Yogev. “Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds”. In: Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1352–1371."}, {"review_id": "3jJuEhsXWj", "reviewer": "Reviewer_VGp6", "summary": "This paper investigates the computational complexity of finding local optima in contrastive learning, proving PLS-hardness for discrete objectives and CLS-hardness for continuous objectives, indicating that no polynomial-time algorithm can find local optima unless complexity classes collapse. It provides theoretical foundations for understanding the optimization challenges in contrastive learning and suggests future research directions, including average-case complexity and the quality of local solutions.", "questions": "1. Could the authors please clarify how worst-case scenario analysis for local optima contributes to either optimization efficiency or convergence reliability, and whether there are any existing mitigation strategies for such scenarios?\n\n2. The experimental evidence (Figure 5) relies on specific worst-case constructions inherited from LocalMaxCut. Is there empirical evidence or theoretical argument about how these scenarios relate to typical or randomly generated instances of contrastive learning? Do the exponential local search behaviors manifest on real datasets?", "limitations": "The paper does not include extensive empirical experiments to validate the theoretical results. While the constructed hard instances demonstrate the potential for exponential time complexity, the paper does not provide a broad empirical study across different datasets and initialization methods.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths：\n1. By focusing on the complexity of local optima (rather than just global optima), the paper connects empirical observations of slow or stuck convergence in contrastive learning to formal complexity-theoretic barriers.\n2. The paper delivers a comprehensive set of hardness results: PLS-hardness for maximization of contrastive triplets and betweenness objectives in both R^d and on trees, and CLS-hardness for continuous triplet loss minimization. These are rigorously demonstrated via reductions from classic hard problems (LocalMaxCut, QuadraticProgram-KKT).\n\nWeaknesses：\n1. There is little discussion or exploration of practical scenarios or real datasets in experiments --- leaving open the question of whether these hardness results are representative of typical training behavior in common machine learning settings beyond theoretical constructions.\n2. The paper focuses on the complexity in the worst case, but does not analyze the behavior in the average case, which makes it difficult to fully understand the complexity of local optima in contrastive learning.\n3. There are no corresponding methods or experiments proposed to address the complexity caused by the worst-case scenarios.", "was_revised": true, "final_justification": "The theoretical framework presented is sound, yet the work would benefit considerably from more comprehensive empirical analysis to substantiate its practical applicability.", "rebuttal": "We thank the reviewer for their valuable time and suggestions.\n\n> \"There is little discussion or exploration of practical scenarios or real datasets in experiments --- leaving open the question of whether these hardness results are representative of typical training behavior in common machine learning settings beyond theoretical constructions.\"\n\nAnd also\n\n>\"The paper focuses on the complexity in the worst case, but does not analyze the behavior in the average case, which makes it difficult to fully understand the complexity of local optima in contrastive learning.\"\n\nThe paper addresses the worst-case runtime complexity of various contrastive settings via local search methods, including gradient descent, which was open prior to our work. Finding local optima is a fundamental question and we present hardness results for them. As such, all results are in terms of worst-case analysis, similar to proofs of NP-hardness for worst-case instances of combinatorial problems. \n\nAs mentioned in the Conclusion (line 334 - 338), real datasets are expected to exhibit non-worst-case behaviors. Moreover, we suggested studying the average-case behavior through other theoretical frameworks such as smoothed analysis in our settings as one of the future directions. It is worth noting that for a lot of classical problems like local Maximum-cut or computing Nash equilibria in general-sum games, the corresponding smoothed analysis results [1, 2] are proven years later than the computational complexity results and they often require new theoretical insights about the problems. We believe this submission is a stand-alone work and, apart from its own theoretical novelty, it serves as a stepping stone for future studies.\n\nFinally, we would like emphasize that this paper is submitted under the Theory primary area, as it mainly focuses on a fundamental question instead of studying practical behaviors over real-world datasets. The key takeaway is that finding local minima requires exponential time in the worst case.\n\n> \"There are no corresponding methods or experiments proposed to address the complexity caused by the worst-case scenarios.\"\n\nAnd also\n\n> \"Could the authors please clarify how worst-case scenario analysis for local optima contributes to either optimization efficiency or convergence reliability, and whether there are any existing mitigation strategies for such scenarios?\"\n\nThe theory of computation deals first with worst-case complexity, and this was open for finding local minima in all our settings. Our goal was to answer this open question and we did this for the worst-case analysis. Similar to the theory of NP-hardness that provides intractability evidence for finding global optima, our work provides strong intractability evidence for finding local optima, which is more challenging. In fact, our hardness results preclude the existence of any polynomial-time algorithm that finds a locally optimum in the settings we study unless there is a collapse of complexity classes (PLS $\\subseteq$ P or CLS $\\subseteq$ P).\n\nWe would like to highlight that our goal was not to bypass hardness in real-life scenarios, similar to how proofs of NP- or PPAD-hardness discuss the underlying complexity of the problem (e.g., 3-SAT, Nash Equilibria etc) and not real-world performance of standard heuristics. Methods that avoid worst-case scenarios in practice could be an interesting future direction to investigate. As we noted in the Conclusion section, one possible approach is to apply small random perturbations and study its smoothed complexity. It is noteworthy that smoothed analysis is problem-specific, existing polynomial-time result for PLS/CLS-complete problems [3] does not directly extend to the contrastive settings that we study.\n\n> \"The experimental evidence (Figure 5) relies on specific worst-case constructions inherited from LocalMaxCut. Is there empirical evidence or theoretical argument about how these scenarios relate to typical or randomly generated instances of contrastive learning? Do the exponential local search behaviors manifest on real datasets?\"\n\nAs we discussed above, randomly generated instances (or instances under random perturbation) are interesting future direction we mentioned in Conclusion, but the scope of this submission focuses on worst-case complexity, which is a fundamental theoretical question on its own.\n\nWe thank the reviewer again for their time and suggestions. We hope our comments address their concerns about this paper. We would really appreciate if the reviewer would reconsider their evaluation of our work.\n\nBest regards,\n\nThe authors.\n\n--------\nReferences:\n\n[1] Michael Etscheid and Heiko R¨oglin. “Smoothed analysis of local search for the maximum-cut problem”. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’14. Portland, Oregon: Society for Industrial and Applied Mathematics, 2014, pp. 882–889.\n\n[2] Shant Boodaghians et al. “Smoothed complexity of 2-player Nash equilibria”. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2020, pp. 271–282.\n\n[3] Pavel Huáček and Eylon Yogev. “Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds”. In: Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1352–1371."}, {"review_id": "VhFD4wYYZQ", "reviewer": "Reviewer_XHnj", "summary": "The paper worked on the complexity of finding local minimum of contrastive learning loss. The main idea is to reduce a polynomial local search or continuous local search problem to the triple minimization/maximization problem, then use the existence theory of PLS and CLS to show the corresponding complexities. The bridge is the LocalMaxCut problem, which was proved to be PLS-hard. The author worked on several variants/cases in 1D and $\\geq 2$-D of the contrastive loss. i.e LocalConstrastive-Euclidean problem, Local Constrastive-Tree problem, LocalBetweenness-Euclidean problem in both discrete case and continuous case. The main ideas in all the proofs are to add some certain triples that have height weights to show the equivalence between two problems.", "questions": "Based on two points stated in the weaknesses, my decision is to reject, although I am not familiar with most of the literature.", "limitations": "Yes, it is theoretical work.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. I think the author make an attempt to introduce the problem and all related works, since I believe they are not familiar with AI conferences.\n2. The presentation is well-structured and clear. \n3. I believe that the results have some valid contribution to the theory of complexity of contrastive learning loss. \n\nWeaknesses:\n\n1. As a practitioner, I do not find any practical benefit from this work when working with contrastive learning.\n2. I am not familiar with most of the literature mentioned in the paper. However, I find the proofs are based on combinatorial structures, but all these structures are quite simple. Thus, I do not appreciate the novelty as well as the difficulty of presented proofs. \n3. No applications.", "was_revised": true, "final_justification": "I keep my score for definite rejection, since I think the paper has very little contributions and impact to the community. The conference should prioritize the place for works with practical benefit.", "rebuttal": "We thank the reviewer for their time and the reviews they provide.\n\n> \"As a practitioner, I do not find any practical benefit from this work when working with contrastive learning.\"\n\nAnd also\n\n> \"No applications.\"\n\nThis is a Theory Track paper dealing with fundamental optimization questions. The theory of computation, celebrated by multiple Turing awards, Godel prizes, and various other mathematical/Computer Science prizes, discusses the worst-case complexity of finding solutions to optimization problems, and we believe our work showing worst-case results is a stepping stone towards understanding the performance on real-world instances. Through our reductions, we highlight the hard-instances of our problems, and typically, worst-case results have yielded important complexity classes, progressed the community's understanding on computation and computability. From a practical point of view, there are theoretical frameworks such as average-case analysis, smoothed analysis, beyond-worst-case analysis (see Roughgarden's book on beyond-worst case). Before moving towards such beyond-worst-analysis theoretical guarantees, one needs to firstly understand the worst-case. Our work serves this purpose and should be considered as stand-alone work.\n\n> \"I find the proofs are based on combinatorial structures, but all these structures are quite simple. Thus, I do not appreciate the novelty as well as the difficulty of presented proofs.\"\n\nWe deem our work highly technical and that it carries significant theoretical novelties. Computational hardness reductions typically involve creating gadgets, such as extra variables, structured functions and geometric configurations etc., which are fundamental building blocks for **all** reductions in computational complexity. Our work follows the convention of typical reductions which operate on purely combinatorial objects such as graphs, trees, circuits, permutations, and embeddings. While some of the gadgets might look easy at the first glance, coming up with such gadgets require much more efforts as we need to preserve the local optimality from our settings to problems we reduce to.\n\nFurthermore, prior to our work, the complexity of finding local optimum in our settings remained open and is a fundamental question in optimization. The PLS/CLS-hardness results in this paper provide strong evidence that the problems we consider are computationally hard and it is unlikely for polynomial-time algorithm to find local solutions. This is the first work that establishes the computational complexity results for contrastive learning and we believe it carries fundamental theoretical contributions to broader machine learning communities.\n\nBelow we provide summaries of the challenges and technical contributions of our reductions.\n\n* **Discrete Contrastive and Betweenness.** When the dimension is one (on a real line), it is not hard to simulate a cut of a graph through discrete contrastive triplets since all vertices of the graph either fall into the left side or the right side of some reference vertex $X$. However, this problem becomes **significantly harder** in high dimensional space. One of the main challenges is that the notion of left side and right side of reference vertex $X$ becomes unclear in high dimensional spaces. In fact, if we construct the same triplets as in the 1D case, all the vertices will be located on different circles centered at $X$ and we would not be able to simulate a cut out of such geometrical configuration of vertices. The key novelty of the high dimensional reduction comes from the Isosceles gadget and the the Equilateral gadget (line 494 - 499), which allow us to simulate a cut of the graph through the relative position between the vertices and a regular simplex enforced by the gadgets. As a result, the triplets we construct in high dimensional case are drastically different from the ones in 1D case and exhibit significant technical insights.\n\n* **Discrete Tree embeddings.** The main challenge for tree embeddings is that unlike the Euclidean embeddings where we can leverage on the properties of the geometric configuration of vertices, tree embeddings are purely combinatorial and lack inherent geometric properties. To bypass this difficulty, we introduce several gadgets that effectively enforce all the vertices to lie on one of the two subtrees. In this way we can simulate a cut of the graph through checking which subtree each vertex lies in. We believe that the gadgets implemented in the tree reduction introduce strong theoretic contributions and could be of independent interest for other hardness reductions involving tree structures.\n\n* **Continuous contrastive learning.** The principle observation for the continuous contrastive learning reduction is to identify the significance of pivot points. As we emphasized in line 189-193, without the introduction of pivot points, the learning task would become trivial as there would be trivial first-order stationary point where all points overlap with each other. Another technical obstacle for this reduction is the coupling between the triplet constructed due to shared variables (line 288-295). We manage to overcome this barrier and reconstruct any quadratic program with three variables through a careful design of triplets and corresponding weights. Finally, we acquire the CLS-hardness result by extending the reduction to high dimensional quadratic programs.\n\nWe thank the reviewer again for the time they spent on providing feedbacks. We hope our comments address their concerns. We would really appreciate if they would reconsider their evaluation of our work.\n\nBest regards,\n\nThe authors."}, {"review_id": "89v3g1PKjd", "reviewer": "Reviewer_dqwU", "summary": "This paper studies contrastive learning, where the input consists of a set of triplets $(x_i, y_i^+,z_i^- )$. This indicates $x_i$ is more similar to $y_i^+$ than to $z_i^-$. Each triplet is associated with weight $w_i$. The objective l is to learn an embedding such that the embedding of $x_i$ is closer to $y_i$ than to $z_i$ . The paper provides the computational complexity of finding locally optimal solutions with three loss formulations for both discrete and continuous settings. Its main contribution is providing proof that optimizing these contrastive loss functions is either PLS-hard or CLS-hard.", "questions": "- Could you clarify the difference between the continuous and discrete settings? I assume the distinction is whether the inputs  $(x_i, y_i^+,z_i^- )$ take values in a continuous or discrete space. But loss is optimized over the space of embedding parameters $\\theta$. $\\theta$ can be continuous even if the   $(x_i, y_i^+,z_i^- )$ are discrete?\n\n- What does the weight $w_i$ represent in practice? How is the importance of a triplet determined?\n\n- I am interested to know if you can provide a practical application of the setting. \n- What would the complexity and suboptimality in an online (dynamic) optimization setting, where the model is updated based on the arrival of each new triplet?\n- Reinforcement Learning from Human Feedback (RLHF) and Direct Preference Optimization (DPO) also consider learning from pairwise preference, where users indicate that they prefer $y$ to $z$. Can the theoretical analysis in this paper be extended to cover such settings?", "limitations": "I do not see any immediate potential negative societal impact.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nComprehensive Theoretical study. \n\nWeakness:\nLack of empirical validation. Currently the result show the number of iterations increase exponentially with the number of vertices. How suboptimal the result would be if it is run using SGD for a finite number of epcohs, which is common in learning embedding.", "was_revised": true, "final_justification": "The authors have addressed my question about the paper. As I stated prior to the rebuttal, this is primarily a theoretical work. While I agree with Reviewers XHnj and VGp6 that additional empirical analysis could further strengthen the paper by demonstrating its practical applicability, I believe the theoretical contributions are well-presented and solid. So, I will maintain my positive rating.", "rebuttal": "We thank the reviewer for their time and positive feedbacks.\n\n> \"Lack of empirical validation.\"\n\nThe main focus of this paper deals with worst-case runtime analysis of local search methods in various contrastive settings and the purpose of our experiments is only to validate our theoretical findings. As we point out in the Conclusion section (line 334 - 338), we deem other theoretical frameworks such as average-case analysis, smoothed analysis, beyond worst-case analysis, and the corresponding empirical validations interesting but go well beyond the scope of our work. For more details regarding the significance of worst-case analysis along with other theoretical models that captures more practical settings, we refer the reviewer to our discussion with Reviewer VGp6 and Reviewer XHnj.\n\n> \"Currently the result show the number of iterations increase exponentially with the number of vertices. How suboptimal the result would be if it is run using SGD for a finite number of epcohs, which is common in learning embedding.\"\n\nThe objective function we consider in the experiment is the discrete objective function $\\sum_{i = 1}^m w_i \\cdot \\mathbf{1}_{(x_i, y_i, z_i)}$ (see our response below regarding the differences between discrete and continuous settings). Due to its discrete nature, it would not be applicable to perform gradient descent on this problem. The local search method in our experiment is natural to the discrete setting and, even the convergence rate is exponential, is guaranteed to converge to a locally optimal point.\n\n> \"Could you clarify the difference between the continuous and discrete settings? I assume the distinction is whether the inputs $(x_i, y_i^+, z_i^-)$ take values in a continuous or discrete space. But loss is optimized over the space of embedding parameters $\\theta$. $\\theta$ can be continuous even if the $(x_i, y_i^+, z_i^-)$ are discrete?\"\n\nThe main distinction between the continuous and discrete settings is whether the objective function is a continuous function. For discrete settings, the typical objective function we consider is $\\sum_{i = 1}^m w_i \\cdot \\mathbf{1}_{(x_i,y_i, z_i)}$ which is a weighted sum of indicators of whether triplet $(x_i, y_i, z_i)$ is satisfied (which is discontinuous). For continuous settings, the objective we consider is the triplet loss function defined in line 186. Notice that this objective function is continuous and we can perform gradient descent to continuous settings.\n\nRegarding the solution space, (i.e., the \"space of embedding parameters $\\theta$\"), it is a continuous space (either $R^d$ or $[0, 1]^d$) in all Euclidean embedding settings (regardless of whether the objective function is continuous or discrete), and is a discrete space in the tree embedding setting (LocalContrastive-Tree).\n\n> \"What does the weight $w_i$ represent in practice? How is the importance of a triplet determined?\"\n\nThe weights $w_i$ serve as a way to determine the importance of given triplets and are usually provided as the input of the problem, just like how the weights of edges are provided in a graph. One way to formulate the weight is that if we consider triplet $(x, y^+, z^-)$ as the constraint that the embedding needs to satisfy, where $w_i$ could be viewed as the cost if such constraint is not satisfied.\n\n> \"I am interested to know if you can provide a practical application of the setting.\"\n\nAs we discussed in the Introduction (line 36-43), many interesting and widely-used applications in our setting include nearest-neighbor, recommendation, ranking, and crowdsourcing. As for our theoretical findings, we would like to emphasize that our paper focuses on providing the first computational hardness results in such settings and could serve as a stepping stone for interesting future works that investigate practical behavior over real-world datasets. We refer the reviewer to our discussion with Reviewer VGp6 and Reviewer XHnj for the significance of worst-case analysis and other theoretical frameworks that capture more practical settings.\n\n> \"What would the complexity and suboptimality in an online (dynamic) optimization setting, where the model is updated based on the arrival of each new triplet?\"\n\nWe address that all our setting assume the algorithms have full access to the input set of triplets and their corresponding weights. Accessing the triplets in an online setting is at least as hard as the full information setting so all our hardness results extend to the online setting.\n\n> \"Reinforcement Learning from Human Feedback (RLHF) and Direct Preference Optimization (DPO) also consider learning from pairwise preference, where users indicate that they prefer $y$ to $z$. Can the theoretical analysis in this paper be extended to cover such settings?\"\n\nWe can formulate RLHF and DPO problems in a contrastive setting such that the model queries are considered as anchor points ($x$), the preferred choices are treated as positive points ($y^+$), and the less preferred choices are viewed as negative points ($z^-$). If the objective functions in this formulation match the settings we study in this work (Contrastive-Euclidean, Contrastive-Tree, Betweenness-Euclidean, or TripletLoss), then our hardness results apply to those problems.\n\nWe would like to thank the reviewer again for their valuable time and helpful comments. We hope our response addresses their concerns. We would really appreciate if the reviewer would reconsider their evaluation of our work.\n\nBest regards,\n\nThe authors."}]

Author rebuttal:

Meta-review: The paper shows that in Contrastive Learning it is hard to fund even a local minima. This type of hardness result is stronger that the usual hardness of learning typically shown. Most of the reviewers therefore found the result of interest and I recommend acceptance.
Decision: Accept (poster)