An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives

Shipra Agrawal,
Nikhil R. Devanur,
Lihong Li

[abs]
[pdf]

Learning and Testing Junta Distributions

Maryam Aliakbarpour,
Eric Blais,
Ronitt Rubinfeld

[abs]
[pdf]

Sign rank versus VC dimension

Noga Alon,
Shay Moran,
Amir Yehudayoff

[abs]
[pdf]

Efficient approaches for escaping higher order saddle points in non-convex optimization

Animashree Anandkumar,
Rong Ge

[abs]
[pdf]

Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes

Nima Anari,
Shayan Oveis Gharan,
Alireza Rezaei

[abs]
[pdf]

An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits

Peter Auer,
Chao-Kai Chiang

[abs]
[pdf]

Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models

Bernardo Ávila Pires,
Csaba Szepesvári

[abs]
[pdf]

Learning and 1-bit Compressed Sensing under Asymmetric Noise

Pranjal Awasthi,
Maria-Florina Balcan,
Nika Haghtalab,
Hongyang Zhang

[abs]
[pdf]

Reinforcement Learning of POMDPs using Spectral Methods

Kamyar Azizzadenesheli,
Alessandro Lazaric,
Animashree Anandkumar

[abs]
[pdf]

Highly-Smooth Zero-th Order Online Optimization

Francis Bach,
Vianney Perchet

[abs]
[pdf]

An Improved Gap-Dependency Analysis of the Noisy Power Method

Maria-Florina Balcan,
Simon Shaolei Du,
Yining Wang,
Adams Wei Yu

[abs]
[pdf]

Learning Combinatorial Functions from Pairwise Comparisons

Maria-Florina Balcan,
Ellen Vitercik,
Colin White

[abs]
[pdf]

Instance-dependent Regret Bounds for Dueling Bandits

Akshay Balsubramani,
Zohar Karnin,
Robert E. Schapire,
Masrour Zoghi

[abs]
[pdf]

On the low-rank approach for semidefinite programs arising in synchronization and community detection

Afonso S. Bandeira,
Nicolas Boumal,
Vladislav Voroninski

[abs]
[pdf]

Information-theoretic thresholds for community detection in sparse networks

Jess Banks,
Cristopher Moore,
Joe Neeman,
Praneeth Netrapalli

[abs]
[pdf]

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak,
Ankur Moitra

[abs]
[pdf]

Basis Learning as an Algorithmic Primitive

Mikhail Belkin,
Luis Rademacher,
James Voss

[abs]
[pdf]

Aggregation of supports along the Lasso path

Pierre C. Bellec

[abs]
[pdf]

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli,
Anastasios Kyrillidis,
Sujay Sanghavi

[abs]
[pdf]

Multi-scale exploration of convex functions and bandit convex optimization

Sébastien Bubeck,
Ronen Eldan

[abs]
[pdf]

Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem

Alexandra Carpentier,
Andrea Locatelli

[abs]
[pdf]

Delay and Cooperation in Nonstochastic Bandits

