research
∙
09/11/2023
Textbooks Are All You Need II: phi-1.5 technical report
We continue the investigation into the power of smaller Transformer-base...
share
research
∙
03/22/2023
Sparks of Artificial General Intelligence: Early experiments with GPT-4
Artificial intelligence (AI) researchers have been developing and refini...
research
∙
12/14/2022
Learning threshold neurons via the "edge of stability"
Existing analyses of neural network training often operate under the unr...
research
∙
11/17/2022
How to Fine-Tune Vision Models with SGD
SGD (with momentum) and AdamW are the two most used optimizers for fine-...
research
∙
11/10/2022
The Randomized k-Server Conjecture is False!
We prove a few new lower bounds on the randomized competitive ratio for ...
research
∙
10/14/2022
AutoMoE: Neural Architecture Search for Efficient Sparsely Activated Transformers
Neural architecture search (NAS) has demonstrated promising results on i...
research
∙
06/09/2022
Unveiling Transformers with LEGO: a synthetic reasoning task
We propose a synthetic task, LEGO (Learning Equality and Group Operation...
research
∙
03/03/2022
Data Augmentation as Feature Manipulation: a story of desert cows and grass cows
Data augmentation is a cornerstone of the machine learning pipeline, yet...
research
∙
02/09/2022
Shortest Paths without a Map, but with an Entropic Regularizer
In a 1989 paper titled "shortest paths without a map", Papadimitriou and...
research
∙
06/23/2021
Adversarial Examples in Multi-Layer Random ReLU Networks
We consider the phenomenon of adversarial examples in ReLU networks with...
research
∙
05/26/2021
A Universal Law of Robustness via Isoperimetry
Classically, data interpolation with a parametrized model class is possi...
research
∙
04/08/2021
A single gradient step finds adversarial examples on random two-layers neural networks
Daniely and Schacham recently showed that gradient descent finds adversa...
research
∙
11/08/2020
Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
We consider the cooperative multi-player version of the stochastic multi...
research
∙
09/30/2020
A law of robustness for two-layers neural networks
We initiate the study of the inherent tradeoffs between the size of a ne...
research
∙
09/17/2020
Metrical Service Systems with Transformations
We consider a generalization of the fundamental online metrical service ...
research
∙
06/04/2020
Network size and weights size for memorization with two-layers neural networks
In 1988, Eric B. Baum showed that two-layers neural networks with thresh...
research
∙
04/16/2020
Entanglement is Necessary for Optimal Quantum Property Testing
There has been a surge of progress in recent years in developing algorit...
research
∙
04/15/2020
Online Multiserver Convex Chasing and Optimization
We introduce the problem of k-chasing of convex functions, a simultaneou...
research
∙
02/27/2020
Online Learning for Active Cache Synchronization
Existing multi-armed bandit (MAB) models make two implicit assumptions: ...
research
∙
02/25/2020
Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
We consider the setting of distributed empirical risk minimization where...
research
∙
02/14/2020
Coordination without communication: optimal regret in two players multi-armed bandits
We consider two agents playing simultaneously the same stochastic three-...
research
∙
01/09/2020
How to trap a gradient flow
We consider the problem of finding an ε-approximate stationary point of ...
research
∙
06/25/2019
Complexity of Highly Parallel Non-Smooth Convex Optimization
A landmark result of non-smooth convex optimization is that gradient des...
research
∙
06/09/2019
Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
Recent works have shown the effectiveness of randomized smoothing as a s...
research
∙
04/28/2019
Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
We consider the non-stochastic version of the (cooperative) multi-player...
research
∙
04/08/2019
Parametrized Metrical Task Systems
We consider parametrized versions of metrical task systems and metrical ...
research
∙
02/02/2019
First-Order Regret Analysis of Thompson Sampling
We address online combinatorial optimization when the player has a prior...
research
∙
01/29/2019
Improved Path-length Regret Bounds for Bandits
We study adaptive regret bounds in terms of the variation of the losses ...
research
∙
11/15/2018
Adversarial Examples from Cryptographic Pseudo-Random Generators
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we arg...
research
∙
11/02/2018
Chasing Nested Convex Bodies Nearly Optimally
The convex body chasing problem, introduced by Friedman and Linial, is a...
research
∙
11/02/2018
Competitively Chasing Convex Bodies
Let F be a family of sets in some metric space. In the F-chasing problem...
research
∙
07/12/2018
Metrical task systems on trees via mirror descent and unfair gluing
We consider metrical task systems on tree metrics, and present an O(dept...
research
∙
07/10/2018
Is Q-learning Provably Efficient?
Model-free reinforcement learning (RL) algorithms, such as Q-learning, d...
research
∙
06/22/2018
A Nearly-Linear Bound for Chasing Nested Convex Bodies
Friedman and Linial introduced the convex body chasing problem to explor...
research
∙
05/25/2018
Adversarial examples from computational constraints
Why are classifiers in high dimension vulnerable to "adversarial" pertur...
research
∙
02/09/2018
Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits
Regret bounds in online learning compare the player's performance to L^*...
research
∙
11/03/2017
An homotopy method for ℓ_p regression provably beyond self-concordance and in input-sparsity time
We consider the problem of linear regression where the ℓ_2^n norm loss (...
research
∙
11/03/2017
k-server via multiscale entropic regularization
We present an O(( k)^2)-competitive randomized algorithm for the k-serve...
research
∙
05/26/2017
Online Auctions and Multi-scale Online Learning
We consider revenue maximization in online auctions and pricing. A selle...
research
∙
02/28/2017
Optimal algorithms for smooth and strongly convex distributed optimization in networks
In this paper, we determine the optimal convergence rates for strongly c...
research
∙
07/11/2016
Kernel-based methods for bandit convex optimization
We consider the adversarial convex bandit problem and we build the first...
research
∙
05/20/2014
Convex Optimization: Algorithms and Complexity
This monograph presents the main complexity theorems in convex optimizat...
research
∙
04/23/2014
Most Correlated Arms Identification
We study the problem of finding the most mutually correlated arms among ...
research
∙
12/27/2013
lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
The paper proposes a novel upper confidence bound (UCB) procedure for id...
research
∙
06/17/2013
On Finding the Largest Mean Among Many
Sampling from distributions to find the one with the largest mean arises...
research
∙
04/21/2013
Prior-free and prior-dependent regret bounds for Thompson Sampling
We consider the stochastic multi-armed bandit problem with a prior distr...
research
∙
02/06/2013
Bounded regret in stochastic multi-armed bandits
We study the stochastic multi-armed bandit problem when one knows the va...
research
∙
09/08/2012
Bandits with heavy tail
The stochastic multi-armed bandit problem is well understood when the re...
research
∙
07/22/2012
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...
research
∙
05/14/2012
