COLT - RankMe – RankMe

127 papers

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