research
∙
09/21/2023
Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation
We study the problem of in-context learning (ICL) with large language mo...
share
research
∙
08/02/2023
Optimal Online Discrepancy Minimization
We prove that there exists an online algorithm that for any sequence of ...
research
∙
05/24/2023
Differentially Private Synthetic Data via Foundation Model APIs 1: Images
Generating differentially private (DP) synthetic data that closely resem...
research
∙
05/23/2023
Selective Pre-training for Private Fine-tuning
Suppose we want to train text prediction models in email clients or word...
research
∙
07/01/2022
When Does Differentially Private Learning Not Suffer in High Dimensions?
Large pretrained models can be privately fine-tuned to achieve performan...
research
∙
06/06/2022
Per-Instance Privacy Accounting for Differentially Private Stochastic Gradient Descent
Differentially private stochastic gradient descent (DP-SGD) is the workh...
research
∙
06/03/2022
Differentially Private Model Compression
Recent papers have shown that large pre-trained language models (LLMs) s...
research
∙
11/01/2021
Online Edge Coloring via Tree Recurrences and Correlation Decay
We give an online algorithm that with high probability computes a (e/e-1...
research
∙
10/13/2021
Differentially Private Fine-tuning of Language Models
We give simpler, sparser, and faster algorithms for differentially priva...
research
∙
10/12/2021
Synergy: Resource Sensitive DNN Scheduling in Multi-Tenant Clusters
Training Deep Neural Networks (DNNs) is a widely popular workload in bot...
research
∙
08/05/2021
Differentially Private n-gram Extraction
We revisit the problem of n-gram extraction in the differential privacy ...
research
∙
06/17/2021
Accuracy, Interpretability, and Differential Privacy via Explainable Boosting
We show that adding differential privacy to Explainable Boosting Machine...
research
∙
04/30/2021
On the Hardness of Scheduling With Non-Uniform Communication Delays
In the scheduling with non-uniform communication delay problem, the inpu...
research
∙
03/29/2021
Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps
We study the differentially private Empirical Risk Minimization (ERM) an...
research
∙
02/17/2021
Differentially Private Correlation Clustering
Correlation clustering is a widely used technique in unsupervised machin...
research
∙
02/05/2021
Fast and Memory Efficient Differentially Private-SGD via JL Projections
Differentially Private-SGD (DP-SGD) of Abadi et al. (2016) and its varia...
research
∙
10/15/2020
Scheduling Opportunistic Links in Two-Tiered Reconfigurable Datacenters
Reconfigurable optical topologies are emerging as a promising technology...
research
∙
08/13/2020
Consistent k-Median: Simpler, Better and Robust
In this paper we introduce and study the online consistent k-clustering ...
research
∙
04/28/2020
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
We consider the classic problem of scheduling jobs with precedence const...
research
∙
04/21/2020
Scheduling with Communication Delays via LP Hierarchies and Clustering
We consider the classic problem of scheduling jobs with precedence const...
research
∙
02/25/2020
The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models
In this paper we study the facility location problem in the online with ...
research
∙
02/22/2020
Differentially Private Set Union
We study the basic operation of set union in the global model of differe...
research
∙
02/21/2020
Locally Private Hypothesis Selection
We initiate the study of hypothesis selection under local differential p...
research
∙
02/21/2020
Privately Learning Markov Random Fields
We consider the problem of learning Markov Random Fields (including the ...
research
∙
10/04/2019
Fully Dynamic (Δ+1)-Coloring in Constant Update Time
The problem of (vertex) (Δ+1)-coloring a graph of maximum degree Δ has b...
research
∙
10/02/2019
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
Consider a unit interval [0,1] in which n points arrive one-by-one indep...
research
∙
08/06/2019
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
In this paper we study the problem of dynamically maintaining graph prop...
research
∙
11/20/2018
Locally Private Gaussian Estimation
We study a basic private estimation problem: each of n users draws a sin...
research
∙
10/08/2018
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
We consider the problem of incremental cycle detection and topological o...
research
∙
07/25/2018
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
We consider the classic scheduling problem of minimizing the total weigh...
research
∙
07/06/2018
Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models
Scheduling a set of jobs over a collection of machines is a fundamental ...
research
∙
07/02/2018
An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors
Differential privacy has emerged as the main definition for private data...
research
∙
05/09/2018
Deterministically Maintaining a (2+ε)-Approximate Minimum Vertex Cover in O(1/ε^2) Amortized Update Time
We consider the problem of maintaining an (approximately) minimum vertex...
research
∙
12/05/2017
Collecting Telemetry Data Privately
The collection and analysis of telemetry data from users' devices is rou...
research
∙
04/25/2016