Nicol`o Cesa-Bianchi,
Claudio Gentile,
Yishay Mansour,
Alberto Minora

[abs]
[pdf]

On the Approximability of Sparse PCA

Siu On Chan,
Dimitris Papailliopoulos,
Aviad Rubinstein

[abs]
[pdf]

Pure Exploration of Multi-armed Bandit Under Matroid Constraints

Lijie Chen,
Anupam Gupta,
Jian Li

[abs]
[pdf]

Provably manipulation-resistant reputation systems

Paul Christiano

[abs]
[pdf]

On the Expressive Power of Deep Learning: A Tensor Analysis

Nadav Cohen,
Or Sharir,
Amnon Shashua

[abs]
[pdf]

A Light Touch for Heavily Constrained SGD

Andrew Cotter,
Maya Gupta,
Jan Pfeifer

[abs]
[pdf]

Adaptive Learning with Robust Generalization Guarantees

Rachel Cummings,
Katrina Ligett,
Kobbi Nissim,
Aaron Roth,
Zhiwei Steven Wu

[abs]
[pdf]

Complexity Theoretic Limitations on Learning DNF’s

Amit Daniely,
Shai Shalev-Shwartz

[abs]
[pdf]

Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables

I. Diakonikolas,
D. M. Kane,
A. Stewart

[abs]
[pdf]

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

I. Diakonikolas,
D. M. Kane,
A. Stewart

[abs]
[pdf]

Asymptotic behavior of \(\ell_p\)-based Laplacian regularization in semi-supervised learning

Ahmed El Alaoui,
Xiang Cheng,
Aaditya Ramdas,
Martin J. Wainwright,
Michael I. Jordan

[abs]
[pdf]

The Power of Depth for Feedforward Neural Networks

Ronen Eldan,
Ohad Shamir

[abs]
[pdf]

Online Learning and Blackwell Approachability in Quitting Games

Janos Flesch,
Rida Laraki,
Vianney Perchet

[abs]
[pdf]

Spectral thresholds in the bipartite stochastic block model

Laura Florescu,
Will Perkins

[abs]
[pdf]

Online Sparse Linear Regression

Dean Foster,
Satyen Kale,
Howard Karloff

[abs]
[pdf]

Preference-based Teaching

Ziyuan Gao,
Christoph Ries,
Hans Simon,
Sandra Zilles

[abs]
[pdf]

Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier,
Emilie Kaufmann

[abs]
[pdf]

Maximin Action Identification: A New Bandit Framework for Games

Aurélien Garivier,
Emilie Kaufmann,
Wouter M. Koolen

[abs]
[pdf]

Semidefinite Programs for Exact Recovery of a Hidden Community

Bruce Hajek,
Yihong Wu,
Jiaming Xu

[abs]
[pdf]

Online Learning with Low Rank Experts

Elad Hazan,
Tomer Koren,
Roi Livni,
Yishay Mansour

[abs]
[pdf]

Optimal rates for total variation denoising

Jan-Christian Hütter,
Philippe Rigollet

[abs]
[pdf]

Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm

Prateek Jain,
Chi Jin,
Sham M. Kakade,
Praneeth Netrapalli,
Aaron Sidford

[abs]
[pdf]

Online Isotonic Regression

Wojciech Kotłowski,
Wouter M. Koolen,
Alan Malek

[abs]
[pdf]

Time series prediction and online learning

Vitaly Kuznetsov,
Mehryar Mohri

[abs]
[pdf]

Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits

Tor Lattimore

[abs]
[pdf]

Gradient Descent Only Converges to Minimizers

Jason D. Lee,
Max Simchowitz,
Michael I. Jordan,
Benjamin Recht

[abs]
[pdf]

Learning Communities in the Presence of Errors

Konstantin Makarychev,
Yury Makarychev,
Aravindan Vijayaraghavan

[abs]
[pdf]

On the capacity of information processing systems

Laurent Massoulie,
Kuang Xu

[abs]
[pdf]

Learning Simple Auctions

Jamie Morgenstern,
Tim Roughgarden

[abs]
[pdf]

Density Evolution in the Degree-correlated Stochastic Block Model

Elchanan Mossel,
Jiaming Xu

[abs]
[pdf]

Cortical Computation via Iterative Constructions

Christos Papadimitriou,
Samantha Petti,
Santosh Vempala

[abs]
[pdf]

When can we rank well from comparisons of \(O(n\log(n))\) non-actively chosen pairs?

Arun Rajkumar,
Shivani Agarwal

[abs]
[pdf]

How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods

Andrej Risteski

[abs]
[pdf]

Simple Bayesian Algorithms for Best Arm Identification

Daniel Russo

[abs]
[pdf]

Interactive Algorithms: from Pool to Stream

Sivan Sabato,
Tom Hess

[abs]
[pdf]

Best-of-K-bandits

Max Simchowitz,
Kevin Jamieson,
Benjamin Recht

[abs]
[pdf]

Memory, Communication, and Statistical Queries

Jacob Steinhardt,
Gregory Valiant,
Stefan Wager

[abs]
[pdf]

benefits of depth in neural networks

Matus Telgarsky

[abs]
[pdf]

A Guide to Learning Arithmetic Circuits

Ilya Volkovich

[abs]
[pdf]

Online learning in repeated auctions

Jonathan Weed,
Vianney Perchet,
Philippe Rigollet

[abs]
[pdf]

The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions

Chicheng Zhang,
Kamalika Chaudhuri

[abs]
[pdf]

First-order Methods for Geodesically Convex Optimization

Hongyi Zhang,
Suvrit Sra

[abs]
[pdf]