Papers
The Complexity of Making the Gradient Small in Stochastic Convex Optimization
Dylan J. Foster, Ayush Sekhari, Ohad Shamir et al.
Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
Dylan J. Foster, Andrej Risteski
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
Vitaly Feldman, Jan Vondrak
Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly
Yingjie Fei, Yudong Chen
Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
Cong Fang, Zhouchen Lin, Tong Zhang
Lower Bounds for Locally Private Estimation via Communication Complexity
John Duchi, Ryan Rogers
On the Performance of Thompson Sampling on Logistic Bandits
Shi Dong, Tengyu Ma, Benjamin Van Roy
Lower Bounds for Parallel and Randomized Convex Optimization
Jelena Diakonikolas, Cristóbal Guzmán
Testing Identity of Multidimensional Histograms
Ilias Diakonikolas, Daniel M. Kane, John Peebles
Communication and Memory Efficient Testing of Discrete Distributions
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane et al.
Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
Michał Dereziński, Kenneth L. Clarkson, Michael W. Mahoney et al.
Computational Limitations in Robust Classification and Win-Win Results
Akshay Degwekar, Preetum Nakkiran, Vinod Vaikuntanathan
Is your function low dimensional?
Anindya De, Elchanan Mossel, Joe Neeman
Reconstructing Trees from Traces
Sami Davies, Miklos Z. Racz, Cyrus Rashtchian
Computationally and Statistically Efficient Truncated Regression
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos et al.
Space lower bounds for linear prediction in the streaming model
Yuval Dagan, Gil Kur, Ohad Shamir
Learning from Weakly Dependent Data under Dobrushin’s Condition
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala et al.
Combining Online Learning Guarantees
Ashok Cutkosky
A near-optimal algorithm for approximating the John Ellipsoid
Michael B. Cohen, Ben Cousins, Yin Tat Lee et al.
Pure entropic regularization for metrical task systems
Christian Coester, James R. Lee
Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
Yun Kuen Cheung, Georgios Piliouras
Fast Mean Estimation with Sub-Gaussian Rates
Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter L. Bartlett
Testing Symmetric Markov Chains Without Hitting
Yeshwanth Cherapanamjeri, Peter L. Bartlett