{"id":"7c86c315-c3c2-4ab5-acc4-1acfccb15a6a","arxiv_id":"2412.06063","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Fair low-rank approximation is NP-hard to approximate and requires exponential time under ETH; bicriteria algorithms achieve polynomial time with a rank and column count blow-up.","lead":"This paper studies versions of low-rank approximation and column subset selection that try to keep error low for every population group, not just on average. It shows constant-factor approximation is exponentially hard under standard hypotheses, then gives an exponential-time algorithm with much better dependence on dataset size and bicriteria polynomial-time algorithms.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.13 proves only cost(eV) <= constant * cost(eV), so the comparison to OPT needed for Theorem 1.4 is never established.","rationale":"The hardness results in Section 2.1 are conceptually fine. For the positive results, the bicriteria claim is the strongest and most consequential, and its proof is where the argument breaks. Re-tracing Lemma 2.13, the early steps are plausible if one accepts the Dvoretzky matrix embedding and the WY23a subset-selection theorem, but the final displayed inequality compares the output cost to the output cost, not to the optimal fair cost. This is not a minor typo in the theorem statement alone: as written, Lemma 2.13 is a tautology, so Theorem 1.4 is not established. I do not endorse one part of the reader's analysis: the claim that (TGAHS)^+(TGAH) is not optimal for the (p,2) objective is false, because the columns of the regression variable are independent and the (p,2) norm is a monotone function of per-column L2 norms; the Frobenius projection is also the (p,2) minimizer. The real defect is the vacuous final comparison. A repaired proof might replace the final RHS with OPT, and the surrounding chain may then go through, but that repair is absent from the submitted text. The empirical study is a useful proof-of-concept but cannot substitute for the missing guarantee. I therefore keep the reader's REJECT verdict.","tokens_in":28516,"tokens_out":15675,"duration_ms":160558,"concrete_test":"Re-derive the chain in Lemma 2.13 from the display after Theorem 2.12 through the final display, carrying OPT = min_{V in R^{k x d}} max_i ||A(i) V^+ V - A(i)||_F explicitly on the right-hand side. At the last inequality, check whether the proof supplies max_i ||A(i)(eV)^+ eV - A(i)||_F (current text) or max_i ||A(i)(V*)^+ V* - A(i)||_F; if the RHS is the output matrix eV, no comparison to OPT is present and Theorem 1.4 is unproved as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.3's Lemma 2.13 is the only proof of Theorem 1.4, but its statement bounds max_i ||A(i)(eV)^+ eV - A(i)||_F by a constant times max_i ||A(i)(eV)^+ eV - A(i)||_F, i.e., the algorithm's own cost. The proof introduces an optimal V* in the middle of the chain, applies Theorem 2.12 and Dvoretzky's Theorem, and then at the final step bounds (sum_i ||A(i)(V*)^+ V* - A(i)||_F^p)^{1/p} by 2^{1/c} max_i ||A(i)(eV)^+ eV - A(i)||_F instead of by 2^{1/c} OPT, where OPT = min_{V in R^{k x d}} max_i ||A(i) V^+ V - A(i)||_F. With that RHS the chain is a tautology; no inequality in the proof converts the output cost back to the optimal fair cost. The reader's additional claim that (TGAHS)^+(TGAH) fails to minimize the (p,2)-norm regression objective is not a sound objection: the columns of X decouple and the objective is a sum of increasing functions of column L2 norms, so the Frobenius minimizer also minimizes the (p,2) objective. The load-bearing gap is therefore the missing comparison to OPT, not the pseudoinverse step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":28815,"tokens_out":14798,"duration_ms":137722,"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":[{"comment":"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.","section":"Section 2.3, Lemma 2.13 and Theorem 1.4"},{"comment":"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.","section":"Section 2.2, Lemma 2.8 and Corollary 2.9"},{"comment":"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.","section":"Section 2.3, use of Dvoretzky's Theorem"}],"minor_comments":[{"comment":"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.","section":"Section 2.1, Theorems 1.1 and 1.2"},{"comment":"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.","section":"Algorithm 3, Step 2"},{"comment":"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.","section":"Lemma 2.13, final constant"},{"comment":"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.","section":"Section 4.1, results discussion"}],"recommendation":"reject","confidential_remarks":"The paper's main positive claims rest on a tautological lemma (Lemma 2.13) and on an unjustified all-candidate-V affine embedding assumption in the feasibility check. These are not local typos but load-bearing proof gaps. Even the corrected chain would need to confront the Dvoretzky embedding issue for the two-factor sketch GMH. I do not see a way to salvage Theorem 1.4 and the derived CSS theorem without a substantially rewritten proof, so I recommend rejection. The hardness results and the overall problem formulation are sound and may be of interest in a future revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read of 2412.06063. The hardness results (Theorems 1.1 and 1.2) are conceptually sound: the reduction from Subspace(k, inf) is direct, and modulo small indexing typos (ell vs n) they establish NP-hardness and an ETH lower bound for constant-factor fair low-rank approximation. That part deserves credit.\n\nThe positive side is where the paper runs into trouble. I confirm the stress-test note: Lemma 2.13 is indeed tautological as printed. The statement bounds the output's cost by a constant times the output's own cost, and the proof's last inequality compares the sum over the optimal V* to max_i over eV, not to OPT. The chain never converts the intermediate quantities back to the optimal fair cost. Without that comparison, Theorem 1.4 is unproven. The reader's separate objection about (TGAHS)^+(TGAH) not minimizing the (p,2) norm is not right, though: the columns of X decouple and the (p,2) objective is a sum of increasing functions of column L2 norms, so the Frobenius minimizer does minimize it. That step is fine; the gap is the missing comparison to OPT.\n\nThe other load-bearing issue is in Section 2.2. The algorithm needs a two-sided distortion bound that holds for every rank-k matrix V simultaneously, but the cited Lemma 2.7 is an affine embedding for a fixed matrix. The infeasibility direction of Corollary 2.9 requires the all-V property, and it's not there. This might be fixable with a different embedding or a union-bound argument, but as written it's a gap.\n\nSince Theorem 1.5 (column subset selection) inherits the bicriteria guarantee, that result is also on shaky ground. The experiments are a proof of concept, not a substitute for the missing proofs.\n\nOverall: the paper has the right questions and some good ideas, and the hardness part is solid, but the main algorithmic theorems don't hold as written. It's still worth a serious referee: the errors are concrete and possibly fixable, and the hardness results alone justify attention.\n\nMy recommendation: send it to peer review, with clear instructions to the authors about these two gaps. This is a conditional reject rather than a desk reject.\n\nBest,","headline":"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.","tokens_in":29370,"tokens_out":8955,"would_cite":true,"duration_ms":79895,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W20","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["socially fair low-rank approximation","fair column subset selection","bicriteria approximation","algorithmic fairness","exponential time hypothesis","randomized linear algebra","Lewis weight sampling"],"falsifier":"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.","tokens_in":28243,"feed_emoji":"⚖️","tokens_out":13617,"duration_ms":119607,"temperature":0.7,"pith_summary":"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.","feed_headline":"Constant-factor fair low-rank approximation is exponentially hard","feed_subtitle":"Bicriteria rank trade-offs put the worst-group error back in polynomial time.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the NP-hardness of approximating Subspace(n−1,∞), which the reduction in Theorem 1.1 embeds into fair low-rank approximation.","marker":"[BGK00]"},{"why":"Sharpens the same subspace-approximation hardness to a $2^{n^{\\Omega(1)}}$ lower bound under ETH, used for Theorem 1.2.","marker":"[DTV11]"},{"why":"States the exponential time hypothesis that drives the $2^{k^{\\Omega(1)}}$ lower bound.","marker":"[IP01]"},{"why":"Provides the affine embedding (Lemma 2.7) that reduces dimension before the polynomial-system feasibility check in Algorithm 1.","marker":"[CEM+15]"},{"why":"Gives the polynomial-system solver whose $(md)^{O(n)}$ runtime bounds Algorithm 2.","marker":"[Ren92a, Ren92b, BPR96]"},{"why":"Bounds the coefficient bit complexity, controlling the solver's dependence on the input size in Lemma 2.10.","marker":"[JPT13]"},{"why":"States the Dvoretzky embedding that converts the max-of-Frobenius objective into an entrywise $L_p$ objective for the bicriteria algorithm.","marker":"[PVZ17]"},{"why":"Provides the column-sampling bicriteria algorithm for $L_p$ low-rank approximation (Theorem 2.12) that produces the subspace $S$ and sets the rank $t$.","marker":"[WY23a]"},{"why":"Constructs Lewis-weight row sampling for $L_p$ subspace embeddings, used to form $T$ and reduce the row count in the bicriteria regression.","marker":"[CP15]"},{"why":"Justifies replacing each group's approximation by the projection $A^{(i)}V^\\dagger V$, the form used throughout the paper.","marker":"[EY36]"}],"fun_headline_variants":["Fair low-rank approximation: constant-factor is exponentially hard","Fair low-rank: exponential hardness, but bicriteria is polynomial","Socially fair low-rank: constant-factor hard, rank trade-off wins","Fair low-rank: exponential lower bound, but bicriteria approximation","Fair low-rank: constant-factor impossible, bicriteria polynomial"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fair low-rank approximation: constant-factor is exponentially hard","Fair low-rank: exponential hardness, but bicriteria is polynomial","Socially fair low-rank: constant-factor hard, rank trade-off wins","Fair low-rank: exponential lower bound, but bicriteria approximation","Fair low-rank: constant-factor impossible, bicriteria polynomial"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000737,"raw_usage":{"total_tokens":3337,"prompt_tokens":1036,"completion_tokens":2301,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":652,"completion_tokens_details":{"reasoning_tokens":2216}},"tokens_in":652,"tokens_out":2301,"duration_ms":17320,"temperature":1.0,"reasoning_tokens":2216,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:05:09.713644+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}