Pith. sign in

REVIEW 3 major objections 4 minor 86 references

On Socially Fair Low-Rank Approximation and Column Subset Selection

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Socially fair low-rank approximation—minimizing worst reconstruction error across subpopulations—is NP-hard to approximate to any constant factor, yet polynomial-time bicriteria algorithms exist that trade a larger rank for a bounded…

desk verdict Hardness results are solid, but both positive algorithmic theorems have load-bearing proof gaps; the bicriteria lemma is tautological and the (1+eps) algorithm needs an all-V embedding it doesn't have. read the letter →

arxiv 2412.06063 v1 pith:XL5YA52R submitted 2024-12-08 cs.LG cs.DSstat.ML

Zhao Song , Ali Vakilian , David P. Woodruff , Samson Zhou This is my paper · ORCID
classification cs.LGcs.DSstat.ML MSC 68Q1768W2068W25
keywords sociallyfairlow-rankapproximationcolumnsubsetselectionbicriteriaalgorithmicfairnessexponentialtimehypothesisrandomizedlinearalgebraLewisweightsampling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Socially fair low-rank approximation asks for a single rank-$k$ subspace that keeps the worst reconstruction error across all population groups small. This paper shows the problem is harder than ordinary low-rank approximation: a constant-factor approximation cannot run in polynomial time unless P=NP, and under the exponential time hypothesis even $2^{k^{\Omega(1)}}$ time is required. On the positive side, a $(1+\varepsilon)$-approximation runs in $2^{\mathrm{poly}(k)}$ time for any constant number of groups, replacing the naive $n^{\mathrm{poly}(k)}$ dependence on dataset size. The paper also gives polynomial-time bicriteria algorithms, for both low-rank approximation and column subset selection, that output solutions with $O(k(\log\log k)(\log^2 d))$ dimensions or $O(k\log k)$ columns while keeping the worst-group Frobenius error within a factor of $\ell^c 2^{1/c} O(k(\log\log k)(\log d))$ of optimal. The upshot is that fairness is not free, but a controlled rank or column trade-off restores polynomial time.

What carries the argument

The proof is carried by two distinct mechanisms. For hardness, the reduction maps Subspace(k,∞)—the problem of finding the $k$-dimensional subspace minimizing the maximum Euclidean distance to a point set—onto fair low-rank approximation with $\ell=k$ groups and one point per group, so any constant-factor fair-LRA algorithm would approximate the subspace problem. For the algorithms, the carrying object is the affine embedding $S$, a random sketch with $m=O(k^2\varepsilon^{-2}\log\ell)$ columns that preserves $\|xAS-bS\|_F^2$ up to $1\pm\varepsilon$; it lets the $(1+\varepsilon)$-approximation encode the unknown subspace $V$ only through $VS$, reducing the polynomial-system variables to $mk$ instead of $kd$. The bicriteria algorithm replaces the max over groups by an $\ell^p$ sum, then uses Dvoretzky's Theorem (a random Gaussian embedding with $(1-\varepsilon)\|GMH\|_p\le\|M\|_F\le(1+\varepsilon)\|GMH\|_p$) to turn each Frobenius term into an entrywise $L_p$ term, a column-sampling matrix $S$ with $t=O(k(\log\log k)(\log^2 d))$ columns from the paper's cited $L_p$ low-rank approximation result, and a Lewis-weight sampling matrix $T$ (a row-sampling scheme that preserves entrywise $L_p$ norms up to constant factors); the closed-form least-squares solution $\tilde V=(TGAHS)^\dagger(TGA)$ is then argued to be a near-optimal fair subspace.

What would settle it

Run Algorithm 3 on a two-group instance with small $k$ and large $d$ where the optimal fair subspace is deliberately chosen far from the global Frobenius subspace, compute the actual worst-group Frobenius error across many Gaussian draws, and compare it with $\ell^c 2^{1/c}O(k(\log\log k)(\log d))$ times the optimal fair error. Concretely, test the proof's crucial equality by finding matrices $B=TGAHS$ and $C=TGAH$ for which $\min_X\|BX-C\|_{(p,2)}$ is achieved by a matrix substantially different from $B^\dagger C$; if the ratio of the two objective values grows with the row count or dimension, the bicriteria theorem's bound collapses.

Watch

Extended reading notes

Core claim

