Ali Vakilian

NeurIPS Conference 2024 Conference Paper

Bayesian Strategic Classification

• Lee Cohen
• Saeed Sharifi-Malvajerdi
• Kevin Stang1
• Ali Vakilian
• Juba Ziani

In strategic classification, agents modify their features, at a cost, to obtain a positive classification outcome from the learner’s classifier, typically assuming agents have full knowledge of the deployed classifier. In contrast, we consider a Bayesian setting where agents have a common distributional prior on the classifier being used and agents manipulate their features to maximize their expected utility according to this prior. The learner can reveal truthful, yet not necessarily complete, information about the classifier to the agents, aiming to release just enough information to shape the agents' behavior and thus maximize accuracy. We show that partial information release can counter-intuitively benefit the learner’s accuracy, allowing qualified agents to pass the classifier while preventing unqualified agents from doing so. Despite the intractability of computing the best response of an agent in the general case, we provide oracle-efficient algorithms for scenarios where the learner’s hypothesis class consists of low-dimensional linear classifiers or when the agents’ cost function satisfies a sub-modularity condition. Additionally, we address the learner’s optimization problem, offering both positive and negative results on determining the optimal information release to maximize expected accuracy, particularly in settings where an agent’s qualification can be represented by a real-valued number.

NeurIPS Conference 2024 Conference Paper

On Socially Fair Low-Rank Approximation and Column Subset Selection

• Zhao Song
• Ali Vakilian
• David P. Woodruff
• Samson Zhou

Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. In this paper, we study the question of socially fair low-rank approximation and socially fair column subset selection, where the goal is to minimize the loss over all sub-populations of the data. We show that surprisingly, even constant-factor approximation to fair low-rank approximation requires exponential time under certain standard complexity hypotheses. On the positive side, we give an algorithm for fair low-rank approximation that, for a constant number of groups and constant-factor accuracy, runs in $2^{\text{poly}(k)}$ rather than the naive $n^{\text{poly}(k)}$, which is a substantial improvement when the dataset has a large number $n$ of observations. We then show that there exist bicriteria approximation algorithms for fair low-rank approximation and fair column subset selection that runs in polynomial time.

ICML Conference 2023 Conference Paper

Approximation Algorithms for Fair Range Clustering

• Sèdjro Salomon Hotegni
• Sepideh Mahabadi
• Ali Vakilian

This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick $k$ centers with the minimum clustering cost such that each group is at least minimally represented in the centers set and no group dominates the centers set. More precisely, given a set of $n$ points in a metric space $(P, d)$ where each point belongs to one of the $\ell$ different demographics (i. e. , $P = P_1 \uplus P_2 \uplus \cdots \uplus P_\ell$) and a set of $\ell$ intervals $[\alpha_1, \beta_1], \cdots, [\alpha_\ell, \beta_\ell]$ on desired number of centers from each group, the goal is to pick a set of $k$ centers $C$ with minimum $\ell_p$-clustering cost (i. e. , $(\sum_{v\in P} d(v, C)^p)^{1/p}$) such that for each group $i\in \ell$, $|C\cap P_i| \in [\alpha_i, \beta_i]$. In particular, the fair range $\ell_p$-clustering captures fair range $k$-center, $k$-median and $k$-means as its special cases. In this work, we provide an efficient constant factor approximation algorithm for the fair range $\ell_p$-clustering for all values of $p\in [1, \infty)$.

NeurIPS Conference 2023 Conference Paper

Constant Approximation for Individual Preference Stable Clustering

• Anders Aamand
• Justin Chen
• Allen Liu
• Sandeep Silwal
• Pattara Sukprasert
• Ali Vakilian
• Fred Zhang

Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $\alpha$-IP stable if the average distance of every data point to its own cluster is at most $\alpha$ times the average distance to any other cluster. Unfortunately, determining if a dataset admits a $1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if an $o(n)$-IP stable clustering always exists, as the prior state of the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in understanding and show that an $O(1)$-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering. We also introduce generalizations of IP stability beyond average distance and give efficient near optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.

NeurIPS Conference 2023 Conference Paper

Improved Frequency Estimation Algorithms with and without Predictions

