
Adversarial Examples in MultiLayer Random ReLU Networks
We consider the phenomenon of adversarial examples in ReLU networks with...
read it

A Universal Law of Robustness via Isoperimetry
Classically, data interpolation with a parametrized model class is possi...
read it

A single gradient step finds adversarial examples on random twolayers neural networks
Daniely and Schacham recently showed that gradient descent finds adversa...
read it

Cooperative and Stochastic MultiPlayer MultiArmed Bandit: Optimal Regret With Neither Communication Nor Collisions
We consider the cooperative multiplayer version of the stochastic multi...
read it

A law of robustness for twolayers neural networks
We initiate the study of the inherent tradeoffs between the size of a ne...
read it

Metrical Service Systems with Transformations
We consider a generalization of the fundamental online metrical service ...
read it

Network size and weights size for memorization with twolayers neural networks
In 1988, Eric B. Baum showed that twolayers neural networks with thresh...
read it

Entanglement is Necessary for Optimal Quantum Property Testing
There has been a surge of progress in recent years in developing algorit...
read it

Online Multiserver Convex Chasing and Optimization
We introduce the problem of kchasing of convex functions, a simultaneou...
read it

Online Learning for Active Cache Synchronization
Existing multiarmed bandit (MAB) models make two implicit assumptions: ...
read it

Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
We consider the setting of distributed empirical risk minimization where...
read it

Coordination without communication: optimal regret in two players multiarmed bandits
We consider two agents playing simultaneously the same stochastic three...
read it

How to trap a gradient flow
We consider the problem of finding an εapproximate stationary point of ...
read it

Complexity of Highly Parallel NonSmooth Convex Optimization
A landmark result of nonsmooth convex optimization is that gradient des...
read it

Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
Recent works have shown the effectiveness of randomized smoothing as a s...
read it

NonStochastic MultiPlayer MultiArmed Bandits: Optimal Rate With Collision Information, Sublinear Without
We consider the nonstochastic version of the (cooperative) multiplayer...
read it

Parametrized Metrical Task Systems
We consider parametrized versions of metrical task systems and metrical ...
read it

FirstOrder Regret Analysis of Thompson Sampling
We address online combinatorial optimization when the player has a prior...
read it

Improved Pathlength Regret Bounds for Bandits
We study adaptive regret bounds in terms of the variation of the losses ...
read it

Adversarial Examples from Cryptographic PseudoRandom Generators
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we arg...
read it

Chasing Nested Convex Bodies Nearly Optimally
The convex body chasing problem, introduced by Friedman and Linial, is a...
read it

Competitively Chasing Convex Bodies
Let F be a family of sets in some metric space. In the Fchasing problem...
read it

Metrical task systems on trees via mirror descent and unfair gluing
We consider metrical task systems on tree metrics, and present an O(dept...
read it

Is Qlearning Provably Efficient?
Modelfree reinforcement learning (RL) algorithms, such as Qlearning, d...
read it

A NearlyLinear Bound for Chasing Nested Convex Bodies
Friedman and Linial introduced the convex body chasing problem to explor...
read it

Adversarial examples from computational constraints
Why are classifiers in high dimension vulnerable to "adversarial" pertur...
read it

Make the Minority Great Again: FirstOrder Regret Bound for Contextual Bandits
Regret bounds in online learning compare the player's performance to L^*...
read it

An homotopy method for ℓ_p regression provably beyond selfconcordance and in inputsparsity time
We consider the problem of linear regression where the ℓ_2^n norm loss (...
read it

kserver via multiscale entropic regularization
We present an O(( k)^2)competitive randomized algorithm for the kserve...
read it

Online Auctions and Multiscale Online Learning
We consider revenue maximization in online auctions and pricing. A selle...
read it

Optimal algorithms for smooth and strongly convex distributed optimization in networks
In this paper, we determine the optimal convergence rates for strongly c...
read it

Kernelbased methods for bandit convex optimization
We consider the adversarial convex bandit problem and we build the first...
read it

Convex Optimization: Algorithms and Complexity
This monograph presents the main complexity theorems in convex optimizat...
read it

Most Correlated Arms Identification
We study the problem of finding the most mutually correlated arms among ...
read it

lil' UCB : An Optimal Exploration Algorithm for MultiArmed Bandits
The paper proposes a novel upper confidence bound (UCB) procedure for id...
read it

On Finding the Largest Mean Among Many
Sampling from distributions to find the one with the largest mean arises...
read it

Priorfree and priordependent regret bounds for Thompson Sampling
We consider the stochastic multiarmed bandit problem with a prior distr...
read it

Bounded regret in stochastic multiarmed bandits
We study the stochastic multiarmed bandit problem when one knows the va...
read it

Bandits with heavy tail
The stochastic multiarmed bandit problem is well understood when the re...
read it

Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality
We consider an original problem that arises from the issue of security a...
read it

Multiple Identifications in MultiArmed Bandits
We study the problem of identifying the top m arms in a multiarmed band...
read it

Regret Analysis of Stochastic and Nonstochastic Multiarmed Bandit Problems
Multiarmed bandit problems are the most basic examples of sequential de...
read it

Regret in Online Combinatorial Optimization
We address online linear optimization problems when the possible actions...
read it

Towards minimax policies for online linear optimization with bandit feedback
We address the online linear optimization problem with bandit feedback. ...
read it

Minimax Policies for Combinatorial Prediction Games
We address the online linear optimization problem when the actions of th...
read it