The central discovery is a complexity dichotomy. The fair objective $\min_{V\in\mathbb{R}^{k\times d}}\max_{i\in[\ell]}\|A^{(i)}V^\dagger V-A^{(i)}\|_F$ is exactly the max-distance-to-subspace problem on the group matrices, so the known hardness of approximating Subspace(k,∞) transfers directly: Theorems 1.1 and 1.2 show that constant-factor approximation is NP-hard and, under ETH, requires $2^{k^{\Omega(1)}}$ time. The paper then shows two ways around the barrier. For a constant number of groups and accuracy $\varepsilon$, a dimension-reduced polynomial-system search decides feasibility of each candidate loss $\alpha$ and returns a $(1+\varepsilon)$-approximation in $2^{\mathrm{poly}(k)}$ time (Theorem 1.3). For full polynomial time, Algorithm 3 embeds the max-of-Frobenius objective into an entrywise $L_p$ objective via Dvoretzky's Theorem, sketches it with column sampling and Lewis-weight row sampling, and solves the resulting regression by the closed form $\tilde V=(TGAHS)^\dagger(TGA)$; Theorem 1.4 guarantees a rank-$t$ output with $t=O(k(\log\log k)(\log^2 d))$ and worst-group error at most $\ell^c 2^{1/c} O(k(\log\log k)(\log d))$ times optimal. Theorem 1.5 extends the same machinery to fair column subset selection, returning $O(k\log k)$ columns with the same approximation factor in polynomial time.

Load-bearing premise

The bicriteria guarantee rests on the assumption that the least-squares solution $(TGAHS)^\dagger(TGA)H$ also minimizes the $(p,2)$-norm objective $\min_X\|TGAHSX-TGAH\|_{(p,2)}$, and the polynomial-system algorithm separately assumes that a single affine embedding preserves the loss simultaneously for every rank-$k$ matrix $V$; if either fails, the stated approximation factors are not secured.

Editorial extensions

If this is right

  • Constant-factor fair low-rank approximation cannot be solved in polynomial time unless P=NP, and under ETH needs $2^{k^{\Omega(1)}}$ time; this separates the fair objective from standard low-rank approximation, which has polynomial-time constant-factor algorithms.
  • For a fixed number of groups and fixed accuracy, the $(1+\varepsilon)$-approximation runs in $2^{\mathrm{poly}(k)}\cdot\mathrm{poly}(n)$ time, so datasets with very large $n$ but modest $k$ become tractable where the naive $n^{\mathrm{poly}(k)}$ bound is not.
  • The polynomial-time bicriteria algorithm returns a rank-$t$ subspace with $t=O(k(\log\log k)(\log^2 d))$ whose worst-group error is within $\ell^c 2^{1/c}O(k(\log\log k)(\log d))$ of the optimal rank-$k$ fair subspace, so a modest rank increase buys polynomial runtime.
  • Fair column subset selection inherits the same trade-off: selecting $O(k\log k)$ columns achieves an $O(k(\log\log k)(\log d))$ worst-group approximation in polynomial time, preserving interpretability of the chosen features.
  • Experiments on the credit-card dataset show the bicriteria fair solution can beat the standard SVD baseline on the fair objective even when both use the same rank, so the theoretical trade-off can also be favorable in practice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial: because the bicriteria factor grows like $\ell^c$, the polynomial-time algorithm is likely practical mainly when the number of groups is small; replacing that $\ell$-dependence with a polylogarithmic one is a natural open target.
  • Editorial: the proof's step that identifies the Frobenius minimizer of the sketched regression with the $(p,2)$-norm minimizer is directly testable on small synthetic matrices; if it fails, substituting an iterative $p$-norm regression solver in Algorithm 3 is the natural repair.
  • Editorial: the sketch pipeline—affine embedding, Dvoretzky embedding, and Lewis-weight sampling—is composable, so streaming and distributed versions of the fair algorithms are plausible extensions that the paper lists but does not develop.
  • Editorial: because the hardness reduction embeds Subspace(k,∞) exactly, any fairness objective that contains max-distance-to-subspace as a special case will inherit the same exponential lower bound, suggesting the dichotomy is structural rather than specific to Frobenius loss.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies socially fair low-rank approximation and socially fair column subset selection, where the objective is the worst-case reconstruction loss over ℓ subpopulations. It claims (i) NP-hardness and an ETH-based lower bound for constant-factor approximation (Theorems 1.1 and 1.2), (ii) a (1+ε)-approximation algorithm with runtime 1/ε · poly(n) · (2ℓ)^{poly(ℓ,k,1/ε)} (Theorem 1.3), (iii) a polynomial-time bicriteria approximation for fair low-rank approximation with rank t = O(k(log log k)(log^2 d)) and approximation factor ℓ^c · 2^{1/c} · O(k(log log k)(log d)) (Theorem 1.4), and (iv) a similar bicriteria guarantee for fair column subset selection (Theorem 1.5). The hardness reductions are straightforward embeddings of the Subspace(k,∞) problem. The main positive theorems, however, rest on a proof of Lemma 2.13 that compares the output's cost to itself rather than to the optimum, and on a feasibility check in Section 2.2 whose all-candidate-V distortion is not established by the cited affine embedding lemma.

