research
∙
02/16/2023
Deterministic Nonsmooth Nonconvex Optimization
We study the complexity of optimizing nonsmooth nonconvex Lipschitz func...
share
research
∙
10/24/2022
Learning and Covering Sums of Independent Random Variables with Unbounded Support
We study the problem of covering and learning sums X = X_1 + ⋯ + X_n of ...
research
∙
10/18/2022
STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games
Min-max optimization problems involving nonconvex-nonconcave objectives ...
research
∙
09/26/2022
On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization
In this paper, we present several new results on minimizing a nonsmooth ...
research
∙
08/25/2022
Efficient Truncated Linear Regression with Unknown Noise Variance
Truncated linear regression is a classical challenge in Statistics, wher...
research
∙
07/15/2022
The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
Introduced by the celebrated works of Debreu and Rosen in the 1950s and ...
research
∙
05/06/2022
What Makes A Good Fisherman? Linear Regression under Self-Selection Bias
In the classical setting of self-selection, the goal is to learn k model...
research
∙
05/04/2022
Estimation of Standard Auction Models
We provide efficient estimation methods for first- and second-price auct...
research
∙
04/07/2022
First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems
We consider the problem of computing an equilibrium in a class of nonlin...
research
∙
12/27/2021
Last-Iterate Convergence of Saddle Point Optimizers via High-Resolution Differential Equations
Several widely-used first-order saddle point optimization methods yield ...
research
∙
07/13/2021
Robust Learning of Optimal Auctions
We study the problem of learning revenue-optimal multi-bidder auctions f...
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
∙
10/22/2020
Computationally and Statistically Efficient Truncated Regression
We provide a computationally and statistically efficient estimator for t...
research
∙
10/22/2020
Optimal Approximation – Smoothness Tradeoffs for Soft-Max Functions
A soft-max function has two main efficiency measures: (1) approximation ...
research
∙
09/21/2020
The Complexity of Constrained Min-Max Optimization
Despite its important applications in Machine Learning, min-max optimiza...
research
∙
07/29/2020
Truncated Linear Regression in High Dimensions
As in standard linear regression, in truncated linear regression, we are...
research
∙
07/07/2020
Estimation and Inference with Trees and Forests in High Dimensions
We analyze the finite sample mean squared error (MSE) performance of reg...
research
∙
06/07/2020
Constant-Expansion Suffices for Compressed Sensing with Generative Priors
Generative neural networks have been empirically found very promising in...
research
∙
03/26/2020
A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting
The classes PPA-p have attracted attention lately, because they are the ...
research
∙
02/26/2020
Consensus-Halving: Does it Ever Get Easier?
In the ε-Consensus-Halving problem, a fundamental problem in fair divisi...
research
∙
02/26/2020
Consenus-Halving: Does it Ever Get Easier?
In the ε-Consensus-Halving problem, a fundamental problem in fair divisi...
research
∙
12/10/2019
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
We study the search problem class PPA_q defined as a modulo-q analog of ...
research
∙
08/02/2019
Efficient Truncated Statistics with Unknown Truncation
We study the problem of estimating the parameters of a Gaussian distribu...
research
∙
06/03/2019
Optimal Learning of Mallows Block Model
The Mallows model, introduced in the seminal paper of Mallows 1957, is o...
research
∙
09/11/2018
Efficient Statistics, in High Dimensions, from Truncated Samples
We provide an efficient algorithm for the classical problem, going back ...
research
∙
08/20/2018
PPP-Completeness with Connections to Cryptography
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP w...
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
∙
09/01/2016