• Anders Aamand
• Justin Chen
• Huy Nguyen
• Sandeep Silwal
• Ali Vakilian

Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e. g. , CountMin and CountSketch) come with worst-case guarantees that probabilistically bound the error of the estimated frequencies for any possible input. The work of Hsu et al. ~(2019) introduced the idea of using machine learning to tailor sketching algorithms to the specific data distribution they are being run on. In particular, their learning-augmented frequency estimation algorithm uses a learned heavy-hitter oracle which predicts which elements will appear many times in the stream. We give a novel algorithm, which in some parameter regimes, already theoretically outperforms the learning based algorithm of Hsu et al. without the use of any predictions. Augmenting our algorithm with heavy-hitter predictions further reduces the error and improves upon the state of the art. Empirically, our algorithms achieve superior performance in all experiments compared to prior approaches.

ICLR Conference 2023 Conference Paper

Learning the Positions in CountSketch

• Yi Li 0002
• Honghao Lin
• Simin Liu
• Ali Vakilian
• David P. Woodruff

We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g., low-rank approximation and regression. In the learning-based sketching paradigm proposed by Indyk et al., the sketch matrix is found by choosing a random sparse matrix, e.g., CountSketch, and then the values of its non-zero entries are updated by running gradient descent on a training data set. Despite the growing body of work on this paradigm, a noticeable omission is that the locations of the non-zero entries of previous algorithms were fixed, and only their values were learned. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries. Our first proposed algorithm is based on a greedy algorithm. However, one drawback of the greedy algorithm is its slower training time. We fix this issue and propose approaches for learning a sketching matrix for both low-rank approximation and Hessian approximation for second-order optimization. The latter is helpful for a range of constrained optimization problems, such as LASSO and matrix estimation with a nuclear norm constraint. Both approaches achieve good accuracy with a fast running time. Moreover, our experiments suggest that our algorithm can still reduce the error significantly even if we only have a very limited number of training matrices.

ICML Conference 2023 Conference Paper

Sequential Strategic Screening

• Lee Cohen 0001
• Saeed Sharifi-Malvajerdi
• Kevin Stangl
• Ali Vakilian
• Juba Ziani

We initiate the study of strategic behavior in screening processes with multiple classifiers. We focus on two contrasting settings: a "conjunctive” setting in which an individual must satisfy all classifiers simultaneously, and a sequential setting in which an individual to succeed must satisfy classifiers one at a time. In other words, we introduce the combination of strategic classificationwith screening processes. We show that sequential screening pipelines exhibit new and surprising behavior where individuals can exploit the sequential ordering of the tests to "zig-zag” between classifiers without having to simultaneously satisfy all of them. We demonstrate an individual can obtain a positive outcome using a limited manipulation budget even when far from the intersection of the positive regions of every classifier. Finally, we consider a learner whose goal is to design a sequential screening process that is robust to such manipulations, and provide a construction for the learner that optimizes a natural objective.

NeurIPS Conference 2023 Conference Paper

Tight Bounds for Volumetric Spanners and Applications

• Aditya Bhaskara
• Sepideh Mahabadi
• Ali Vakilian

Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate norm). Formally, given a set of vectors $X = [v_1, v_2, \dots, v_n]$, the goal is to find $T \subseteq [n]$ such that every $v \in X$ can be expressed as $\sum_{i\in T} \alpha_i v_i$, with $\Vert \alpha \Vert$ being small. This notion, which has also been referred to as a well-conditioned basis, has found several applications, including bandit linear optimization, determinant maximization, and matrix low rank approximation. In this paper, we give almost optimal bounds on the size of volumetric spanners for all $\ell_p$ norms, and show that they can be constructed using a simple local search procedure. We then show the applications of our result to other tasks and in particular the problem of finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem.

SODA Conference 2022 Conference Paper

Approximating Fair Clustering with Cascaded Norm Objectives

• Eden Chlamtac
• Yury Makarychev
• Ali Vakilian

We introduce the ( p, q )-Fair Clustering problem. In this problem, we are given a set of points P and a collection of different weight functions W. We would like to find a clustering which minimizes the ℓ q -norm of the vector over W of the ℓ p -norms of the weighted distances of points in P from the centers. This generalizes various clustering problems, including Socially Fair k -Median and k -Means, and is closely connected to other problems such as Densest k -Subgraph and Min k -Union. We utilize convex programming techniques to approximate the ( p, q )-Fair Clustering problem for different values of p and q. When p ≥ q, we get an O ( k ( p – q )/(2 pq ) ), which nearly matches a k Ω(( p – q ) / ( pq )) lower bound based on conjectured hardness of Min k -Union and other problems. When q ≥ p, we get an approximation which is independent of the size of the input for bounded p, q, and also matches the recent O ((log n /(log log n )) 1/ p )-approximation for ( p, ∞)-Fair Clustering by Makarychev and Vakilian (COLT 2021).

