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