# Discrepancy Minimization in Input-Sparsity Time

arXiv: https://arxiv.org/abs/2210.12468 · HTML: https://mlsanity.com/paper/2210.12468/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2022.

## Built on by (most cited first, 22 of 22)

- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (2023)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [A Unified Scheme of ResNet and Softmax](https://mlsanity.com/paper/2309.13482/) (2023)
- [Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights](https://mlsanity.com/paper/2310.12462/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression](https://mlsanity.com/paper/2311.15390/) (2023)
- [Solving Tensor Low Cycle Rank Approximation](https://mlsanity.com/paper/2304.06594/) (2023)
- [Fast and Efficient Matching Algorithm with Deadline Instances](https://mlsanity.com/paper/2305.08353/) (2023)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer](https://mlsanity.com/paper/2311.13624/) (2023)
- [Structured and Fast Optimization: The Kronecker SGD Algorithm](https://mlsanity.com/paper/2305.08001/) (2023)
- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method](https://mlsanity.com/paper/2408.11267/) (2024)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)

## Abstract (arXiv)

A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal's SDP algorithm for finding a coloring x ∈ -1, 1n that approximately minimizes the discrepancy disc(A, x) := | A x |∞ of a real-valued m × n matrix A. Larsen's algorithm runs in widetildeO(mn2) time compared to Bansal's widetildeO(mn4.5)-time algorithm, with a slightly weaker logarithmic approximation ratio in terms of the hereditary discrepancy of A [Bansal, FOCS 2010]. We present a combinatorial widetildeO(nnz(A) + n3)-time algorithm with the same approximation guarantee as Larsen's, optimal for tall matrices where m = poly(n). Using a more intricate analysis and fast matrix multiplication, we further achieve a runtime of widetildeO(nnz(A) + n2.53), breaking the cubic barrier for square matrices and surpassing the limitations of linear-programming approaches [Eldan and Singh, RS&A 2018]. Our algorithm relies on two key ideas: (i) a new sketching technique for finding a projection matrix with a short ℓ2-basis using implicit leverage-score sampling, and (ii) a data structure for efficiently implementing the iterative Edge-Walk partial-coloring algorithm [Lovett and Meka, SICOMP 2015], and using an alternative analysis to enable ''lazy'' batch updates with low-rank corrections. Our results nearly close the computational gap between real-valued and binary matrices, for which input-sparsity time coloring was recently obtained by [Jain, Sah and Sawhney, SODA 2023].