ICML Conference 2022 Conference Paper

Faster Fundamental Graph Algorithms via Learned Predictions

• Justin Y. Chen
• Sandeep Silwal
• Ali Vakilian
• Fred Zhang

We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or similar instances. Given the additional information, we aim to improve upon the traditional worst-case run-time guarantees. Our contributions are the following: (i) We give a faster algorithm for minimum-weight bipartite matching via learned duals, improving the recent result by Dinitz, Im, Lavastida, Moseley and Vassilvitskii (NeurIPS, 2021); (ii) We extend the learned dual approach to the single-source shortest path problem (with negative edge lengths), achieving an almost linear runtime given sufficiently accurate predictions which improves upon the classic fastest algorithm due to Goldberg (SIAM J. Comput. , 1995); (iii) We provide a general reduction-based framework for learning-based graph algorithms, leading to new algorithms for degree-constrained subgraph and minimum-cost 0-1 flow, based on reductions to bipartite matching and the shortest path problem. Finally, we give a set of general learnability theorems, showing that the predictions required by our algorithms can be efficiently learned in a PAC fashion.

ICML Conference 2022 Conference Paper

Individual Preference Stability for Clustering

• Saba Ahmadi
• Pranjal Awasthi
• Samir Khuller
• Matthäus Kleindessner
• Jamie Morgenstern
• Pattara Sukprasert
• Ali Vakilian

In this paper, we propose a natural notion of individual preference (IP) stability for clustering, which asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster. Our notion can be motivated from several perspectives, including game theory and algorithmic fairness. We study several questions related to our proposed notion. We first show that deciding whether a given data set allows for an IP-stable clustering in general is NP-hard. As a result, we explore the design of efficient algorithms for finding IP-stable clusterings in some restricted metric spaces. We present a polytime algorithm to find a clustering satisfying exact IP-stability on the real line, and an efficient algorithm to find an IP-stable 2-clustering for a tree metric. We also consider relaxing the stability constraint, i. e. , every data point should not be too far from its own cluster compared to any other cluster. For this case, we provide polytime algorithms with different guarantees. We evaluate some of our algorithms and several standard clustering approaches on real data sets.

ICML Conference 2021 Conference Paper

Learning Online Algorithms with Distributional Advice

• Ilias Diakonikolas
• Vasilis Kontonis
• Christos Tzamos
• Ali Vakilian
• Nikos Zarifis

We study the problem of designing online algorithms given advice about the input. While prior work had focused on deterministic advice, we only assume distributional access to the instances of interest, and the goal is to learn a competitive algorithm given access to i. i. d. samples. We aim to be competitive against an adversary with prior knowledge of the distribution, while also performing well against worst-case inputs. We focus on the classical online problems of ski-rental and prophet-inequalities, and provide sample complexity bounds for the underlying learning tasks. First, we point out that for general distributions it is information-theoretically impossible to beat the worst-case competitive-ratio with any finite sample size. As our main contribution, we establish strong positive results for well-behaved distributions. Specifically, for the broad class of log-concave distributions, we show that $\mathrm{poly}(1/\epsilon)$ samples suffice to obtain $(1+\epsilon)$-competitive ratio. Finally, we show that this sample upper bound is close to best possible, even for very simple classes of distributions.

SODA Conference 2020 Conference Paper

Improved Local Computation Algorithm for Set Cover via Sparsification

• Christoph Grunau
• Slobodan Mitrovic
• Ronitt Rubinfeld
• Ali Vakilian

We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most s and each element is contained in at most t sets, the algorithm reports whether a given set is in some fixed set cover whose expected size is O (log s ) times the minimum fractional set cover value. Our algorithm requires s O (log s ) t O (log s +log log t )) queries. This result improves upon the application of the reduction of [Parnas and Ron, TCS’07] on the result of [Kuhn et al. , SODA’06], which leads to a query complexity of ( st ) O (log s · log t ). To obtain this result, we design a parallel set cover algorithm that admits an efficient simulation in the LCA model by using a sparsification technique introduced in [Ghaffari and Uitto, SODA’19] for the maximal independent set problem. The parallel algorithm adds a random subset of the sets to the solution in a style similar to the PRAM algorithm of [Berger et al. , FOCS’89]. However, our algorithm differs in the way that it never revokes its decisions, which results in a fewer number of adaptive rounds. This requires a novel approximation analysis which might be of independent interest.