Significance. If all theorems were correct, the paper would be a meaningful contribution to fair numerical linear algebra: the hardness dichotomy and the FPT-like runtime for constant ℓ would be new, and the bicriteria rank-approximation trade-off is a natural and potentially useful target. The hardness reductions are simple and conceptually correct modulo indexing typos. The paper also provides reproducible code and proof-of-concept experiments, which is a strength. However, the central positive claim, Theorem 1.4, is not established as written because Lemma 2.13 is tautological, and the error propagates to Theorem 1.5 and Lemma 3.2. The (1+ε)-approximation theorem also depends on a feasibility argument that is not justified by the cited embedding lemma. The significance of the positive results is therefore, at present, not assessable.

major comments (3)
  1. [Section 2.3, Lemma 2.13 and Theorem 1.4] The lemma as stated is tautological. Its right-hand side is max_i ||A(i)(eV)†eV − A(i)||_F, i.e., the cost of the very output it is supposed to bound; since the multiplicative factor is at least 1, the inequality carries no information. In the proof, the last inequality takes (Σ_i ||A(i)(V*)†V* − A(i)||_F^p)^{1/p} and bounds it by 2^{1/c} max_i ||A(i)(eV)†eV − A(i)||_F, using the output's own max loss rather than OPT = min_{V∈R^{k×d}} max_i ||A(i)V†V − A(i)||_F. No step of the chain compares the output cost to OPT, so Theorem 1.4 is not established. Since Lemma 3.2 and Theorem 1.5 invoke Theorem 1.4, the fair column subset selection guarantee is likewise unsupported.
  2. [Section 2.2, Lemma 2.8 and Corollary 2.9] The feasibility test requires an affine embedding S that preserves ||X(i)VS − A(i)S||_F relative to ||X(i)V − A(i)||_F for all regression matrices X(i) and all candidate matrices V simultaneously. Lemma 2.7 (Lemma 11 of [CEM+15]) only provides an affine embedding for a fixed matrix and a fixed vector, and Lemma 2.8 only analyzes the fixed optimal V. The polynomial system solver in Algorithm 1 may return arbitrary Y, W, R(i) satisfying the algebraic constraints; nothing shows that such a solution corresponds to Y = VS for the optimal V or that the output V = (A(1)SWR(1))†A(1) satisfies the claimed cost bound for every group. Thus Corollary 2.9, which is the correctness argument for Algorithm 2 and Theorem 1.3, does not follow.
  3. [Section 2.3, use of Dvoretzky's Theorem] The proof asserts that Theorem 2.11 yields matrices G and H such that (1−ε)||GMH||_p ≤ ||M||_F ≤ (1+ε)||GMH||_p for all matrices M. Theorem 2.11, as stated, is a Dvoretzky embedding for vectors in R^n using a single Gaussian matrix G; it does not by itself imply a two-sided Frobenius-to-entrywise-ℓ_p embedding for all M through the two-factor product GMH. This distortion is used repeatedly in Lemma 2.13, so even a repaired comparison to OPT would require an additional argument at this point.
minor comments (4)
  1. [Section 2.1, Theorems 1.1 and 1.2] The proof of Theorem 1.1 states 'we set ℓ = k = n−1 and A(i) = v(i) for all i∈[n]'; since ℓ = n−1, the index set should be [ℓ] (or ℓ should be n). Similarly, Theorem 1.2 sets ℓ = k−1 but uses i∈[k]. These indexing typos should be corrected.
  2. [Algorithm 3, Step 2] The line 'Let S ∈ R^{n′×t}, Z ∈ R^{t×d′} be the output of Theorem 2.12 on input GAH' has inconsistent dimensions. When Theorem 2.12 is applied to an n′×d′ matrix, it returns a column-sampling matrix in R^{d′×t}; the stated S ∈ R^{n′×t} does not match the theorem.
  3. [Lemma 2.13, final constant] For p = c log ℓ, one has ℓ^{1/p} = e^{1/c}, not 2^{1/c}; the constants in the final displayed bound should be reconciled.
  4. [Section 4.1, results discussion] The sentence 'most ratios in are less than 1' is missing the figure reference; it should refer to Figure 1b. In addition, the experimental section does not state how the parameters of Theorem 2.11 were chosen for the reported runs.

Circularity Check

1 steps flagged · score 6.0 of 10

Lemma 2.13 bounds the algorithm's cost by its own cost, so Theorem 1.4's comparison to OPT is never established.

  1. self definitional [Section 2.3, Lemma 2.13 (statement and proof), used to derive Theorem 1.4]
    "Lemma 2.13. Let eV be the output of Algorithm 3. Then with probability at least 9/10, max_{i∈[ℓ]} ∥A(i)( eV)† eV − A(i)∥_F is at most ℓ^c · 2^{1/c} · O(k(log log k)(log d)) max_{i∈[ℓ]} ∥A(i)( eV)† eV − A(i)∥_F. ... For p = c log ℓ with c < 1, we have ( Σ_{i∈[ℓ]} ∥A(i)(V∗)†V∗ − A(i)∥_F^p )^{1/p} ≤ 2^{1/c} max_{i∈[ℓ]} ∥A(i)( eV)† eV − A(i)∥_F."

    The lemma's RHS is the algorithm's own cost q = max_i ∥A(i)(eV)†eV − A(i)∥_F, so the statement is q ≤ C q, which is true for any output with C ≥ 1. The proof's final inequality bounds the term involving the fair optimum V* by 2^{1/c} q instead of by 2^{1/c} OPT, where OPT = min_V max_i ∥A(i)V†V − A(i)∥_F. Since V* is the fair optimizer, the V* term is at most ℓ^{1/p} OPT; replacing OPT with q is exactly the missing comparison needed for Theorem 1.4. The proof therefore never shows q ≤ C' OPT; the chain upper-bounds q by itself. Theorem 1.4, stated as an immediate consequence of Lemma 2.13, asserts a bound against OPT and is not derivable from the lemma as written.

full rationale

The only identifiable circular step is in Section 2.3. Lemma 2.13 as printed asserts q ≤ ℓ^c 2^{1/c} O(k(log log k)(log d)) q, with q = max_i ∥A(i)(eV)†eV − A(i)∥_F, i.e., it compares the output to itself. Its proof introduces the fair optimum V* and then, at the last inequality, bounds the sum over V* by 2^{1/c} q rather than by 2^{1/c} OPT. Since the chain begins by upper-bounding q, the whole proof is q ≤ C q; it never shows q ≤ C' OPT. Theorem 1.4, which is stated to follow from Lemma 2.13, has OPT on the RHS and therefore does not follow from the lemma as written. This is a localized but load-bearing circularity in the proof of the main polynomial-time bicriteria result. The reader's additional premise that (TGAHS)†(TGAH) is not the (p,2)-minimizer is not sound and is not counted as circularity: the columns of the regression variable decouple, so the Frobenius minimizer also minimizes the (p,2) objective. The lower-bound results (Theorems 1.1 and 1.2) and the (1+ε)-approximation Theorem 1.3 are grounded in external hardness results and in an affine-embedding/polynomial-system argument, respectively; no circularity appears there. The use of [WY23a, Theorem 2.12] is a self-citation with one overlapping author, but it is a separate published black-box theorem with stated assumptions that do not include the target result, so under the review rules it is real independent support rather than circularity. Score 6: one central claimed guarantee — the polynomial-time bicriteria approximation — reduces in the written proof to a statement about its own cost, while the hardness results and the other algorithmic claims retain independent content.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central results rest on standard complexity assumptions, known subspace-approximation hardness, and several unproven or misstated technical premises introduced for this paper's proofs (all-V affine embedding, F-minimizer as (p,2)-minimizer). No new physical or mathematical entities are postulated.

free parameters (2)
  • trade-off parameter c
    User-chosen parameter in Theorems 1.4/1.5 and Algorithms 3/4 controlling the approximation factor ℓ^c · 2^{1/c} and the bicriteria rank/column count; not fitted to data.
  • Dvoretzky embedding dimensions (rows of G, columns of H) = not specified
    The proofs invoke Theorem 2.11 but do not state the concrete dimensions n' and d' needed for the stated embedding. In experiments G is 30 x n and H is d x 30 (Section 4.1), but the theoretical guarantee does not fix these dimensions.
assumptions (5)
  • domain assumption P != NP
    Theorems 1.1 hardness relies on NP-hardness of Subspace(n-1, inf) from [BGK00, DTV11].
  • domain assumption Exponential Time Hypothesis (Hypothesis 2.2)
    Theorem 1.2 lower bound uses ETH for 3-SAT.
  • ad hoc to paper The affine embedding S distorts fair low-rank losses for all rank-k matrices V simultaneously
    Section 2.2 requires (1-eps)||A(i)V†V - A(i)|| <= ||A(i)V†VS - A(i)S|| <= (1+eps)||...|| for all rank-k V; Lemma 2.7 only provides this for a fixed V.
  • ad hoc to paper The Frobenius-norm minimizer (TGAHS)†(TGA)H also minimizes the (p,2)-norm regression objective
    Assumed in Lemma 2.13 proof; false in general, needs an extra dimension-dependent distortion factor.
  • domain assumption Dvoretzky's theorem embeds the Frobenius norm into the entrywise Lp norm via GMH for all M simultaneously
    Theorem 2.11 from [PVZ17] is invoked; dimensions must be large enough, but the concrete required sizes are not specified in the algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Socially Fair Low-Rank Approximation and Column Subset Selection." pith.science (2026). https://pith.science/paper/XL5YA52R

@misc{pith2026241206063,
  author       = {Pith},
  title        = {Pith review of: On Socially Fair Low-Rank Approximation and Column Subset Selection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XL5YA52R}},
  note         = {Machine review of arXiv:2412.06063}
}
abstract

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)}$ time rather than the na\"{i}ve $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 run in polynomial time.

