COLT 2020: The No-Frills Schedule

Wednesday 2020-07-08 03:00 AoE	WiML-T Lunch
Thursday 2020-07-09 00:30 AoE	Session 1A (Session chair: Jayadev Acharya) [Zoom link for plenary]
	1. Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices Alia Abbara, Florent Krzakala, Cedric Gerbelot [Zoom link for poster session]
	2. Sharper Bounds for Uniformly Stable Algorithms Olivier Bousquet, Yegor Klochkov, Nikita Zhivotovskiy [Zoom link for poster session]
	3. A Greedy Anytime Algorithm for Sparse PCA Dan Vilenchik, Adam Soffer, Guy Holtzman [Zoom link for poster session]
	4. Data-driven confidence bands for distributed nonparametric regression Valeriy Avanesov [Zoom link for poster session]
	5. A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere Marco Schmalhofer [Zoom link for poster session]
	6. Privately Learning Thresholds: Closing the Exponential Gap Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, Uri Stemmer [Zoom link for poster session]
	7. Pan-Private Uniformity Testing Kareem Amin, Matthew Joseph, Jieming Mao [Zoom link for poster session]
	8. Parallels Between Phase Transitions and Circuit Complexity? Colin P Sandon, Ankur Moitra, Elchanan Mossel [Zoom link for poster session]
	9. Closure Properties for Private Classification and Online Prediction Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer [Zoom link for poster session]
	10. Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models Antonio Blanca, Zongchen Chen, Eric Vigoda, Daniel Stefankovic [Zoom link for poster session]
Thursday 2020-07-09 03:00 AoE	Keynote 1: Salil Vadhan (+ Opening Remarks) [Zoom link for plenary]
Thursday 2020-07-09 04:05 AoE	Coffee Break 1A
Thursday 2020-07-09 05:00 AoE	Session 1B (Session chair: Aravindan Vijayaraghavan) [Zoom link for plenary]
	1. PAC learning with stable and private predictions Yuval Dagan, Vitaly Feldman [Zoom link for poster session]
	2. ID3 Learns Juntas for Smoothed Product Distributions Eran Malach, Amit Daniely, Alon Brutzkus [Zoom link for poster session]
	3. Efficient Parameter Estimation of Truncated Boolean Product Distributions Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos [Zoom link for poster session]
	4. Hierarchical Clustering: A 0.585 Revenue Approximation Noga Alon, Yossi Azar, Danny Vainstein [Zoom link for poster session]
	5. From tree matching to sparse graph alignment Luca Ganassali, Laurent Massoulie [Zoom link for poster session]
	6. Bounds in query learning Hunter S Chase, James Freitag [Zoom link for poster session]
	7. Bessel Smoothing and Multi-Distribution Property Estimation Yi Hao, Ping Li [Zoom link for poster session]
	8. Proper Learning, Helly Number, and an Optimal SVM Bound Olivier Bousquet, Steve Hanneke, Shay Moran, Nikita Zhivotovskiy [Zoom link for poster session]
	9. Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities Jelena Diakonikolas [Zoom link for poster session]
	10. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes Alekh Agarwal, Sham Kakade, Jason Lee, Gaurav Mahajan [Zoom link for poster session]
	11. High probability guarantees for stochastic convex optimization Damek Davis, Dmitriy Drusvyatskiy [Zoom link for poster session]
	12. Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond Oliver Hinder, Aaron Sidford, Nimit S Sohoni [Zoom link for poster session]
	13. Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning Guannan Qu, Adam Wierman [Zoom link for poster session]
	14. Highly smooth minimization of non-smooth problems Brian Bullins [Zoom link for poster session]
	15. The estimation error of general first order methods Michael V Celentano, Andrea Montanari, Yuchen Wu [Zoom link for poster session]
Thursday 2020-07-09 07:30 AoE	Coffee Break 1B
Thursday 2020-07-09 12:00 AoE	Session 1C (Session chair: Rachel Cummings) [Zoom link for plenary]
	1. Pan-Private Uniformity Testing Kareem Amin, Matthew Joseph, Jieming Mao [Zoom link for poster session]
	2. Parallels Between Phase Transitions and Circuit Complexity? Colin P Sandon, Ankur Moitra, Elchanan Mossel [Zoom link for poster session]
	3. Closure Properties for Private Classification and Online Prediction Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer [Zoom link for poster session]
	4. Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models Antonio Blanca, Zongchen Chen, Eric Vigoda, Daniel Stefankovic [Zoom link for poster session]
	5. Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning Mikito Nanashima [Zoom link for poster session]
	6. Lipschitz and Comparator-Norm Adaptivity in Online Learning Zakaria Mhammedi, Wouter M Koolen [Zoom link for poster session]
	7. Locally Private Hypothesis Selection Sivakanth Gopi, Gautam Kamath, Janardhan D Kulkarni, Aleksandar Nikolov, Steven Wu, Huanyu Zhang [Zoom link for poster session]
	8. Private Mean Estimation of Heavy-Tailed Distributions Gautam Kamath, Vikrant Singhal, Jonathan Ullman [Zoom link for poster session]
	9. Consistent recovery threshold of hidden nearest neighbor graphs Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang [Zoom link for poster session]
	10. Adaptive Submodular Maximization under Stochastic Item Costs Srinivasan Parthasarathy [Zoom link for poster session]
