Cover Image

The Complexity of Finding Local Optima in Contrastive Learning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yan, Jingming, Luo, Yiyuan, Chatziafratis, Vaggos, Panageas, Ioannis, Shahkar, Parnian, Stavroulakis, Stelios
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
by: Hollender, Alexandros, et al.
Published: (2023)

Welfare Approximation in Additively Separable Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
by: Daskalakis, Constantinos, et al.
Published: (2018)

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
by: Lu, Yiyang, et al.
Published: (2025)

From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
by: Pedramfar, Mohammad, et al.
Published: (2024)

Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs
by: Endor, Faniriana Rakoto, et al.
Published: (2024)

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
by: Daskalakis, Constantinos, et al.
Published: (2018)

High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise
by: Fang, Yuchen, et al.
Published: (2025)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
by: Bassan, Shahaf, et al.
Published: (2026)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
by: Blanchard, Moise
Published: (2024)

A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization
by: Liu, Wei, et al.
Published: (2025)

Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
by: Jadav, Hareshkumar, et al.
Published: (2026)

Submodular Information Selection for Hypothesis Testing with Misclassification Penalties
by: Bhargav, Jayanth, et al.
Published: (2024)

Second-Order Min-Max Optimization with Lazy Hessians
by: Chen, Lesi, et al.
Published: (2024)

On Approximate Computation of Critical Points
by: Ahmadi, Amir Ali, et al.
Published: (2026)

Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
by: Pedramfar, Mohammad, et al.
Published: (2024)

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
by: Barakat, Anas, et al.
Published: (2026)

The Adaptive Complexity of Finding a Stationary Point
by: Zhou, Huanjian, et al.
Published: (2025)

On the Complexity of p-Order Cone Programs
by: Blanco, Víctor, et al.
Published: (2025)

The Complexity of Recognizing Facets for the Knapsack Polytope
by: Chen, Rui, et al.
Published: (2022)

The Complexity of Computing KKT Solutions of Quadratic Programs
by: Fearnley, John, et al.
Published: (2023)

Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
by: Tyurin, Alexander
Published: (2024)

Arithmetic Circuits and Neural Networks for Regular Matroids
by: Hertrich, Christoph, et al.
Published: (2025)

Efficient Convex Optimization Requires Superlinear Memory
by: Marsden, Annie, et al.
Published: (2022)

Neural Networks and (Virtual) Extended Formulations
by: Hertrich, Christoph, et al.
Published: (2024)

Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
by: Arvanitakis, Dionysis, et al.
Published: (2026)

Subgradient Method for System Identification with Non-Smooth Objectives
by: Yalcin, Baturalp, et al.
Published: (2025)

Linear Equations with Min and Max Operators: Computational Complexity
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Convergence of Regret Matching in Potential Games and Constrained Optimization
by: Anagnostides, Ioannis, et al.
Published: (2025)

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms
by: Bhargav, Jayanth, et al.
Published: (2024)

Learning complexity of gradient descent and conjugate gradient algorithms
by: Jiao, Xianqi, et al.
Published: (2024)

A Parameterized-Complexity Framework for Finding Local Optima
by: Ganian, Robert, et al.
Published: (2026)

On the Computational Complexity of Multi-Objective Ordinal Unconstrained Combinatorial Optimization
by: Figueira, José Rui, et al.
Published: (2024)

Efficient LP warmstarting for linear modifications of the constraint matrix
by: Derval, Guillaume, et al.
Published: (2025)

On the Degree Automatability of Sum-of-Squares Proofs
by: Bortolotti, Alex, et al.
Published: (2025)

Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
by: Büsing, Christina, et al.
Published: (2025)

Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions
by: Chen, Ying, et al.
Published: (2025)

Counterfactual Explanations for Integer Optimization Problems
by: Engelhardt, Felix, et al.
Published: (2025)

A parameterized linear formulation of the integer hull
by: Eisenbrand, Friedrich, et al.
Published: (2025)