Optimization
18Relative 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
Other Videos By Simons Institute for the Theory of Computing
| 2021-01-15 | Sharp Threshold Rates for Random Codes |
| 2021-01-15 | The Complexity of Finding Fair Independent Sets in Cycles |
| 2021-01-15 | Algorithmic Persuasion with Evidence |
| 2021-01-15 | Comparing computational entropies below majority (or: When is the dense model theorem false?) |
| 2021-01-15 | The entropy of lies: playing twenty questions with a liar |
| 2021-01-12 | Error Correcting Codes for Uncompressed Messages |
| 2021-01-12 | Algorithms and Hardness for Multidimensional Range Updates and Queries |
| 2021-01-12 | Algebraic and circuit complexity |
| 2021-01-12 | Online and streaming algorithms |
| 2021-01-12 | Algorithmic Game Theory |
| 2021-01-12 | Optimization |
| 2021-01-12 | Codes and information |
| 2021-01-12 | Machine Learning |
| 2021-01-11 | Circuits and communication |
| 2021-01-10 | Graph algorithms |
| 2021-01-10 | Algorithms |
| 2021-01-10 | GRADUATING BITS |
| 2021-01-10 | Algorithmic game theory |
| 2021-01-10 | Quantum information |
| 2021-01-10 | Quantum |
| 2021-01-09 | Analytic methods |