Thursday 2020-07-09 14:00 AoE	Coffee Break 1C and Baidu booth
Thursday 2020-07-09 15:00 AoE	Session 1D (Session chair: Praneeth Netrapalli) [Zoom link for plenary]
	1. Bounds in query learning Hunter S Chase, James Freitag [Zoom link for poster session]
	2. Bessel Smoothing and Multi-Distribution Property Estimation Yi Hao, Ping Li [Zoom link for poster session]
	3. Proper Learning, Helly Number, and an Optimal SVM Bound Olivier Bousquet, Steve Hanneke, Shay Moran, Nikita Zhivotovskiy [Zoom link for poster session]
	4. Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes Alekh Agarwal, Sham Kakade, Jason Lee, Gaurav Mahajan [Zoom link for poster session]
	5. High probability guarantees for stochastic convex optimization Damek Davis, Dmitriy Drusvyatskiy [Zoom link for poster session]
	6. Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond Oliver Hinder, Aaron Sidford, Nimit S Sohoni [Zoom link for poster session]
	7. Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning Guannan Qu, Adam Wierman [Zoom link for poster session]
	8. Highly smooth minimization of non-smooth problems Brian Bullins [Zoom link for poster session]
	9. The estimation error of general first order methods Michael V Celentano, Andrea Montanari, Yuchen Wu [Zoom link for poster session]
Thursday 2020-07-09 20:00 AoE	Session 1E (Session chair: Prateek Jain) [Zoom link for plenary]
	1. Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices Alia Abbara, Florent Krzakala, Cedric Gerbelot [Zoom link for poster session]
	2. Sharper Bounds for Uniformly Stable Algorithms Olivier Bousquet, Yegor Klochkov, Nikita Zhivotovskiy [Zoom link for poster session]
	3. A Greedy Anytime Algorithm for Sparse PCA Dan Vilenchik, Adam Soffer, Guy Holtzman [Zoom link for poster session]
	4. Data-driven confidence bands for distributed nonparametric regression Valeriy Avanesov [Zoom link for poster session]
	5. A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere Marco Schmalhofer [Zoom link for poster session]
	6. Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank Kefan Dong, Jian Peng, Yining Wang, Yuan Zhou [Zoom link for poster session]
	7. Calibrated Surrogate Losses for Adversarially Robust Classification Han Bao, Clayton Scott, Masashi Sugiyama [Zoom link for poster session]
	8. Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding Xiaotong Yuan, Ping Li [Zoom link for poster session]
	9. Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise Maksim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, Hoi-To Wai [Zoom link for poster session]
Thursday 2020-07-09 22:00 AoE	Coffee Break 1E
Friday 2020-07-10 00:30 AoE	Session 2A (Session chair: Tim van Erven) [Zoom link for plenary]
	1. The Influence of Shape Constraints on the Thresholding Bandit Problem James Cheshire, Pierre Menard, Alexandra Carpentier [Zoom link for poster session]
	2. Selfish Robustness and Equilibria in Multi-Player Bandits Etienne Boursier, Vianney Perchet [Zoom link for poster session]
	3. Exploration by Optimisation in Partial Monitoring Tor Lattimore, Csaba Szepesvari [Zoom link for poster session]
	4. Information Directed Sampling for Linear Partial Monitoring Johannes Kirschner, Tor Lattimore, Andreas Krause [Zoom link for poster session]
	5. Tight Lower Bounds for Combinatorial Multi-Armed Bandits Nadav Merlis, Shie Mannor [Zoom link for poster session]
	6. Efficient and robust algorithms for adversarial linear contextual bandits Gergely Neu, Julia Olkhovskaya [Zoom link for poster session]
	7. Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits Chloé Rouyer , Yevgeny Seldin [Zoom link for poster session]
	8. Near-Optimal Algorithms for Minimax Optimization Tianyi Lin, Chi Jin, Michael Jordan [Zoom link for poster session]
	9. Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations Yossi Arjevani, Yair Carmon, John Duchi, Dylan Foster, Ayush Sekhari, Karthik Sridharan [Zoom link for poster session]
	10. On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter Bartlett, Michael Jordan [Zoom link for poster session]
	11. Gradient descent algorithms for Bures-Wasserstein barycenters Sinho Chewi, Philippe Rigollet, Tyler Maunu, Austin Stromme [Zoom link for poster session]
	12. From Nesterov's Estimate Sequence to Riemannian Acceleration Kwangjun Ahn, Suvrit Sra [Zoom link for poster session]
	13. Provably Efficient Reinforcement Learning with Linear Function Approximation Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael Jordan [Zoom link for poster session]
	14. Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal Alekh Agarwal, Sham Kakade, Lin Yang [Zoom link for poster session]
	15. Wasserstein Control of Mirror Langevin Monte Carlo Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, Marcelo Pereyra [Zoom link for poster session]
