research
∙
08/07/2023
TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
We introduce TeraHAC, a (1+ϵ)-approximate hierarchical agglomerative clu...
share
research
∙
08/02/2023
Causal Inference with Differentially Private (Clustered) Outcomes
Estimating causal effects from randomized experiments is only feasible i...
research
∙
08/01/2023
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
We study the classic Euclidean Minimum Spanning Tree (MST) problem in th...
research
∙
06/01/2023
Causal Estimation of User Learning in Personalized Systems
In online platforms, the impact of a treatment on an observed outcome ma...
research
∙
05/25/2023
Learning across Data Owners with Joint Differential Privacy
In this paper, we study the setting in which data owners train machine l...
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
∙
04/23/2023
Robust and differentially private stochastic linear bandits
In this paper, we study the stochastic linear bandit problem under the a...
research
∙
04/12/2023
Measuring Re-identification Risk
Compact user representations (such as embeddings) form the backbone of p...
research
∙
03/27/2023
Learning Rate Schedules in the Presence of Distribution Shift
We design learning rate schedules that minimize regret for SGD-based onl...
research
∙
03/21/2023
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
In fully dynamic clustering problems, a clustering of a given data set i...
research
∙
02/20/2023
Replicable Clustering
In this paper, we design replicable algorithms in the context of statist...
research
∙
02/16/2023
Joint Feedback Loop for Spend and Return-On-Spend Constraints
Budget pacing is a popular service that has been offered by major intern...
research
∙
02/08/2023
Approximately Optimal Core Shapes for Tensor Decompositions
This work studies the combinatorial optimization problem of finding an o...
research
∙
02/03/2023
Robust Budget Pacing with a Single Sample
Major Internet advertising platforms offer budget pacing tools as a stan...
research
∙
02/03/2023
Multi-channel Autobidding with Budget and ROI Constraints
In digital online advertising, advertisers procure ad impressions simult...
research
∙
02/01/2023
Autobidding Auctions in the Presence of User Costs
We study autobidding ad auctions with user costs, where each bidder is v...
research
∙
01/31/2023
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees
Hierarchical Clustering is a popular unsupervised machine learning metho...
research
∙
01/13/2023
Differentially Private Continual Releases of Streaming Frequency Moment Estimations
The streaming model of computation is a popular approach for working wit...
research
∙
12/29/2022
Constant Approximation for Normalized Modularity and Associations Clustering
We study the problem of graph clustering under a broad class of objectiv...
research
∙
12/05/2022
Stars: Tera-Scale Graph Building for Clustering and Graph Learning
A fundamental procedure in the analysis of massive datasets is the const...
research
∙
10/28/2022
Cluster Randomized Designs for One-Sided Bipartite Experiments
The conclusions of randomized controlled trials may be biased when the o...
research
∙
10/21/2022
Anonymous Bandits for Multi-User Systems
In this work, we present and study a new framework for online learning i...
research
∙
10/04/2022
Reproducible Bandits
In this paper, we introduce the notion of reproducible policies in the c...
research
∙
09/29/2022
Sequential Attention for Feature Selection
Feature selection is the problem of selecting a subset of features for a...
research
∙
09/10/2022
Fairness in the Autobidding World with Machine-learned Advice
The increasing availability of real-time data has fueled the prevalence ...
research
∙
08/22/2022
Efficiency of the First-Price Auction in the Autobidding World
We study the price of anarchy of the first-price auction in the autobidd...
research
∙
07/14/2022
Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
Personalized PageRank (PPR) is a fundamental tool in unsupervised learni...
research
∙
07/13/2022
Smooth Anonymity for Sparse Binary Matrices
When working with user data providing well-defined privacy guarantees is...
research
∙
06/17/2022
Scalable Differentially Private Clustering via Hierarchically Separated Trees
We study the private k-median and k-means clustering problem in d dimens...
research
∙
05/20/2022
Tackling Provably Hard Representative Selection via Graph Neural Networks
Representative selection (RS) is the problem of finding a small subset o...
research
∙
04/11/2022
Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets
Motivated by data analysis and machine learning applications, we conside...
research
∙
02/12/2022
From Online Optimization to PID Controllers: Mirror Descent with Momentum
We study a family of first-order methods with momentum based on mirror d...
research
∙
12/13/2021
Optimal Fully Dynamic k-Centers Clustering
We present the first algorithm for fully dynamic k-centers clustering in...
research
∙
12/01/2021
Synthetic Design: An Optimization Approach to Experimental Design with Synthetic Controls
We investigate the optimal design of experimental studies that have pre-...
research
∙
11/03/2021
Robust Auction Design in the Auto-bidding World
In classic auction theory, reserve prices are known to be effective for ...
research
∙
10/29/2021
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
Streaming computation plays an important role in large-scale data analys...
research
∙
10/22/2021
Tight and Robust Private Mean Estimation with Few Users
In this work, we study high-dimensional mean estimation under user-level...
research
∙
10/05/2021
Label differential privacy via clustering
We present new mechanisms for label differential privacy, a relaxation o...
research
∙
07/27/2021
Scalable Community Detection via Parallel Correlation Clustering
Graph clustering and community detection are central problems in modern ...
research
∙
07/16/2021
Bidding and Pricing in Budget and ROI Constrained Markets
In online advertising markets, setting budget and return on investment (...
research
∙
07/01/2021
Almost Tight Approximation Algorithms for Explainable Clustering
Recently, due to an increasing interest for transparency in artificial i...
research
∙
06/10/2021
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
We study the widely used hierarchical agglomerative clustering (HAC) alg...
research
∙
06/04/2021
Massively Parallel and Dynamic Algorithms for Minimum Size Clustering
In this paper, we study the r-gather problem, a natural formulation of m...
research
∙
06/02/2021
Parallelizing Thompson Sampling
How can we make use of information parallelism in online decision making...
research
∙
03/24/2021
Towards Efficient Auctions in an Auto-bidding World
Auto-bidding has become one of the main options for bidding in online ad...
research
∙
03/11/2021
Design and Analysis of Bipartite Experiments under a Linear Exposure-Response Model
The bipartite experimental framework is a recently proposed causal setti...
research
∙
02/25/2021
Batched Neural Bandits
In many sequential decision-making problems, the individuals are split i...
research
∙
11/18/2020
The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems
Online allocation problems with resource constraints are central problem...
research
∙
10/22/2020
Optimal Approximation – Smoothness Tradeoffs for Soft-Max Functions
A soft-max function has two main efficiency measures: (1) approximation ...
research
∙
10/20/2020