research
∙
06/07/2023
Fast Optimal Locally Private Mean Estimation via Random Projections
We study the problem of locally private mean estimation of high-dimensio...
share
research
∙
05/25/2023
Online and Streaming Algorithms for Constrained k-Submodular Maximization
Constrained k-submodular maximization is a general framework that captur...
research
∙
03/25/2023
Identification of Negative Transfers in Multitask Learning Using Surrogate Models
Multitask learning is widely used in practice to train a low-resource ta...
research
∙
10/03/2022
High Probability Convergence for Accelerated Stochastic Mirror Descent
In this work, we describe a generic approach to show convergence with hi...
research
∙
09/29/2022
META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions
We study the application of variance reduction (VR) techniques to genera...
research
∙
09/29/2022
On the Convergence of AdaGrad on ^d: Beyond Convexity, Non-Asymptotic Rate and Acceleration
Existing analysis of AdaGrad and other adaptive methods for smooth conve...
research
∙
01/28/2022
Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction
In this paper, we study the finite-sum convex optimization problem focus...
research
∙
05/31/2021
Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error
Given a data set of size n in d'-dimensional Euclidean space, the k-mean...
research
∙
12/22/2020
Projection-Free Bandit Optimization with Privacy Guarantees
We design differentially private algorithms for the bandit convex optimi...
research
∙
10/15/2020
Adaptive and Universal Single-gradient Algorithms for Variational Inequalities
Variational inequalities with monotone operators capture many problems o...
research
∙
09/28/2020
A note on differentially private clustering with large additive error
In this note, we describe a simple approach to obtain a differentially p...
research
∙
09/04/2020
Fair and Useful Cohort Selection
As important decisions about the distribution of society's resources bec...
research
∙
07/17/2020
Adaptive Gradient Methods for Constrained Convex Optimization
We provide new adaptive first-order methods for constrained convex optim...
research
∙
11/29/2019
An Optimal Streaming Algorithm for Non-monotone Submodular Maximization
We study the problem of maximizing a non-monotone submodular function su...
research
∙
05/30/2019
Parallel Algorithm for Non-Monotone DR-Submodular Maximization
In this work, we give a new parallel algorithm for the problem of maximi...
research
∙
04/08/2019
A note on Cunningham's algorithm for matroid intersection
In the matroid intersection problem, we are given two matroids of rank r...
research
∙
02/24/2019
Efficient Private Algorithms for Learning Halfspaces
We present new differentially private algorithms for learning a large-ma...
research
∙
12/04/2018
A Parallel Double Greedy Algorithm for Submodular Maximization
We study parallel algorithms for the problem of maximizing a non-negativ...
research
∙
11/19/2018
Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
We consider fast algorithms for monotone submodular maximization subject...
research
∙
08/29/2018
Submodular Maximization with Packing Constraints in Parallel
We consider the problem of maximizing the multilinear extension of a sub...
research
∙
05/22/2018
Improved Algorithms for Collaborative PAC Learning
We study a recent model of collaborative PAC learning where k players wi...
research
∙
04/15/2018
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
In this paper, we study the tradeoff between the approximation guarantee...
research
∙
06/27/2016
A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns
A function f: Z_+^E →R_+ is DR-submodular if it satisfies f( + χ_i) -f (...
research
∙
06/24/2015
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
We study the tradeoff between the statistical error and communication co...
research
∙
02/09/2015