ICML Conference 2020 Conference Paper

Individual Fairness for k-Clustering

• Sepideh Mahabadi
• Ali Vakilian

We give a local search based algorithm for $k$-median and $k$-means (and more generally for any $k$-clustering with $\ell_p$ norm cost function) from the perspective of individual fairness. More precisely, for a point $x$ in a point set $P$ of size $n$, let $r(x)$ be the minimum radius such that the ball of radius $r(x)$ centered at $x$ has at least $n/k$ points from $P$. Intuitively, if a set of $k$ random points are chosen from $P$ as centers, every point $x\in P$ expects to have a center within radius $r(x)$. In this work, we show how to get an approximately optimal such fair $k$-clustering: The $k$-median ($k$-means) cost of our solution is within a constant factor of the cost of an optimal fair $k$-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor).

NeurIPS Conference 2019 Conference Paper

Learning-Based Low-Rank Approximations

• Piotr Indyk
• Ali Vakilian
• Yang Yuan

We introduce a “learning-based” algorithm for the low-rank decomposition problem: given an $n \times d$ matrix $A$, and a parameter $k$, compute a rank-$k$ matrix $A'$ that minimizes the approximation loss $\|A-A'\|_F$. The algorithm uses a training set of input matrices in order to optimize its performance. Specifically, some of the most efficient approximate algorithms for computing low-rank approximations proceed by computing a projection $SA$, where $S$ is a sparse random $m \times n$ “sketching matrix”, and then performing the singular value decomposition of $SA$. We show how to replace the random matrix $S$ with a “learned” matrix of the same sparsity to reduce the error. Our experiments show that, for multiple types of data sets, a learned sketch matrix can substantially reduce the approximation loss compared to a random matrix $S$, sometimes up to one order of magnitude. We also study mixed matrices where only some of the rows are trained and the remaining ones are random, and show that matrices still offer improved performance while retaining worst-case guarantees. Finally, to understand the theoretical aspects of our approach, we study the special case of $m=1$. In particular, we give an approximation algorithm for minimizing the empirical loss, with approximation factor depending on the stable rank of matrices in the training set. We also show generalization bounds for the sketch matrix learning problem.

ICML Conference 2019 Conference Paper

Scalable Fair Clustering

• Arturs Backurs
• Piotr Indyk
• Krzysztof Onak
• Baruch Schieber
• Ali Vakilian
• Tal Wagner

We study the fair variant of the classic k-median problem introduced by (Chierichetti et al. , NeurIPS 2017) in which the points are colored, and the goal is to minimize the same average distance objective as in the standard $k$-median problem while ensuring that all clusters have an “approximately equal” number of points of each color. (Chierichetti et al. , NeurIPS 2017) proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time.

SODA Conference 2018 Conference Paper

Set Cover in Sub-linear Time

• Piotr Indyk
• Sepideh Mahabadi
• Ronitt Rubinfeld
• Ali Vakilian
• Anak Yodpinyanee

STOC Conference 2014 Conference Paper

Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements

• Alina Ene
• Ali Vakilian

We consider degree bounded network design problems with element and vertex connectivity requirements. In the degree bounded Survivable Network Design (SNDP) problem, the input is an undirected graph G = ( V, E ) with weights w ( e ) on the edges and degree bounds b ( v ) on the vertices, and connectivity requirements r ( uv ) for each pair uv of vertices. The goal is to select a minimum-weight subgraph H of G that meets the connectivity requirements and it satisfies the degree bounds on the vertices: for each pair uv of vertices, H has r ( uv ) disjoint paths between u and v ; additionally, each vertex v is incident to at most b ( v ) edges in H . We give the first ( O (1), O (1) · b ( v )) bicriteria approximation algorithms for the degree-bounded SNDP problem with element connectivity requirements and for several degree-bounded SNDP problems with vertex connectivity requirements. Our algorithms construct a subgraph H whose weight is at most O (1) times the optimal such that each vertex v is incident to at most O (1) · b ( v ) edges in H . We can also extend our approach to network design problems in directed graphs with out-degree constraints to obtain ( O (1), O (1) · b + ( v )) bicriteria approximation.