Friday 2020-07-10 03:00 AoE	Keynote 2: Rebecca Willett [Zoom link for plenary]
Friday 2020-07-10 04:00 AoE	Coffee Break 2A
Friday 2020-07-10 05:00 AoE	Session 2B (Session chair: Kfir Levy) [Zoom link for plenary]
	1. How to trap a gradient flow Dan Mikulincer, Sebastien Bubeck [Zoom link for poster session]
	2. On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems Dan Garber [Zoom link for poster session]
	3. Learning a Single Neuron with Gradient Methods Gilad Yehudai, Ohad Shamir [Zoom link for poster session]
	4. Complexity Guarantees for Polyak Steps with Momentum Mathieu Barre, Adrien B Taylor, Alexandre d'Aspremont [Zoom link for poster session]
	5. On Suboptimality of Least Squares with Application to Estimation of Convex Bodies Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina [Zoom link for poster session]
	6. How Good is SGD with Random Shuffling? Itay M Safran, Ohad Shamir [Zoom link for poster session]
	7. The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians Jeongyeol Kwon, Constantine Caramanis [Zoom link for poster session]
	8. Learning Halfspaces with Massart Noise Under Structured Distributions Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis [Zoom link for poster session]
	9. Estimating Principal Components under Adversarial Perturbations Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan [Zoom link for poster session]
	10. An O(m/eps^3.5)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints Swati Padmanabhan, Yin Tat Lee [Zoom link for poster session]
	11. Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Nikos Zarifis [Zoom link for poster session]
	12. Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity Pritish Kamath, Omar Montasser, Nathan Srebro [Zoom link for poster session]
	13. Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant [Zoom link for poster session]
	14. Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK Yuanzhi Li, Tengyu Ma, Hongyang R Zhang [Zoom link for poster session]
	15. Information Theoretic Optimal Learning of Gaussian Graphical Models Sidhant Misra, Marc D Vuffray, Andrey Lokhov [Zoom link for poster session]
Friday 2020-07-10 07:30 AoE	Coffee Break 2B and Baidu booth
Friday 2020-07-10 12:00 AoE	Session 2C (Session chair: Alekh Agarwal) [Zoom link for plenary]
	1. Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities Jelena Diakonikolas [Zoom link for poster session]
	2. Near-Optimal Algorithms for Minimax Optimization Tianyi Lin, Chi Jin, Michael Jordan [Zoom link for poster session]
	3. Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations Yossi Arjevani, Yair Carmon, John Duchi, Dylan Foster, Ayush Sekhari, Karthik Sridharan [Zoom link for poster session]
	4. On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter Bartlett, Michael Jordan [Zoom link for poster session]
	5. Gradient descent algorithms for Bures-Wasserstein barycenters Sinho Chewi, Philippe Rigollet, Tyler Maunu, Austin Stromme [Zoom link for poster session]
	6. From Nesterov's Estimate Sequence to Riemannian Acceleration Kwangjun Ahn, Suvrit Sra [Zoom link for poster session]
	7. Provably Efficient Reinforcement Learning with Linear Function Approximation Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael Jordan [Zoom link for poster session]
	8. Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal Alekh Agarwal, Sham Kakade, Lin Yang [Zoom link for poster session]
	9. Wasserstein Control of Mirror Langevin Monte Carlo Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, Marcelo Pereyra [Zoom link for poster session]
	10. Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank Kefan Dong, Jian Peng, Yining Wang, Yuan Zhou [Zoom link for poster session]
	11. Calibrated Surrogate Losses for Adversarially Robust Classification Han Bao, Clayton Scott, Masashi Sugiyama [Zoom link for poster session]
	12. Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding Xiaotong Yuan, Ping Li [Zoom link for poster session]
