8 papers
Faster Algorithms for Multimarginal Optimal Transport
Brandon Augustino, Yue Sun, Atithi Acharya +4
We study algorithms for approximating the multimarginal optimal transport (MOT) distance, a generalization of the classic optimal transport distance, between discrete probabili…
Anytime Training with Schedule-Free Spectral Optimization
Anuj Apte, Pranav Deshpande, Niraj Kumar +2
Standard neural network training relies on learning-rate schedules tied to a fixed horizon, leading to strong path dependence and costly re-tuning as data availability changes. Sch…
Quantum Speedups for Group Relaxations of Integer Linear Programs
Brandon Augustino, Dylan Herman, Guneykan Ozgul +5
Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-qua…
End-to-end quantum algorithms for tensor problems
Enrico Fontana, Sivaprasad Omanakuttan, Junhyung Lyle Kim +4
We present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over cla…
Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions
Dylan Herman, Guneykan Ozgul, Anuj Apte +4
We present new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, expanding the scope of quantum advantage beyond traditional tunneling-b…
On Speedups for Convex Optimization via Quantum Dynamics
Shouvanik Chakrabarti, Dylan Herman, Jacob Watkins +4
We explore the potential for quantum speedups in convex optimization using discrete simulations of the Quantum Hamiltonian Descent (QHD) framework, as proposed by Leng et al., and…