Figures

Figures reproduced from arXiv: 2412.06063 by the authors.

Figure 1
Figure 1. Empirical evaluations on the Default Credit dataset. [PITH_FULL_IMAGE:figures/full_fig_p023_1.png] view at source ↗
Figure 2
Figure 2. Ratio of the cost of our bicriteria algorithm to the cost of the standard low-rank approximation [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

86 extracted references · 72 canonical work pages

  1. [1]

    Abernethy, Pranjal Awasthi, Matth \" a us Kleindessner, Jamie Morgenstern, Chris Russell, and Jie Zhang

    Jacob D. Abernethy, Pranjal Awasthi, Matth \" a us Kleindessner, Jamie Morgenstern, Chris Russell, and Jie Zhang. Active sampling for min-max fairness. In International Conference on Machine Learning, ICML , pages 53--65, 2022

    2022

  2. [2]

    Fair clustering via equitable group representations

    Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency , pages 504--514, 2021

    2021

  3. [3]

    Fair regression: Quantitative definitions and reduction-based algorithms

    Alekh Agarwal, Miroslav Dud \' k, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and reduction-based algorithms. In International Conference on Machine Learning , pages 120--129. PMLR, 2019

    2019

  4. [4]

    Fair hierarchical clustering

    Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang. Fair hierarchical clustering. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS , 2020

    2020

  5. [5]

    Fair and fast k-center clustering for data summarization

    Haris Angelidakis, Adam Kurpisz, Leon Sering, and Rico Zenklusen. Fair and fast k-center clustering for data summarization. In International Conference on Machine Learning, ICML , pages 669--702, 2022

    2022

  6. [6]

    Fair algorithms for clustering

    Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems , 32, 2019

    2019

  7. [7]

    Woodruff, and Samson Zhou

    Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 517--528, 2020

    work page 2020

  8. [8]

    Gender shades: Intersectional accuracy disparities in commercial gender classification

    Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on Fairness, Accountability and Transparency, FAT , volume 81 of Proceedings of Machine Learning Research , pages 77--91, 2018

    work page 2018

Show all 86 references
  1. [9]

    Inapproximability of some geometric and quadratic optimization problems

    Andreas Brieden, Peter Gritzmann, and Victor Klee. Inapproximability of some geometric and quadratic optimization problems. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems , pages 96--115, 2000

    2000

  2. [10]

    On the cost of essentially fair clusterings

    Ioana O Bercea, Martin Gro , Samir Khuller, Aounon Kumar, Clemens R \"o sner, Daniel R Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. arXiv preprint arXiv:1811.10319 , 2018

    2018 arXiv

  3. [11]

    A convex framework for fair regression

    Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. A convex framework for fair regression. arXiv preprint arXiv:1706.02409 , 2017

    2017 arXiv

  4. [12]

    Fairness in criminal justice risk assessments: The state of the art

    Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research , 50(1):3--44, 2021

    2021

  5. [13]

    Scalable fair clustering

    Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In International Conference on Machine Learning , pages 405--413. PMLR, 2019

    2019

  6. [14]

    On the combinatorial and algebraic complexity of quantifier elimination

    Saugata Basu, Richard Pollack, and Marie - Fran c oise Roy. On the combinatorial and algebraic complexity of quantifier elimination. J. ACM , 43(6):1002--1045, 1996

    1996

  7. [15]

    Big data's disparate impact

    Solon Barocas and Andrew D Selbst. Big data's disparate impact. California law review , pages 671--732, 2016

    2016

  8. [16]

    Woodruff, and Qiuyi (Richard) Zhang

    Frank Ban, David P. Woodruff, and Qiuyi (Richard) Zhang. Regularized weighted low rank approximation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 4061--4071, 2019

    2019

  9. [17]

    Woodruff

    Graham Cormode, Charlie Dickens, and David P. Woodruff. Leveraging well-conditioned bases: Streaming and distributed summaries in minkowski p -norms. In Proceedings of the 35th International Conference on Machine Learning, ICML , Proceedings of Machine Learning Research, pages...

    2018

  10. [18]

    Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu

    Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k -means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC , pages 163--172, 2015

    2015

  11. [19]

    Woodruff

    Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P. Woodruff. Algorithms for l_p low-rank approximation. In Proceedings of the 34th International Conference on Machine Learning, ICML , pages 806--814, 2017

    2017

  12. [20]

    Fair prediction with disparate impact: A study of bias in recidivism prediction instruments

    Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data , 5(2):153--163, 2017

    2017

  13. [21]

    Fair clustering through fairlets

    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems , pages 5029--5037, 2017

    2017

  14. [22]

    Solving linear programs in the current matrix multiplication time

    Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC) , 2019

    2019

  15. [23]

    Cohen, Cameron Musco, and Christopher Musco

    Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1758--1777, 2017

    2017

  16. [24]

    Approximating fair clustering with cascaded norm objectives

    Eden Chlamt \'a c , Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Proceedings of the 2022 annual ACM-SIAM symposium on discrete algorithms (SODA) , pages 2664--2683. SIAM, 2022

    2022

  17. [25]

    Cohen and Richard Peng

    Michael B. Cohen and Richard Peng. L_p row sampling by lewis weights. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC , pages 183--192, 2015

    2015

  18. [26]

    Active regression via linear-sample sparsification

    Xue Chen and Eric Price. Active regression via linear-sample sparsification. In Conference on Learning Theory, COLT , pages 663--695, 2019

    2019

  19. [27]

    Algorithmic decision making and the cost of fairness

    Sam Corbett - Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of fairness. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 797--806, 2017

    2017

  20. [28]

    Crawford

    Wenjing Chen, Shuo Xing, Samson Zhou, and Victoria G. Crawford. Fair submodular cover. CoRR , abs/2407.04804, 2024

    2024 arXiv

  21. [29]

    Mahoney, and S

    Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-based methods. In 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems ( APPROX ) and 10th International Worksh...

    2006

  22. [30]

    Mahoney, and S

    Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-row-based methods. In Algorithms - ESA 2006, 14th Annual European Symposium, Proceedings , pages 304--314, 2006

    2006

  23. [31]

    Fair representation clustering with several protected classes

    Zhen Dai, Yury Makarychev, and Ali Vakilian. Fair representation clustering with several protected classes. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency , pages 814--823, 2022

    2022

  24. [32]

    Amit Deshpande, Madhur Tulsiani, and Nisheeth K. Vishnoi. Algorithms and hardness for subspace approximation. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 482--496, 2011

    2011

  25. [33]

    Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John Dickerson

    Seyed A. Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John Dickerson. Probabilistic fair clustering. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS , 2020

    2020

  26. [34]

    The approximation of one matrix by another of lower rank

    Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika , 1(3):211--218, 1936

    1936

  27. [35]

    On the stochastic matrices associated with certain queuing processes

    Frederic G Foster. On the stochastic matrices associated with certain queuing processes. The Annals of Mathematical Statistics , 24(3):355--360, 1953

    1953

  28. [36]

    Tight FPT approximation for socially fair clustering

    Dishant Goyal and Ragesh Jaiswal. Tight FPT approximation for socially fair clustering. Information Processing Letters , 182:106383, 2023

    2023

  29. [37]

    Socially fair k -means clustering

    Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k -means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency , pages 438--448, 2021

    2021

  30. [38]

    Constant-factor approximation algorithms for socially fair k -clustering

    Mehrdad Ghadiri, Mohit Singh, and Santosh S Vempala. Constant-factor approximation algorithms for socially fair k -clustering. arXiv preprint arXiv:2206.11210 , 2022

    2022 arXiv

  31. [39]

    Solving SDP faster: A robust IPM framework and efficient implementation

    Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving SDP faster: A robust IPM framework and efficient implementation. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 233--244, 2022

    2022

  32. [40]

    Approximation algorithms for fair range clustering

    Sedjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian. Approximation algorithms for fair range clustering. In International Conference on Machine Learning , pages 13270--13284. PMLR, 2023

    2023

  33. [41]

    Equality of opportunity in supervised learning

    Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems , pages 3315--3323, 2016

    2016

  34. [42]

    On the complexity of k - SAT

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k - SAT . J. Comput. Syst. Sci. , 62(2):367--375, 2001

    2001

  35. [43]

    A faster interior point method for semidefinite programming

    Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In FOCS , 2020

    2020

  36. [44]

    Service in your neighborhood: Fairness in center location

    Christopher Jung, Sampath Kannan, and Neil Lutz. Service in your neighborhood: Fairness in center location. In Aaron Roth, editor, 1st Symposium on Foundations of Responsible Computing, FORC 2020 , pages 5:1--5:15, 2020

    2020

  37. [45]

    Mahankali, and David P

    Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, and David P. Woodruff. Streaming and distributed algorithms for robust column subset selection. In Proceedings of the 38th International Conference on Machine Learning, ICML , volume 139 of Proceedings of Machine Le...

    2021

  38. [46]

    Liu, and Aaron Sidford

    Arun Jambulapati, Yang P. Liu, and Aaron Sidford. Improved iteration complexities for overconstrained p-norm regression. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 529--542, 2022

    2022

  39. [47]

    An improved cutting plane method for convex optimization, convex-concave games, and its applications

    Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 944--953, 2020

    2020

  40. [48]

    Fair k -centers via maximum matching

    Matthew Jones, Huy Nguyen, and Thy Nguyen. Fair k -centers via maximum matching. In International conference on machine learning , pages 4940--4949. PMLR, 2020

    2020

  41. [49]

    Tsigaridas

    Gabriela Jeronimo, Daniel Perrucci, and Elias P. Tsigaridas. On the minimum of a polynomial function on a basic closed semialgebraic set and applications. SIAM J. Optim. , 23(1):241--255, 2013

    2013

  42. [50]

    A faster algorithm for solving general lps

    Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general lps. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 823--832, 2021

    2021

  43. [51]

    Fair k -center clustering for data summarization

    Matth \" a us Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k -center clustering for data summarization. In Proceedings of the 36th International Conference on Machine Learning, ICML , pages 3448--3457, 2019

    2019

  44. [52]

    Efficient fair pca for fair representation learning

    Matth \"a us Kleindessner, Michele Donini, Chris Russell, and Muhammad Bilal Zafar. Efficient fair pca for fair representation learning. In International Conference on Artificial Intelligence and Statistics , pages 5250--5270. PMLR, 2023

    2023

  45. [53]

    Human decisions and machine predictions

    Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. Human decisions and machine predictions. The quarterly journal of economics , 133(1):237--293, 2018

    2018

  46. [54]

    Matthew Kay, Cynthia Matuszek, and Sean A. Munson. Unequal representation and gender stereotypes in image search results for occupations. In Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, CHI , pages 3819--3828, 2015

    2015

  47. [55]

    Kleinberg, Sendhil Mullainathan, and Manish Raghavan

    Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In 8th Innovations in Theoretical Computer Science Conference, ITCS , pages 43:1--43:23, 2017

    2017

  48. [56]

    Woodruff

    Ravi Kumar, Rina Panigrahy, Ali Rahimi, and David P. Woodruff. Faster algorithms for binary matrix factorization. In Proceedings of the 36th International Conference on Machine Learning, ICML , pages 3551--3559, 2019

    2019

  49. [57]

    Faster algorithms for convex and combinatorial optimization, 2016

    Yin Tat Lee. Faster algorithms for convex and combinatorial optimization, 2016

    2016

  50. [58]

    Fast and efficient mmd-based fair pca via optimization over stiefel manifold, 2022

    Junghyun Lee, Gwangsu Kim, Mahbod Olfat, Mark Hasegawa-Johnson, and Chang D Yoo. Fast and efficient mmd-based fair pca via optimization over stiefel manifold, 2022

    2022

  51. [59]

    A faster cutting plane method and its implications for combinatorial and convex optimization

    Yin Tat Lee, Aaron Sidford, and Sam Chiu - wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS , pages 1049--1065, 2015

    2015

  52. [60]

    Row sampling for matrix algorithms via a non-commutative bernstein bound

    Malik Magdon - Ismail. Row sampling for matrix algorithms via a non-commutative bernstein bound. CoRR , abs/1008.0587, 2010

    2010 arXiv

  53. [61]

    Meyer, Cameron Musco, Christopher Musco, David P

    Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou. Fast regression for structured inputs. In The Tenth International Conference on Learning Representations, ICLR , 2022

    2022

  54. [62]

    Meyer, Cameron Musco, Christopher Musco, David P

    Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou. Near-linear sample complexity for L_p polynomial regression. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 3959--4025, 2023

    2023

  55. [63]

    Woodruff, and Taisuke Yasuda

    Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda. Active linear regression for L_p norms and beyond. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 744--753, 2022

    2022

  56. [64]

    Fair column subset selection

    Antonis Matakos, Bruno Ordozgoiti, and Suhas Thejaswi. Fair column subset selection. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 2189--2199, 2024

    2024

  57. [65]

    Individual fairness for k -clustering

    Sepideh Mahabadi and Ali Vakilian. Individual fairness for k -clustering. In Proceedings of the 37th International Conference on Machine Learning, ICML , pages 6586--6596, 2020

    2020

  58. [66]

    Approximation algorithms for socially fair clustering

    Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory , pages 3246--3264. PMLR, 2021

    2021

  59. [67]

    Better algorithms for individually fair k-clustering

    Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k-clustering. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS , pages 13340--13351, 2021

    2021

  60. [68]

    Fair range k-center

    Huy L \^e Nguyen, Thy Nguyen, and Matthew Jones. Fair range k-center. arXiv preprint arXiv:2207.11337 , 2022

    2022 arXiv

  61. [69]

    Convex formulations for fair principal component analysis, 2019

    Matt Olfat and Anil Aswani. Convex formulations for fair principal component analysis, 2019

    2019

  62. [70]

    L_1 regression with lewis weights subsampling

    Aditya Parulekar, Advait Parulekar, and Eric Price. L_1 regression with lewis weights subsampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 49:1--49:21, 2021

    2021

  63. [71]

    Random version of dvoretzky’s theorem in _p^n

    Grigoris Paouris, Petros Valettas, and Joel Zinn. Random version of dvoretzky’s theorem in _p^n . Stochastic Processes and their Applications , 127(10):3187--3227, 2017

    2017

  64. [72]

    On the computational complexity and geometry of the first-order theory of the reals

    James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of symbolic computation , 13(3):2...

    1992

  65. [73]

    On the computational complexity and geometry of the first-order theory of the reals

    James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part ii: The general decision problem. preliminaries for quantifier elimination. Journal of Symbolic Computation , 13(3):301--327, 1992

    1992

  66. [74]

    Privacy preserving clustering with constraints

    Clemens R \" o sner and Melanie Schmidt. Privacy preserving clustering with constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP , pages 96:1--96:14, 2018

    2018

  67. [75]

    Razenshteyn, Zhao Song, and David P

    Ilya P. Razenshteyn, Zhao Song, and David P. Woodruff. Weighted low rank approximations with provable guarantees. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC , pages 250--263, 2016

    2016

  68. [76]

    The price of fair pca: One extra dimension

    Samira Samadi, Uthaipon Tantipongpipat, Jamie H Morgenstern, Mohit Singh, and Santosh Vempala. The price of fair pca: One extra dimension. Advances in neural information processing systems , 31, 2018

    2018

  69. [77]

    Woodruff

    Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 802--813, 2018

    2018

  70. [78]

    Clustering with fair-center representation: Parameterized approximation algorithms and heuristics

    Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Michal Osadnik. Clustering with fair-center representation: Parameterized approximation algorithms and heuristics. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 1749--1759, 2022

    2022

  71. [79]

    Multi-criteria dimensionality reduction with applications to fairness

    Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh, Jamie H Morgenstern, and Santosh Vempala. Multi-criteria dimensionality reduction with applications to fairness. Advances in neural information processing systems , 32, 2019

    2019

  72. [80]

    Woodruff, and Samson Zhou

    Ameya Velingker, Maximilian V \" o tsch, David P. Woodruff, and Samson Zhou. Fast (1+ ) -approximation algorithms for binary matrix factorization. In International Conference on Machine Learning, ICML , pages 34952--34977, 2023

    2023

  73. [81]

    Improved approximation algorithms for individually fair clustering

    Ali Vakilian and Mustafa Yalciner. Improved approximation algorithms for individually fair clustering. In International conference on artificial intelligence and statistics , pages 8758--8779. PMLR, 2022

    2022

  74. [82]

    Woodruff

    David P. Woodruff. Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. , 10(1-2):1--157, 2014

    2014

  75. [83]

    Woodruff and Taisuke Yasuda

    David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC , pages 1802--1813, 2023

    2023

  76. [84]

    Woodruff and Taisuke Yasuda

    David P. Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 4622--4666, 2023

    2023

  77. [85]

    Default of Credit Card Clients

    I-Cheng Yeh. Default of Credit Card Clients . UCI Machine Learning Repository, 2016. DOI : https://doi.org/10.24432/C55S3H

    2016 doi

  78. [86]

    The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients

    I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications , 36(2):2473--2480, 2009

    2009

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.