Damian Straszak

ICML Conference 2018 Conference Paper

Fair and Diverse DPP-Based Data Summarization

• L. Elisa Celis
• Vijay Keswani
• Damian Straszak
• Amit Deshpande 0001
• Tarun Kathuria
• Nisheeth K. Vishnoi

Sampling methods that choose a subset of the data proportional to its diversity in the feature space are popular for data summarization. However, recent studies have noted the occurrence of bias {–} e. g. , under or over representation of a particular gender or ethnicity {–} in such data summarization methods. In this paper we initiate a study of the problem of outputting a diverse and fair summary of a given dataset. We work with a well-studied determinantal measure of diversity and corresponding distributions (DPPs) and present a framework that allows us to incorporate a general class of fairness constraints into such distributions. Designing efficient algorithms to sample from these constrained determinantal distributions, however, suffers from a complexity barrier; we present a fast sampler that is provably good when the input vectors satisfy a natural property. Our empirical results on both real-world and synthetic datasets show that the diversity of the samples produced by adding fairness constraints is not too far from the unconstrained case.

STOC Conference 2017 Conference Paper

Real stable polynomials and matroids: optimization and counting

• Damian Straszak
• Nisheeth K. Vishnoi

Several fundamental optimization and counting problems arising in computer science, mathematics and physics can be reduced to one of the following computational tasks involving polynomials and set systems: given an oracle access to an m -variate real polynomial g and to a family of (multi-)subsets ℬ of [ m ], (1) compute the sum of coefficients of monomials in g corresponding to all the sets that appear in B (1), or find S ε ℬ such that the monomial in g corresponding to S has the largest coefficient in g . Special cases of these problems, such as computing permanents and mixed discriminants, sampling from determinantal point processes, and maximizing sub-determinants with combinatorial constraints have been topics of much recent interest in theoretical computer science.

FOCS Conference 2017 Conference Paper

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

• Javad B. Ebrahimi
• Damian Straszak
• Nisheeth K. Vishnoi

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v 1, .. ., v m ∈ ℝ d and a constraint family B ⊆ 2 [m], find a set S ∈ B that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint (B = ( r [m] )), the r problem becomes NP-hard and has received much attention starting with a result by Khachiyan [1] who gave an r O(r) approximation algorithm for this problem. Recently, Nikolov and Singh [2] presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i. e. , when B corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits [3], and was recently extended to regular matroids [4], [5]. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms - that also output a set - remained open. The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena has recently been deployed.

SODA Conference 2016 Conference Paper

Natural Algorithms for Flow Problems

• Damian Straszak
• Nisheeth K. Vishnoi

In the last few years, there has been a significant interest in the computational abilities of Physarum polycephalum (a slime mold). This arose from a remarkable experiment which showed that this organism can compute shortest paths in a maze [10]. Subsequently, the workings of Physarum were mathematically modeled as a dynamical system and algorithms inspired by this model were proposed to solve several graph problems: shortest paths, flows, and linear programs to name a few. Indeed, computer scientists have initiated a rigorous study of these dynamics and a first step towards this was taken by [1, 2] who proved that the Physarum dynamics for the shortest path problem are efficient (when edge-lengths are polynomially bounded). In this paper, we take this further: we prove that the discrete time Physarum-dynamics can also efficiently solve the uncapacitated mincost flow problems on undirected and directed graphs; problems that are non-trivial generalizations of shortest path. This raises the tantalizing possibility that nature, via evolution, developed algorithms that efficiently solve some of the most complex computational problems, about a billion years before we did.

SODA Conference 2015 Conference Paper

Fast Generation of Random Spanning Trees and the Effective Resistance Metric

• Aleksander Madry
• Damian Straszak
• Jakub Tarnawski