Friday 2020-07-10 14:00 AoE	Coffee Break 2C
Friday 2020-07-10 15:00 AoE	Session 2D (Session chair: Kamalika Chaudhuri) [Zoom link for plenary]
	1. The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians Jeongyeol Kwon, Constantine Caramanis [Zoom link for poster session]
	2. Learning Halfspaces with Massart Noise Under Structured Distributions Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis [Zoom link for poster session]
	3. Estimating Principal Components under Adversarial Perturbations Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan [Zoom link for poster session]
	4. An O(m/eps^3.5)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints Swati Padmanabhan, Yin Tat Lee [Zoom link for poster session]
	5. Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Nikos Zarifis [Zoom link for poster session]
	6. Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity Pritish Kamath, Omar Montasser, Nathan Srebro [Zoom link for poster session]
	7. Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant [Zoom link for poster session]
	8. Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK Yuanzhi Li, Tengyu Ma, Hongyang R Zhang [Zoom link for poster session]
	9. Information Theoretic Optimal Learning of Gaussian Graphical Models Sidhant Misra, Marc D Vuffray, Andrey Lokhov [Zoom link for poster session]
Friday 2020-07-10 20:00 AoE	Session 2E (Session chair: Wouter Koolen) [Zoom link for plenary]
	1. The Influence of Shape Constraints on the Thresholding Bandit Problem James Cheshire, Pierre Menard, Alexandra Carpentier [Zoom link for poster session]
	2. Selfish Robustness and Equilibria in Multi-Player Bandits Etienne Boursier, Vianney Perchet [Zoom link for poster session]
	3. Exploration by Optimisation in Partial Monitoring Tor Lattimore, Csaba Szepesvari [Zoom link for poster session]
	4. Information Directed Sampling for Linear Partial Monitoring Johannes Kirschner, Tor Lattimore, Andreas Krause [Zoom link for poster session]
	5. Tight Lower Bounds for Combinatorial Multi-Armed Bandits Nadav Merlis, Shie Mannor [Zoom link for poster session]
	6. Efficient and robust algorithms for adversarial linear contextual bandits Gergely Neu, Julia Olkhovskaya [Zoom link for poster session]
	7. Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits Chloé Rouyer , Yevgeny Seldin [Zoom link for poster session]
	8. Faster Projection-free Online Learning Elad Hazan, Edgar Minasyan [Zoom link for poster session]
	9. Fast Rates for Online Prediction with Abstention Gergely Neu, Nikita Zhivotovskiy [Zoom link for poster session]
	10. Pessimism About Unknown Unknowns Inspires Conservatism Michael K Cohen, Marcus Hutter [Zoom link for poster session]
	11. Covariance-adapting algorithm for semi-bandits with application to sparse outcomes Pierre Perrault, Vianney Perchet, Michal Valko [Zoom link for poster session]
Friday 2020-07-10 22:00 AoE	Coffee Break 2E
Saturday 2020-07-11 00:30 AoE	Session 3A (Session chair: Tim van Erven) [Zoom link for plenary]
	1. Faster Projection-free Online Learning Elad Hazan, Edgar Minasyan [Zoom link for poster session]
	2. Fast Rates for Online Prediction with Abstention Gergely Neu, Nikita Zhivotovskiy [Zoom link for poster session]
	3. Pessimism About Unknown Unknowns Inspires Conservatism Michael K Cohen, Marcus Hutter [Zoom link for poster session]
	4. Covariance-adapting algorithm for semi-bandits with application to sparse outcomes Pierre Perrault, Vianney Perchet, Michal Valko [Zoom link for poster session]
	5. A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates Zhixian Lei, Kyle Luh, Prayaag Venkat, Fred Zhang [Zoom link for poster session]
	6. Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion William C Franks, Ankur Moitra [Zoom link for poster session]
	7. Tree-projected gradient descent for estimating gradient-sparse parameters on graphs Sheng Xu, Zhou Fan, Sahand Negahban [Zoom link for poster session]
	8. Balancing Gaussian vectors in high dimension Paxton M Turner, Raghu Meka, Philippe Rigollet [Zoom link for poster session]
	9. On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels Tengyuan Liang, Alexander Rakhlin, Xiyu Zhai [Zoom link for poster session]
	10. Estimation and Inference with Trees and Forests in High Dimensions Vasilis Syrgkanis, Emmanouil Zampetakis [Zoom link for poster session]
	11. Costly Zero Order Oracles Renato Paes Leme, Jon Schneider [Zoom link for poster session]
	12. Precise Tradeoffs in Adversarial Training for Linear Regression Adel Javanmard, Mahdi Soltanolkotabi, Hamed Hassani [Zoom link for poster session]
	13. Free Energy Wells and Overlap Gap Property in Sparse PCA Gerard Ben Arous, Alexander S. Wein, Ilias Zadik [Zoom link for poster session]
	14. Learning Polynomials in Few Relevant Dimensions Sitan Chen, Raghu Meka [Zoom link for poster session]
	15. Private Mean Estimation of Heavy-Tailed Distributions Gautam Kamath, Vikrant Singhal, Jonathan Ullman [Zoom link for poster session]
	16. Consistent recovery threshold of hidden nearest neighbor graphs Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang [Zoom link for poster session]
