research
∙
07/18/2023
On the works of Avi Wigderson
This is an overview of some of the works of Avi Wigderson, 2021 Abel pri...
share
research
∙
06/29/2023
Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations
We consider the problem of approximating a d × d covariance matrix M wit...
research
∙
06/16/2023
Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions
We consider the problem of subset selection where one is given multiple ...
research
∙
05/03/2023
Maximizing Submodular Functions for Recommendation in the Presence of Biases
Subset selection tasks, arise in recommendation systems and search engin...
research
∙
11/30/2022
Fair Ranking with Noisy Protected Attributes
The fair-ranking problem, which asks to rank a given set of items to max...
research
∙
11/11/2022
Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
Given a symmetric matrix M and a vector λ, we present new bounds on the ...
research
∙
07/06/2022
Private Matrix Approximation and Geometry of Unitary Orbits
Consider the following optimization problem: Given n × n matrices A and ...
research
∙
06/19/2022
Faster Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk
We consider the problem of sampling from a d-dimensional log-concave dis...
research
∙
02/03/2022
Selection in the Presence of Implicit Bias: The Advantage of Intersectional Constraints
In selection processes such as hiring, promotion, and college admissions...
research
∙
11/24/2021
Fairness for AUC via Feature Augmentation
We study fairness in the context of classification where the performance...
research
∙
11/07/2021
Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization
For a d-dimensional log-concave distribution π(θ)∝ e^-f(θ) on a polytope...
research
∙
10/28/2021
Coresets for Time Series Clustering
We study the problem of constructing coresets for clustering problems wi...
research
∙
09/02/2021
Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory
In the last few years, the notion of symmetry has provided a powerful an...
research
∙
08/27/2021
An Introduction to Hamiltonian Monte Carlo Method for Sampling
The goal of this article is to introduce the Hamiltonian Monte Carlo (HM...
research
∙
06/10/2021
Fair Classification with Adversarial Perturbations
We study fair classification in the presence of an omniscient adversary ...
research
∙
11/10/2020
A Polynomial-Time Algorithm and Applications for Matrix Sampling from Harish-Chandra–Itzykson-Zuber Densities
Given two n × n Hermitian matrices Y and Λ, the Harish-Chandra–Itzykson–...
research
∙
11/03/2020
On the Computability of Continuous Maximum Entropy Distributions: Adjoint Orbits of Lie Groups
Given a point A in the convex hull of a given adjoint orbit 𝒪(F) of a co...
research
∙
11/02/2020
Coresets for Regressions with Panel Data
This paper introduces the problem of coresets for regression problems to...
research
∙
10/21/2020
The Effect of the Rooney Rule on Implicit Bias in the Long Term
A robust body of evidence demonstrates the adverse effects of implicit b...
research
∙
06/22/2020
A Provably Convergent and Practical Algorithm for Min-max Optimization with Applications to GANs
We present a new algorithm for optimizing min-max loss functions that ar...
research
∙
06/22/2020
A Second-order Equilibrium in Nonconvex-Nonconcave Min-max Optimization: Existence and Algorithm
Min-max optimization, with a nonconvex-nonconcave objective function f: ...
research
∙
06/08/2020
Fair Classification with Noisy Protected Attributes
Due to the growing deployment of classification algorithms in various so...
research
∙
04/16/2020
On the computability of continuous maximum entropy distributions with applications
We initiate a study of the following problem: Given a continuous domain ...
research
∙
04/14/2020
Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal
Given a collection of n points in ℝ^d, the goal of the (k,z)-clustering ...
research
∙
01/23/2020
Interventions for Ranking in the Presence of Implicit Bias
Implicit bias is the unconscious attribution of particular qualities (or...
research
∙
06/20/2019
Coresets for Clustering with Fairness Constraints
In a recent work, Chierichetti et al. studied the following "fair" varia...
research
∙
06/05/2019
Fair Distributions from Biased Samples: A Maximum Entropy Optimization Framework
One reason for the emergence of bias in AI systems is biased data -- dat...
research
∙
05/05/2019
Faster algorithms for polytope rounding, sampling, and volume computation via a sublinear "Ball Walk"
We study the problem of "isotropically rounding" a polytope K⊆R^n, that ...
research
∙
02/22/2019
Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
The Langevin Markov chain algorithms are widely deployed methods to samp...
research
∙
02/21/2019
Online Sampling from Log-Concave Distributions
Given a sequence of convex functions f_0, f_1, ..., f_T, we study the pr...
research
∙
02/21/2019
Stable and Fair Classification
Fair classification has been a topic of intense study in machine learnin...
research
∙
01/29/2019
Toward Controlling Discrimination in Online Ad Auctions
Online advertising platforms are thriving due to the customizable audien...
research
∙
01/29/2019
Fair Online Advertising
Online advertising platforms are thriving due to the customizable audien...
research
∙
06/24/2018
Balanced News Using Constrained Bandit-based Personalization
We present a prototype for a news search engine that presents balanced v...
research
∙
06/17/2018
Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity
Convex optimization is a vibrant and successful area due to the existenc...
research
∙
06/15/2018
Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees
Developing classification algorithms that are fair with respect to sensi...
research
∙
04/11/2018
On Geodesically Convex Formulations for the Brascamp-Lieb Constant
We consider two non-convex formulations for computing the optimal consta...
research
∙
02/24/2018
Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
Hamiltonian Monte Carlo (HMC) is a widely deployed method to sample from...
research
∙
02/24/2018
Dimensionally Tight Running Time Bounds for Second-Order Hamiltonian Monte Carlo
Hamiltonian Monte Carlo (HMC) is a widely deployed method to sample from...
research
∙
02/23/2018
An Algorithmic Framework to Control Bias in Bandit-based Personalization
Personalization is pervasive in the online space as it leads to higher e...
research
∙
02/12/2018
Fair and Diverse DPP-based Data Summarization
Sampling methods that choose a subset of the data proportional to its di...
research
∙
11/07/2017
Convex Optimization with Nonconvex Oracles
In machine learning and optimization, one often wants to minimize a conv...
research
∙
11/06/2017
Computing Maximum Entropy Distributions Everywhere
We study the problem of computing the maximum entropy distribution with ...
research
∙
10/27/2017
Group Fairness in Multiwinner Voting
We study multiwinner voting problems when there is an additional require...
research
∙
08/08/2017
Belief Propagation, Bethe Approximation and Polynomials
Factor graphs are important models for succinctly representing probabili...
research
∙
08/07/2017
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
We derandomize the famous Isolation Lemma by Mulmuley, Vazirani, and Vaz...
research
∙
07/10/2017
Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration
Several fundamental problems that arise in optimization and computer sci...
research
∙
08/01/2016
On the Complexity of Constrained Determinantal Point Processes
Determinantal Point Processes (DPPs) are probabilistic models that arise...
research
∙
01/12/2016