research
∙
09/20/2023
GLM Regression with Oblivious Corruptions
We demonstrate the first algorithms for the problem of regression for ge...
share
research
∙
08/06/2023
Self-Directed Linear Classification
In online classification, a learner is presented with a sequence of exam...
research
∙
06/06/2023
Buying Information for Stochastic Optimization
Stochastic optimization is one of the central problems in Machine Learni...
research
∙
01/31/2023
Weitzman's Rule for Pandora's Box with Correlations
Pandora's Box is a central problem in decision making under uncertainty ...
research
∙
12/06/2022
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
The Forster transform is a method of regularizing a dataset by placing i...
research
∙
11/23/2022
Perfect Sampling from Pairwise Comparisons
In this work, we study how to efficiently obtain perfect samples from a ...
research
∙
08/22/2022
Graph Connectivity with Noisy Queries
Graph connectivity is a fundamental combinatorial optimization problem t...
research
∙
06/17/2022
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
We study the fundamental problem of learning a single neuron, i.e., a fu...
research
∙
06/09/2022
Clustering with Queries under Semi-Random Noise
The seminal paper by Mazumdar and Saha <cit.> introduced an extensive li...
research
∙
05/26/2022
Contextual Pandora's Box
Pandora's Box is a fundamental stochastic optimization problem, where th...
research
∙
04/05/2022
Buy-Many Mechanisms for Many Unit-Demand Buyers
A recent line of research has established a novel desideratum for design...
research
∙
02/10/2022
Online Learning for Min Sum Set Cover and Pandora's Box
Two central problems in Stochastic Optimization are Min Sum Set Cover an...
research
∙
09/10/2021
ReLU Regression with Massart Noise
We study the fundamental problem of ReLU regression, where the goal is t...
research
∙
08/30/2021
Approximating Pandora's Box with Correlations
The Pandora's Box problem asks to find a search strategy over n alternat...
research
∙
08/22/2021
Efficient Algorithms for Learning from Coarse Labels
For many learning problems one may not have access to fine grained label...
research
∙
08/19/2021
Threshold Phenomena in Learning Halfspaces with Massart Noise
We study the problem of PAC learning halfspaces on ℝ^d with Massart nois...
research
∙
07/12/2021
Forster Decomposition and Learning Halfspaces with Noise
A Forster transform is an operation that turns a distribution into one w...
research
∙
06/30/2021
A Statistical Taylor Theorem and Extrapolation of Truncated Densities
We show a statistical version of Taylor's theorem and apply this result ...
research
∙
06/14/2021
Boosting in the Presence of Massart Noise
We study the problem of boosting the accuracy of a weak learner in the (...
research
∙
06/08/2021
Pricing Ordered Items
We study the revenue guarantees and approximability of item pricing. Rec...
research
∙
02/10/2021
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
We study the problem of agnostically learning halfspaces under the Gauss...
research
∙
12/01/2020
Convergence and Sample Complexity of SGD in GANs
We provide theoretical convergence guarantees on training Generative Adv...
research
∙
11/12/2020
Optimal Private Median Estimation under Minimal Distributional Assumptions
We study the fundamental task of estimating the median of an underlying ...
research
∙
10/22/2020
Computationally and Statistically Efficient Truncated Regression
We provide a computationally and statistically efficient estimator for t...
research
∙
10/04/2020
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
We study the problem of PAC learning homogeneous halfspaces in the prese...
research
∙
08/24/2020
Fast and Simple Modular Subset Sum
We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...
research
∙
07/05/2020
Efficient Parameter Estimation of Truncated Boolean Product Distributions
We study the problem of estimating the parameters of a Boolean product d...
research
∙
06/11/2020
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
We study the problem of agnostically learning homogeneous halfspaces in ...
research
∙
06/11/2020
Learning Halfspaces with Tsybakov Noise
We study the efficient PAC learnability of halfspaces in the presence of...
research
∙
03/24/2020
Menu-size Complexity and Revenue Continuity of Buy-many Mechanisms
We study the multi-item mechanism design problem where a monopolist sell...
research
∙
03/21/2020
Black-box Methods for Restoring Monotonicity
In many practical applications, heuristic or approximation algorithms ar...
research
∙
02/13/2020
Learning Halfspaces with Massart Noise Under Structured Distributions
We study the problem of learning halfspaces with Massart noise in the di...
research
∙
02/10/2020
Robust Mean Estimation under Coordinate-level Corruption
Data corruption, systematic or adversarial, may skew statistical estimat...
research
∙
11/05/2019
Learning Optimal Search Algorithms from Data
Classical algorithm design is geared towards worst case instances and fa...
research
∙
08/02/2019
Efficient Truncated Statistics with Unknown Truncation
We study the problem of estimating the parameters of a Gaussian distribu...
research
∙
06/26/2019
The Complexity of Black-Box Mechanism Design with Priors
We study black-box reductions from mechanism design to algorithm design ...
research
∙
06/24/2019
Distribution-Independent PAC Learning of Halfspaces with Massart Noise
We study the problem of distribution-independent PAC learning of halfsp...
research
∙
05/13/2019
Diversity and Exploration in Social Learning
In consumer search, there is a set of items. An agent has a prior over h...
research
∙
04/26/2019
Learning to Prune: Speeding up Repeated Computations
It is common to encounter situations where one must solve a sequence of ...
research
∙
02/27/2019
Buy-many mechanisms are not much better than item pricing
Multi-item mechanisms can be very complex offering many different bundle...
research
∙
02/27/2019
Reasonable multi-item mechanisms are not much better than item pricing
Multi-item mechanisms can be very complex offering many different bundle...
research
∙
09/11/2018
Efficient Statistics, in High Dimensions, from Truncated Samples
We provide an efficient algorithm for the classical problem, going back ...
research
∙
07/17/2018
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing
We investigate distribution testing with access to non-adaptive conditio...
research
∙
07/12/2018
Fast Modular Subset Sum using Linear Sketching
Given n positive integers, the Modular Subset Sum problem asks if a subs...
research
∙
02/20/2018
Actively Avoiding Nonsense in Generative Models
A generative model may generate utter nonsense when it is fit to maximiz...
research
∙
02/18/2018
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
One of the most fundamental problems in Theoretical Computer Science is ...
research
∙
11/07/2017
Combinatorial Assortment Optimization
Assortment optimization refers to the problem of designing a slate of pr...
research
∙
09/12/2017
Certified Computation in Crowdsourcing
A wide range of learning tasks require human input in labeling massive d...
research
∙
02/23/2017
A Converse to Banach's Fixed Point Theorem and its CLS Completeness
Banach's fixed point theorem for contraction maps has been widely used t...
research
∙
01/02/2017