Saturday 2020-07-11 03:00 AoE	Keynote 3: David Blei [Zoom link for plenary]
Saturday 2020-07-11 04:00 AoE	Coffee Break 3A
Saturday 2020-07-11 05:00 AoE	Session 3B (Session chair: Csaba Szepesvari) [Zoom link for plenary]
	1. Efficient improper learning for online logistic regression Pierre Gaillard, Rémi Jézéquel, Alessandro Rudi [Zoom link for poster session]
	2. Improper Learning for Non-Stochastic Control Max Simchowitz, Karan Singh, Elad Hazan [Zoom link for poster session]
	3. Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without Sebastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke [Zoom link for poster session]
	4. Coordination without communication: optimal regret in two players multi-armed bandits Sebastien Bubeck, Thomas Budzinski [Zoom link for poster session]
	5. Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent James P Bailey, Gauthier Gidel, Georgios Piliouras [Zoom link for poster session]
	6. A Closer Look at Small-loss Bounds for Bandits with Graph Feedback Chung-Wei Lee, Haipeng Luo, Mengxiao Zhang [Zoom link for poster session]
	7. Winnowing with Gradient Descent Ehsan Amid, Manfred K. Warmuth [Zoom link for poster session]
	8. Taking a hint: How to leverage loss predictors in contextual bandits? Chen-Yu Wei, Haipeng Luo, Alekh Agarwal [Zoom link for poster session]
	9. The Gradient Complexity of Linear Regression Mark Braverman, Elad Hazan, Max Simchowitz, Blake E Woodworth [Zoom link for poster session]
	10. Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo Yin Tat Lee, Ruoqi Shen, Kevin Tian [Zoom link for poster session]
	11. Kernel and Rich Regimes in Overparametrized Models Blake E Woodworth, Suriya Gunasekar, Jason Lee, Edward Moroshko, Pedro Henrique Pamplona Savarese, Itay Golan, Daniel Soudry, Nathan Srebro [Zoom link for poster session]
	12. Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang [Zoom link for poster session]
	13. Gradient descent follows the regularization path for general losses Ziwei Ji, Miroslav Dudik, Robert Schapire, Matus Telgarsky [Zoom link for poster session]
	14. Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar [Zoom link for poster session]
Saturday 2020-07-11 07:30 AoE	Coffee Break 3B
Saturday 2020-07-11 12:00 AoE	Session 3C (Session chair: Dylan Foster) [Zoom link for plenary]
	1. A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates Zhixian Lei, Kyle Luh, Prayaag Venkat, Fred Zhang [Zoom link for poster session]
	2. Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion William C Franks, Ankur Moitra [Zoom link for poster session]
	3. Tree-projected gradient descent for estimating gradient-sparse parameters on graphs Sheng Xu, Zhou Fan, Sahand Negahban [Zoom link for poster session]
	4. Balancing Gaussian vectors in high dimension Paxton M Turner, Raghu Meka, Philippe Rigollet [Zoom link for poster session]
	5. On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels Tengyuan Liang, Alexander Rakhlin, Xiyu Zhai [Zoom link for poster session]
	6. Estimation and Inference with Trees and Forests in High Dimensions Vasilis Syrgkanis, Emmanouil Zampetakis [Zoom link for poster session]
	7. Costly Zero Order Oracles Renato Paes Leme, Jon Schneider [Zoom link for poster session]
	8. Precise Tradeoffs in Adversarial Training for Linear Regression Adel Javanmard, Mahdi Soltanolkotabi, Hamed Hassani [Zoom link for poster session]
	9. Free Energy Wells and Overlap Gap Property in Sparse PCA Gerard Ben Arous, Alexander S. Wein, Ilias Zadik [Zoom link for poster session]
	10. Learning Polynomials in Few Relevant Dimensions Sitan Chen, Raghu Meka [Zoom link for poster session]
