Optimization

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
Michael B. Cohen (MIT), Aaron Sidford (Stanford University), Kevin Tian (Stanford University)

Majorizing Measures for the Optimizer
Sander Borst (CWI Amsterdam), Daniel Dadush (CWI Amsterdam), Neil Olver (London School of Economics), Makrand Sinha (CWI Amsterdam)

Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation
Cameron Musco (University of Massachusetts Amherst), Christopher Musco (New York University), David P. Woodruff (Carnegie Mellon University)

Agnostic learning with unknown utilities
Kush Bhatia (University of California Berkeley), Peter L. Bartlett (University of California, Berkeley), Anca Dragan (University of California, Berkeley), Jacob Steinhardt (University of California, Berkeley)

No quantum speedup over gradient descent for non-smooth convex optimization
Ankit Garg (Microsoft Research), Robin Kothari (Microsoft Quantum), Praneeth Netrapalli (Microsoft Research), Suhail Sherif (School of Technology and Computer Science, TIFR, Mumbai)

ITCS 2021