68 citations · 163 across the 18 of their papers we have counts for
14 papers · 1 filter
Better Private Linear Regression Through Better Private Feature Selection
Travis Dick, Jennifer Gillenwater, Matthew Joseph
Existing work on differentially private linear regression typically assumes that end users can precisely set data bounds or algorithmic hyperparameters. End users often struggle to…
Subset-Based Instance Optimality in Private Estimation
Travis Dick, Alex Kulesza, Ziteng Sun +1
We propose a new definition of instance optimality for differentially private estimation algorithms. Our definition requires an optimal algorithm to compete, simultaneously for eve…
Easy Learning from Label Proportions
Robert Istvan Busa-Fekete, Heejin Choi, Travis Dick +2
We consider the problem of Learning from Label Proportions (LLP), a weakly supervised classification setup where instances are grouped into "bags", and only the frequency of class…
Scalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning
Kaiwen Wang, Travis Dick, Maria-Florina Balcan
This paper introduces the first provably accurate algorithms for differentially private, top-down decision tree learning in the distributed setting (Balcan et al., 2012). We propos…
Algorithms and Learning for Fair Portfolio Design
Emily Diana, Travis Dick, Hadi Elzayn +5
We consider a variation on the classical finance problem of optimal portfolio design. In our setting, a large population of consumers is drawn from some distribution over risk tole…
Random Smoothing Might be Unable to Certify Robustness for High-Dimensional Images
Avrim Blum, Travis Dick, Naren Manoj +1
We show a hardness result for random smoothing to achieve certified adversarial robustness against attacks in the ball of radius when . Although random smoothing…
How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design
Maria-Florina Balcan, Dan DeBlasio, Travis Dick +3
Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit mea…
Learning piecewise Lipschitz functions in changing environments
Maria-Florina Balcan, Travis Dick, Dravyansh Sharma
Optimization in the presence of sharp (non-Lipschitz), unpredictable (w.r.t. time and amount) changes is a challenging and largely unexplored problem of great significance. We cons…
Learning to Link
Maria-Florina Balcan, Travis Dick, Manuel Lang
Clustering is an important part of many modern data analysis pipelines, including network analysis and data retrieval. There are many different clustering algorithms developed by v…
Semi-bandit Optimization in the Dispersed Setting
Maria-Florina Balcan, Travis Dick, Wesley Pegden
The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science…
Envy-Free Classification
Maria-Florina Balcan, Travis Dick, Ritesh Noothigattu +1
In classic fair division problems such as cake cutting and rent division, envy-freeness requires that each individual (weakly) prefer his allocation to anyone else's. On a conceptu…
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Maria-Florina Balcan, Travis Dick, Ellen Vitercik
Data-driven algorithm design, that is, choosing the best algorithm for a specific application, is a crucial problem in modern data science. Practitioners often optimize over a para…
Data Driven Resource Allocation for Distributed Learning
Travis Dick, Mu Li, Venkata Krishna Pillutla +3
In distributed machine learning, data is dispatched to multiple machines for processing. Motivated by the fact that similar data points often belong to the same or similar classes,…
Label Efficient Learning by Exploiting Multi-class Output Codes
Maria Florina Balcan, Travis Dick, Yishay Mansour
We present a new perspective on the popular multi-class algorithmic techniques of one-vs-all and error correcting output codes. Rather than studying the behavior of these technique…