Saturday 2020-07-11 14:00 AoE	Coffee Break 3C
Saturday 2020-07-11 15:00 AoE	Session 3D (Session chair: Sanjoy Dasgupta) [Zoom link for plenary]
	1. Improper Learning for Non-Stochastic Control Max Simchowitz, Karan Singh, Elad Hazan [Zoom link for poster session]
	2. Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without Sebastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke [Zoom link for poster session]
	3. Coordination without communication: optimal regret in two players multi-armed bandits Sebastien Bubeck, Thomas Budzinski [Zoom link for poster session]
	4. Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent James P Bailey, Gauthier Gidel, Georgios Piliouras [Zoom link for poster session]
	5. A Closer Look at Small-loss Bounds for Bandits with Graph Feedback Chung-Wei Lee, Haipeng Luo, Mengxiao Zhang [Zoom link for poster session]
	6. Winnowing with Gradient Descent Ehsan Amid, Manfred K. Warmuth [Zoom link for poster session]
	7. Taking a hint: How to leverage loss predictors in contextual bandits? Chen-Yu Wei, Haipeng Luo, Alekh Agarwal [Zoom link for poster session]
	8. The Gradient Complexity of Linear Regression Mark Braverman, Elad Hazan, Max Simchowitz, Blake E Woodworth [Zoom link for poster session]
	9. Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo Yin Tat Lee, Ruoqi Shen, Kevin Tian [Zoom link for poster session]
	10. Kernel and Rich Regimes in Overparametrized Models Blake E Woodworth, Suriya Gunasekar, Jason Lee, Edward Moroshko, Pedro Henrique Pamplona Savarese, Itay Golan, Daniel Soudry, Nathan Srebro [Zoom link for poster session]
	11. Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang [Zoom link for poster session]
	12. Gradient descent follows the regularization path for general losses Ziwei Ji, Miroslav Dudik, Robert Schapire, Matus Telgarsky [Zoom link for poster session]
	13. Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar [Zoom link for poster session]
Saturday 2020-07-11 20:00 AoE	Session 3E (Session chair: Vasilis Syrgkanis) [Zoom link for plenary]
	1. Privately Learning Thresholds: Closing the Exponential Gap Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, Uri Stemmer [Zoom link for poster session]
	2. PAC learning with stable and private predictions Yuval Dagan, Vitaly Feldman [Zoom link for poster session]
	3. ID3 Learns Juntas for Smoothed Product Distributions Eran Malach, Amit Daniely, Alon Brutzkus [Zoom link for poster session]
	4. Efficient Parameter Estimation of Truncated Boolean Product Distributions Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos [Zoom link for poster session]
	5. Hierarchical Clustering: A 0.585 Revenue Approximation Noga Alon, Yossi Azar, Danny Vainstein [Zoom link for poster session]
	6. Optimal group testing Oliver Gebhard, Philipp Loick, Maximilian Hahn-Klimroth, Amin Coja-Oghlan [Zoom link for poster session]
	7. From tree matching to sparse graph alignment Luca Ganassali, Laurent Massoulie [Zoom link for poster session]
	8. Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning Mikito Nanashima [Zoom link for poster session]
	9. Lipschitz and Comparator-Norm Adaptivity in Online Learning Zakaria Mhammedi, Wouter M Koolen [Zoom link for poster session]
