research
∙
07/07/2023
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
In this work, we aim to characterize the statistical complexity of reali...
share
research
∙
06/15/2023
Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning
Thompson sampling (TS) is widely used in sequential decision making due ...
research
∙
05/31/2023
Replicability in Reinforcement Learning
We initiate the mathematical study of replicability as an algorithmic pr...
research
∙
05/28/2023
Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning
Methods for carefully selecting or generating a small set of training da...
research
∙
05/26/2023
Submodular Minimax Optimization: Finding Effective Sets
Despite the rich existing literature about minimax optimization in conti...
research
∙
05/23/2023
Statistical Indistinguishability of Learning Algorithms
When two different parties use the same learning rule on their own data,...
research
∙
05/16/2023
Learning from Aggregated Data: Curated Bags versus Random Bags
Protecting user privacy is a major concern for many machine learning sys...
research
∙
05/03/2023
Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally
We establish matching upper and lower generalization error bounds for mi...
research
∙
02/20/2023
Replicable Clustering
In this paper, we design replicable algorithms in the context of statist...
research
∙
02/05/2023
KDEformer: Accelerating Transformers via Kernel Density Estimation
Dot-product attention mechanism plays a crucial role in modern deep arch...
research
∙
01/23/2023
The Impossibility of Parallelizing Boosting
The aim of boosting is to convert a sequence of weak learners into a str...
research
∙
10/18/2022
Exact Gradient Computation for Spiking Neural Networks Through Forward Propagation
Spiking neural networks (SNN) have recently emerged as alternatives to t...
research
∙
10/06/2022
On Optimal Learning Under Targeted Data Poisoning
Consider the task of learning a hypothesis class ℋ in the presence of an...
research
∙
10/05/2022
Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes
In this paper we study the problem of multiclass classification with a b...
research
∙
10/04/2022
Reproducible Bandits
In this paper, we introduce the notion of reproducible policies in the c...
research
∙
09/09/2022
Fast Neural Kernel Embeddings for General Activations
Infinite width limit has shed light on generalization and optimization a...
research
∙
07/01/2022
Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes
A determinantal point process (DPP) is an elegant model that assigns a p...
research
∙
04/26/2022
Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD
We provide sharp path-dependent generalization and excess error guarante...
research
∙
03/17/2022
Learning Distributionally Robust Models at Scale via Composite Optimization
To train machine learning models that are robust to distribution shifts ...
research
∙
03/03/2022
The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches
In this paper, we study the problem of regret minimization for episodic ...
research
∙
02/14/2022
Black-Box Generalization
We provide the first generalization error analysis for black-box learnin...
research
∙
01/20/2022
Scalable Sampling for Nonsymmetric Determinantal Point Processes
A determinantal point process (DPP) on a collection of M items is a mode...
research
∙
07/02/2021
Data-driven mapping between functional connectomes using optimal transport
Functional connectomes derived from functional magnetic resonance imagin...
research
∙
06/14/2021
An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
It is well known that modern deep neural networks are powerful enough to...
research
∙
06/09/2021
Submodular + Concave
It has been well established that first order optimization methods can c...
research
∙
06/02/2021
Parallelizing Thompson Sampling
How can we make use of information parallelism in online decision making...
research
∙
05/18/2021
Learning and Certification under Instance-targeted Poisoning
In this paper, we study PAC learnability and certification under instanc...
research
∙
04/06/2021
The Power of Subsampling in Submodular Maximization
We propose subsampling as a unified algorithmic technique for submodular...
research
∙
02/25/2021
Batched Neural Bandits
In many sequential decision-making problems, the individuals are split i...
research
∙
09/29/2020
Simultaneous Greedys: A Swiss Army Knife for Constrained Submodular Maximization
In this paper, we present SimultaneousGreedys, a deterministic algorithm...
research
∙
08/03/2020
Multiple Descent: Design Your Own Generalization Curve
This paper explores the generalization loss of linear regression in vari...
research
∙
06/21/2020
Continuous Submodular Maximization: Beyond DR-Submodularity
In this paper, we propose the first continuous optimization algorithms t...
research
∙
06/19/2020
Meta Learning in the Continuous Time Limit
In this paper, we establish the ordinary differential equation (ODE) tha...
research
∙
02/25/2020
The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
Despite remarkable success, deep neural networks are sensitive to human-...
research
∙
02/11/2020
More Data Can Expand the Generalization Gap Between Adversarially Robust and Standard Models
Despite remarkable success in practice, modern machine learning models h...
research
∙
02/10/2020
Submodular Maximization Through Barrier Functions
In this paper, we introduce a novel technique for constrained submodular...
research
∙
02/10/2020
Regularized Submodular Maximization at Scale
In this paper, we propose scalable methods for maximizing a regularized ...
research
∙
02/09/2020
Streaming Submodular Maximization under a k-Set System Constraint
In this paper, we propose a novel framework that converts streaming algo...
research
∙
11/09/2019
Adaptivity in Adaptive Submodularity
Adaptive sequential decision making is one of the central challenges in ...
research
∙
10/28/2019
Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
In this paper, we propose three online algorithms for submodular maximis...
research
∙
10/24/2019
Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
We study the problem of switching-constrained online convex optimization...
research
∙
10/11/2019
Batched Multi-Armed Bandits with Optimal Regret
We present a simple and efficient algorithm for the batched stochastic m...
research
∙
10/10/2019
One Sample Stochastic Frank-Wolfe
One of the beauties of the projected gradient descent method lies in its...
research
∙
05/02/2019
Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
Streaming algorithms are generally judged by the quality of their soluti...
research
∙
04/19/2019
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
It is generally believed that submodular functions -- and the more gener...
research
∙
02/19/2019
Stochastic Conditional Gradient++
In this paper, we develop Stochastic Continuous Greedy++ (SCG++), the fi...
research
∙
02/17/2019
Quantized Frank-Wolfe: Communication-Efficient Distributed Optimization
How can we efficiently mitigate the overhead of gradient communications ...
research
∙
02/15/2019
Adaptive Sequence Submodularity
In many machine learning applications, one needs to interactively select...
research
∙
01/28/2019
Black Box Submodular Maximization: Discrete and Continuous Settings
In this paper, we consider the problem of black box continuous submodula...
research
∙
11/15/2018