b'Amin Karbasi'

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...

0 Idan Attias, et al. ∙

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 ...

0 Amin Karbasi, et al. ∙

research

∙ 05/31/2023

Replicability in Reinforcement Learning

We initiate the mathematical study of replicability as an algorithmic pr...

0 Amin Karbasi, et al. ∙

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...

0 Patrik Okanovic, et al. ∙

research

∙ 05/26/2023

Submodular Minimax Optimization: Finding Effective Sets

Despite the rich existing literature about minimax optimization in conti...

0 Loay Mualem, et al. ∙

research

∙ 05/23/2023

Statistical Indistinguishability of Learning Algorithms

When two different parties use the same learning rule on their own data,...

0 Alkis Kalavasis, et al. ∙

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...

0 Lin Chen, et al. ∙

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...

0 Konstantinos E. Nikolakakis, et al. ∙

research

∙ 02/20/2023

Replicable Clustering

In this paper, we design replicable algorithms in the context of statist...

0 Hossein Esfandiari, et al. ∙

research

∙ 02/05/2023

KDEformer: Accelerating Transformers via Kernel Density Estimation

Dot-product attention mechanism plays a crucial role in modern deep arch...

0 Amir Zandieh, et al. ∙

research

∙ 01/23/2023

The Impossibility of Parallelizing Boosting

The aim of boosting is to convert a sequence of weak learners into a str...

0 Amin Karbasi, et al. ∙

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...

0 Jane H Lee, et al. ∙

research

∙ 10/06/2022

On Optimal Learning Under Targeted Data Poisoning

Consider the task of learning a hypothesis class ℋ in the presence of an...

0 Steve Hanneke, et al. ∙

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...

0 Alkis Kalavasis, et al. ∙

research

∙ 10/04/2022

Reproducible Bandits

In this paper, we introduce the notion of reproducible policies in the c...

0 Hossein Esfandiari, et al. ∙

research

∙ 09/09/2022

Fast Neural Kernel Embeddings for General Activations

Infinite width limit has shed light on generalization and optimization a...

0 Insu Han, et al. ∙

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...

0 Insu Han, et al. ∙

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...

2 Konstantinos E. Nikolakakis, et al. ∙

research

∙ 03/17/2022

Learning Distributionally Robust Models at Scale via Composite Optimization

To train machine learning models that are robust to distribution shifts ...

8 Farzin Haddadpour, et al. ∙

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 ...

3 Grigoris Velegkas, et al. ∙

research

∙ 02/14/2022

Black-Box Generalization

We provide the first generalization error analysis for black-box learnin...

11 Konstantinos E. Nikolakakis, et al. ∙

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...

0 Insu Han, et al. ∙

research

∙ 07/02/2021

Data-driven mapping between functional connectomes using optimal transport

Functional connectomes derived from functional magnetic resonance imagin...

0 Javid Dadashkarimi, et al. ∙

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...

0 Shashank Rajput, et al. ∙

research

∙ 06/09/2021

Submodular + Concave

It has been well established that first order optimization methods can c...

0 Siddharth Mitra, et al. ∙

research

∙ 06/02/2021

Parallelizing Thompson Sampling

How can we make use of information parallelism in online decision making...

0 Amin Karbasi, et al. ∙

research

∙ 05/18/2021

Learning and Certification under Instance-targeted Poisoning

In this paper, we study PAC learnability and certification under instanc...

0 Ji Gao, et al. ∙

research

∙ 04/06/2021

The Power of Subsampling in Submodular Maximization

We propose subsampling as a unified algorithmic technique for submodular...

0 Christopher Harshaw, et al. ∙

research

∙ 02/25/2021

Batched Neural Bandits

In many sequential decision-making problems, the individuals are split i...

6 Quanquan Gu, et al. ∙

research

∙ 09/29/2020

Simultaneous Greedys: A Swiss Army Knife for Constrained Submodular Maximization

In this paper, we present SimultaneousGreedys, a deterministic algorithm...

0 Moran Feldman, et al. ∙

research

∙ 08/03/2020

Multiple Descent: Design Your Own Generalization Curve

This paper explores the generalization loss of linear regression in vari...

2 Lin Chen, et al. ∙

research

∙ 06/21/2020

Continuous Submodular Maximization: Beyond DR-Submodularity

In this paper, we propose the first continuous optimization algorithms t...

0 Moran Feldman, et al. ∙

research

∙ 06/19/2020

Meta Learning in the Continuous Time Limit

In this paper, we establish the ordinary differential equation (ODE) tha...

30 Ruitu Xu, et al. ∙

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-...

10 Yifei Min, et al. ∙

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...

38 Lin Chen, et al. ∙

research

∙ 02/10/2020

Submodular Maximization Through Barrier Functions

In this paper, we introduce a novel technique for constrained submodular...

9 Ashwinkumar Badanidiyuru, et al. ∙

research

∙ 02/10/2020

Regularized Submodular Maximization at Scale

In this paper, we propose scalable methods for maximizing a regularized ...

11 Ehsan Kazemi, et al. ∙

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...

0 Ran Haba, et al. ∙

research

∙ 11/09/2019

Adaptivity in Adaptive Submodularity

Adaptive sequential decision making is one of the central challenges in ...

12 Hossein Esfandiari, et al. ∙

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...

16 Mingrui Zhang, et al. ∙

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...

11 Lin Chen, et al. ∙

research

∙ 10/11/2019

Batched Multi-Armed Bandits with Optimal Regret

We present a simple and efficient algorithm for the batched stochastic m...

0 Hossein Esfandiari, et al. ∙

research

∙ 10/10/2019

One Sample Stochastic Frank-Wolfe

One of the beauties of the projected gradient descent method lies in its...

7 Mingrui Zhang, et al. ∙

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...

4 Ehsan Kazemi, et al. ∙

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...

0 Christopher Harshaw, et al. ∙

research

∙ 02/19/2019

Stochastic Conditional Gradient++

In this paper, we develop Stochastic Continuous Greedy++ (SCG++), the fi...

0 Hamed Hassani, et al. ∙

research

∙ 02/17/2019

Quantized Frank-Wolfe: Communication-Efficient Distributed Optimization

How can we efficiently mitigate the overhead of gradient communications ...

0 Mingrui Zhang, et al. ∙

research

∙ 02/15/2019

Adaptive Sequence Submodularity

In many machine learning applications, one needs to interactively select...

8 Marko Mitrovic, et al. ∙

research

∙ 01/28/2019

Black Box Submodular Maximization: Discrete and Continuous Settings

In this paper, we consider the problem of black box continuous submodula...

6 Lin Chen, et al. ∙

research

∙ 11/15/2018

Unconstrained Submodular Maximization with Constant Adaptive Complexity

In this paper, we consider the unconstrained submodular maximization pro...

0 Lin Chen, et al. ∙

Amin Karbasi

Featured Co-authors