Saturday 2020-07-11 22:00 AoE	Coffee Break 3E
Sunday 2020-07-12 00:30 AoE	Session 4A (Session chair: Gergely Neu) [Zoom link for plenary]
	1. Optimal group testing Oliver Gebhard, Philipp Loick, Maximilian Hahn-Klimroth, Amin Coja-Oghlan [Zoom link for poster session]
	2. Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes YICHUN HU, Nathan Kallus, Xiaojie Mao [Zoom link for poster session]
	3. ODE-Inspired Analysis for the Biological Version of Oja’s Rule in Solving Streaming PCA Mien Brabeeba Wang, Chi-Ning Chou [Zoom link for poster session]
	4. No-Regret Prediction in Marginally Stable Systems Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang [Zoom link for poster session]
	5. Online Learning with Vector Costs and Bandits with Knapsacks Thomas Kesselheim, Sahil Singla [Zoom link for poster session]
	6. Dimension-Free Bounds for Chasing Convex Functions Guru Guruganesh, Anupam Gupta, Charles Argue [Zoom link for poster session]
	7. Logistic Regression Regret: What’s the Catch? Gil I Shamir [Zoom link for poster session]
	8. New Potential-Based Bounds for Prediction with Expert Advice Vladimir A Kobzar, Robert Kohn, Zhilei Wang [Zoom link for poster session]
	9. Reasoning About Generalization via Conditional Mutual Information Thomas Steinke, Lydia Zakynthinou [Zoom link for poster session]
	10. Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation Allen X Liu, Ankur Moitra [Zoom link for poster session]
	11. A Corrective View of Neural Networks: Representation, Memorization and Learning Dheeraj M Nagaraj, Guy Bresler [Zoom link for poster session]
	12. Extrapolating the profile of a finite population Yihong Wu, Yury Polyanskiy, Soham Jana [Zoom link for poster session]
	13. List Decodable Subspace Recovery Morris Yau, prasad raghavendra [Zoom link for poster session]
	14. Reducibility and Statistical-Computational Gaps from Secret Leakage Matthew S Brennan, Guy Bresler [Zoom link for poster session]
	15. Locally Private Hypothesis Selection Sivakanth Gopi, Gautam Kamath, Janardhan D Kulkarni, Aleksandar Nikolov, Steven Wu, Huanyu Zhang [Zoom link for poster session]
	16. Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise Maksim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, Hoi-To Wai [Zoom link for poster session]
	17. Adaptive Submodular Maximization under Stochastic Item Costs Srinivasan Parthasarathy [Zoom link for poster session]
Sunday 2020-07-12 03:00 AoE	Coffee Break 4A-1
Sunday 2020-07-12 03:30 AoE	Open Problems [Zoom link for plenary]
	1. Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection Yuetian Luo, Anru Zhang
	2. Open Problem: Fast and Optimal Online Portfolio Selection Tim van Erven, Dirk van der Hoeven, Wojciech Kotłowski, Wouter M. Koolen
	3. Open Problem: Tight Convergence of SGD in Constant Dimension Tomer Koren, Shahar Segal
	4. Open Problem: Model Selection for Contextual Bandits Dylan J. Foster, Akshay Krishnamurthy, Haipeng Luo
	5. Open Problem: Information Complexity of VC Learning Thomas Steinke, Lydia Zakynthinou
Sunday 2020-07-12 04:00 AoE	Business Meeting [Zoom link for plenary]
Sunday 2020-07-12 05:00 AoE	Coffee Break 4A-2
Sunday 2020-07-12 05:30 AoE	Session 4B (Session chair: Peter Grunwald) [Zoom link for plenary]
	1. Universal Approximation with Deep Narrow Networks Patrick Kidger, Terry J Lyons [Zoom link for poster session]
	2. Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss Lénaïc Chizat, Francis Bach [Zoom link for poster session]
	3. Non-asymptotic Analysis for Nonparametric Testing Yun Yang, Zuofeng Shang, Guang Cheng [Zoom link for poster session]
	4. Robust causal inference under covariate shift via worst-case subpopulation treatment effects Sookyo Jeong, Hongseok Namkoong [Zoom link for poster session]
	5. Embedding Dimension of Polyhedral Losses Jessica J Finocchiaro, Rafael Frongillo, Bo Waggoner [Zoom link for poster session]
	6. Noise-tolerant, Reliable Active Classification with Comparison Queries Max Hopkins, Shachar Lovett, Daniel Kane, Gaurav Mahajan [Zoom link for poster session]
	7. Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit Jayadev Acharya, Clement L Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi [Zoom link for poster session]
	8. Active Learning for Identification of Linear Dynamical Systems Andrew J Wagenmaker, Kevin Jamieson [Zoom link for poster session]
	9. Active Local Learning Arturs Backurs, Avrim Blum, Neha Gupta [Zoom link for poster session]
	10. Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model Yingyu Liang, Hui Yuan [Zoom link for poster session]
	11. Efficient, Noise-Tolerant, and Private Learning via Boosting Mark Bun, Marco L Carmosino, Jessica Sorrell [Zoom link for poster session]
	12. Distributed Signal Detection under Communication Constraints Jayadev Acharya, Clement L Canonne, Himanshu Tyagi [Zoom link for poster session]
	13. Approximation Schemes for ReLU Regression Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam Klivans, Mahdi Soltanolkotabi [Zoom link for poster session]
Sunday 2020-07-12 07:30 AoE	Coffee Break 4B
Sunday 2020-07-12 12:00 AoE	Session 4C (Session chair: Csaba Szepesvari) [Zoom link for plenary]
	1. Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes YICHUN HU, Nathan Kallus, Xiaojie Mao [Zoom link for poster session]
	2. ODE-Inspired Analysis for the Biological Version of Oja’s Rule in Solving Streaming PCA Mien Brabeeba Wang, Chi-Ning Chou [Zoom link for poster session]
	3. No-Regret Prediction in Marginally Stable Systems Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang [Zoom link for poster session]
	4. Online Learning with Vector Costs and Bandits with Knapsacks Thomas Kesselheim, Sahil Singla [Zoom link for poster session]
	5. Dimension-Free Bounds for Chasing Convex Functions Guru Guruganesh, Anupam Gupta, Charles Argue [Zoom link for poster session]
	6. Logistic Regression Regret: What’s the Catch? Gil I Shamir [Zoom link for poster session]
	7. New Potential-Based Bounds for Prediction with Expert Advice Vladimir A Kobzar, Robert Kohn, Zhilei Wang [Zoom link for poster session]
	8. Reasoning About Generalization via Conditional Mutual Information Thomas Steinke, Lydia Zakynthinou [Zoom link for poster session]
	9. Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation Allen X Liu, Ankur Moitra [Zoom link for poster session]
	10. A Corrective View of Neural Networks: Representation, Memorization and Learning Dheeraj M Nagaraj, Guy Bresler [Zoom link for poster session]
	11. Extrapolating the profile of a finite population Yihong Wu, Yury Polyanskiy, Soham Jana [Zoom link for poster session]
	12. List Decodable Subspace Recovery Morris Yau, prasad raghavendra [Zoom link for poster session]
	13. Reducibility and Statistical-Computational Gaps from Secret Leakage Matthew S Brennan, Guy Bresler [Zoom link for poster session]
Sunday 2020-07-12 14:00 AoE	Coffee Break 4C
Sunday 2020-07-12 15:00 AoE	Session 4D (Session chair: Pranjal Awasthi) [Zoom link for plenary]
	1. Non-asymptotic Analysis for Nonparametric Testing Yun Yang, Zuofeng Shang, Guang Cheng [Zoom link for poster session]
	2. Robust causal inference under covariate shift via worst-case subpopulation treatment effects Sookyo Jeong, Hongseok Namkoong [Zoom link for poster session]
	3. Embedding Dimension of Polyhedral Losses Jessica J Finocchiaro, Rafael Frongillo, Bo Waggoner [Zoom link for poster session]
	4. Noise-tolerant, Reliable Active Classification with Comparison Queries Max Hopkins, Shachar Lovett, Daniel Kane, Gaurav Mahajan [Zoom link for poster session]
	5. Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit Jayadev Acharya, Clement L Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi [Zoom link for poster session]
	6. Active Learning for Identification of Linear Dynamical Systems Andrew J Wagenmaker, Kevin Jamieson [Zoom link for poster session]
	7. Active Local Learning Arturs Backurs, Avrim Blum, Neha Gupta [Zoom link for poster session]
	8. Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model Yingyu Liang, Hui Yuan [Zoom link for poster session]
	9. Efficient, Noise-Tolerant, and Private Learning via Boosting Mark Bun, Marco L Carmosino, Jessica Sorrell [Zoom link for poster session]
	10. Distributed Signal Detection under Communication Constraints Jayadev Acharya, Clement L Canonne, Himanshu Tyagi [Zoom link for poster session]
	11. Approximation Schemes for ReLU Regression Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam Klivans, Mahdi Soltanolkotabi [Zoom link for poster session]
Sunday 2020-07-12 20:00 AoE	Session 4E (Session chair: Prateek Jain) [Zoom link for plenary]
	1. How to trap a gradient flow Dan Mikulincer, Sebastien Bubeck [Zoom link for poster session]
	2. On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems Dan Garber [Zoom link for poster session]
	3. Learning a Single Neuron with Gradient Methods Gilad Yehudai, Ohad Shamir [Zoom link for poster session]
	4. Universal Approximation with Deep Narrow Networks Patrick Kidger, Terry J Lyons [Zoom link for poster session]
	5. Complexity Guarantees for Polyak Steps with Momentum Mathieu Barre, Adrien B Taylor, Alexandre d'Aspremont [Zoom link for poster session]
	6. Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss Lénaïc Chizat, Francis Bach [Zoom link for poster session]
	7. On Suboptimality of Least Squares with Application to Estimation of Convex Bodies Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina [Zoom link for poster session]
	8. How Good is SGD with Random Shuffling? Itay M Safran, Ohad Shamir [Zoom link for poster session]
	9. Efficient improper learning for online logistic regression Pierre Gaillard, Rémi Jézéquel, Alessandro Rudi [Zoom link for poster session]
Sunday 2020-07-12 22:00 AoE	Coffee Break 4E