Discrepancy Minimization in Input-Sparsity Time
Authors: Yichuan Deng
Xiaoyu Li
Zhao Song
OMRI WEINSTEIN
Venue: ICML 2025 spotlightposter (2025)
Keywords: combinatorial optimization
algorithmic discrepancy theory
sketching
input-sparsity time
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We give the algorithm for discrepancy minimization which runs in input-sparsity time.

Abstract: A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal's SDP algorithm for finding a coloring $x \in \\{-1, 1\\}^n$ that approximately minimizes the discrepancy $\mathrm{disc}(A, x) := \\| A x \\|_{\infty}$ of a real-valued $m \times n$ matrix $A$. Larsen's algorithm runs in $\widetilde{O}(mn^2)$ time compared to Bansal's $\widetilde{O}(mn^{4.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 $\widetilde{O}(\mathrm{nnz}(A) + n^3)$-time algorithm with the same approximation guarantee as Larsen's, optimal for tall matrices where $m = \mathrm{poly}(n)$. Using a more intricate analysis and fast matrix multiplication, we further achieve a runtime of $\widetilde{O}(\mathrm{nnz}(A) + n^{2.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 $\ell_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].

Discrepancy Minimization in Input-Sparsity Time
Yichuan Deng'
Xiaoyu Li
Zhao Song? Omri Weinstein
Abstract
color elements of finite set-system St,..., S. C ......,n] with two colors (c.g., red and blue) to mini- mize the maximum imbalance in color distribution across all sets. It finds diverse applications in fields such as com- putational geometry (Matousek, 1999b; De Berg, 2000), probabilistic algorithms (Spencer, 1985; Chazelle, 2000), machine learning (Vapnik & Chervonenkis, 1971; Talagrand, 1995; Karnin & Liberty. 2019; Bechavod et al., 2022: Han et el., 2025), differential privacy (Muthukrishnan & Nikolov, 2012; Nikolov et al., 2013), and optimization (Beck & Fiala, 1981; Bansal, 2010; 2012; Nikolov, 2015).
A recent work by [Larsen, SODA 2023] in- troduced faster combinatorial alternative Bansal's SDP algorithm for finding coloring (-1, that approximately minimizes the discrepancy disc(A, x) := ||Ax|le oloo of real- valued m x n matrix A. Larsen's 's algorithm runs in (0mn)) time compared to Bansal's Ö Ommm433 time algorithm, with a slightly weaker logarith- mic approximation ratio terms of the heredi- tary discrepancy of A [Bansal, FOCS 2010]. We present combinatorial ((nz A) + n2² ) algorithm with the same approximation guaran- tee as Larsen's, s. optimal for tall matrices where m = (n)y Using a more intricate analysis and fast matrix multiplication, we further achieve runtime of O(uz((A) + n² 2,255,), breaking the cubic barrier for square matrices and surpassing the limitations of linear-programinn 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 ba-basis using implicit leverage-score sam- pling, and (ii) data structure for efficiently imple- menting the iterative Edge-Walk partial partial-coloring algorithm [Lovett and Meka, SICOMP 2015], and using an alternative analysis to enable "lazy" batch updates with low-rank corrections. Our re- sults 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].
Definition 1.1 (Discrepancy). The discrepancy of real matrix A E Bmxx with respect to "coloring" vector x E [113" is defined as
(iso(A,x) = || max ((xx)))- JE(m)
The discrepancy of a real matrix E Rm is defined as
disc(A) == min (isc(A,2)) =E(+1)"
This is a natural generalization of the classic combinatorial notion of discrepancy of set systems, corresponding bi-
nary matrices A {0, 1] mxx where rows represent (the indicator vector of) m sets
ground set of [n]] elements, and the goal is to find coloring x E {+1} which is as "balanced" as possible simultaneously on all sets.
Most of the history of this problem was focused on the ex- istential question of understanding the minimum possible discrepancy achievable for various classes of matrices. For general set systems of size (arbitrary trices A), the classic result of Spencer (1985) states that disc(A) < 6,/n, which is asymptotically better than ran- dom coloring (O( vn l). More recent works have fo- cused on restricted matrix families, such as sparse matri- ces (Banaszezyk, 1998; Beck & Fiala, 1981), showing that possible achieve the o( discrepancy in these re- stricted cases. For example, the monnimum-discrepaaae oring of k-sparse binary matrices (sparse set systems) turns out to have discrepancy at most O( ((vhi log n) (Banaszezyk, 1998).
binary
1. Introduction
Discrepancy theory is fundamental subject in combi- natorics and theoretical computer science, studying how
'The University of Washington University of New South Wales Universsity of California, Berkeley 'Columbia University. Corre- spondence to: Xiaoyu Li x7.xiaoyu.li gmail.com>, Zhao Song Emagic.linuxkdee @ com..
col-
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
All of these results, however, do not provide polynomial time algorithms since they are con-constructive-oo they only

---

Discrepancy Minimization in Input-Sparsity Time
argue about the existence of low-discrepancy colorings, which prevents their use in algorithmic applications that rely on low-discrepancy (partial) coloring, such bin- packing problems (RothvoB, 2013; Hoberg & Rothvoss, 2017).' Indeed, the question of efficiently finding a low- discrepancy coloring, i.c., computing (As) was less un- derstood until recently and more nuanced: Charikar et al. (2011) showed that is NP-hard to distinguish whether a matrix has disc(A) = or disc(A) 52( 32(v)), suggest- ing that (1) approximation is inevitable to achieve fast runtimes. The celebrated work of Bansal (2010) gave the first polynomial-timg time algorithm which achieves an additive ((yn) -pproxxiiiinn to the optimal coloring of general n X n matrices, matching Spencer's non-constructive result. Bansal's s algorithm has approximation guarantees in terms of the hereditary discrepancy (Lovász et al., 1986).
yields an O" (max(mm + n², (m + n)" time approxi- mate discrepancy algorithm via state-of-art (tall) LP solvers (Brand et al., 2020). This line of work, however, has funda- mental setback for achieving siput-sparsity time, which is a major open problem for (high-accuracy) I.P solvers (Bubeck et al., 2018). Sparse matrices are often the realistic case for discrepancy problems, and have been widely studied in this context as discussed earlier in the introduction. Another drawback of convex- coneex-optimization based algorithms is that they are far from being practical due to the complicated nature of fast LP solvers.
Interestingly, in the binary (set-system) case, these limita- tions have been very recently overcome in the breakthrough work of Jain et al. (2023), who gave an O + nnz( -t)m coloring algorithm for binary matrices A {-1, jmxn with near optimal (O(yn) log(m/n //n + 2))) discrepancy. While their approach, too, was based on convex optimiza- tion, their main observation was that an approximate LP solver, using first-order methods, in fact suffices for a log- arithmic approximation. Unfortunately, the input-sparsity running time of the algorithm in Jain et al. (2023) does not extend to real-valued matrices, as their LP is based on a "heavy-light" decomposition of the rows of binary matrices based on their support size. More precisely, generalizing the argument of Jain et al. (2023) to matrices with entries in range, say. [-R2, R2,, guarantees that a uniformly random vector would only have discrepancy Ö(poly (R) vTr) on the "heavy" rows, and this term would also govern the ap- proximation ratio achieved by their algorithm.
Definition 1.2 (Hereditary discrepancy). Given a matrix A E Rmxn, its hereditary discrepancy is defined
herdisc (A) == max disc(B),
BEA
where i the set of all matrices obtained from A by delet-
ing some columns from A.
Bansal (2010) gave an SDP-based algorithm that finds a col- oring 5 satisfying disc(A, ž) (log(mmn) -herdisc(AA)) for any real matrix A, in time bm assuming state-of- the-art SDP solvers (Jiang et al., 2020b; Huang et al., 2022b). In other words, if all submatrices of A have low-discrepancy colorings, then it is in fact possible (yet still quite expensive) to find an almost-matching matching overall coloring.
By contrast, a concurrent result of Larsen (2023) gave a purely combinatorial (randomized) algorithm, which not as fast, but handles general real matrices and makes a step toward practical coloring algorithms. Larsen's 's algorithm improves Bansal's SDP from 0mm 4.5) to O(mn² + n²) time, at the price of a slightly weaker approximation guar- antee: For any A E Rmxx, Larsen (2023) finds a coloring T E (-1, +1}" such that disc A, T) = O (herdisc(A)) log log 1.5 m). Recent work by Jambulapati et al. (2024) introduced a new framework for efficient computing of the discrepancy, with which they successfully recovered Spencer's result in time ((nn((A) log" (n)) for matrix A with entries restricted within 1.
Building on Bansal's work. Lovett & Meka (2015) de- signed a simpler algorithm for set-systems (binary matri- ces A). running in (((n+m)))))))))) + m)) time. The main new idea of their algorithm, which is also central to our work, was subroutine for repeatedly finding a partial-coloring via mandom-walks (a.k.a EDGE- WALK), which in every iter- ation "rounds" constant-fractin of the coordinates of a fractional-coloring to an integral one in {-1, 1} (more on this in the next section). Followup works by Rothvoss (2017) and Eldan & Singh (2018) extended these ideas to the real-valued case, and developed faster convex optimiza- tion frameworks for obtaining diw-eiscryyancy coloring, the latter requiring Ologn) linear programs instead of semidefinite program (Bansal, 2010), assuming value or- acle to herdisc A).2 In this model, Eldan & Singh (2018)
The recent exciting developments naturally raise the follow- ing question:
'If we don't 't have polynomial constructive algorithm, then can't approximate solution for bin packing in polynomial. This is common in integer programming where we first relax it to linear programming and then round it back to an integer solution.
Is it possible to achieve input-paarsity time for discrepancy minimization with general (real-valued) matrices?
'Eldan & Singh (2018)'s LP requires an upper-bound estimate on herdisc(A) for each of the Ollog n) sequential LPs, hence standard aooonential-ueesiing seems too expensive: the number of possible "branches" is > vlog
In fact, this was one of the main open questions raised in 2018 workshop on Discrepancy Theory and Integer Pro- gramming (Dadush, 2018).
2

---

Discrepancy Minimization in Input-Sparsity Time
Table 1. Progress on approximate bnscrepancy-miiimiaaiiiii algorithms of real-valued m x matrices (m 2 n). For simplicity, we ignore n (1) and poly (log n) factors in the table. "(Eldan & Singh, 2018)** refers to a (black-bog) combination of our Theorem 1.5 with (Eldan Singh. 2018) and using state-of-art LP solvers for square and tall matrices (Lee & Sidford, 2014; Brand et al., 2020; Jiang et al., 2021).
References
Methods
Running Time
Bansal (2010)
SDP (Jiang et al., 2020c; Huang et al., 2022b)
mn.15
Eldan & Singh (2018)* 8)**
(Step I: Theorem 1.5) + (Step 2: LP (Jiang et al., 2021))
m + 2+11/18
Eldan & Singh (2018)*
(Step I: Theorem 1.5) (Step 2: LP (Brand et al., 2020))
mn nd
Eldan & Singh (2018)*
(Step I: Theorem 1.5) + (Step 2: LP (Lee & Sidford, 2014))
nnz (A) /n + n 2.5
Larsen (2023)
Combinatorial
mn² 2 + +n²
Ours (Theorem 1.3)
Combinatorial
nnz (A) + n2
Ours (Theorem 1.3)
(Step I: Theorem 1.5) + (Step 2: Lemma E.1
nnz [A) + n2. 2.53
1.1. Our Results
solvers (Cohen et al., 2019; Jiang et al., 2021), dynamic attention (Brand et al., 2024) and weight pruning (Li et al., 2024) in large language models.
We answer this question in the affirmative. To this end, we develop an algorithm that achieves a near-optimal runtime for tall matrices with for square matrices, while maintaining the same approxima- tion guarantees as Larsen's 's algorithm, up to constant factors. We state our main result in the following theorem.
poly(n) and subcubic runtime
A central technical component of Theorem 1.3 is the follow- ing theorem, which allows us to quickly find a "hereditary projection" matrix (i.e., a subspace such that the projection of a constant fraction of the rows of its orthogonal com- plement has small f--norm), and is of independent interest in randomized linear algebra. We state it follows.
Theorem 1.3 (Main result, informal version of Theorem D.1 and Theorem D.2). For any parameter a E [0, 1], there is a randomized algorithm that, given real matrix Rmxx,
Theorem 1.5 (Fast hereditary projection, informal version of Theorem C.2 and Theorem C.3). Let A E mm with m 2 n, and let d = n/4. There is a randomized algorithm that outputs d X n matrix V such that with probability 6, the followings hold simultaneously:
finds a coloring E +11 such that
disc A, x)- Oherdisc(AA) llog n. log" 1.5 m).
Moreover, it runs in time
Ö(nz((A) + n + n2
n (1(1))a)))))
* For all 1 E [d] we have I|V1,=l2 = 1,
It holds that
Here, w(a, b, c) denotes the time for multiplying an n x n matrix with an n' x nº matrix, and w w11, 1, 1) denotes the exponent of fast matrix multiplication (FMM).
max |[ - VV);-- = O(herdisc(A) log(m/n)) jE[m]
Remark 1.4. With the current value of 2.371, accord- ing to Table I in Alman et al. (2025), we choose the parame- ter a 2 0.53 to balance the terms 2+o and n (111,a))))) Consequently, the running time in Theorem 1.3 simplifies to (A) + n2.53).. Without FMM, our algorithm runs in ((nz((A) + n²) time and is purely combinatorial.
where Vi,, denotes the 1-th row of V for any I E [d].
Moreover, it runs in time Ö(nz((A) no),, where the Ö- notation hides a log(m/ (0) factor.
Theorem 1.5 directly improves Theorem 3 in Larsen (2023) which runs in (mm?² time without using FMM, and in (mm-~1) time using FMM. In either case, Larsen's 's algo- rithm pays at least mn- time, even when A is sparse (see more discussion Section 2.. Theorem 1.5 is in some sense best possible: Reading the input matrix A requires ((nz (A)) time, and explicitly computing the projection matrix P VTV V in Theorem 1.5 requires n time. We note that, in the case of binary matrices, the projection-free algorithm of Jain et al. (2023) avoids this bottleneck (and hence the n term), but for real-valued matrices, all known discrepancy algorithms involve projections (Bansal, 2010; Lovett & Meka, 2015; Larsen, 2023; Rothvoss, 2017).
Let a denote the dual exponent of matrix multiplication, i.c.,
2 = (1, 1, a). and let a E [0, 1] be the tunable parameter Theorem 1.3. Currently, a Rs 0.32 (Williams et al., 2024). Note that the running time of our algorithm (when using FMM) has a tradeoff between the additive terms n+a and n [1+a(,,aa)aa, so it is never better than 2.5 as it is never beneficial to set a < 1/2. This tradeoff also means that our runtime is barely sensitive to future improvements in the value of the dual exponent (even a 2 1 would improve the exponent of the additive term by merely 0.03). Curiously, a similar phenomenon occurs in recent FMM-based LP
3

---

Discrepancy Minimization in Input-Sparsity Time
1.2. Related Work
such as Spielman & Srivastava (2011); Batson al. (2012); Zhang (2022); Song et al. (2022b).
Algorithmic discrepancy theory Constructive discrep- ancy theory has become a pivotal area of research, fo- cusing on efficiently finding low-discrepancy solutions. Bansal's seminal work introduced a semidefiitte program- ming (SDP)-based algorithm that achieves additive ((vn) discrepancy (Bansal, 2010), matching the nonconstructive bounds but incurring a significant computational cost of Om. Subsequent contributions, such as Lovett & Meka (2015) and Eldan & Singh (2018), developed faster al- gorithms leveraging random walks and convex optimization techniques, respectively. Recent advances include Larsen's s combinatorial approach (Larsen, 2023), which attains a run- time of 0(m2²+ and the near-input-sparsity algorithms for binary matrices proposed by Jain et al. (2023). Fur- thermore.Jambulapati et al. (2024) introduced an efficient framework for computing discrepancy, recovering Spencer's result in ((nz(A)) 1og"(n) (n)) time for matrices A with en- tries bounded by 1. These innovations have substantially narrowed the computational gap between theoretical results and practical applications, advancing the field's capabilities within polynomial time. For further details, we refer readers to related works (Cohen, 2016b; Bansal et al., 2018; 2019; Dadush et al., 80 Alweiss et al., 2021; Bansal et al., 2020; 2022; Pesenti & Vladu, 2023; Jambulapati al., 2024). Most recently, Han et al. (2025) uses the discrepancy theory to approximate the attention computation in the streaming model.
2. Technical Overview
In this section, we give the overview of the techniques used to prove the main results, and the formal proofs are in Ap- pendix. In Section 2.1, we first give an overview and discuss the barriers of Larsen's 's algorithm. In Section 2.2, we intro- duce our techniques used to improve the Larsen's algorithm and overcome the barriers.
2.1. Overview and Barriers of Larsen's Algorithm
Larsen's algorithm (Larsen, 2023) is clever re- implementation of the iterated purtial-coloring subroutine of Lovett & Mcka (2015): In each iteration, with constant probability, this subroutine "rounds" at least half of the coordinates of a fractional coloring x E R to {-1, As in Lovett & Meka (2015), this is done by performing random-walk in the orthogonal complement subspace V1 spanned by set of rows from A (a.k.a FEdge-Walk' (Lovett & Meka, 2015)). The key idea in Larsen (2023) lies in a clever choice of V: Using connection between the eigenvalues of A A and herdisc(A) (A) (Larsen, 2017), Larsen shows that there is a subspace V spanned by S n rows of A, so that the projection of onto the complement V1 has small Eg norm, i.e., every row of A(I VTV) V) has norm less than O(herdisc(A) (A) log(m/n)). Larsen shows that comput- ing this projection operator (henceforth B B) can be done in Omm²) time combinatorially, or in Tintt (m, n, n) Omm*-) ') time" using FMM.
Sketching and leverage-score sampling Sketching is a versatile technique employed across numerous fundamental problems, including linear programming (Jiang al., 2021; Brand al., 2020; Song& & Yu, 2021; Liu et al., 2023), em- pirical risk minimization (Lee et al., 2019; Qin et al., 2023; Gu et al., 2025), and semidefinite programming (Jiang et al., 2020a; Huang et al., 2022a; Song et al., 2023b). It is partic- ularly prominent in randomized linear algebra, where it has been applied to a wide range of tasks (Clarkson & Woodruff, 2013; Nelson & Nguyên, 2013; Razenshteyn et al., 2016; Boutsidis et al., 2016; Song al., 2017; Xiao et al., 2018; Song et al., 2019b; Lee et al., 2019; Jiang et al., 2021; Song & Yu, 2021; Brand et al., 2021; Song et al., 2022a; Hu et al., 2022; Gu & Song, 2022). Sketching frequently serves as an effective tool for oblivious dimension reduction (Clarkson & Woodruff, 2013; Nelson & Nguyên, 2013). The use of sampling matrices to enhance computational efficiency is a well-established approach in numerical linear algebra (see Clarkson & Woodruff (2013); Razenshteyn et al. (2016); Boutsidis et al. (2016); Song et al. (2017); Cohen et al. (2019); Song et al. (2019b); Brand et al. (2020); Li et al. (2023); Gao et al. (2023); Deng et al. (2023)). In this pa- per, we employ leverage score sampling as a non-oblivious dimension reduction method, in line with previous works
The second part (PARTIALCOLORRING) of Larsen's al- gorithm is to repeatedly apply the above subroutine (PROJECTTOSMALLROWSS to implement the Edge-Wait Walk of (Lovett & Meka, 2015): Starting from a partial coloring x E R","" the algorithm first generates a subspace V/2 by calling the afformentioned PROJECTTOSMALL routine. Then it samples fresh random Gaussian vector g. in each iteration & E [N] = O(n), and projects it to obtain Ii = (I - V, Vi)g, The algorithm then decides whether or not to update V: More precisely, it maintains a vector uy, and gradually updates it to account for large entries of x + u,+1 that have reached 2 in absolute value (as in Lovett & Meka (2015)). When a coordinate i [n]] reaches this threshold at some iteration, the corresponding unit vec- tor e; is added to V, and V, is updated to V4+1- This update is necessary to ensure that in future iterations, no amount will be added to the i-th entry of u;- At the end of the loop, the algorithm outputs a vector x: new = x + uN+1 with property that for each row a; of A, the difference between (a,, 2) and
sub-
Trnaemm, (m, n, k) represents the time required to multiply an Tra x n matrix by an n x l matrix.
TTuat
4

---

Discrepancy Minimization in Input-Sparsity Time
(a,, ( is less than (herrdisc log": (m)). Since Vi constantly changing thoughout iterations, each iteration re- quires online Matrix- multiplication (1-V, Vo)ge. Hence, since there are N- (n)) iterations, O(mn² + n²) time is required to implement this part, even fast-matrix multiplication is allowed- - Indeed, the Online Matrix-Vector conjecture (Henzinger et al., 2015) postulates that mn² is essentially best possible for such online problem. Beating this barrier for the MARTIALCOLORRIG subroutine there- fore requires to somehow avoid this online problem, as we discuss in the next subsection.
throughout iterations), and cannot be batched via FMM (as- suming the OMv Conjecture (Henzinger et al., 2015)) We circumvent this step by slightly modifying the algorithm and analysis of Larsen, and using the fact that, while the subspace V2 is changing throughout iterations, the projected random Gaussian vectors 9t themselves are independent We show this enables to batch the projections and then perform low-rank corrections as needed the last step. We now turn to explain our technical approach and the main ideas for overcoming these computational bottlenecks.
2.2. Our Techniques
Below we summarize the computational bottlenecks in Larsen's 's algorithm, and then explain the new ideas required to overcome them and achieve the claimed overall runtime of Theorem 1.3.
A natural approach to accelerate the first part of the above algorithm is to use linear sketching techniques (Clarkson & Woodruff, 2013) as they enable working with much smaller matrices in the aforementioned steps. However, sketching techniques naturally introduce (spectral) error to the algo- rithm, which is exacerbated iterative algorithms. Indeed, nontrivial challenge showing that Larsen's 's algorithm can be made robust noise, which requires to modify his anal- ysis in several parts of the algorithm. The main technical obstacle (not present in vanilla "sketch-and-soovv" prob- lems such as linear-regression, low-rank, tensor, inverse problems (Clarkson & Woodruff, 2013; Nelson & Nguyên, 2013; Razenshteyn et al., 2016; Song et al., 2017; 2019a; Lee et al., 2019; Jiang et al., 2021)) is that we can never afford to explicitly store the projection matrix Br, as even writing it would already require 0(m)) time. This con- straint makes it more challenging to apply non-oblivious sketching tools, in particular approximate leverage-score sampling (LSS, (Spielman & Srivastava, 2011) 1)), which are key to our algorithm.
Implementing the first part of Larsen's algorithm PROJECTTOSMATL.RR incurs the following computa- tional bottlenecks, which we overcome in Theorem 1.5:
Barrier 1. Computing the projection matrix B, A(I V. Vi) E RRax explicitly (exactly) already takes Tiat (m, n, n) time."
Barrier 2.
Computing the jth-row's norm |ee] Bell2
requires Tmat (m, n,, n) time.
Barrier 3. Computing B, B, E Rnx" requires multi- plying an n X m with a m x n matrix, which also takes Tmaa (n, m, 2)) time.
Implementing the second part of Larsen's algorithm (PARTIALCOLORING) incurs the following two (main) com- putational bottlenecks:
Breaking the n runtime of Larsen's partial-coloring algo- rithm (which is important for near-square matrices m n) requires a different idea, as this bottleneck stems from the Online Matrix-Vector Conjecture (Henzinger et al., 2015). To circumvent this bottleneck, we modify the analysis and implementation of the Edge-Wall Walk subroutine (dropping cer- tain verification steps via concentration arguments), and then design sauuss-anddccrreedd data structure (inspired by "lookahead" algorithms (Brand et al., 2019)) that batches the prescribed gaussian projections, with low-rank amor- tizes corrections. We now turn to formalize these three main ideas.
Barrier 4. The coloring algorithm requires comput- ing 17 [mm] [le] A(T V VVll2, which takes Tmm n, n) time.
Barrier 5. In each of the N = O(n) iterations, the al- gorithm first chooses a Gaussian vector g ~ (0, Ta) and projects it to the orthogonal span of Vi, i.e., gV, = - V.)g. Next, finds a rescaling factor y by solving single variable maximization problem. 5 Finally, the algorithm checks whether Kaj, 9 2 т, (ag,,)) < for each j E [m]] The overall runtime is therefore mn?.
1.2.1. ROBUST ANALYSIS OF LARSEN'S ALGORITTM
Approximate norm-estimation suffices. The original al- gorithm (Larsen, 2023) explicitly calculates the exact norm of each row of B, A(I VV). Since the JL lemma
As mentioned above, the last step conceptually challeng- ing, as it must be done adaptively (V, is being updated
"We remark that, Tm, n, n.) = (mn?) without using FMM, and Tmaat (m, n) = O(mn with using FMM 'The naive computation here would take (nz) time. Later show how to do in (nz) time.
'The study of OMv originates from (Henzinger et al., 2015). the (Larsen & Williams, 2017; Chakraborty et al., 2018) provide surprising upper bound for the problem.
5

---

Discrepancy Minimization in Input-Sparsity Time
guarantees |ee Bella E (1 + eo)lle; B, Vj [m]] except with polynomially-small probability dg (as the sketch di- mension is logarithmic in 1/60), it is not hard to show that, even though our approximation could potentially miss some "heavy" rows, this has a minor effect on the correctness of the algorithm: the rows our algorithm selects will be larger than (1 - <o) times a pre-specified threshold, and the ones that are not chosen will be smaller than (1 + eo) times the threshold. This allows to set co (2(1).
Olea
n1
n
Ö ?
X
V
x
R
n
m B f
m
A
Approximate SVD suffices. Recall that in the PROJECT- ToSMALLRows algorithm, expanding the subspace V it- eratively, requires to compute (B, B²). Since exact SVD is too costly for us, we wish to maintain an approxi- mate SVD instead. Even though this may result in substan- tially different eigen-spectrum, we observe that a spectral- approximation of SVD(B, B:) suffices for this subroutine, since we only need eigenvectors to be: (i) orthogonal to the row space of A(T - v,T; (ii) orthonormal to each other. Our correctness analysis shows that an én (1)) spectral approximation will preserve (up to constant factor) the row-norm guarantee of PROJECTTOSMAL.ROW
The original matrix B by Larsen
Figure 1. We use the above sketch technique to reduce the time cost when computing the row norms. B E R mm Ó 2) is our sketched matrix. A mxxx n x n unit matrix. VVV E RT*" is the projection matrix onto the row span of V. And R (==xx(="") is our JL sketching matrix. After sketched, we are able to fast query row norms of B, which are close to row norm of B with an accuracy co. We select the rows from using this approximated norms. For the details of the selection operation, see Figure 2 and Figure 3.
x is the original data matrix. I E R="x is an
2.2.2. OVERCOMING THE BARRIERS
Speeding-up the -rroiittrrr-pooetiioon step In the PROJECTTOSMALLRON subroutine in Larsen (2023), the matrix Bg is used for (i) detecting rows with largest norms; (ii) extracting the largest rows to generate a matrix B; and (iii) computing the eigenvectors of B B. To optimize this process and reduce computational overhead, we avoid the explicit representation of matrix B, by substituting it with product of uppropriately-chosen sketching matrices. Given the aforementioned robustness-guarantee, Barriers in the first step can be bypassed traight-foowardi by using a JL sketch. Specifically, we utilize a random matrix R e Rax" 1og(1/6g) (o to obtain the compressed matrix B, := A(T - V. R. Similarly, detecting rows with large & norm can be done in the sketched subspace since we can preserve norms up to constant by choosing ca = 6(1) and 5o = 5/ poly (m, which reduces the time for querying row-norms from O(ma²) to ((nz((A) + n
to produce compressed matrix M, whose QR factoriza- tion gives R. Using another sparse embedding matrix Sg. we calculate the compressed matrix N, which is used to compute the approximate leverage scores. This allows us to carry out the LSS lemma without computing Br. With IMPLLCITLEEERAGEESCOM
we can generate diagonal sampling matrix D in ((nnz(A) + n²) time. Using this subroutine to calculate B, = D,B. approximates the SVD of B, B. Finally, we prove that adding the eigenvectors of B. B, instead of B, B, to V will still satisfy the required "oversampling" prerequisite for each row in B.
2.2.3. BEATING THE CUBIC BARRIER
Where does the n barrier arise from? Recall that, in order simulate the Edge-Walk process, the PARTIALCOL- ORING algorithm generates, in each iteration, Gaussian vector g and projects it to Span (V.. This requires generic Mat- Vec product (I - V. V.), which takes n² time. Since Vi is dynamically changing throughout iterates (depend- ing on whether [z; + 0; Iv.ll = 1 and [r; + 0:| < 1 is satisfied or not for each i). and there are N = (n)) iterations, the OMv Conjecture (Henzinger et al.. 2015) generally implies an Q(n²) runtime for implementing this iterative loop (Note that each e; can be added to V at most once, (n)) iterations indeed suffice). Nonetheless, we show how to re-implement MARTIALCOLORIG using a "looka- head" (guess- wwn--ncrrecetto data structure, which combines FMM with low-rank corrections. We now describe the main ingredients of this data structure.
Implicit leverage-score sampling To address the hard- ness of computation of B, B, (overcoming Barrier 3), we use robust analysis to ensure that approximating the Top-k SVD of B, B, (where k z n/ log(m/n) nn) using leverage- score sampling (Drineas et al., 2012; Clarkson & Woodruff, 2013; Nelson & Nguyên, 2013) preserves algorithm correct- ness. However, we lack explicit access to the input matrix B, so we must perform implicit leverage-score sampling w.r.t B, in ~ (A time. We propose IMPLICITLEVE AGESCORE (Algorithm 9), which takes A and an orthonor- mal basis V and generates a sparse embedding matrix S
6

---

Discrepancy Minimization in Input-Sparsity Time
72
178
Ya
T2
7
x
I
Ve
Ve
n
m
B
+
m
D
X
A
D my
(a) Larsen's 's selection matrix
7T7
72
17
X
V, Vi
n2
X
X
A
Dello = Ö(eg2n) n))
|Pollo = my
(b) Our subsample matrix
Figure This figure shows the difference of the row selection. Figure (a): Larsen's algorithm explicitly selected the m, largest rows
from B. A(I V."V.), V.). and compute the eigenvectors of B, B., whose time cost expensive. Figure (b): our design, we use subsample matrix D. to generate the matrix B., who has the eigenvalues elose to B3. We use the ahove subsamping technique to reduce the time cost when computing the SVD decomposition. By using this, we can fast compute the eigenvectors.
Precomputing Gaussian projections. To overcome the ~ n2 rumning time for computing the Gaussian projections for g. we add preprocessing phase (INIT subroutine) to the PARTIAL.COLORING iterative algorithm, which generates- in advance-a Gaussian matrix E RaxN and stores the projection of every column of G to the row space of V. denoted {gvi Juc. We also design QUERY procedure, which outputs any desired output vector on-demand. Since we do not know apriori if the subspace V2 will change (and which coordinates e, will be added to Vi), we use a Cruess-and-Correde approach: We guess the batch Gaussian projections, and then in iteration t, we perform a low-rank corrections via our update and query procedure in data structure. This idea is elaborated in more detail below.
some clean-up operations for future iterations, adding up the vectors which are not present yet, and computes new batch of g's is for future use). This procedure runs in time ( (n, K, n)), and contributes Tmmat (n, K,n) time to the RESTART procedure.
Now, Recall that the beginning of the PARTIALCOLOR- ING algorithm, when we initialize the data structure, compute the first K projections .i...., Ts. Then we enter the iteration. Recall in INIT, we generate matrix P which is defined to be V V for the imput matrix V. And we pre- compute a batch of projections onto the row space of V. (G P. G.,s, where S [K] at the beginning.) Besides, if there some rows are added V during the running of the algorithm, we first find its factor that is vertical to the space of V. Then rescale this vector to unit and name it w. We maintain at most K w's. Then through the running of the algorithm, when we call the QUERY, we just simply select the corresponding row in G, denoted as g. and output the vector g p- Eie, wwwm Recall that the number of we pre-computed and the number of w we maintained are both limited to be less than K, when one of them reach the limit, we call the RESTART procedure. When this condition happens, QUERY and UPDATE will take Timat ( n, n). Thus by applying this lazy update idea, finally reach the subeubic running time. The final runtime of COLORIGG using our data structure is therefore a tradeoff based on the choice of batch size K. Denoting
(I V, Vi)g
Lazy updates for the past rank-1 sequence. Updating all the projections ÿ stored in the data structure would result in prohibitively expensive runtime. Instead, we use the idea of lazy updates: We divide the columns of G into different batches, each batch having the size K. We also use counter Tu denote which batch is being used currently, and initialize two counters k, and ki, to record the times QUERY and UPDATE were called, respectively. Every time we call QUERY or UPDATE, we increment the counter by 1. When either kg or ky reaches the threshold K, we RESTART the process, and "accumulate" the current updates as well

---

Discrepancy Minimization in Input-Sparsity Time
B
B
my largest rows
M4-1 largest rows
Compute
Compute
Compute
B, A( -2
B. A(I VV,
Be1 A(I V.)
B--1
B.
Larsen's 's matrix row selection
B
B
my approximated
m, approximated
largest
largest rows
Compute
Compute
Compute
B A(I - (22V-22)
B. A(1 -(2V1-2)
B A(1 - V12V
B, = A(1- -VI
B AU
(b) Our matrix row selection
Figure 3. This figure shows idea the operation at the t-th iteration in the projection algorithm. The figure (a) shows the idea of Larsen's, and the figure (b) shows the idea of ours. Figure (a): Larsen's algorithu selects the m. largest B, = A(1 Vi_, va-)). then the rest of the rows not selected will have norm less than the threshold Co T herdisc(A). But the time cost of row norm computation is expensive. Figure (b): we compute the sketched matrix B, A(I - VA Vi-1) R, where R an JL matrix. Then we seleet the rows based on the approximated norms. Thus significantly reduce the time cost of norm computation. We show that, under our setting, the norm of the rows not selected will have another guarantee, that is, (1 + ca) C. T herdisc(A), This constant loss will still make algorithm correct. (Since selecting operation. To demonstrate this, we use the darker red to demonstrate the real largest rows without being selected.)
from the matrix
computation approximated, there constant loss effecting the
K- = n2, we get total runtime of
Faster Iterative Coloring Recall that with the approxi- mate small-projection matrix in hand, we still need to over- come Barriers 4 and 5 above. Computing the heaviest row r == maxje [m]] || (I V VTV V) (Barrier 1) can again be done (approximately) via the JL-sketch (as in the first step), by computing
Ō(nz((A) n + n+a n (
For the current upper bound on the fast rectangular matrix multiplication function -() (Alman et al., 2025), set- ting = 0.53 yields an optimal overall runtime time of (Anzz(A) + n 2.53). We note that even an ideal value of w would not improve this result by much, as would merely enable setting a = 0.5 which in turn would translate into an 2.5 time algorithm, and this the limit of our approach.
max [|a] [a]((T- VV) jE[m)
using the JL matrix R. Since R has only 2 (1g())))) columns (where choosing é1 = @(1) and 81 = 8/ poly(mn) sufficient ) this step reduces from
8

---

Discrepancy Minimization in Input-Sparsity Time
Iteration start
Generating set of random Gaussian vectors g and store a batch of them projected onto V
Generating random
Gaussian vector g
Iteration Start
Projecting g onto Span(V)
Query a projected g directly
Condition check 1
Condition check
no
yes
Add to V
yes
Update e; to V and update the projection automatically
yes
Condition check 2
Return fail
Condition check
Add to V
yes
no
Condition check 3
no
Condition check
yes
Return fail
yes
Return
Return
(a) Larsen's 's Partial Coloring Algorithm
(b) Our Fast Partial Coloring Algorithm
Figure The flowehart shows different design the partial coloring algorithm of Larsen (2023) and ours. In figure (a), the blue blocks are the steps causing the mainly time cost. In figure (b), the red blocks the steps design overcome those time costs. The E R" the new-gene generated Gaussian vector and g the projected vector. That is, = (1 V V)g.
Taae (m, n) time to Ö(n²).
new idea required to overcome the cubic term n², which is important for the near-square case (m Rs n)).
As discussed earlier, Barrier 5 is a different ballgame and major obstruction to speeding up Larsen's algorithm, since the verification step
3. Conclusion
In this work, we address the longstanding challenge of dis- crepancy minimization for real-values matrices with focus achieving input-sparsity time algorithms. By introducing novel algorithmic components such as implicit leverage- score sampling and lazy update, our combinatorial algorithm achieves runtime ((nnz(A))))) A) + n²) and a FMM-based variant breaks the cubic barrier to reach ((nz((A) ( + We significantly improve the computational efficiency while matching the approximation guarantees of existing meth- ods. Our approach not only introduces novel algorithmic components but also demonstrates the potential of combin- ing sketching and fast matrix multiplication in advancing computational geometry and optimization. We believe these techniques are of independent interest. Future work could extend these ideas to reduce the runtime of other problems in combinatorial optimization, or adapt techniques to tackle the problems in streaming and distributed models.
m E, == A
A Kay <> (I)
needs be performed adaptively in each of the iterations, which appears impossible to perform in < mn² time given the OMv Conjecture (Henzinger et al., 2015). Fortunately, it turns out we can avoid this verification step using slight change in the analysis of Larsen (2023): Larsen's 's analysis shows the event & Eq. (1) happens with constant prob- ability. By slightly increasing the threshold to r' =(6), we can ensure the event E,- happens with probability Setting& 5 to small enough constant other parts of the algorithm, we can avoid this verification step altogether. At this point, the entire algorithm can be of success. combining
6.
not to affect the
boosted to ensure high-probabilie these ideas yields a (combinatorial) coloring algorithm that runs in ((nz(AA + n Next, we turn explain the

---

Discrepancy Minimization in Input-Sparsity Time
Acknowledgements
Bansal, N. Constructive algorithms for discrepancy min- imization. In 2010 IEFE 51st Annual Symposium Foundations of Computer Science, pp. 3-10. IEEE, 2010.
The author would like to thank the anonymous reviewer of ICML 2025 for their highly insightful suggestions.
Bansal, N. Semidefinite optimization in discrepancy theory. Mathematical programming. 134:5-22, 2012.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning and Optimization. There are many potential societal consequences our work, but none of which we feel must be specifically highlighted here.
Bansal, N., Dadush, D., Garg, S., and Lovett, S. The gram-
schmidt walk: cure for the banaszezyk blues. In Pro- ceedings of the 50th annual acm sigact symposium on theory of computing, pp. 587-597, 2018.
Bansal, N., Dadush, D., and Garg, S. An algorithm for komlós conjecture matching banaszczyk's bound. SIAM Journal on Computing, (aci:nn...(()):5:3:):::::: 48(2):534-553, 2019.
References
Allen-Zhu, and Li, Y. Follow the compressed leader: faster online learning of eigenvectors and faster mmwu. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
Bansal, N., Jiang, H., Singla, S., and Sinha, M. Online vec- tor balancing and geometric discrepancy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1139-1152, 2020.
Allen Zhu, Z., Lee, Y. T., and Orecchia, L. Using opti- mization to obtain a width-indeppedent, parallel, simpler, and faster positive SDP solver. Proceedings of the Twenty-Seventh Annual (CM-SIAM Symposium on Dis- crete Algorithms(SODA) 2016.
Bansal, N., Laddha, A., and Vempala, S. S. A unified approach to discrepancy minimization. arXiv preprint arXiv:2205.011 010023, 2022.
Alman, J. and Williams, V. V. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM- Symposium on Discrete Algorithms (SODA), pp. 522-539. SIAM, 2021.
Batson, J., Spielman, D. A., and Srivastava, N. Twice- ramanujan sparsifiers. SIAM Journal on Computing, 41 (6):1704-1721, 2012.
Bechavod, Y., Podimata, C., Wu, S., and Ziani, J. In- formation discrepancy strategic learning. In Inter- national Conference on Machine Learning (ICML), pp. 1691-1715. PMLR, 2022.
Alman, J., Duan, R., Williams, V. V., Xu, Y., Xu, Z.,, and Zhou, R. More asymmetry yields faster matrix multipli- cation. In Proceedings of the 2025 Annual ACM-SIAM SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2025.
Beck, J. and Fiala, integer-making theorems. Discrete Applied Mathematics, 3(1):1-8, 1981.
Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium Theory of computing (STOC), pp. 20-29, 1996.
Bläser, M. Fast matrix multiplication. Theory of Computing, pp. 1-60, 2013.
Alweiss, R., Liu, Y. P., and Sawhney, M. Discrepancy minimization via a self-balancing walk. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 14-20, 2021.
Boutsidis, C., Woodruff, D. P., and Zhong, P. Optimal principal component analysis in distributed and streaming models. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing (STOC), pp. 236- 249, 2016.
Anstreicher, K. M. The volumetric barrier for semidefi- nite programming. Mathematics of Operations Research, 2000.
Brand, J. d., Nanongkai, D., and Saranurak, T. Dynamic matrix inverse: Improved algorithms and matching condi- tional lower bounds. In 2019 IEEE 60th Anmual Sympo- sium on Foundations of Computer Science (FOCS), pp. 456 480. IEEE, 2019.
Arora, S. and Kale, S. combinatorial, primal-dual ap- proach semidefinite programs. In Proceedings of the 39th Annual ACM Symposium Theory of Computing (STOC), 2007.
Brand, J. v. d., Lee, Y. T., Sidford, A., and Song, Z. Solving tall dense linear programs in nearly linear time. In Pro- ceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 775-788, 2020.
Banaszezyk, W. Balancing vectors and gaussian measures of n-dimensional convex bodies. Random Structures & Algorithms, 2(4):351-361) 1998.
10

---

Discrepancy Minimization in Input-Sparsity Time
Brand, J. v. d., Peng, B., Song, Z., and Weinstein, O. Train- ing (overparametrizee) neural networks in near-linear time. In ITCS, 2021.
the forty-fifth annual ACM symposium on Theory of Computing (STOC), pp. 81-90, 2013.
Cohen, M. B. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the eventy-seventle annual ACM-SIAM symposiun on Discrete algorithms, pp. 278-287, SIAM, 2016a.
Brand, J. v. d., Song. Z., and Zhou, Algorithm and hard- ness for dynamic attention maintenance large language models. In Forty-first International Conference on Ma- chine Learning, 2024.
Cohen, M. B. Ramanujan graphs in polynomial time. In 2016 IEEE 57th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 276-287-821 IEEE, 201
Brand, J. v. D., Song, Z., and Weng, A. Subquadratic space representation of flows. In arxiv preprint, 2025.
Bubeck, S., Cohen, M. B., Lee, Y. T., and Li, Y. An ho- motopy method for lp regression provably beyond self- concordance and in input-sparsity time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1130-1137, 2018.
Cohen, M. B., Lee, Y. T., and Song. Z. Solving linear programs in the current matrix multiplication time. In STOC, 2019.
Dadush, D. Discrepancy open problems. https:
/ //homepages. cwi nl/ www.dduw.nnnuai////aaaaaaaaa.aia hwtpsssswwwwwwwwooooooooo peppeeppncy-ippppee-ppoooe 2018.
Bürgisser, P., Clausen, M., and Shokrollahi, M. A. Alge- bruic complexity theory, volume 315. Springer Science & Business Media, 2013.
html,
Dadush, D., Nikolov, A., Talwar, K., and Tomczak- Jaegermann, N. Balancing vectors in any norm. In 2018 IEEE 59th Annual Symposium Foundations of Com- puter Science (FOCS), pp. 1-10. IEEE, 2018.
Carmon, Y., Duchi, C., Sidford, A., and Tian, A rank-1 sketch for matrix multiplicative weights. In Conference Learning Theory (COLT), pp. 589-623, 2019.
Dantzig, B. Maximization of linear function of vari- ables subject linear inequalities. Activity analysis of production and allocation, 13:339 043,,-37,11 1947.
Chakraborty, D., Kamma, L., and Larsen, K. G. Tight cell probe bounds for succinct boolean matrix-vector multipli- cation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1297- 1306, 2018.
De Berg, M. Computational geometry: algorithms and applications. Springer Science & Business Media, 2000.
Charikar, M., Chen, K., and Farach-Colton, M. Finding frequent items in data streams. International Collo- quium on Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Deng, Y., Li, Z., and Song, Z. Attention scheme inspired softmax regression. arXiv preprint arXhv:2304.1041. 2023.
Drineas, P., Magdon-Ismail M., Mahoney, M. W., and Woodruff, D. P. Fast approximation of matrix coher- ence and statistical leverage. The Journal of Machine Learning Research. 13(1):3475-3506 2012.
Charikar, M., Newman, A., and Nikolov, A. Tight hard- ness results for minimizing discrepancy. In Proceedings of the secnny annual ACM-SIAM symposium on Discrete Algorithms, pp. 1607-1614. SIAM, 2011.
Eldan, R. and Singh, M. Efficient algorithms for discrep- ancy minimization in convex sets. Random Structures Algorithms, 53(2):289 -07, 2018.
Chazelle, B. The discrepancy method: randomness and complexity. Cambridge University Press, 2000.
Chen, L., Kol, G., Paramonov, D., Saxena, R.. Song, Z., and Yu, H. Towards multi-pass streaming lower bounds for optimal approximation of max-cut. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 878-924. SIAM, 2023.
Gall, F. L. and Urrutia, F. Improved rectangular matrix multiplication using powers of the coppersmith-winogee tensor. In Proceedings of the Twenty-Ninth Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pp- 1029-1046. SIAM, 2018.
Chen, 7.,, Yuan, X., Lu, J., Tian, Q., and Zhou, J. Deep hashing via discrepancy minimization. In Proceedings of the IEEE conference computer vision and pattern recognition (CVPR), pp. 6838-6844 6847, 2018
Gao, Y., Song, Z., and Yin, An iterative algorithm for rescaled hyperbolic functions regression. arXiv preprint arXiv:2305.000 00660, 2023.
Garber, D. and Hazan, E. Sublinear time algorithms for approximate semidefinite programming. Mathematical Programming. (58(1-2):329-36) 2016.
Clarkson, K. L. and Woodruff, D. P. Low rank approxima- tion and regression input sparsity time. In Proceedings

---

Discrepancy Minimization in Input-Sparsity Time
Grigorescu, E., Lin, Y.-.,, Silwal, S., Song, M., and Zhou, S. seamning-augmentn algorithms for online linear and semidefinite programming. Advances in Neural Infor- mation Processing Systems (NeurIPS), 15:38643-38655 2022.
Jain, R. and Yao, P. A parallel approximation algorithm for positive semidefinite programming. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.
Jain, V., Sah, A., and Sawhney, M. Spencer's theorem in nearly input-sparsity time. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3946-3958. SIAM, 2023.
Gu, Y. and Song. Z. faster small treewidth sdp solver. arXiv preprint orXiv:221..0603 1.0003,, 2022.
Gu, Y., Kuang, N. L., Ma, Y.-A., Song, Z.,, and Zhang, L. Log-coneave sampling over convex body with barrier: robust and unified dikin walk. In Advances in Neural Information Processing Systems (NeurIPS), 2024a.
Jambulapati, A., Reis. V., and Tian, K. Linear-sized sparsi- fiers via near-linear time discrepancy theory. In Proceed- ings of the 2024 Annual ACM-SIAM Symposium on Dis- crete Algorithms (SODA), pp. 5169-5208, SIAM, 2024.
Gu, Y. Song. Z., Yin, J., and Zhang, L. Low rank matrix completion via robust alternating minimization in nearly linear time. In The Twelfth International Conference on Learning Representations (ICLR), 2024b.
Jiang. H., Kathuria, T., Lee, T., Padmanabhan, S., and Song, Z. faster interior point method for semidefinite programming. In 2020 IEEE 61st annual symposium on foundations of computer science (FOCS), pp. 910-918. IEFE, 2020a.
Gu, Y., Song, Z., and Zhang, L. A nearly-linear time algo- rithm for structured support vector machines. In ICLR, 2025.
Jiang, H., Kathuria, T., Lee, Y. T., Padmanabhan, S., and Song, Z. A faster interior point method for semidefinite programming. In FOCS, 2020b.
Han, I., Kapralov, M., Kochetkova, E., Sheth, K., and Zandieh, Balancekv: Kv cache compression through discrepancy theory. arXiv preprint arXiv:2502.07861, 2025.
Jiang, H., Lee, Y. T., Song, Z., and Wong, S. C.-w. An improved cutting plane method for convex optimization, convex-concave games, and its applications. In Proceed- ings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 944-953, 2020c.
Henzinger, M., Krinninger, S., Nanongkai, D., and Saranu- rak, T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication con- jecture. Proceedings of the forty-seventh annual ACM symposium on Theory of computing (STOC), pp. 21-30, 2015.
Jiang, H., Lee, Y. T., Song, Z.,, and Zhang, L.. Convex minimization with integer minima in (n time. In Proceedings of the 2024 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 3659-36866 SIAM, 2024.
Hoberg, R. and Rothvoss, T. A logarithmic additive inte- grality gap for bin packing. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pp. 2616 2625. SIAM, 2017.
Jiang, S., Song, Z., Weinstein, O., and Zhang, H. Faster dynamic matrix inverse for faster Ips. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2021.
Hu, H., Song, Z., Weinstein, O., and Zhuo, D. Training overparametrized neural networks in sublinear time. In arXiv preprint arxiv: 2208.04508. 2022.
Johnson, W. B. and Lindenstrauss, J. Extensions of lipschitz mappings into a hilbert space. Contemp. Math., 26:189) 206, 1984.
Huang, B., Jiang, S., Song, Z., Tao, R., and Zhang, R. Solving sdp faster: A robust ipm framework and efficient implementation. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 233- 244. IEEE, 2022a.
Karmarkar, N. new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing (STOC), 1984.
Huang, B., Jiang, S., Song. Z., Tao, R., and Zhang, R. Solving sdp faster: A robust ipm framework and efficient implementation. In FOCS, 2022b.
Karnin, Z. and Liberty, E. Discrepancy. coresets, and sketches in machine learning. In Conference Learning Theory, pp. 1993. PMLR, 2019.
Huang, B., Jiang, S., Song, Z., Tao, R., and Zhang, R. Solving sdp faster: robust ipm framework and efficient implementation. In FOCS, 2022c.
Khachiyan, L. G. Polynomial algorithms in linear program- ming. USSR Computational Mathematics and Mathemat- ical Physics, 20(1):53-72, 1980.
12

---

Discrepancy Minimization in Input-Sparsity Time
Larsen, K. G. Constructive discrepancy minimiza- tion with hereditary 12 guarantees. arXiv preprint arXiv:1711.02860, 2017.
Lyu, Y. Fast rank-1 lattice targeted sampling for black-box optimization. Advances in Neural Information Processing Systems, 36: 16:10494-10515. 2023.
Larsen, K. G. Fast discrepancy minimization with hereditary guarantees. In SODA. arXiv preprint mrXiv:2207.0322 2023.
Lyu, Y., Yuan, Y., and Tsang, I. Subgroup-based rank-1 lat- tice quasi-monte carlo. Advances in Neural Information Processing Systems,
2020.
Larsen, K. G. and Nelson, J. Optimality of the johnson- lindenstrauss lemma. In 2017 IEEE 58th Anmual Sympo- sium Foundations of Computer Science (FOCS), pp. 633-638, IEEE, 2017.
Matousek, J. Geometric discrepancy: An illustrated guide, volume 18. Springer Science & Business Media, 1999a.
Matousek, J. Geometric discrepancy: An illustrated guide, volume 18, Springer Science & Business Media, 1999b.
Larsen, K. G. and Williams, R. Faster online matrix-vector multiplication. In Proceedings of the Twenty-Eight Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp: 2182-2189, 2017.
Muthukrishnan, S. and Nikolov, A. Optimal private half- space counting via discrepaney. In Proceedings of the forty-fourth annual ACM symposium Theory of com- puting, pp. 1285-1292, 2012.
Lee, Y. T. and Padmanabhan, S. An Ö(m/ / algo- rithm for semidefinite programs with diagonal constraints. In Conference on Learning Theory (COLT), Proceedings of Machine Learning Research. PMLR, 2020.
Nelson, J. and Nguyên, H. L. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embed- dings. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 117-126. IEEE, 2013.
Lee, Y. T. and Sidford, A. Path finding methods for linear programming: Solving linear programs O (vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 424 433. IEEE, 2014.
Nesterov, Y. and Nemirovski, A. Conic formulation of a convex programming problem and duality. Optimization Methods and Software, 1(2):95-115, 1992.
Lee, Y. T., Sidford, A., and Wong, C. faster cutting plane method and its implications for combinatorial and convex optimization. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2015.
Nikolov, A. Randomized rounding for the largest simplex problem. Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 861-870, 2015.
Nikolov, A., Talwar, K., and Zhang, L. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fitth annual ACM symposium on Theory of computing, pp. 351-360, 2013.
Lee, Y.T., Song, Z.,, and Zhang, Q. Solving empirical risk minimization in the current matrix multiplication time. In Conference on Learning Theory, pp. 2140-22 2140-2157. PMLR, 2019.
Li, X., Liang. Y., Shi, Z., and Song, Z. A tighter complexity analysis of sparsegpt. In Workshop on Machine Learning and Compression, NeurlPS 2024.
Pesenti, L. and Vladu, A. Discrepancy minimization via regularization. In Proceedings of the 2023 Annual ACM- SIAM Symposium Discrete Algorithmss (SODA), pp- 1734-1758. SIAM, 2023.
Li, 7.,, Song, 7., and Zhou, T. Solving regularized exp, cosh and sinh regression problems. arXiv preprint arXiv:2303. 15725, 2023.
Qin, L., Song, Z., Zhang, L., and Zhuo, D. An online and unified algorithm for projection matrix vector multiplica- tion with application to empirical risk minimization. In International Conference on Artificial Intelligence and Statistics, pp. 101-156. PMLR, 2023.
Liu, S. C., Song, Z., Zhang, H., Zhang, L., and Zhou, T. Space-efficient interior point method, with applications to linear programming and maximum weight bipartite matching. In ICALP, 2023.
Razenshteyn, I., Song, Z., and Woodruff, D. P. Weighted low rank approximations with provable guarantees. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 250-263. 2016.
Lovász, I.,, Spencer, J., and Vesztergombi, K. Discrep- ancy of set-systems and matrices. European Journal of Combinatorics, 7(2):151-16) 1986.
Lovett, S. and Meka, R. Constructive discrepancy mini- mization by walking on the edges. SIAM Journal on Computing, 44(5):1573-15822 2015.
Renegar, J. A polynomial-tin algorithm, based on new- ton's method, for linear programming. Mathematical Programming, 40(1-3):59 1988.
13

---

Discrepancy Minimization in Input-Sparsity Time
RothvoB, T. Approximating bin packing within O(og((PPT) loglog(OPT)) bins. In 2013 IEEE 54th Annual Sympo- sium Foundations of Computer Science, pp. 20-29. IEEE, 2013.
Song, Z., Ye, M., and Zhang, L. Streaming semidefinte
programs: of ((n)) passes, small space and fast runtime. arXiv preprint 23Xi::3300001335 2023c.
Spencer, J. Six standard deviations suffice. Transactions of the American mathematical society, 289())667--76, 1985.
Rothvoss, T. Constructive discrepancy minimization for convex sets. SIAM Journal on Computing, 46(1):224- 234, 2017.
Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6): 1913-1926, 2011.
Sarlos, T. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS'06) 06). pp. 143-152. IEEE, 2006.
Talagrand, M.
Concentration of measure and isoperi- metric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scien- tifiques, 81:73-205, 1995.
Shamir, O. A variant of azuma's inequality for martingales with subgaussian tails. CoRR, abs/1 2011. URL http:/ / /arxivv.vv... wwtgabsgg//aooooooet..o/eee abs .3992.
Tropp. J. A. Improved analysis of the subsampled random- ized hadamard transform. Advances in Adaptive Data Analysis, 3(01n02): 115-):1111116,, 2011.
Song, Z. Matrix Theory: Optimization, Concentration and Algorithms. PhD thesis, The University Texas at Austin, 2019.
Song, Z. and Yu, Z. Oblivious sketching-based central path method for linear programming. In International Con- ference Machine Learning, pp. 9985-99847 PMLR, 2021.
Tropp. J. A. et al. An introduction to matrix concentra- tion inequalities. Foundations and Trends@ in Machine Learning, 8(1-2)11-230, 2015.
Vaidya, M. An algorithm for linear programming which requires O (((m+n))n² (m-+n))--n)) arithmetic oper- ations. In 28th Annual IEEE Symposium Foundations of Computer Science (FOCS), 1987.
Song, Z., Woodruff, D. P., and Zhong, P. Low rank approxi- mation with entrywise 11-norm error. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 688-701, 2017.
Vaidya, P. M. A new algorithm for minimizing convex functions over convex sets. In 30th Annual IEEF Sympo- sium on Foundations of Computer Science (FOCS), pp. 338-343, 1989.
Song, Z., Woodruff, D. P., and Zhong, P. Relative error tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Al- gorithms, pp. 2772-2789. SIAM, 2019a.
Vapnik, V. and Chervonenkis, A. Y. On the uniform conver- gence of relative frequencies of events to their probabil- ities. Theory of Probability and its Applications, 16(2): 264, 1971.
Song. Z. Woodruff, D. P., and Zhong, P. Relative enror tensor low rank approximation. In SODA. arXiv preprint arXiv:1704.08246, 2019b.
Song, Z., Xu, Z., Yang, Y., and Zhang. L. Accelerating frank- wolfe algorithm using fow-dimensional and adaptive data structures. arXiv preprint (:XXi:2207.09000 2022a.
Wang. R., Yan, J., and Yang, X. Unsupervised learning of graph matching with mixture modes via discrepancy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 45(8): 2023.
Song, Z., Xu, Z., and Zhang, Speeding up sparsification using inner product search data structures. arXiv preprint arXiv:2204.0322 032009 2022b.
Williams, V. V. coppersmith-winee In Proceedings of the forty-ourth annual ACM symposium on Theory of computing (STOC), pp. 887-898. ACM, 2012.
Multiplying matrices faster than
Song, Z., Wang, Y., Yu, Z., and Zhang, L. Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability. International Conference on Machine Learning (ICML), pp. 32365-32417. PMLR, 2023a.
Williams, V. V., Xu, Y., Xu, Z., and Zhou, R. New bounds for matrix multiplication: from alpha to omega. In Pro- ceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3792-3835. SIAM, 2024.
Song. Z., Yang, X., Yang, Y., and Zhang, L. Sketching meets differential privacy: Fast algorithm for dynamic kronecker projection maintenance. In ICML,, 2023b.
14

---

Discrepancy Minimization in Input-Sparsity Time
Woodruff, D. P. Sketching tool for numerical linear algebra. Foundations and Trends Theoretical Computer Science, 10(1-2):1-157, 2014.
Xiao, C.,, Zhong, P., and Zheng. C. Bourgan: Generative networks with metric embeddings. Advances in neural information processing systems, 31, 2018.
Yurtsever, A., Tropp. A., Fercoq, O., Udell, M., and Cevher, V. Scalable semidefinite programming. arXiv preprint arXiv: 1912.02949, 2019.
Zhang, L. Speeding up optimizations via data structures: Faster search, sample and maintenance. Master's thesis, Carnegie Mellon University, 2022.
15

---

Discrepancy Minimization in Input-Sparsity Time
Appendix
Rodamap. We organize the appendix as follows. Section A, we give the preliminaries of the paper, including the notations we use, the definitions and some useful results from prior works. In Section B, we provide previous tools and results on sketching. In Section C, we present our first result, fast algorithm of projecting matrix into small rows. In Section D, present the final algorithm of hereditary minimize. In Section E, we present the second main result, the fast partial coloring algorithm. In Section F, we discuss the fast maintaining algorithm we use to boost the running time. In Section G, we provide our implicit leverage score sampling algorithm.. In Section H, we give a sparsification tool for the matrix that has pattern A" A. In Section I, we provide the algorithm to find proper step size in Partial Coloring algorithm. In Section J. we provide empirical validation of the efficiency of our algorithm. In Section K, we discuss more related work on linear programming, semidefinite programming, and applications of discrepancy theory in machine leraning.
A. Preliminaries
A.1. Notations
For vector x E IR", we use ||=||| to denote its entrywise & norm. We use ||=]|>> to denote its entrywise foo norm. For matrix X, we use || to denote the spectral norm. We use to denote the vector where i-th location is 1 and everywhere else is O. For matrix A, we say matrix A positive semi-definite if A ž O, i... x' Ax 2 O for all vectors r. We say A > B, for all æ E Rd, x Ar 2 x² Br. For a positive semi-definite matrix A, let UEU be the SVD decomposition of A. We use A 1/2 to denote UE We use A- to denote UE UE-1/27? where E E-1/2 is diagonal matrix that i, i-entry is E 1/2 E A and i, i-th entry is 0 if E = 0. For matrix A, we use nnz(A) to denote the number of non-zeros in matrix A.
A.2. Definitions
Here, we define disc and herdisc.
Definition A.1 (Discrepancy). For a real matrix A E Rmxx, and vector 11,- We define the discrepancy of A be
fisc(A, || = max (Ax))l-
sm/m]
And we define the discrepancy of the matrix A as
disc(A) == min =1(1--1)
(isc(A,z))
Definition A.2 (Hereditary Discrepaney). For real matrix A E Rmxn Let A be defined the of matrices obtained from A by deleting some columns from A. We define the hereditary discrepancy of A to be
herdisc(A) == max disc BB), BЕA
where disc is defined Definition A.I.
A.3. Basic Linear Algebra
Lemma A.3. Given two psd matrices A gaxn and B E Ruxn If
(1 c) = B (1+
then, we have
(1 (1- ())))((A) = (BB) - (1+ ()A().
Note that, Ax( the i-the largest eigenvalue of A.
16

---

Discrepancy Minimization in Input-Sparsity Time
A.4. Prior Results Herdise
We state tool from previous work.
Theorem A.4 (Larsen (2017)). Given real matrix A Rmxn, let X1 2 A2 2 ...2 An 2 0 be the eigenvalues of A A. For all positive integers min(m, n), we have
k
A
herdisc
2e
mn
A.5. Properties of Gaussians
We state two statements about the Gaussian variables.
Claim A.5. Let be a random variable such that ~ (V(,,)), 1). Then for any O, we have that
Pr[ld] > X] < 2 exxp(-X2/2
Claim A.6 (Claim 2 in Larsen (2023)). For an arbitrary matrix V E R such that S n and all rows of V form an orthogonal basis. Let 9 E be vector which sampled with n iid. No0, 1) distributed coordinates. Then for any arbitrary vector a IR" we have that
(I (I- ~ N(0.aa) VT1))..
A.6. Azuma for Martingales with Subgaussian Tails
Then for martingales with subgaussian tails, we introduce the following Azuma's inequality. We first define the following martingale difference sequence.
Definition A.7 (Martingale Difference Sequence). For two sequences of random variables A {Ai, A2... and B = (B,, B,.... }. for any integer t Z, A4t1 is fumction of (B.....,,,, and the following holds,
Pr[E[A441 BI..... B₂] 0]
then we say that A is a martingale difference sequence with respect to B.
Then we introduce the following Azuma's 's inequality for martingales with Subgaussian tails.
Theorem A.8 (Shamir (2011)). Let å E (0, 1) be an arbitrary failure probability, Let A {A Ar) a martingale difference sequence with respect to a sequence B (Bi...., Br Let and c be two constants. If for any integer t and all E R,,, the following holds,
max(Pr[A: > a SI,...... B, B,-1), Pr[A, < -a B B B- I bexp(-ca'
Then it holds that
1 T
28h 1g(gg/10))
A,l $ 21
T -=1
cT
with probability at least 1 1-6 5.
A.7. Concentration Inequality
We state the matrix Bernstein bound follows:
Lemma A.9 (Matrix Bernstein Bound (Tropp, 2011; Tropp et al., 2015)). Let XI,...,Xe be independent copies of
symmetric random matrix X E R with [[X] = 0. XX|| < almost surely and E X]]l I 0². Let W
Eiete] X,. For any E (0, 1),
(__
SEa
Pr]][W||| 2 el < 2n exp
(-
4
Note the [[W] the spectral norm of matrix W.
17

---

Discrepancy Minimization in Input-Sparsity Time
A.8. Fast Matrix Multiplication
We describe several basic backgrounds about fast matrix multiplication.
Definition A.10. Given three integers n1, R2, ng, we use Tmat (11, n2, na) to denote time of multiplying a ni x matrix with another n2 x 0g matrix.
is known that the ordering of n1, R2, ng only affects the constant factor in the time complexity of matrix multiplication. Fact A.11 (Bürgisser et al. (2013); Bläser (2013)).
mam (ni, n2,, n3) = O (f1, n3. (2))) = O (n22, ni, n3)))
n2)
For convenience, we also define the ..)) function and the exponent w matrix multiplication (Williams, 2012; Gall Urrutia, 2018; Alman & Williams, 2021; Williams al., 2024; Alman et al., 2025).
Definition A.12. For o, b, C >> 0, we use (aabb)))) to denote the time of multiplying n x n² matrix with another no x n matrix. We denote w == w(1, 1) as the exponent of matrix multiplication. we denote a as the dual exponent of matrix multipiiaation, ie.. = w(1, 1.)).
By the state-of-the-art fast matrix multiplication result in Alman et al. (2025), we have
Lemma A.13 (Alman et al. (2025)). We have
w = (11, = 2.371.
w1,, = 2.055.
B. Previous Tools and Results on Sketching
Here this section, we provide tools and previous results on sketching matrices. Section B.1 we introduce some sketching matrices. In Section B.2 we provide traditional JL transform. In Section B.3 we give some previous results on subspace embedding.
B.1. Sketching Matrices
Definition B.1 (Random Gaussian matrix or Gaussian transform, folklore ). S= G Rsx where a is a sealar, and each entry of G E Raxm is chosen independently from the standard Gaussian distribution. For any matrix A E Rm SA can be computed in O(s nnz(A)) time.
Definition B.2 (AMS (Alon et al., 1996)). Let h1, h2..... hy be random hash functions picking from a 4-wise independent hash family
{h: [m] { vb. + Jo }.. Then R E Rbxn n is AMS sketch matrix if we set R = hę(j).
Definition B.3 (CountSketch (Charikar et al., 2002)). Let h: [m]- a: : [m] > {+1,-1} be a random 4-wise independent hash function. Then R E Bbxn is a count-sketch matrix if we set RR(0 oi) for all E [n]] and other entries to zero.
- [b] be a random 2-wise independent hash function and
Definition B.4 (Sparse Embedding Matrix I (Nelson & Nguyên, 2013)). We say E gbxn a sparse embedding matrix with parameter each column has exactly non-zero elements being =1/ uniformlly at random, whose locations picked uniformly at random without replacement (and independent across columns).
Definition B.5 (Sparse Embedding Matrix II (Nelson & Nguyên, 2013)). Let h
[m] x [s] + [b/s] be a random 2-wise independent hash function and a [n] [s] + (-1. 1} be a wisi independent. Then R TRox a sparse embedding matrix II with parameter s we set (1-1))/=+(55)) ofi, /5 for all (i.j) [m] x [s] and all other entries zero.
Definition B.6 (CountSketch + Gaussian transform, Definition 1.18 in Song et al. (2019a))- Let S' = S11, where II E 1m is the COUNTSKETCH transform (defined in Definition B.3) and S E Rext is the Gaussian transform (defined in Definition B. For any matrix A E Rmxn, S'AA can be computed in (())((A) + n time, where w is the matrix multiplication exponent.
18

---

Discrepancy Minimization in Input-Sparsity Time
B.2. JL Transform
We define Johnson-Lindensrraus transform (Johnson & Lindenstrauss, 1984) as follows:
Definition B.7 (Johnson & Lindenstrauss (1984)). Let e (0, 1) be the precision parameter. Let (0, be the failure probability. Let A E m be a fixed matrix. Let a denote the i-th row of matrix A, for all E [m]] We say R is an e, Ö-JL transform if with probability at least 1
6,
(1 - c)llalle & |Razll2 - +)llasla, Vi E [m].
well-known that random Gaussian matrices and AMS matrices give JL-transform property.
Lemma B.8
transform (Johnson & Lindenstrauss, 1984)). Let e E (0, be the precision parameter.
Let E 1) be the failure probability. Let E Rmx= be a real matrix Then there exists an sketching matrix
R E R log(mm/A)xa (defined as Definition B.1 or Definition B.2), such that the following holds with probability at least
1 1-d 8,
(1-c)laaale I |Raill2 S (1 (1+ cllosll,, Vi E [m].
where for a matrix A, of denotes the i-th row of matrix A mkxx
The JL Lemma is known to be tight due to Larsen & Nelson (2017).
B.3. Subspace Embedding
We first define a well-known property called subspace embedding.
Definition B.9 (Subspace embedding (Sarlos, 2006)). A (1 + c) l2-subspace embedding for the column space of an m x
matrix A is matrix S for which for all a E R
|A = (1 + Ax
Let U denote the orthonormal basis of A, then it is equivalent to the all the singular values of SU are within [1 - c, + with probability
- 6.
Nelson & Nguyên (2013) shows that O log (n/ and column sparsity
(n/8)) suffices for subspace embedding (See Theorem 9 in Nelson & Nguyên (2013)). Later Cohen (2016a) improves the result to O(e -0ee-n log(n/0)
and column sparsity is (e log(n/8)) (see Theorem 4.2 in Cohen (2)1
Lemma B.10 (Nelson & Nguyên (2013); Cohen (2016a)), Let A E RRxx be matrix. Let S E Rr denote the sketching matrix (defined as Definition B.4). If r O(c-2n log(n/5)) and the column sparsity of S is O(c-1 log(n/)), then S satisfies that with probability 8
|Ax (1 Ax
Further, SA can be done in (s (e)nz(AA) time.
C. Small Row Projection via Implicit Leverage-Score Sampling
Here this section, we build our algorithm of projecting a matrix to small rows. In Section C. we present the orghogonalize subroutine which is useful in later algorithms. In Section C.2 we present our projection algorithm together with its analysis.
C.I. Orthogonalize Subroutine
Here in this section, we present the following algorithm named ORTHOGONALIZE, which is just the Gram-Schmidh process. This subroutine very useful in the construction of the following algorithms.
The following lemma gives the running time of the above algorithm, with input vector sparsity time.
Lemma C.1. The algorithm (ORTHOGONALIZE Algorithm 1) runs ([] n) time.
19

---

Discrepancy Minimization in Input-Sparsity Time
Algorithm 1 Algorithm I in Larsen (2023)
1: procedure ORTHOGONNAIIZE( E R", V E RiXx)
>i Lemma C.
2: s' 3'+ -'+(1-V'V))
3: if * 0 then
4: add s'/l|s'llz 112 row of V
5: end if
6: return V
7:
end procedure
Proof.
The running time of ORTHOGONALIZE can divided follows,
Line takes time O([|s]lo n) to compute s', where for a vector a E R2, ||=/|o denotes the to norm of r.
Line 4 takes time (nn) to compute s' //Is"I12.
Thus have the total running time of O[I n).
C.2. Fast Projecting to Small Rows
Here in this section, present first main result, i.e., the faster algorithm for projecting a matrix to small rows. We first show the algorithm follows.
C.2.1. RUNNING TIME
The goal of this section is to prove running time of Algorithm 2. We have the following lemma.
Theorem C.2 (Running time of Algorithm 2). The algorithm (RASTPROJECTTOSMALLOO)) in Algoritium 2) runs
(A) + n²)) time". The succeed probability is 1 - 6. Note that Ô hides log(n/8).
Proof. The running time of FASTPROJECTTOSMMLLLOOO
can be divided as follows,
Run the following lines for i [T] times, where T = O(log(m/n)):
Line 14 needs to compute B,, takes the following time
O(nn((A)r n. + n2r) = ((n)2(())2AA) n²)
Line 18 takes time Ö(m) to construct D, by computing the norms, and takes time Ö(m) to find the largest m4-1 of them.
Using Lemma G.4, compute D, in ((nzz(A) + n²) time
Line 31 runs ORTHOGONIZE for (nn) times, and takes (n)) each time.
Adding these together, we have the total running time of Ō(nu((A) + n
C.2.2. CORRECTNESS
Here we present the correctness theorem of the Algorithm 2, and together with its proof.
Theorem C.3 (Correctness of Algorithm ). For any given m n matrix A, there is an algorithm that takes A as input and output a matrix V n/4/4xn such that
7 Note that e denotes the exponent of matrix multiplication, currently w Rs 2.373 (Williams, 2012; Alman Williams, 2021).
20

---

Discrepancy Minimization in Input-Sparsity Time
Algorithm 2 Our input sparsity projection algorithm (this improves the Algorithm 2 in (Larsen, 2023))
procedure FASTPROFECTTTSSSAL.ROWWS E R (0, 1))
Theorem C.3
2:
Vi E 00xn
Initialize an empty matrix
3: T log(8m/n)
4:
dg +- ((6/(mT))
5:
60 < 0.01
6:
- 5 log(1/60)
7:
ón + (
8:
EB + 0.1
9:
for + do
11:
m4 +- -m/22
12:
1Ideally., we need to compute Be + A(I - V Vi) E Rmxx, but have time to do that.
13:
Let R E ER denote JL sketching matrix (Either Definition B.2 or Definition B.1) Compute B2 - A(T - V, V.
14:
Br,ill E (1 + <0)l Br, Vj E [m]] Lemma B.8 1s Ideally, we need to compute [] ll,, but we had no time to do that.*/
15:
16:
Compute || |Bryill for all E [m]]
3. C [mm] denote the indices of B, such that it contains m4-1 rows the largest norm
18:
Let D, denote sparse diagonal matrix where (i, i)-th location is 1 if S, and 0 otherwise
19:
Let B, D.A(I- - V Vi) E mm be the submatrix obtained from Br
20:
1* Ideally, we need to compute B, Br, but in algorithm we had no time to do that.
21:
D. + SUBSAMPLE(DIA,, V,, E,
Algorithm 10
B. D.A(I-V, V,
23:
Note that o. > and an = AB,
24:
10 Ideally, we need to compute the eigenvalues 01 2 2 o 2 0 and corresponding eigenvectors U1,
of B, Br, but algorithm we had no time to that*/
Let Ø1,- Un E RR" denote the eigenvectors of SVD decomposition of B, B, = ÜSÜT
25:
Construct matrix V4+1 E BRl Xn by adding rows vectors "",,".. "nn((8T) to the bottom V E R
26:
27:
end for
Br < A (I VT
T+1 V2+1)
29:
Let ... .'n/ be the n/8 rows of By with largest
30:
for j
n/8 do
31:
V - ORTIHOGONALIZE(T; V) end for
P Algorithm 1
32:
33:
return V
b V E Reen and S n/4
34:
end procedure
having unit length orthogonal rows
all rows of A(I VVVV) have norm at most O4herdisc(4)
holds with probability at least - 5.
Proof. We define
T = log(8m//1)
which is the time of the main loop of Algorithm 2 execute.
We define
Co 1000
21

---

Discrepancy Minimization in Input-Sparsity Time
to be constant used later.
And we define
my := m/2
to denote the number of rows in B at each iteration. We then continue the proof in the following paragraphs.
The rows of V form an orthonormal basis. To start with, let us show that, the output matrix V form an orthonormal basis with its rows. Since Vo has no rows, the claim is true initially.
We first fix & T. consider at f-th iteration,afic constructing Vi+1 by adding row vectors
(......, (
to the bottom of V, in Line 26.
Note that these are eigenvectors, so they must be orthogonal to each other and for any u of them, ||l||2 = 1. Moreover, we have that
fu,.... (8T())) S span B.).
We note that, since define B,
B. = - VV VV)V)),
all rows of B, muse be orthogonal to any of V, E R4xx and it follows that adding the above set of eigenvectors
(8T)
rows of V2 R4 maintains the rows of Ve+1 E glor form an orthonormal basis.
After the first for-loop, we claim obviously that, the last for-loop (Line 31) preserves the property of V such that, V form an orthonormal basis with its rows.
We now claim that, after the t-th iteration of the first for-loop (Line to Row norm guarantee, proved with induction. Line 27), we have that
(i [m] ||b (1 co) Co T herdisc( S mgy
i.e. there are at most m, rows in B, A(I V/ Vi) having norm larger than (1 (1+0 co) Co T herdisc(A). We first note that, for / 0 this holds obviously.
Then have the following inductive assumption:
After iteration / 1, there are at most m rows have norm larger than (1 (0)) Co T herdisc(AA) (A).
We split the inductive step into the following two parts:
Norm of rows not B, will not increase. We first fix & [2]. Then by the inductive assumption and our approximated norm computation, have that for the t'th iteration, all rows not in B, have norm most
(1 + Eo) Co T herdisc(())
Since we have
span(AV, V.) S sVan(V),
then the norm of each row in matrix A(I - Vg V/) will never increase after we add new rows to V. Thus we have the claim proved.
22

---

Discrepancy Minimization in Input-Sparsity Time
At most my rows in B, reach the threshold after adding rows. Now in this paragraph we prove that, after adding
{ūr ( /8T)))
the bottom of V (Then we name the new matrix to be 0141), there are no less than my rows in (T V2+1) E Rm having norm larger than
(1 - en) : Co T herdisc(A) (A).
Here we note that, before adding the new rows to V2, since all rows of B, are already orthogonal to all rows of Vi, we have the following
B, = B. V V.).
We now prove by contradiction. For the sake of contradiction, we assume that, more than my rows in B&( - ViT1 V4+1) have norm larger than Co - herdisc(A) after adding
(ū (8r()
to the bottom of Vg. We assume that V1+1 has 441 rows. Select an arbitrary set of unit vectors fwi...., W/ -n-1e1 l01 C R" such that.
span(w1..... Wn-ben1 RR (sssspn(V++1))
Using norms, can generate
B, = -
Using SUBSAMPLE (Algorithm 10), generate matrix
B. -.A([IVVV Vi).
By Lemma H.2, we know that B, only has roughly | O( log(n/88)) rows so that
Pr -
B, B.] 2 1 - 5B
Using Lemma A.3, the above approximation implies that
Pr [L - EB) B.) = (B ( [n]] 2 1 -8.
We define
Q B,(I - V,T V441).
And for the approximated metrics, define
:= = B - VTT Vo+1).
We first note that, all rows of Q lie in span(w), (1,,.. also lie in span(w1,... (p-ber)) ). It follows that
Wn-4 Then by the construction of B, we have that, all rows of Q
Σ JEE 11
(T wy)²
Σ
1
RE [m(mm
RE(m, 1]
> m ((1 - -60) Co T herdiso(A)) A))2
where the second step follows from the contradiction assumption.
23

---

Discrepancy Minimization in Input-Sparsity Time
Taking the average over the vectors wy IR" there has be a E [n- 4411 such that
Σ
(gx: wx)² > my ((1 - En) Co T herdisc(A)) n.
ke(m--l
We denote u = wy-. Thus we have that,
[Buull2 2 (1 - EB) (
> (1 EB) ((1 60) Co T herdiso(A))
(2)
where the first step follows from Lemma H.2. and the second step follows from the contradiction assumption that there are more than my rows in BT Vet1 V4+1) with norm more than (1 e0) Co T herdisc( A) and v unit vector.
We can upper bound B
BBool r. B, B.u
S nS(() S EB) on/(8T)
(3)
where the first step follows from the definition of la norm the second step follows from that is orthogonal to "1,...,, (n)()T) E RD and, the third step follows from the way we generate B.
Thus we have that,
1 EB
my ((1 60) Co T herdiso( A))? //
(8TT)
1 + CB
1
2 4
m.
(Co T herdisc(A))))
where the first step follows from Eq. (2) and Eq. (3), the second step follows from that we eB E (0,0.5) and co 0.01. But at the same time have the following,
herdisc(AA ()) 2 herdiso B.)
1
m. (Co- T --hediiccc)))
16eT
V
m n
= 2 herdisc(A),
where the first step follows from that B, is matrix obtained from A E Rmxx by deleting a subset of the rows of A, the second step follows from Theorem A.4 and & = 12/(8") here, and the last step follows from simplify the above step.
Thus, we get contradiction.
By the proof above, we have the claim that after the first for-loop (Line Line 27 in Algorithm 2), there are at most mt n2/8 rows in BT A(1 V V)) having norm larger than
Co T herdisc(A).
Then do the second for-loop (Line 31 in Algorithm 2). We notice after that, all these rows lie in Span(Vi). Thus we have the desired guarantee of the algorithm.
And by union bound of the above steps, we have the result holds with probability at least 1 - 5. Thus complete the proof.
D. Diserepany--Miiinizztion Algorithm
D.I. Correctness
The goal of this section to prove Theorem D.1.
24

---

Discrepancy Minimization in Input-Sparsity Time
Theorem D.I. The algorithm (FASTHERREDDTTARRMMNINMZZ Algorithm takes matrix A Rxxx inpul and outpus coloring x E {-1,+1]" such that
disc(A, x) O(herdisc(A)) log n log m).
holds with probability -Final-
Proof. We divide the proof into the following two parts.
Proof Quality of Answer. By the condition the algorithm stops, we have that, there no [n]] such that |æ,| 1. And by Lemma E.2, every time after we call CASTPARRTIALCOOLORINNG (Algorithm 4), herdisc( (A, 2)) changes at most O(herdise(A) (A) log!.6 m)). Note that, the FASTPARTIA.COOLORIGG is called Ologgn) times, thus have the guarantee. Thus complete the proof.
Proof of Success Probability. For the FASTPARTIALCOLLORIA Algorithm, each time we call it, we have that
with probability most 19/20, we know that it outputs fail.
with 1/20 /nn it outputs good neww.
with probability at most 8 / it outputs new with no guarantee.
As long repeat second while loop more than k O(log(n/Odma)) times, then can promise that with probability 1 67 / we obtain non-final "eww
Then by union bound we have the final succeed probability is
(orial/ ) log n
-0iiaa/nnn) le log
all log iterations non-fail
all V/ and good
Sinal-
D.2. Running Time
The goal of this section is to prove Theorem D.2.
Theorem D.2. For any parameter E [0, 1], the expected running time of algorithm PAATHEREDDTAAY in Algorithm 3) is
Ó(nn((A) + nz + 2+a + +n (=11111,)))))
Note that function defined as Definition A.12.
Proof. For the running time of FASTHEREDTTAYYMINIMEEE we analyze it as follows.
First we notice that, |S] halves for each iteration of the outer while loop. Thus for each iteration, can only examine the Jyyss for i E S, where is from the previous iteration. Then,
maintain S in O(n) time.
By the same argument, Line 6 takes a total time of ((nz(AA) to generate the submatrices A.
Recall we have the S halved each iteration, so |S| S n/22 at i'th iteration. Thus we have by Lemma E. Line 12 takes time
TFPC Ö(nua A) + n + n2 2+a + (n(((a)))-
to call FASTPARTTAL.CLLORING
e Note that the exponent of matrix multiplication, currently w Rs 2.373 (Williams, 2012; Alman Williams, 2021).
25

---

Discrepancy Minimization in Input-Sparsity Time
Algorithm 3
procedure FASTHERRERDRARYYYINNMEZE R Ofinal E (0, 0.001))
Lemma D.I, Lemma D.2
2: I+ -0,,
3: while & [-1,++1) do
4:
S Ei [n] | <
5: Let <- Is be the coordinates of indexed by $
6: Let A + A..s E Rmx|ss| be the columns of A indexed by S
7:
finished &- false
8:
counter 0 f- (log(n/66hal))
9:
while finished false and counter do counter counter + 1 new + FASTPARTIALCOOLOINNGG.
11:
12:
"iina//n
D. Algorithm 4
13:
x new fail then
14:
Ts - ueu finished < true end if
15:
17:
end while
18:
if finished false then
return fail 20: end
19:
21:
end while
22:
return æ
23:
end procedure
Let p denote the succeed probability of FASTPARTIAL. each time, it takes TFPC time, total
Expected time p. TFFC + (1 (1- 2TFPC + (1 - -p)pppp 3T +
Σ (1 p) i-1 ppppppppp p.i. i. TFPC
1=1
Let ((p) = Σi - pp Then we have
8
8
S(t) - (1 (1-p)/()) Σ (1 11-pp)- p)² pi Σ p) pi
(1 p) +
(1 p)
1=0
1=1
=p+ Σ (1 p)'p
i=1
Sptp- 1/p
=1+p
Thus,
1 f(P) S
p
Thus the expected time is O(TFpc/p).
Since there are at most log n iterations, so the expected time is
O(p -TFFcc log n).
26

---

Discrepancy Minimization in Input-Sparsity Time
Algorithm 4 Input sparsity time partial coloring algorithm
1: procedure FASTPARTIAL.COLORRINN/ E Rmx*, I E (-1, E [0, Annal (0,0.01), (0,0.01)
Lemma E.2, Lemma E.12
2: u1 On
3:
ô1 +- /i
4:
82 + /
5:
V + TASTPROIECTTOSMALLOOWSAAA
D Algorithm 2
6:
- FASTAPROXMAXXORRY P,62)
> Algorithm 5
7:
> r S O(herdisc log(m/n))
8:
< ((log(mm)) 1/2)
9:
N + O 2
10:
3 < O(heriisc(A) log (m)) Generate a Gaussian matrix G E |=*,,, where each column is sampled from (0, 4n)
8 O(enyN log(m/6))
11:
12:
MAINTAIN ds Is. G, n, n*)
b Algorithm 6 b Algorithm
13:
14:
for t = 1 + N do
9V: ds. QUERY()
Algorithm 6, 9v. (I V, Vz)
Let μ > 0 be maximal such that max x + de + μ 9v, oloo || U2 4 gv, ] Algorithm 11
17:
FINDBOUNDARY (v,9))
18:
9: min(f, u1 9V: for i = n do
Dr R"
19:
20:
if' [24 + un + I 1 and [. + ur,1 < 1 then
21:
We will add e, into V in an implicit way via data structure ds
The explicit way can be found here
Algorithm
ds. UPDATE((e)
Algorithm
23:
end if
24:
end for
25:
U++1 + Dt
26:
if Hi E [n] : I + 11+1.l = 1Hl 2 n/2 then
27:
A4 > 3 then
return fail
Case of Lemma E.2
else
30:
return new +- + 1441
Case of Lemma E.2
31:
end if
32:
end if
33:
end for
34:
return fail
D Case 3 of Lemma E.2
35:
end procedure
E. Partial Coloring
E.1. Fast Algorithm for Approximating Norms
Algorithm 5
1: procedure FASTAPPROXNORM Rmxn V R 82 E (0,0.01)
Lemma E.
2: Let R E xx denote random JL matrix with O(e, log(m/52)
Either Definition B.2 or Definition B.
3: Compute (1 V V V)R
This takes O(nrr) time
4:
t maxje[m] ||a] VTV)
> This takes ((nzz(A) time
5: return r)
6: end procedure
Here in this section, we present an subroutine used as a tool to get fast approximation to the row norm of a matrix, based on
27

---

Discrepancy Minimization in Input-Sparsity Time
the JL lemma. The goal of this section is to prove Lemma E.
Lemma E.1. Let V E f where 8 S n. and E TRxx.. For any accuracy parameter 61 E (0, 0.1), failure probability
61 (0,0.1), let r = O(ei" 2 log(m/ )))), there is an algorithm (procedure FASTAPPROXMAXNORM in Algorithm 5) that runs in (((nnz(A) + n²) r) time and outputs a number dj E E such that
(1 E1)
max jm
|a -1-V (1-viv)ll
holds with probability 81-
Proof. Let Re Rxxr denote random JL matrix. The running time from computing
Computing V R takes n²r time.
Computing VT (VR) takes n²r time.
Computing AR takes nnz(A)r time.
Computing A (VT. (VR)) takes nnz(A)r time.
Computing (AR AA (VT. ( for all j [m]] This takes (mr) time.
Taking the max over all the j E [m]] This step takes ((m) time.
The correctness follows from Lemma (Lemma B.8) directly.
E.2. Correctness
The goal of this section to prove Lemma E.2, which gives the correctness guarantee of the Algorithm 4.
Lemma E.2 (Output Gurantees of Algorithm 4). Let A E mxx be input matrix and E (-1,1)" be an input partial coloring, Let 8 E (0, 0.01) denote parameter. Conditioning the event that V is good and 1j is good. We have:
Case 1. The Algorithm 4 outputs vector x new E IR" such that with probability at least 1/10 - 8 the following holds.
1lo 1;
Hi E [mi] [ n/2;
Let uJ denote the j-th row of matrix A Rmxn for each E [mm]. For all j E [mil, the following holds
(ew new (aj,z)) S Oherdisc((A) llg(m) log 1/2 (m/8)).
Case With probubility at most the Algorithm will output fail Line 28.
Case 3. With probability most 9/10, the Algorithm 4 will output fail Line 34.
Proof.
We start with choosing the parameters:
N = O(n max max(mm)mm m3) 0(n log(m));
and
6 = O(min (log 1/2 (mn), n -1/23)
28

---

Discrepancy Minimization in Input-Sparsity Time
Proof of Case 1. We first prove that for any iteration Note that in 1-th iteration, if we find i-th entry of x: + 1t + Dt reaches absolute value of 1, we add to the matrix V (Line 22). Then in the following iterations, after get the query y (We omit the here for g and V), we have by Lemma F.4 that, g is the distance of original Gaussian vector to the row space of V, thus the i-th entry of will be O. Hence in the following iterations, the entry that we add to i-th entry of u will stay 0. Thus we complete the claim.
[M] no entry of vr It has absolute value larger than
By the algorithm design, the number entries reach the absolute value 1 keeps increasing, and by the condition check of Line 20, we have that
{i E [n]]
| 13 2 n/2.
Then by Lemma E.7 we have that
Vj [m], (a,, x)), 1 s
with probability at least 1/10- 6, where notice that
B mi min 1/2 (mm)), n 1/2} 1/2)/n (logmm)//oomm///// = On 1/2 (m)). (m))))
Thus we have the guarantce.
Proof of Case 2. From Lemma E.7 we know that, there a failure probability at most that,
Aj E [m], Kay, g) (aj, .²) > B.
Thus we have proved the claim.
Proof of Case 3. By Lemma E.8, the Algorithm returns fail with probability at most 4/5.
Thus complete the proof.
Now if we consider the probability of the returning V and 1) are not good, we have the following corollary.
Corollary E.3. Let A E Ruxn be inpul matrix and x E 1" be input partial coloring. Let drinal (0, 0.01) denote parameter. We assume 5 = 1/100 here in the algorithm. Then we have
Case 1. The Algorithm 4 outputs a vector new RR. such that with probability at least 1/10 8 Ornal the following holds,
-|l,.ew| 100 1; 1; Hi E [n]]
n/2: - Let af denote the j-th row of matrix A E Rmxx for each j E [m]. For all j E [mi), the following holds
Kay, x - (az. x)1 S O(herdiso(A)) log(m) log 1/2 logg/²(m)):
Case 2.
With probability at most + Shnat, the Algorithm 4 will output fail at Line 28.
Case With probability most 9/10- Siiaa,, the Algorithm 4 will outpul fail at Line 34.
Case With probability at most 8tnat: the Algorithm will output new with no guarantee.
Proof. Recall Lemma E.2 is conditioning on V and v are good, here we mention the failure probability of these two operations.
By the construction of Algorithm 4, when we call
FASTPROUCCTSSMALRRWSSA...
29

---

Discrepancy Minimization in Input-Sparsity Time
Line set 01 / Also when we call FASTAAPROXMANOOM(AA we set 82 0rinal/2 22
Thus, we know
Pr[V, good] 2 òfinal.
(4)
and use "V, 77 not good" to denote the complement event of "V, good", then we have
Pr[V, not good] I Óiinll
(5)
Proof of Case 1. By Lemma E.2, we have
Pr[case happens
V, good]
> 1/10 - 8.
(6)
By basic probability rule,
Pr[case I happens]
Prfcase
happens
V, good!
Pr([V good!
+ Pr[case
happens
V, not good] Pr[V, not good]
2 Pr Pr|case| happens V. good
Pr[V, good
2 (1/10 - 5) Pr[V, 7) good]
2 (1/10 - 5) (1 - Ornaa)
2 1/10
dänal-
where the second step follows from Pr[ 2 0, the third step follows from Eq. (6), the forth step follows from Eq. (4).
Proof of Case 2. Then by Lemma F.2, we have the case happens with prohability at most when conditioning on V, 1 are good, i.e.,
Pr|case 2 happens V, good] 6.
(7)
By basic probability rule,
Prfcase 2 happens]
Pr|case 2 happens
V, good] Pr(V, n good]
Pr|case 2 happens
V/ not good] Pr(V. not good]
S Pr|case 2 happens
V, good] + Pr[V, v not good)
$ + Pr[V, not good]
S + 8final
where the second step follows from Pr[ < 1, the third step follows from Eq. (7), and the forth step follows from Eq. (5).
Proof of Case 3. By Lemma E.2, we have the case happens with probability at most 9/10 conditioning on V and is good, i...
Pr|case 3 happens
V, good] < 9/10.
By basic probability rule,
Pr[case 3 happens]
Pr[case happens V, good] Pr(VV 1 good
Pr[case happens V, not good] Pr[V, n not good]
Pr Pr[case happens V. good PriV, n not good]
9/10 + Pr(V, not good]
< 9/110 + danal-
where the second step follows from Pr[ < 1, the third step follows from Eq. (8), and the last step follows from Eq. (5).
30

---

Discrepancy Minimization in Input-Sparsity Time
Proof of Case 4. This happens when least of the returning V and v is not good, and the algorithm returns wuew Line 30. By union bound we have this happens with probability most
Pr|case happens] S drnaa-
E.3. Iterative Notations
Here in this section, we introduce some notations to be used in later proofs. We first define the matrix Vi we maintained as follows.
Definition E.4 (Matrix V of each iteration). For all [T], define Vi to be the matrix forming orthonormal basis which implicitly maintained in the MAINTAIN data-structure at the start of t-th iteration. For t = 1, we define V1 to be generated from CESTPROJECTTOSMALLEE
at Line 5 in Algorithm 4.
We then define the Gaussian random vectors related to the above Ve,
Definition E.5 (Random Gaussian vectors). For all [T), in the 1-th iteration, We define &: R to be random Gaussian sampled from (0,, 1). We define vector gv. to be generated by query the MAINTAIN data-structure Line 15 in Algorithm 4. By Lemma F.4, we have
gv. = Vi Vi) gr-
And we define Øt to be the vector rescaled from Iv, at Line 18 in Algorithm 4, that is,
g. == min p} gv.
Through the whole Algorithm 4, we iteratively maintain vector E R to accumulate the random Gaussian vectors of each iteration. We formally define it here follows.
Definition E.6 (Accumulated maintained vector). For all L [T', we define the accumulated maintained vector un E R be as follows
U++1 == Ue + 9t-
For the case that -= 1, we define = Oz-
E.4. Upper Bound for the Inner Products
Here in this section, the goal is to prove Lemma E.7, which gives the upper bound of the inner products of the output vector with the rows of input matrix.
Lemma E.7 (A variation of Lemma 4 in (Larsen, 2023)). Let B O(eny N Vlog(m/5)). For any input matrix A E R and any vector x E (-1,1) 1)", let af denote the i-th row of A. Let uN+1 E R denote the vector u E R in the last iteration of Algorithm 4. Then we have that,
Pr[vi E [m], uN42)l < 3 2 6.
Proof. To prove the lemma, we first fix E [m] here. Then for 1-th iteration of the outer for-loop (Line 14 in Algorithm 4). We let gv, be defined as Definition E.5. For simplicity, sometimes we use 9: to denote gv, if it is clear from text.
For the I's that Algorithm returns fail before the (-th iteration, we define gr = RR.. also define cumulative vector
Ue = D( Zi- Then we have that
(as, u+) =
Σ (as 9j). j=1
31

---

Discrepancy Minimization in Input-Sparsity Time
Now condition the previous iterations and look into the (-th iteration, we generate vector & R2 such that every entry is drawn ii.d. from NV 1). Then have for any & 0, we have
(as (I Vx))) > 4 2 [r[ u) (as, (1 ( (V))) > E
2 Pr[](a,,9)) gr) > E
where the first step follows from min p S 1, the second step follows from Lemma F.4. We also have the following
c. C.(az. (I - V Vi)g) ~ N(0,c=aa,(I - 1) by the linearity of the distribution. We can bound the variance in the following sense,
(I V S 2tp
by the definition of 77-
Let 3 >> 0 denote some parameter. Thus using Claim A.5, we have the following
(rs gtوl > 8 & Pr[le (a,, (1 V7 Vi)g) > 3]
< eexp(-(en) 2B2/2)
Finally, since the di independent from ut's for i [t 1), we have that
Bl(ai, 9()
Uy 1x-1, 1.... .......,,....................... uil = 0.
This follows by the fact that we define a in Line 17 to be
arg max{|l= + + ugelloo ||x + us pg: 1lo 1. 120
Thus we have that, the sequence (a;, 91) ........ (a,.g) becomes martingale difference sequence (Definition A.7) with respect 01y..ry Mr. Then by Theorem A.8 have that with probability at least 8, the following holds
NV
Ka, uN++1) =
(a, 9.)1
$ 20n 112N (1/8)
< 100em N lg(1/)),
where we set the parameters in Theorem A.8 to be
2 and c 2/22
Then we set 5/m and let 3 100cn log(m/5), we have
Pr[k(a, s $ 2 5/m.
The above implies that Applying a union bound over all the E [m], then we complete the proof.
Pr[laa, uN+1)l 8] 5 8/m
32

---

Discrepancy Minimization in Input-Sparsity Time
E.5. Upper Bound for the Failure Probability
Here in this section, the goal is prove Lemma E.8, which gives the upper bound of the probability that the algorithm returns fail.
Lemma E.8 (A variation of Lemma 5 in (Larsen, 2023)). For any input matrix A E R=x" and any vector I E [0, 1]", the probability that Algorithm 4 returns fail at Line 34 is most 4/5.
Proof. The basic idea of the proof is that, after many iterations (N in Algorithm 4), we have the expectation of || + ull2 large enough. Hence lots of entries of x + u will reach the absolute value of 1. We denote the number of e₁ 's added to Vi in Line 22 through the running of Algorithm 4 to
Recall we define gr to be generated in Line 15 of Algorithm 4 (Definition E.5). We notice that, we add E 9t or μ gt to U, in Line 25. Here in this paragraph, we first assume that, add μ 9t, i.e. μ Recall we generate 1 in Line 17 of Algorithm 4 to be
# arg px5 max || + ue + μ. gelloo: | + u - p -- gelloo 1}.
Thus have that in Line 20 of Algorithm there must be at least one entry i [n]] satisfying that
xy + ue,s + gt.sl and xy
ug,s
We define P: to denote the probability such that the algorithm never return fail before reaching t-th iteration and μ < in this iteration. For any E [n]] and [N]. we define the following event by E the index satisfies
[xy + ues + por.al = 1 and |x + me <
in Line 20 of the t-th iteration.
By the symmetry of the vector ge (Since gi is Gaussian, ge and -ge are equally likely conditioned on V/),, we have that
{i E [r]] E.e holds} 2 pt/2.
We denote the number of e; added to Vn in Line 22 through the running of Algorithm 4 to be R. And we denote the number of rows added to V, by rr. By the analysis above, we have that
E R
E
Pr/2.
By the construction of our algorithm, no than et's will be added V through the algorithm running, thus have
Σ Pt
2 R <
2n.
Now for each iteration E [N], we define to be the vector added to us at Line 25 of Algorithm 4. Here we note that after N iterations,
N
UN+1
ge
And this is the final vector output by the algorithm (if it doesn't return fail).
We have that:
|||| + uN+1 [2 = E|il +
gele
33

---

Discrepancy Minimization in Input-Sparsity Time
N
|
Bllgg 12)
(9)
where the first step follows from the definition of and the second step follows from Elgelg....., 0.
Recall we define the Vi to be the matrix V at the start of t-th iteration" 10 (Definition E.4), We denote the original Gaussian before projection by & (Definition E.5).
By Claim E.9, we have
El| ge [2] 2 (1 - 8) .) nn/4 n/4-B(RR è 22
By Claim E.10 we have the lower bound of the expectation of It
E 2 0.63n.
Using Claim 1.11, we obtain
Pr[R 2 n/2] > 0.2.
When R n/2. Algorithm 4 must terminate and return the neew in Line 30. Thus we have that, the probability of terminating and returning fail in Line 34 is at most 4/5.
Thus we complete the proof.
E.6. Lower Bound for the Vector after Projection
Here in this section, we prove the following claim, giving the lower bound of the projected vector gt-
Claim E.9 (Lower Bound for the projection of projected vector gr). We define R to be the total number ofe'ss e4's 's added V in Line 22 through the rumning of Algorithm 4. We define Pt denote the probability such that the algorithm never return fail before reaching t-th iteration and in this iteration. Then we have that
9 - 8) e 10/-n/4--- 1//- E(R) e²v22 22
Proof. For any E [N], we define the indicators F; to be
F. 1 [m] (ai < <}},,
and Yg to
y= =1 << ct.
Then we have that
E [1 1 = E[F.Y ||T V,T,
V.) 8:122 + F1(1 Y;)o² 1[T
----VV V. V.) 1
> [L -
-1([11 -1(1-V,
Vn, Vi) 1
2 2 [[ V.) ge - E| VVTV
V.) g.
where the first step follows from the definition of F; and G₁, the second step follows from 2 V,TV,) Vo) gel13 < 0. and the last step follows from splitting the terms.
Using Sauchy-Schwarce inequality, we have that
B|y |(T - V, V.) 11
E[
EII VTTV) gell))
Note that, in design our algortithm, we maintain this matrix V implicitly in MAINTAIN data structure.
34

---

Discrepancy Minimization in Input-Sparsity Time
Recall define Y, be indicator, thus have that IE [E{??] [B[ Since (I- Vo) is a projection matrix, we have
g+ z (I V, V/) gell2. B|Y, 11(7 V))
(10)
Thus, the following holds
Vi) 8el181 E Y
El
&
Pr E
8r 11
where the first step follows from Eq. (10), the second step follows from the definition of Pc-
For any E [ra], we denote the i-th entry ge by gr,a- Note that gr, ~ No, 1) for all E [r]] and t E [NT] And all gr, 's are ii.d. Thus have that
E
El
8i, )
1=1
E
(g.. g
where the first step follows from the definition of gr, the second step follows from that gr, are i.idd For the terms that 8 o J, we have that
E Elgi E B = 1. For the terms that = j. by the 4-th moment of the normal distribution, we have
E 3.
Thus we have
Ellgg [5] S n(n - 1) + 3m $ 2n?
Hence
B|y; ||(I - V1 Vi) g 111121 S 2pm
Also we have that
E[F: [I(T V Vi) g.l2 Pr(F: B V. Vi) g:l12)
Pr(F. 1 dim dim(Vi))
= Pr[F, 1] (1--(nnn-- --diim(mV))))
where the first step follows from the definition of expectation, the second step follows from the property of the vector (I VV, VV). g. (Since g Gaussian), and the last step follows from the definition of expectation.
Note that for any t E [AV], have that
(V, < R + n/4
Thus have
E|dim (V:)] < ER + n/4.
Hence we conclude that
El [1] Pr[Fi e? n/4 B(R) è² 2²v 2
We have by Lemma E.7 that
Pr|F; 1-
Hence have
E[1191111 2 (1 - 6) e n/4 E(R() 2 /2pmn.
35

---

Discrepancy Minimization in Input-Sparsity Time
E.7. Lower Bound on Expectation
Here we prove the following claim, which gives the lower bound of expectation of the unit vectors added V through the algorithm rumning.
Claim E.10. We denote the number of ei 's added to V2 in Line 22 through the running of Algorithm 4 to be R. We define pr.
to denote that Algorithm never return fail before i-th iteration and μ < E in this iteration. We assume Pt S 0.005 and < 0.01.
g 2 (1 5) 2 (n-nn/4 E(R) e² 2pmn.
Then we have that
E[R] 2 0.63n.
Proof. By Assumption this claim, we have
B[ 2 (1- 2 nn4 1/4-E((R 2 2pen.
Note that we assume that Pt 0.005 and 5 s 0.01. Then by the above step we have that
9 12
0.99 (n 1 fnnnn/4- 1/4- 0.102n)
0.99 20.6988n - B[R)).
Note here that if P. 0.005, have B[ll [ is lower bounded by 0. Recall that have E Pe S 2n, thus the number of iterations that Pt 0.005 is at most 400n.
Now considering the rest N 400n iterations, it also holds that
[llg 3 2 0.99 e (0.6988n - E[R)..
(1))
Hence we have
||[| + uN+1 1
2 ||>|12 - + (N 400m) 0.99 (0.6988n - B[R)
2 (N 400n) 0.99 200.698n - [E(R)
16 0.99 (0.698n B[R),,
where the first step follows from Eq. (9) and Eq. (11), the second step follows from || S 0, and the last step follows by setting N 16e + 400n.
Notice now that Algorithm 4 will only produce an output such that || + uN+1lloo 1. Thus conclude it happens when B[[| ux+1l
[2) < n.. Thus we have
2 16 0.99 (0.698n - E(R))
By the above inequality, it holds that
E|R 2 (0.698 1.02(L/16))n > 0.634n.
36

---

Discrepancy Minimization in Input-Sparsity Time
E.8. From Expectation to Probability
Claim E.11. [ 0.62n then
Pr[R 2 n/2] > 0.2.
Proof. Here we define Z : R. Then we have the expectation of Z
B|Z] = 7t E[R] - 0.38n.
where the first step follows from the definition of Z, the second step follows from [B[]] 2 0.62n.
Then by Markov's incquality have that
E Pr[Z > a| -
Thus have
Pr[Z > n/2] < 0.388
= -0776
< 0.8,
which implies that,
Pr|Z S m/2 > 0.2.
Finally we have by Z=
== n
that
Pr[R 2 n/2] 0.2
E.9. Running Time
The goal of this section is prove Lemma E.12.
Lemma E.12. For any parameter a E [0, 1). the algorithm (PASTPARTTALCOLLORIG in Algorithm 4) runs in Ó(nnz(A) + + + 2ta + +n (1(((11)))-))
time. Note that w the exponent of matrix multiplication.
Proof. The running time of FASTPARTIAL.COLORING can be divided as follows,
Line takes time Ō(nnz(A) + n²), by Lemma C.2.
Line takes time O(unz( A) + n²)), by Lemma E.
Line 13 takes time O + n??) to initialize the data structure, by Lemma F.7.
Run the following for N O 2 n.) O(n log m) times,
Line 15 takes time 0(n²+a) to query g. by Lemma F.7).
Line 17 takes time (n)) to find y due to Lemma 1.1 (via Algorithm 11).
Line 22 takes time O (ta) update the data structure, by Lemma F.7.
Over the entire, algorithm we will enter Line 28 at most once. To check the satisfied condition for that only takes mnz(A) time.
Adding them together and by the tighter time for operations of FASTMAINTAIN data structure (Lemma F.10), we have the total running time of FASTPARTIALCOLORINGG of
TRATTPANTA.CCOLLONNG (nnz A) + n² + 2+a + nn (
Therefore, we complete the proof.
37

---

Discrepancy Minimization in Input-Sparsity Time
F. Fast Maintaining Lazy Data Structure
In this section, we provide faster maintaining data structure with the idea of lazy update for the Partial Coloring algorithm. In Section F.1 we provide main theorem of the data structure. In Section F.2. Section F.3, Section F.4, Section F.5 we give analysis for the INIIIALIZATION, QUERY, UPDATE, RESTART procedures respectively. Section F.6 we provide the running time analysis. In Section F.7 give the correctness analysis. In Section F88 we give tighter running time analysis.
Algorithm
data structure MAINTAIN
Theorem F.I
2: members
3:
P R
4: V E Raxn
5: G E 1axN
6:
l
7:
Tq
D total counter for query Ki a counter for update process D kig counter for query process This is a list
8: ki
9: kig
10: W1.-.. WK R"
11: end members
12:
13: public:
14: procedure INIT(V E Rxxn Rxe", RRXN,, K)
b Lemma F.2
hy + 0, Kig f-0
Tg +0
17:
P- VTV
This takes Tmat (n, n,
18:
Let S 11,2...., K}
19:
G E R2 N denote G.,S
Compute G P. G. and let ğ1.
.K denote those new vectors
This takes Tmat (K, n,, n.)
21:
for i + K do
22:
O,
23:
end for
24: end procedure
25:
public:
procedure QUERY(
Lemma F.3, F.4
28:
Kg ki + Ty f- Tg +1
29:
30:
if ki 2 K then
31:
RESTART()
32:
end
return Is. -9N, Dkun w.S. Ih.
This takes O(nK) time
end procedure
35:
data structure
F.1. Main Data Structure
The goal of this section to prove Theorem F.1.
Theorem F.1. For a input matrix V E RRxn with E S n, a matrix G RaXN and a integer K > 0, = there exists
a data structure MAINTAnN(Algoritlm 7) uses O(n²) space and supports the following operations:
INIT(V E pixn GERUX K E N4): It initializes the projection matrix P= VTV e Raxn stores the matrix
For the first K column vectors G, it computes their projection when apply P. It sets counter hi and li be zero.
38

---

Discrepancy Minimization in Input-Sparsity Time
Algorithm 7 Update
1: data structure MAINTAIN
Theorem F.1
2: public:
3: procedure UPDATE(U E IR")
b Lemma F.5
4:
The input vector u is 1-sparse and the nonzero entry is 1
5: ku +- Ry +1
6: W - (1I P)
Σ i=1 w:w, y
This takes (nn))
7:
Wkk
2|12
8: if ku 2 K then
9:
RESTART()
10: end if
11: end procedure
12:
13: private:
procedure RESTART()
Lemma F.6
15:
P P Σ WmW!
This takes Tmat (n, K K,n)
16:
Let = Tq. Tax
K + Tqg
17:
Let E R denote G.,s
Compute G p. G and let 91,
,9K denote those new K vectors
This takes Tmat (K, ni n)
19:
ky
0, hn f- 0
20:
for = K do
21:
- On 22: end for
Reset to an all zero vector
23:
end procedure
end data structure
sets Ty be zero. This procedure runs in time
Tmaa (n,, (2, n) + Tmaa (K, n).
QUeRY(): output (T V V)g where g E R is the next column vector in G to be used. The rumning time of this procedure is
OnKK) time, lig E JK- - 1]
- Tmat (n, k n) time, if ku K
UPDATE(U E R"): takes an 1-sparse vector u IR" as input and maintains by adding w into next row of V (according Algorithm w w/|liipp where ü (I (T-VT VT-VVV Vyu. obvious that w LVV. The running time of this procedure is
-((K) time, kh, [K- 1): Tmat (n, n, time, if kn K.
RESTART(): It updates the projection P = VTV, generates K fresh Gaussian vectors by switching the batch of Gaussian vectors we use by Tg. and compute their projections when apply P. It reset the counter ki and ky to be zero. The running time of this procedure
Tmatt (n, K, n.)
Proof. It follows from combining Lemma F.2, Lemma F.3, Lemma F.4, Lemma F.5 and Lemma F.6.
39

---

Discrepancy Minimization in Input-Sparsity Time
F.2. Initialization
The goal of this section prove Lemma F.2.
Lemma F.2 (Running time for INIT). The procedure (NIT(V E RR G BEXN K N4) initializes the projection matrix P VTV E R=x". stores the matrix G. For the first K column vectors in it computes their projection when apply P. It sets counter kg and ky be zero. It sets Tq to be zero. This procedure runs in time
maa (n, nl n)) + Tmat (K, n).
Proof.
The rumning time of INIT can be divided into the following lines,
Line 17 takes time Tmat (n, n, n) to compute matrix P.
Line 17 takes time (nn)) generate matrix G.
Line 20 takes time maat (K, n. n) to compute matrix G.
Taking these together, have the total running time is
Maa (n,, n,, + Tmaa (K, n, n).
Thus, we complete the proof.
F.3. Query
The goal of this section to prove Lemma F.3 and Lemma F.4.
Lemma F.3 (Running time for QUERY), The rumning time of procedure QUERY is
OnK)) time, ky [K 1].
mma k, n) time, kf K.
Proof. The proof can be splitted into two cases.
For the case that ki E [K 1), Line 33 takes time O(nk,) (nn) obviously.
For the case that kg K, Line runs time Tiat (n, n)). Thus we complete the proof.
Lemma F.4 (Correctness for QUERY). the procedure QUERY outputs (I VTg where RD is the next vector in G to be used.
72
w
Output vector n n 9k
gha
ku Σ
Wi
glo
i=
Figure 5. The decomposition of the output vector by QUERY. The green composition is the pre-computed factor and the blue composition is the new added ones, these two together form the projection of g onto the row span of V.
40

---

Discrepancy Minimization in Input-Sparsity Time
(1 - VT ghg = g
Span V22
Span V)
Σen wawm 9h, = V22
VT
Span 11)
9 P
x
Figure The Visualization the decomposition. Here we denote the matrix of rows encoded to by V1, the matrix rows not encoded yet by V2. Thus have that, P P= Vi Vi. And assume that, Span(Vi) Span(e=), Span(V5) Span(ey). Thus visualize idea of the decomposition as above. We divide the projection onto SVan(V) into the projection onto Span(Vi (V1) and the projection onto Span(V2) (V2). That is, have V Vg Vs Vi g V22 V22 = Σ cm www, g-
Proof. We divide the rows V E Rxxn, into two parts: the rows that have been encoded into P. and the ones that have not, Without loss of generality, note the first & - ky rows are encoded, and the last k. rows not. Thus have that
II
V)g
g
0:0; g
t-kn
ky w; w;w; g
g
W g,
where the first step follows from split the multiplication, the second step follows from split the summation, and the last step follows from the definition of y and the construction P. Thus we complete the proof.
F.4. Update
The goal of this section to prove Lemma F.5.
Lemma F.5 (Running time for UPDATE). The running time of procedure UPDATR
OnK))) time, if bi E [K- - 1].
(n, k n) time, if kn K.
Proof. For the UPDATE procedure, the running time can be divided into the following lines,
Line 6 takes time O(nK).
Line takes time Onn).

---

Discrepancy Minimization in Input-Sparsity Time
If k reaches K, Line 9 takes time Taat (n, K,n) TTmmat ( n, n))
Thus we have that, & doesn't 't reach K, the running time is
(
reaches K, the running time is
Taaa (n1, K + Tiae (K, n, n).
E55 Restart
The goal of this section is to prove Lemma F.6.
Lemma F.6 (Running time for RESTART). The running time of procedure UPDATE is
( (K, n)).
Proof. For the RESTART procedure, the running time be divided as the following lines
Line 15 takes time Tmat (n, K, n).
Line 77 takes time (n
Line 18 takes time Tiaat K, n. n..
Adding them together, we have the runnning time is
Tmat (n, K, n) + Tmat (K, n, = O(Tmat (K, n, n)).
F.6. Running Time of the Maintain algorithm
The goal of this section is to prove Lemma F.7.
Lemma E.7 (Rumning time of FASTMAIN Let N On)). For any parameter [0, let = where is the dual exponent of matrix multiplication. For any input G E _R and input b {0, 1 such that only entry of each row of b is 1, the procedure FASTMAINTAIN (Algorithm 8) runs in time
On + n 2+a + n1²-a)
For the current R. 2.373 and a Rs 0.31. Due to the above equation, if we choose the min(a, 1/2), then the running time can be simplified to
O + +n3-a).
Remark F88. Instead of using provide a tighter analysis of Lemma F.7.
the w())))))) function in Table 3 in (Gall & Urrutia, 2018). In Lemma F. 10,
Proof. The running time can be divided as follows.
Line takes time Tmaat (n, n., n1) Tmat (K, n, n) 0( n2) initialize the data structure.
Run the following lines for N O(n) times (We ignore the condition restart here):
Line takes time (nn)) On1++a) to query for g-
42

---

Discrepancy Minimization in Input-Sparsity Time
Line 7 takes time O(nK) ( time update the data structure.
The above runs ( time in total.
For the restart condition, we note that, UPDATE is called for O(n) times, so we will call RESTART for O(n/K) = ( times, each time will take (nn²) time for restarting. The condition that QUERY calls RESTART is as the same. Thus we have the restart time bounded by O(n3
Combining the above together, we have the running time of MAINTTIN is
O(n" + n 2+ + n n
E7. Correctness
Algorithm 8 'he purpose writing down SLOWMAINTAIN is proving the correctness FASTMAINTAIN, See Lemma F.9.
1: procedure FASTMAINTAING E 10, G R n, N)
2: ds. G, K)
b Algorithm
3: for / = = N do
4:
9t. 6 ds. QuERY)) do
Algorithm
5: for i
6:
if bi, then ds. UPDATE(es)
7:
> Algorithm 7
8: end if
9: end for
10: end for
return "1.-.' NNN
end procedure
13:
14: procedure SLOWMAINTAING E {0, 1) .
Ge gox N)
15: for f = 1 N do
16:
9:. - -1-V VVG., for i= 1 n do
G.,t is the 1-th column of
17:
b then
Add e; to according Algorithm and update V
20: end if
21:
end for
22:
end for
23:
return "..""
24:
end procedure
The goal of this section is to prove Lemma F.9
Lemma F9,, For any input b {0, 1J and G E R the N vectors outputted by procedure FASTMAINTAIN (Algorithm 8) are exactly same as the N vectors outputted by procedure SLOWMAINTAIN (Algorithm 8).
Proof. For all e [N], we denote vectors output by the two algorithms by Js.F for FASTMAINTAIN and 9s,8 for SLOW- MAINTAIN.
Induction Hypothesis. For any t E [N], we have that JG,F 9s,s for all i e [t- 11t--] 1).
Proof of Base Case. For the case that i 1, we have by Lemma F.4 that
91.F = (1 (1- VVVV = 91.9.
Thus the base case holds.
43

---

Discrepancy Minimization in Input-Sparsity Time
Proof of Inductive case. For the inductive case, we prove it by the following steps. We first notice that, with the binary matrix b, we have added some vectors into V through the procedure when it reaches 1-th iteration. We divide it into the following two circumstances:
No vectors added to V after the last query of 9t-1- Since no vectors are added to V after query of 9t-1, the V stays the same when querying the dt. Thus by Lemma F.4, we have that
9i,F VV-VVV)G., 9i,8-
Hence we have the correctness.
There are vectors added to V after the last query of 9t-1- If there's vectors added to the matrix V, then the FASTMAINTAIN calls the UPDATE for some times, and added some vectors into ds. Without loss of generality, we assume the UPDATE never calls RESTART. Then we have that, new vectors are encoded as in the ds. We divide the rows into
Rows added before querying 9t-1, denoted the rows as the first Wo ones.
Rows added after querying 9t-1 and before querying Jt. denote the set as the last W ones.
We denote the Gaussian vector g, Thus have that query (I - VTV) as follows,
Wo+W,
9t.s = (1 V)g.s = 8t,5
Σ
wissw;,sBe.s
wi.sW,,BBt.s
iE[Wo]
f=
And in the FASTMAINTAIN (Algorithm 8), when we call QUERY, we divide the rows as the ones encoded into P and the ones not, that
Σ
W.FWW, F.t.
9t.F = 8t.F - Ft
iElkul
we denote the rows have been encoded into as the first rows. We have that
Ft.F
Σ
wiF.
sEld
By the construction of the procedures, we have that
+ Ki Wo + W1.
and
W.FF = Wi,5
for each [e + ku]. And by the using of the counter Ty in the ds, we have that
Ft,F Bt,S-
Then by Lemma F4,, we have the f-th query
ds. QUERY())() (I -VTVVGG..
Thus we complete the proof.
F.8. Tighter Running Time Analysis
The time analysis of Lemma F.7 is not tight. We can further improve by using function w(s::)).
44

---

Discrepancy Minimization in Input-Sparsity Time
Lemma F.10 (A Tighter Analysis of Running time of FASTMAINTAIN). Let N = O(n). For any parameter [0, 1].
let K n². For any input G RaxN and input b E {0, 1) such that only one entry of each row of b is 1, the procedure FASTMAINTAIN (Algorithm 8) runs in time
O( + + + )
For the current w(:)))) function (see Table in (Gall & Urrutia, 2018)). We can choose 0.529, then the running time becomes
Onn2.3))
For the ideal w, we can choose 0.5, then the running time becomes n
G. Implicit Leverage Score Sampling Algorithm
In this section, we present two crucial subroutines. based on it.
That is, leverage score approximation and a fast sampling algorithm
G.1. Leverage Score Approximation
Here we present the following algorithm, which providing a fast leverage score approximation.
Algorithm 9 Implicit Leverage Score Computation
procedure IMPLICIILLEEERACESCCORAAA Rmxn R=x" Eg (1),
Lemma G.2 The goal of this procedure is to compute constant approximation
2:
3: $1 < ((,c²n)
4: Choose S₁ E IR to be sparse embedding matrix
Definition B.4 It takes Ō(E,1 mnz((A) time. It takes O(e,2n') 3nd) time
5: Compute (S1 A)
6: Compute M (S1 A). (I (V-VVV)
7: Let R E Rx denote the R of QR factorization of M
8: 82 + (log(mm/d))
9: Choose S2 R nx* to be a JL matrix
b Either Definition B.1 or Definition B.2 N E 8 b It takes ((nz((A) time
10: Compute N + (1 - V)R-'S S2
11: for j = 1 + m do
12:
Compute 3; + [ee A]
13: end for return
o = O(o)). [m]
15:
end procedure
Definition G.1 (Leverage score), Let A E Rmxn The leverage score A is vector (AA) m satisfying
o(A); = a A) A) aj
where a, denote the i-th row of A.
The above algorithm provides approximation all the leverage scores of matrix A(I VTV), see the following lemma. Lemma G.2 (Implicit leverage score). Given matrix A E Rm and matrix V R there is algorithm (procedure IMPLICITLEEERGEESCOO Algorithm 9) that runs in Ö ((nnz(A) n²)) time and output vector ő R", such that, á is an approximation of the leverage score of matrix A(T - VTV), Le..
with probability at least 1 1 d,. The Ô hides the log(n/ 6a) factors.
Remark G.3. The only difference between classical statement is, in classical there is one input matrix A. In our case, the target matrix is implicitly given in a way A(I - VVTVV, V). and we' re not allowed to formally write down A(I - VTV. The correctness proof similar as literature (Clarkson & Woodruff. 2013; Nelson Nguyên, 2013).
45

---

Discrepancy Minimization in Input-Sparsity Time
For our task, we only need an overestimation of the leverage score. We believe that the two-sides error might have fulure applications, therefore, we provide two-sided error proof.
Proof. We follow an approach of (Woodruff, 2014), but instead we use a high precision sparse embedding matrix (Nelson Nguyên, 2013) and prove two-sided bound on leverage score.
Correctness.
Let Sj be sparse embedding matrix with s = O(E,²n poly (g(nn(eo8g))) rows and column sparsity O(e log(n/6)). We first compute M := (S14) (I V), then compute the QR decomposition M = QR.
Now, let S2 E Rax matrix with 82 = ( log(m/5.) )) each entry S2 is i.i.d. A\O, 1/82) random variables. Then we generate sketched matrix N == V)R S2. Set ōj (ee] N) for all j E [m]] We argue ōj good approximation to j--
First, with failure probability at most 6 /mm we have that ē; E (1 + (o) |e] A(T - ((T--VV)R-- R via Lemma B.8. Now, it suffices to argue that lee] A(I V VTV) approximates ||e] U13 well, where U E Ruxn is the left singular vectors of A(I - V V). To see this, first observe that for any æ E R".
||A - VV
2012 = (1 + ex) ||| - -V
(1 + 6,) ||
(1 (z) ||=122
where the first step follows from Lemma B.10, and the last step is due Q has orthonormal columns.
This means that all singular values of A(I - V V)R- are in the range [1 - Eor 1 + E.]. Now, since U is an orthonormal basis for the column space of A(T - VT. A(T - VTV)R-1 and U has the same column space (since R is full rank). This means that there exists change of basis matrix T' E _ with A(1 - VV V)R 'T' = U. Our goal is to provide a bound on all singular values of T. For the upper bound, we claim the largest singular value is at most 1 + 2c,, to see this, suppose for the contradiction that the largest singular is larger than + 2e, and let v be its corresponding (unit) singular vector. Since the smallest singular value of AR- is least E.. we have
||([1 V V)R Tul
3 2 (1 E T| 2
(1 E )1 + 2Ea)
1,
however, recall A(I VTV)R-'T- = U. therefore ||(II - (VV--VV)R--TR = 1U0l =111|2 = 1, contradiction.
One can similarly establish a lower bound of 2c.. Hence, the singular values of T are in the range of [1 26,; 1 + 2r This means that
|ee] AQ]A V UITTUT-11
= +1 2c,) ( U13
(1 + 26,) o(A(( - (V]--VV)),,
as desired. Scaling e, by e./2 yields the approximation result.
Running Time.
We divided the running time of the algorithm into the following lines.
Line takes time Ö(e," nnz(A)) to compute the matrix M.
Line takes time -(c_2nn) compute the QR decomposition of M.
In Line 10, we can first multiply R-1 with S2 in time Ō(c=2n?). this gives matrix of size 82. Multiplying this matrix with (I VTV) takes Ö(n")) time. Note that E RR hence R-1 can be computed in O(z") time.
46

---

Discrepancy Minimization in Input-Sparsity Time
Line 11 loop takes in total (A)) time to compute the output vector T.
Hence, the overall time for computing ((A(T-
- VTV) E R is (( + +
G.2. Fast Subsampling
Here present the fast subsampling algorithm based the leverage score approximation.
Algorithm 10 Fast Subsample Algorithm
1: procedure SUBSAMPLE(B _ E R=X=, EB. (B. (B)
Lemma G.4
2: σ t IAPLICILLEVERAGSSCOREBB V,ōB)
b Compute an O(1) approximatnn to the leverage scores of
B(I V V). ō E IRM
3: Sample a subset rows of B B(1 - VV with proper re-weighting according to approximate leverage score
4: Let D denote the diagonal sampling matrix such that Pr(B DDB (l+ -B BB 1-2119
5: return D
D DER Rmxm
6: end procedure
Lemma G.4. There is an algorithm (Algorithmm 10) takes B E Rmxx and V E R as inputs and outputs a diagonal sampling matrix D with ||laa = O( -22 n log(n/68)) and runs in time
((nz((B) + n²))
Here Ô hides the log(n/88) factors Here w is the exponent of matrix multiplication. Currently, w RJ 2.373.
Proof. We first approximately compute the leverage score, i.c., gives an a(Ap-xpppoiniaation to all leverage scores via Lemma G.2. Then run we samples number of rows according to the leverage scores, using Lemma H.2, we can show the correctness.
H. Sampling a Batch of Rank-1 Terms In this section, we give sparsification tool for the matrix that has pattern ATA A.
We define our sampling process follows:
Definition H.1 (Sampling process). Let и = A.A. Let Z 3- (A)/n,, suppose sample with replacement
independently for rows of matrix A, with probability Pj of sampling row j for some 3 2 1. Let je denote the index of the row sampled in the 1-th trial. Define the generated sampling matrix as
T
Oj j0
Pj.
where T denotes the number of the trials.
For our sampling process defined as Definition H.I. we can have the following guarantees:
Lemma H.2 (Sample using Matrix Chernoff), Let co, &n E (0, 1) be precision and failure probability parameters, respec- tively. Suppose H is generated as in Definition H.1, then with probability at least - do, we have
cw) H H 3 (1) H.
Moreover, the number of rows sampled is
T= en 2n log(n/60))
Proof. The proof this Lemma is follows by designing the sequence of random matrices, then applying the matrix Chernoff bound get the desired guarantee.
47

---

Discrepancy Minimization in Input-Sparsity Time
We first define the following vector generated from scaling the rows of A,
yj = (ATA)) A) aj
for all E [m]. And for i [m], we define the matrix Y, = Py Uo generated by yj. and we define X;: == Yj - In, where I, is identity matrix.
Based on the above vector and matrix definitions, we define the following distributions:
We define a distribution y for random vector: For y E RR, y ~ y, then for each j E [ml] y = yy with probability ps-
We define a distribution Y' such that, For Y E Rnxa, if ~ y, then for each E [m]] Y Y, with probability Pj-
We define a distribution X such that, For E gaxa, X X, then for each j [m]. X; = Y, In with probability Pj-
Using H = A A, we write the y
Vj H-1/2 aj.
We notice that,
H 1/2 ajaj H 1/2
1=1
j=1
H - 1/2
aja ) 1/2
1H11/2(1 = In.
A)H 1/2
(12)
where the first step follows from the definition of yj. the second step follows from reorganization, the third step follows from definition of (j. and the last step follows from the definition of H.
Besides, we notice the the connection between the norm of yj and the leverage score of A:
y 112 = a3 (AT A) A)-'a,
(A)
(13)
Here we denote the index of the row that we sample during 1-th trial as j.. note that je E [m]. for all i E (T]. Unbiased Estimator. For a matrix X ~ X. here we show that X has the expectation of 0, we note that
E X
X
=
E Yau
M
In
1
Uハı ) In
Pj
Pj
j=1
where the first step follows from the definition of X, the second step follows from the definition of and the definition of expectation, and the last step follows from Eq. (12).
Upper Bound on |X]|| To give an upper bound of || we first provide an upper bound for any ||Xy|| then the upper bound of |X| follows immediately. We note that,
X Y J.
48

---

Discrepancy Minimization in Input-Sparsity Time
S1+ ID
1 + [u,u]
Pj
n 1
5 1 1+
3. (A)
1+ 3
where the first step follows from the definition of x,. the second step follows from triangle inequality and the definition of Ins the third step follows from the definition of Yz. the forth step follows from Py 2 B o (A))/nn /nd and the definition of &g norm and the last step follows from Eq. (13).
Bound on || |[X X|II- To upper bound the spectral norm of the matrix, we first provide the upper bound of the expectation of the matrix X T X. We compute the matrix expectation:
E
x,]
30
Mie M Mre Miy [
= In
E
E
U/ -y
pj.
Mic my
Pse
m
(A)
I +
yoys ) 2T
Pj
j=1
m
n
1
In
1=1
n1 3 1)ln:
where the first step follows from definition of X. the second step follows from Eq. (12), Eq. (13) and the definition of
expectation, the third step follows from pj 2 8- o, (A)/n, and the last step follows from Eq. (12) and factorising.
Thus we upper bound the spectral norm of E ys. -y [X] X5,] as
n 1.
E
U/ w
B
Put things together. Here we define W Σi=1 X5. We choose the parameter
7 1+ n
0²
n 3
-1 1
Then, we apply Matrix Chernoff Bound as in Lemma A.9:
P||]||||| 2 co]
Te
2n exp
n/3 - 1 + (1 + n/3))o/3)
-nn exp(-Ted) -(8/n))
where the last step follows from that we choose T = 0 2n lloooo/nnn))) Finally, we notice that
T
1
1
W
Ui. My.
T
Im)
T
Pje
49

---

Discrepancy Minimization in Input-Sparsity Time
-H 1/2 -/2 1
_ 1/2
In
T
Pi.
=1-1/21111 1/2 -n-
where the first step follows from definition of W, the second step follows from Vj. H 1/30, aj., and the last step follows from definition of H. Since
1/2 1/2 Inll S c0
Thus, we know that
(1 - c0)4n 1/2 1 (1 en
which implies that
(1-60) H 3 H (1 + H.
Thus, complete the proof.
Boundary-Seeking Subroutine for Partial Coloring
In order to find the proper step size in the Partial Coloring algorithm, we propose the following subroutine.
Algorithm 11
1: procedure FINDBOUNDARY(A R"" b IR*)
Lemma I.1
2: Compute intervals [z4, 34] such that z4, y/ are the two boundaries of -1 S aıu-b; S 1, C.g. U4 1=1 b+1 and 2; S Vi, for all i [n]
3:
Compute n intervals [mn+is Dn+s] such that ra are the two boundaries of -1 S a, + b. $ 1, e.g., 24,36
(b,-1 -bb-1,-b-11 and F; & yı, for all i E [n]
0,
4:
Linear scan the -1. ................................ J2. find the index u such that u + max yon. Linear scan the r1. yon. find the index e such that +- min hee
5:
6:
if then
7:
if [u| S |o| then return
8:
9:
else
10:
return u
11:
end
else
return fail
14:
end if
15:
end procedure
Here we illustrate the idea of this algorithm with an example in the following Figure 7.
Lemma I.1. There is an algorithm (Algorithm I1) that takes two vectors a, E TR.", and outputs an positive number μs E IR such that p is the number with the largest absolute value satisfying that
max(llu a + blloo || a - -blloo} =
And runs in time (n).
Proof. Running Time. The running time of Algorithm 11 can be divided into the following lines,
-Lnne takes time O(n) to compute the æ;, ys 's for [n).
50

---

Discrepancy Minimization in Input-Sparsity Time
= p
a1
+ b1
μ 01
b1
02
b2
1
b1
b2
16
01
01
11-02 02
+1
02
81
02
02 + b2
(a) The lines of constraints our example
y
C2
Y/2
.3
y
C44
y4
U
(b) The feasible intervals
Figure 7. Here give example of our Algorithm 11. The algorithu is looking for the intervals make every constraint (lw- +bb,l or ja bs| < 1) hold, so we have 2n lines in total (n is the dimension). Here in the example, we assume v 2, so we have 2n 4 lines in total. Thus have intervals, and taking the intersection over them, we get the interval (u, v). Figure (a) shows the lines of the constraints we have, the green area shows the feasible region. Figure (b) shows our idea of taking intersection over the 2n = constraints. (Here
(1, 16) and (0.7, }).)
Line takes time (nn) to compute the ys's 's for i E 1,..,, 2n).
Line takes time (nn) to linear scan the xy for E [2m].
Line takes time (n) to linear scan the y 's for i E [2m].
The part of the algorithm all runs in constant time. Thus have the total running time is
(
51

---

Discrepancy Minimization in Input-Sparsity Time
Correctness. We first prove that, if the algorithm outputs number μ4, then for every i [n], holds that
b, S 1, -1 S and - 1 - + b, 1.
Here we call the feasible region the above question to be M. By the construction of our algorithm we have that,
[ii Vo]
{ar R
1 S μ a, b, S }]
Vi [n]] Vi E (n + 1,... 2m}
and [ii W/] {u R 1 S μ as-n D,-n S 1},
Thus we have that
4= = n [ois wi].
(c(2m)
We note that, if the algorithm outputs a number then it must holds that Recall that we define and to be
S U.
u == max (ee(n)) v == min yi he
thus we have that Recall the output number equals to either u or v, it must stands that
uu, 2) U.
ja E U.
Thus the constraints hold for μ.
Now we prove that
max a + blloo 11 a bbl
Without loss of generality, we assume |u] > lu]. that is, f = u. The case that |u] S |u| is just the same. We first define
j: {i E [2m] u x.
Here we first assume j E [n], that is, we have that
Ip aj - bj 1.
(For the case that j E {n 1,... 2n), we have IN aj byl 1, which is the same to analyse.) Note that, l E U, have that
lu- a. bil < 1, Vi E [M] and 11u a; + b, < 1, Vi E [n].
Thus have that
||u bl1.0 1 and || bllo0 5 1,
which is
max + blloo, || a blloc}
52

---

Discrepancy Minimization in Input-Sparsity Time
Now for the that j (n .,,,, 2n). by similar analysis have that
|| bllc0
and ||p blloo S
which also implies the result that
max + blloo, al a - b =
By same analysis we can have the above result if
Now we prove that, u and = v are the only two case that
ma + biloo l|u bllb0} 1.
Suppose for the contradiction that there exists R such that + and v, and it holds that
max + blloo: ||t a bll50} 1.
(14)
t & 24, then there must exists and E [n] such that
[t a; + bul > 1 or |t a; b,] > 1,
which is a violation of the hypothesis (Eq,(14)). Then for the case that t E Ui since t * u and è & it must holds that t E (u, v). Note we define
== max(aa
v: min
It must holds that
t Fi, Vi [2n], and t Mi, Vi [2m].
Then we have that
It a; + bal <
or |t a; byl 1,
which implics that
max + blloo, || - bl1,0 < 1,
which is violation of the hypothesis (14,(14)). Thus we conclude there is no such L.
If we define to be one of or depending on who has larger absolute value, then is the number with the largest absolute value satisfying that
max + blloo. llu a blloo} = 1.
Thus complete the proof.
Corollary L.2. For the case that ||b]lc & 1, Algorithm 1I always return a number
Proof. If [16]loo 1, then we have that
[bl] < 1, Vi [n].
53

---

Discrepancy Minimization in Input-Sparsity Time
Without loss of generality assume 2 0, then by E [0, 1]. which implies that
b. - d₁
S 0
b. +
and
2
Thus we have that By similar analysis we have
0 E Vil, Vi E [m].
0 [2t, M.l. Vi {n + 1,... 2n}.
Thus have
0 E 4 0 [2t yels
(E(2n)
which means
u +
So it must holds that
U.
Thus complete the proof.
J. Experimental Results
We conduct the experiments to empirically validate the efficiency of our algorithm. We focused our experimental evaluation on demonstrating the improvements achieved through the fast hereditary projection. This is because the lazy update scheme primarily designed leverage fast matrix multiplication. Although fast matrix multiplication theoretically has lower asymptotic complexity, algorithms based on FMM often suffer from significantly large constant factors, adversely affecting their practical runtime performance. Additionally, for practical considerations, the parameters used in the experiments do not strictly follow the theoretical suggestions in the algorithm. Our experimental setup follows the matrix configurations used in Larsen (2023):
Uniform matrices: Every entry chosen independently and uniformly from the set (-1,+1},
2D corner matrices: Sample two point sets P= {pi...., Pa and Q = (q....., Fm independently and uniformly from the unit square [o, 1] x [o, 1]. Construct a matrix with one column per p, E P and one row per E Q; set the entry (i to py is dominated by gt. i.e. (g:, x²) (p), a)) and (gr, v) > (p). y), and to 0 otherwise.
2D halfspacc matrices: Draw P = {pi...., Pn uniformly from j0. 1] x [o, 1] and construct a set Q of m half-spaces as follows: pick a point a uniformly on either the left or the top boundary of the unit square, a point uniformly on either the right or the bottom boundary, and then choose uniformly whether the half-space consists of all points above the line through a and all points below it. Form a matrix with one column per Pj P and one row per half-space h4 E Q: set the entry (i.j) to 1 if pj f,, and otherwise.
Our algorithm achieves substantial speedups with only minor sacrifices in approximation guarantees. The speedup will be more significant once m much bigger than n, as sketching is known to work well in the regime where m >> n.
Our code is available https: /ttt::///hhhaa com www/magiccinuu.....ooo.oaaoooaee int.pissuuunnpttttpssssttt hiwpeetttyydsrepacyyyyieiee 2025.
54

---

Discrepancy Minimization in Input-Sparsity Time
Table Results of experiments on uniform matrices. Here Larsen's 's algorithm Larsen (2023). The runtime is measured in second.
Matrix Size
Sparsity
Larsen's 's Obj. Val.
Our Obj. Val.
Larsen's Runtime
Our Runtime
400 x 400
1.0
54
56
2.98
2.16
400 x 400
0.5
38
42
2.90
1.95
400 x 400
0.1
14
20
2.91
1.90
2000 x 2000
1.0
140
148
345
164
2000 x 2000
0.5
96
99
334
156
2000 x 2000
0.1
46
47
331
152
10000 X 1000
1.0
132
140
378
63
10000 X 1000
0.5
92
97
374
62
10000 X 1000
0.1
42
44
375
62
Table Results of experiments on 2D corner matrices. Here Larsen's 's algorithm is Larsen (2023).
The runtime measured in second.
Matrix Size
Sparsity
Larsen's Obj. Val.
Our Obj. Val.
Larsen's Runtime
Our Runtime
400 x 400
1.0
24
28
2.80
2.15
400 x 400
0.5
30
40
2.79
2.18
400 x 400
0.1
17
18
2.75
1.93
2000 x 2000
1.0
52
60
347
170
2000 x 2000
0.5
83
92
352
169
2000 x 2000
0.1
45
44
350
181
10000 x 1000
1.0
46
52
386
65
10000 x 1000
0.5
76
77
374
60
10000 x 1000
0.1
37
40
375
62
Table 4. Results of experiments on 2D halfspace matrices. Here Larsen's algorithm is Larsen (2023).
The runtime is measured in second.
Matrix Size
Sparsity
Larsen's Obj.
Val.
Our Obj.
Val.
Larsen's 's Runtime
Our Runtime
400 400
1.0
38
42
2.67
2.08
400 400
0.5
30
40
2.70
2.12
400 400
0.1
17
18
2.62
1.89
2000 2000
1.0
50
56
352
174
2000 2000
0.5
75
76
345
171
2000 2000
0.1
38
40
345
169
10000 1000
1.0
62
66
390
67
10000 1000
0.5
71
75
389
68
10000 1000
0.1
33
36
382
64
55

---

Discrepancy Minimization in Input-Sparsity Time
K. More Related Work
Because sketching techniques are pivotal in both linear and semidefinite programming, we first survey this body of work. We then discuss how discrepancy theory has been leveraged in modern machine- learninn applications.
Linear programming Linear programming has long and rich history in both mathematics and computer science. The simplex algorithm (Dantzig, 1947), while foundational, admits exponential worst-case running time. The ellipsoid method brought the first polynomial guarantee (Khachiyan, 1980), but was slower than simplex in practice. Karmarkar's 's interior- point method (Karmarkar, 1984) was major advance, offering polynomial complexity together with strong empirical performance. When the number of constraints d satisfies d = [2(n) (where n is the number of variables), Karmarkar's algorithm runs in (n...) time, later improved to (Vaidaa, 1987; Renegar, 1988) and then to O" (n22d)aaaidyya 1989). Cohen et al. (2019) achieved a time bound of On + 122.5-a/2 + n221/66), where w is the maatiiiimuttilliaaiionn exponent and a its dual. Their techniques were subsequently generalized to empirical risk minimization(Lee et al., 2019; Song, 2019; Qin al., 2023; Gu al., 2025), while Song& & Yu (2021) reproduced the results of Cohen et al. (2019) using oblivious sketching matrices instead of non-oblivious sampling. For tall, dense constraint matrices, Brand al. (2020) obtained running time of ((nd) + poly (d). There are also works studying linear programming in the streaming setting (Chen et al., 2023; Song et al., 2023c; Brand et al., 2025).
Semidefinite programming Two principal families of algorithms address semidefinite programming (SDP): second- -oddrr and first-order methods. Second-order methods enjoy logarithmic dependence on the accuracy parameter c, whereas first- order methods typically have polynomial dependence on 1/e. Among second-order techniques, cutting-plane approaches such as Lee et al. (2015); Jiang et al. (2020c: 2024) solve SDPs in (m + m² + n²)) time, where m is the number of constraints. Interior-point methods based on self-concordant barriers constitute another major line: log-barrier algorithms (Nesterov & Nemirovski, 1992; Jiang et al., 2020b; Huang al., 2022c; Liu et al., 2023), -ybrid-barrier variants (Anstreicher, 2000; Huang et al., 2022c; Liu et al., 2023), and those using the Lee-Sidford barrier (Lee & Sidford, 2014; Liu et al., 2023; Gu et al., 2024a). Notably, Jiang et al. (2020b) obtains running time of O(yr(mmn² + nz)),, and Huang et al. (2022c) shows that when m = ?(n²). an SDP can be solved in Om + m 2+14/) time. First-order algorithms avoid second-order information but pay a higher cost in their dependence on 1/c. Representative results include Arora & Kale (2007); Jain & Yao (2011), 1); Allen Zhu et al. (2016); Garber & Hazan (2016); Allen-Zhu & Li (2017); Carmon et al. (2019); Lee & Padmanabhan (2020); Yurtsever al. (2019); Grigorescu et al. (2022); Song et al. (2023a;c); Chen et al. (2023); Gu et al. (2024b).
Applications of discrepancy theory in machine learning Matousek (1999a); Karnin & Liberty (2019) introduce the relationship of discrepancy and concepts in learning theory such as VC dimension and PAC learning. Chen et al. (2018) introduces a method to learn hash functions via discrepancy minimization. Learning hash functions in content- based image retrieval optimize binary codes to preserve similarity in high-dimensional feature spaces, enabling faster and more efficient image search. Wang et al. (2023) leverage discrepancy minimization for unsupervised graph matching by aligning predictions from classical solvers and neural models. Han et al. (2025) proposed an algorithm for compressing the KV cache recursively using geometric correlated sampling process based on discrepancy theory. Nikolov et al. (2013) investigated the relationship between discrepancy minimization and differential privacy in the context of linear queries over histograms. Quasi-Monte Carlo methods (Lyu et al., 2020; Lyu, 2023) leverage concepts from discrepancy theory by employing low-discrepancy sequences to efficiently approximate high-dimensional integrals and expectations.
56


Reviews:
[{"review_id": "lzgBAcDqeJ", "reviewer": "Reviewer_8esX", "summary": "This paper proposes an improved randomized algorithm for discrepancy minimization problem for real-valued matrices m*nmatrices A with m = poly(n). The paper builds on top of work of Larsen and proposes an improvements to Larsen's algorithm that allow authors to achieve a combinatorial algorithm that runs in input-sparsity time $\\widetilde{O}(nnz(A)+n^3)$  with the same approximation guarantee as Larsen's algorithm. The authors also demonstrate how using Fast matrix multiplication one can decrease the runtime to $\\widetilde{O}(nnz(A)+n^2.53)$. Prior to this work, the best runtime guarantee in a similar setup was O(mn^2).\n\nThe paper introduces novel ideas for each subroutine of the Larsen's algorithm using sketching and score sampling. The authors use sketching techniques to speed up ProjectToSmallRows subroutine of Larsen's algorithm. To overcome $\\Omega(n^3)$ barrier for the iterative Partial coloring subroutine authors propose a clever way to perform updates in batches with a new \"lookahead\" data structure.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's recognition of our contributions, specifically, including significant runtime improvements, novel algorithmic techniques, clear comparisons to existing literature, and rigorous theoretical justifications. We believe our contributions represent a significant step forward in improving computational efficiency and advancing algorithmic techniques for discrepancy minimization. Please let us know if you have any further comments regarding our work. Thank you again for your positive feedback.", "claims_and_evidence": "The authors provide detailed well-written proofs for the claims made in the paper. They present conceptual arguments and brief summary of the key steps and new ideas compared to the Larsen algorithm in the main text, while detailed definitions and proofs, justifying the claims are presented in the appendix.", "methods_and_evaluation_criteria": "No experiments are conducted", "theoretical_claims": "I skimmed through the proofs and they seem to be sound, but I did not verify the details", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The discrepancy minimization problem has been extensively studied in the literature from both existence (to understand minimal possible discrepancy) and algorithmic perspective. Prior to this work best runtime for the real-valued matrices was by Larsen (2023) running in O(mn^2). This paper focuses on an important practical case of sparse matrices and achieves the first algorithm that works O(nnz(A) +n^3) time providing a significant improvement for tall sparse matrices.  This problem was earlier solved by Jain, Sah and Sawhney 2023 for binary matrices, however, their proof does not seem to translate to real-valued matrices easily.", "essential_references_not_discussed": "In my opinion, the paper provides a very nice overview of the related literature and gives a detailed comparison to the related work.", "other_strengths_and_weaknesses": "The problem solved in this paper is a well-known problem with multiple applications and a randomized theoretical algorithm with a sub-cubic runtime is definitely of great interest. The paper introduces several new ideas and provides a nice overview of key novelties compared to Larsen's work it builds upon. In my opinion the results are well-presented and easy to read.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bb2MFBroXt", "reviewer": "Reviewer_N7kM", "summary": "The paper is on discrepancy minimization for real matrices - goal is to develop constructive methods that exploit input sparsity.  Algorithmic discrepancy is a well-studied topic in TCS and there have been many breakthroughs in the last 15 years, starting with Bansal.  Recently there was a result for binary matrices based on sparsity.  This paper obtains an analogous result for real-valued matrices.\n\nThe main technique is basically dig into Larsen's algorithm, identify all the barriers to improve Larsen's algorithm for sparse real matrices.  Then, the idea is to bring in techniques from randomized linear algebra and sketching to save computation.  It is not straightforward since there are several steps involved and naive ways could lead to error accumulation.  Besides carefully using these tools, tightening/modifying the analysis of Larsen, the paper also introduces new techniques including an implicit leverage score sampler and efficiently implementing certain random-walk based rounding step.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and for recognizing the novelty, significance, and technical contributions of our work.\n\n### W1: Connection to existing works\nWhile our work indeed builds upon Larsen's algorithm and Lovett–Meka random walk method, we would like to highlight the significant theoretical and algorithmic advances in our work:\n-  We introduce an innovative implicit leverage-score sampling technique, enabling us to significantly reduce the computational complexity of hereditary projection from Larsen’s original $O(mn^2)$ (or $O(mn^\\omega)$ with fast matrix multiplication) to $O(nnz(A)+n^{\\omega})$. This improvement is crucial, particularly for sparse input matrices.\n- We provide a robust theoretical analysis that carefully manages error accumulation introduced by randomized sketching methods. Such robustness was not previously established and represents a substantial methodological advancement over existing discrepancy minimization frameworks.\n- The lazy-update mechanism we introduce to efficiently implement the iterative Edge-Walk algorithm fundamentally reduces computational complexity from Larsen’s $O(mn^2+n^3)$ to our result of $\\tilde{O}(nnz(A) + n^{2.53})$. This addresses and overcomes a significant computational barrier identified in prior literature.\n\n### W2: Interest to ICML community\nThanks for pointing this out. We argue that the broad relevance of discrepancy theory to the ICML community stems from its strong connections to central themes in machine learning. Specifically, discrepancy minimization intersects significantly with computational learning theory [1,2], computer vision [3], unsupervised learning [4], attention KV caching [5], differential privacy [6], and sampling [7,8]. \n\nMore specifically,\n[1,2] introduces the relationship of discrepancy and concepts in learning theory such as VC dimension, PAC learning.\n[3] introduces a method to learn hash functions via discrepancy minimization. Learning hash functions in content-based image retrieval optimize binary codes to preserve similarity in high-dimensional feature spaces, enabling faster and more efficient image search.\n[4] leverage discrepancy minimization for unsupervised graph matching by aligning predictions from classical solvers and neural models.\n[5] proposed an algorithm for compressing the KV cache recursively using a geometric correlated sampling process based on discrepancy theory\n[6] investigated the relationship between discrepancy minimization and differential privacy in the context of linear queries over histograms.\nQuasi-Monte Carlo methods [7,8] leverage concepts from discrepancy theory by employing low-discrepancy sequences to efficiently approximate high-dimensional integrals and expectations.\nIn the final manuscript, we will explicitly clarify and elaborate on these connections to further emphasize the relevance and significance of our work to the ICML audience.\n\n[1] Matousek, Jiri. Geometric discrepancy: An illustrated guide. 2009\n\n[2] Karnin, Zohar, and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. COLT’19\n\n[3] Chen, Zhixiang, et al. Deep hashing via discrepancy minimization. CVPR’18\n\n[4] Wang, Runzhong, Junchi Yan, and Xiaokang Yang. Unsupervised learning of graph matching with mixture of modes via discrepancy minimization. TPAMI’23\n\n[5] Han, Insu, et al. BalanceKV: KV Cache Compression through Discrepancy Theory. arXiv preprint:2502.07861\n\n[6] Nikolov, Aleksandar, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. STOC’13.\n\n[7] Lyu, Yueming, Yuan Yuan, and Ivor Tsang. Subgroup-based rank-1 lattice quasi-monte carlo. NeurIPS’20\n\n[8] Lyu, Yueming. Fast rank-1 lattice targeted sampling for black-box optimization. NeurIPS’23\n\n### C1: Adding the combinatorial bound to Table 1\nThank you for your nice suggestion. We will add this to Table 1.\n\n### C2: notation $V_{l,*}$ undefined\nThanks for pointing this out. This means the $l$-th row of the matrix $V$. We will define this in the final manuscript.\n\n### C3: Could you adopt a single notation to capture both \\cal{T}_mat(m,n,k) and \\omega(a,b,c)?\nThank you for your insightful question. We use two notations intentionally due to their different emphases and contexts:  We use $\\mathcal{T}_\\mathrm{mat}(m,n,k)$ to explicitly highlight absolute matrix dimensions, making it convenient for describing the algorithm's complexity at a high level; meanwhile, $\\omega(a,b,c)$ concisely captures relative dimension ratios and is widely adopted in algebraic complexity theory, facilitating rigorous complexity analysis. We will clarify this distinction in our revision to ensure readers fully understand why both notations are necessary and complementary.\n\n### C4: page 5 line 223 and on & 234 and on - most of the content seems repeated\nThanks for pointing this out. We will remove the repeated parts.\n\nWe greatly appreciate the positive evaluation of our paper and thank you for your constructive review.", "claims_and_evidence": "Yes - don't see any problems.", "methods_and_evaluation_criteria": "Theory work.", "theoretical_claims": "Yes - don't see major problems.", "experimental_designs_or_analyses": "Theory work.", "relation_to_broader_scientific_literature": "Improvement to the running time of real-valued matrix discrepancy.", "essential_references_not_discussed": "Looks adequate.", "other_strengths_and_weaknesses": "+ves\n\n+ Makes good progress on an important combinatorics / algorithmic question\n+ The techniques are non-trivial and this area is usually challenging\n+ There are some novel components such as the lazy updates and implicit leverage score sampling.  It is conceivable these might have other applications\n+ Brings matrix sketching/randomized linear algebra techniques to the algorithmic discrepancy space\n\n-ves\n- Heavily built on Larsen's algorithm / Lovett--Meka random walk and other existing tools from the literature\n- The problem might be of narrow interest, even to the ICML audience", "other_comments_or_suggestions": "Might be worth adding nnz(A)+n^3 combinatorial bound to Table 1\n\npage 2 - notation V_{l,*} undefined\n\nCould you adopt a single notation to capture both \\cal{T}_mat(m,n,k) and \\omega(a,b,c)?\n\npage 5 line 223 and on & 234 and on - most of the content seems repeated", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xMNAzKFedB", "reviewer": "Reviewer_8Nfk", "summary": "The authors develop a new, faster algorithm for approximate discrepancy minimization with bounds on the computation time depending on the input-sparsity. Their algorithm is optimal for \"tall\" matrices, i.e. m x n matrices with m being a polynomial in n.\nAdditionally, the accuracy of the approximation matches a previous algorithm by Larsen.\n\nThey identify five \"barriers\", i.e. shortcomings, in Larsen's algorithm and they claim to improve on all of them. Some of the main ideas here are: \n1) using sketching matrices and \"ImplicitLeverageScore\" to approximate some matrices efficiently.\n2) Introducing a data structure that allows batching a series of computations.\n\nFinally, they have a variant of their algorithm which uses \"Fast Matrix Multiplication (FMM)\"", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n### Theoretical Claims: The proof of Theorem C.3 (page 19) claimed that a particular set of eigenvectors are orthogonal, which is not true in general.\n\nBecause any real symmetric matrix admits an orthogonal diagonalization, its eigenvectors can always be taken to be orthonormal. \n\n### W1: Originality and connection to existing methods\n\nWhile our work builds upon Larsen's algorithm and Lovett–Meka random walk method, we would like to highlight the significant theoretical and algorithmic advances introduced in our work:\n-  We introduce an innovative implicit leverage-score sampling technique, enabling us to significantly reduce the computational complexity of hereditary projection from Larsen’s original $O(mn^2)$ (or $O(mn^\\omega)$ with fast matrix multiplication) to $O(nnz(A)+n^{\\omega})$. This improvement is crucial, particularly for sparse input matrices.\n- We provide a robust theoretical analysis that carefully manages error accumulation introduced by randomized sketching methods. Such robustness was not previously established and represents a substantial methodological advancement over existing discrepancy minimization frameworks.\n- The lazy-update mechanism we introduce to efficiently implement the iterative Edge-Walk algorithm fundamentally reduces computational complexity from Larsen’s $O(mn^2+n^3)$ to our result of $\\tilde{O}(nnz(A) + n^{2.53})$. This addresses and overcomes a significant computational barrier identified in prior literature.\n\n### W2 and Q2: Interest to the ICML community and applications in ML\nThanks for pointing this out. We argue that the broad relevance of discrepancy theory to the ICML community stems from its strong connections to central themes in machine learning. Specifically, discrepancy minimization intersects significantly with computational learning theory [1,2], computer vision [3], unsupervised learning [4], attention KV caching [5], differential privacy [6], and sampling [7,8]. \nMore specifically,\n[1,2] introduces the relationship of discrepancy and concepts in learning theory such as VC dimension, PAC learning.\n[3] introduces a method to learn hash functions via discrepancy minimization. Learning hash functions in content-based image retrieval optimize binary codes to preserve similarity in high-dimensional feature spaces, enabling faster and more efficient image search.\n[4] leverage discrepancy minimization for unsupervised graph matching by aligning predictions from classical solvers and neural models.\n[5] proposed an algorithm for compressing the KV cache recursively using a geometric correlated sampling process based on discrepancy theory\n[6] investigated the relationship between discrepancy minimization and differential privacy in the context of linear queries over histograms.\nQuasi-Monte Carlo methods [7,8] leverage concepts from discrepancy theory by employing low-discrepancy sequences to efficiently approximate high-dimensional integrals and expectations.\n\nIn the final manuscript, we will explicitly clarify and elaborate on these connections to further emphasize the relevance and significance of our work to the ICML audience.\n\n[1] Matousek, Jiri. Geometric discrepancy: An illustrated guide. 2009\n\n[3] Karnin, Zohar, and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. COLT’19\n\n[3] Chen, Zhixiang, et al. Deep hashing via discrepancy minimization. CVPR’18\n\n[4] Wang, Runzhong, Junchi Yan, and Xiaokang Yang. Unsupervised learning of graph matching with mixture of modes via discrepancy minimization. TPAMI’23\n\n[5] Han, Insu, et al. BalanceKV: KV Cache Compression through Discrepancy Theory. arXiv preprint:2502.07861\n\n[6] Nikolov, Aleksandar, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. STOC’13\n\n[7] Lyu, Yueming, Yuan Yuan, and Ivor Tsang. Subgroup-based rank-1 lattice quasi-monte carlo. NeurIPS’20\n\n[8] Lyu, Yueming. Fast rank-1 lattice targeted sampling for black-box optimization. NeurIPS’23\n\n### W3: Typos\nWe sincerely appreciate the detailed list of typos and suggestions provided by the reviewer. We will carefully proofread the manuscript, correcting all listed typographical errors and ensuring clarity in terminology and statements. We recognize that readability and precision are crucial, particularly in technical papers, and will make substantial efforts to improve the overall presentation quality.\n### Q1: Competitiveness relative to Larsen’s algorithm\nThank you for pointing this out. We conduct the experiments to demonstrate the effectiveness of our algorithm. Due to space limit, please refer to the rebuttal to the reviewer ZGyW for the experiment results.\n\nWe sincerely appreciate your valuable feedback, which will significantly help us improve our paper. We hope that we have adequately addressed your concerns. Please do not hesitate to reach out if you have any further questions or comments. Thank you once again for your thoughtful review.", "claims_and_evidence": "The claims are supported by informal overviews of the various parts of the algorithm as well as proofs in the appendix. While I did not read the proofs in detail, the informal overview seemed convincing enough.", "methods_and_evaluation_criteria": "Their algorithm is compared with several existing algorithms and results in the discrepancy minimization litterature, which makes sense.\n\nNo experimental comparisons, does it actually compare in practise to existing algorithms? In particular, the previous algorithm of Larsen is accompanied by practical experiments, so it might have made sense to compare the new algorithm in practice. Of course, a purely theoretical improvement may be interesting in its own right.", "theoretical_claims": "I did not read any proofs in full as they all appear in the appendix. However, I skimmed part of the proof of Theorem C.3 (page 19) in which it is claimed that a particular set of eigenvectors are orthogonal. This is not true in general, and it was unclear to me why it should be true in their proof. It might still be true, but at least I think it requires an argument.", "experimental_designs_or_analyses": "Not relevant for this paper", "relation_to_broader_scientific_literature": "The paper provides a fairly thorough overview of existing theoretical results and previous algorithms in discrepancy minimization. Additionally, several applications of discrepancy minimzation are mentioned, although these are kept pretty vague.\n\nThe most important references are the algorithms by Larsen (2023) and Eldahn & Singh (2018).", "essential_references_not_discussed": "The discussion of the literature seems appropriate.", "other_strengths_and_weaknesses": "The results themselves seem fine. It might not be the most original work, since it seems to mostly consist of several existing algorithms stitched together. However, in terms of technical depth, it is well beyond most NeurIPS papers.\n\nI'm unsure whether the paper fits the scope of the conference. There may be applications to machine learning, but the paper itself seems to have very little to do with machine learning and would probably fit better at a TCS venue. The authors also do not give convincing arguments that the paper belongs in a machine learning conference.\n\nFinally, there are simply too many typos and weird, unclear phrases that don't make sense, especially in the appendices. This is very distracting and makes for a tedious reading experience. See \"Other Comments or Suggestions\" for some examples.", "other_comments_or_suggestions": "List of typos and unclear phrases:\n\nTypo p. 22: \"proof of suceed probability\" should be \"proof of success probability\"\n\nTypo p. 15: \"For convinient\" should be \"For convenience\"\n\n\nTypos p. 16, \"It is well-known that random Gaussian matrices an AMS matrices gives JL-transform property\" should instead be\n\n\"It is well-known that random Gaussian matrices and AMS matrices give JL-transform property\".\n\nTypo p. 20, \"we now proof\" should be \"we now prove\"\nOn p. 24, it says \"expectated time\". Expectated is not a word, should probably be \"expected time\".\nOn p. 24, there should probably be a \"such that\" or something similar before the inequality in the statement of Lem. E.1, right after \"eta \\in R\".\n\nTypo p. 26:  It says \"have have\" at the bottom of the page.\nOn page 26, it says \"the number entries reach the absolute value 1 keeps increasing\" which makes very little sense to the point where I'm not sure what the sentence is trying to convey.\n\nTypo page 27: The last \"We\" should not be capitalized in Corollary E.3.\nTypo pages 27 and 28: \"fourth\" should be \"fourth\".\nTypo in definition E.4. Should be \"which is implicitly maintained...\" instead of \"which implicitly maintained...\"\n\nOn page 30, should it not be g_t in \"we first assume that, we add mu \\cdot g\"?\n\nOn page 30, on the bottom of the page it says \"there must be at least one entry i \\in [n] satisfying that ...\" the two equations that come after this are identical which surely must be a mistake? Additionally, there is a | too much at the beginning of the second equation here here.\n\n\nOn page 31 at the top, what does it mean that a set is larger than a number?\n\nIn Lem. E.2, and Cor. E.3 it says (0,1)^n - should this not be (-1,1)^n?\n\nIn definition E.5, what does it mean that a vector g_t is sampled from a univariate Gaussian N(0,1)? Are the coordinates i.i.d from this distribution?", "questions_for_authors": "- Do you think your algorithm would be competitive in practice with the previous algorithm by Larsen?\n\n- Can you give some further examples of why discrepancy minimization is interesting for the ML community?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S70bpywVB0", "reviewer": "Reviewer_ZGyW", "summary": "The paper gives a new algorithm for discrepancy minimization over real valued matrices that nearly runs in input-sparsity time. Specifically, building on Bansal's and Larsen's previous algorithms, the authors give a \n\n1) A combinatorial algorithm that runs in time $\\tilde{O}(nnz(A) + n^3)$ time. \n\n2) If Fast Matrix Multiplication (FMM) is allowed, then $\\tilde{O}(nnz(A) +n^{2.53})$, breaking the cubic barrier for the first time. \n\nThe algorithm guarantees a coloring $x\\in \\set{-1,1}^n$ achieving discrepancy $O(\\text{herdisc}(A) \\log n \\log^{1.5}m)$\n\nThey do this by introducing a host of interesting techniques, notably:\n\n1) A new sketching method using implicit leverage‐score sampling (which is being utilised very heavily in a lot of recent papers) to quickly compute a hereditary projection (Theorem 1.3), while simultaneously avoiding explicitly calculating the entire projection matrix (the theorem is technical, this is just an informal description). \n\n2) A “guess-and-correct” data structure that batches gaussian projections. \n\nThe paper is relatively readable, but quite frankly too technical sometimes. Intuition for the proofs of Theorems or even their utilities in the \"big picture\" is rarely communicated, and for a 51 pages paper, I expected significantly more handholding and intuition sharing throughout the reading journey. I've had to skip some proofs completely because they offered almost no intuition and were time sinks to verify, not to mention that they felt extremely mechanical. \n\nUltimately, I think the main result is interesting enough to be published in ICML since it tackles a long standing open problem, and it is clearly important, though I would've wished if the presentation was more accessible for a result of this importance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful comments and thorough evaluation of our paper. \n### W1 and W2: Technical Density and Intuition\nWe appreciate the reviewer's concern regarding the technical density of our presentation. Given the complex nature of discrepancy minimization and the depth of the theoretical contributions, our initial goal was to ensure rigorous correctness. However, we acknowledge that improving readability and intuition is crucial. In the final version, we will include additional intuitive explanations and clear roadmaps to guide readers through the intricate parts of our proofs, particularly emphasizing high-level insights before delving into technical details.\n### W3: Experiments\nThank you for pointing this out. We conduct the experiments to demonstrate the effectiveness of our algorithm. We focused our experimental evaluation on demonstrating the improvements achieved through the fast hereditary projection. This is because the lazy update scheme is primarily designed to leverage fast matrix multiplication. Although fast matrix multiplication theoretically has lower asymptotic complexity, algorithms based on FMM often suffer from significantly large constant factors, adversely affecting their practical runtime performance. Additionally, for practical considerations, the parameters used in the experiments do not strictly follow the theoretical suggestions in the paper.\nOur experimental setup follows the matrix configurations used in Larsen’s paper. \n\n**Uniform matrices:** Each entry of $A$ is uniformly chosen from $\\\\{-1,1\\\\}$\n| Matrix Size      | Sparsity | Larsen's Obj. Val. | Our Obj. Val. | Larsen's Runtime (s) | Our Runtime (s)|\n|------------------|----------|--------------------|---------------|------------------|-------------|\n| 400×400          | 1.0      | 54                 | 56            | 2.98             | 2.16        |\n| 400×400          | 0.5      | 38                 | 42            | 2.90             | 1.95        |\n| 400×400          | 0.1      | 14                 | 20            | 2.91             | 1.90        |\n| 2000×2000        | 1.0      | 140                | 148           | 345              | 164         |\n| 2000×2000        | 0.5      | 96                 | 99            | 334              | 156         |\n| 2000×2000        | 0.1      | 46                 | 47            | 331              | 152         |\n| 10000×1000       | 1.0      | 132                | 140           | 378              | 63          |\n| 10000×1000       | 0.5      | 92                 | 97            | 374              | 62          |\n| 10000×1000       | 0.1      | 42                 | 44            | 375              | 62          |\n\n**2D Corner matrices:** $A$ is constructed by choosing two sets of points in the unit square—one for rows and one for columns—and marking an entry as 1 if the row point strictly exceeds the column point in both coordinates, otherwise marking it as 0.\n| Matrix Size      | Sparsity | Larsen's Obj. Val. | Our Obj. Val. | Larsen's Runtime (s)| Our Runtime (s) |\n|------------------|----------|--------------------|---------------|------------------|-------------|\n| 400×400          | 1.0      | 30                 | 32            | 2.80             | 2.15        |\n| 400×400          | 0.5      | 36                 | 36            | 2.79             | 2.18        |\n| 400×400          | 0.1      | 17                 | 18            | 2.75             | 1.93        |\n| 2000×2000        | 1.0      | 52                 | 58            | 347              | 170         |\n| 2000×2000        | 0.5      | 83                 | 92            | 350              | 169         |\n| 2000×2000        | 0.1      | 45                | 46            | 350            | 171        |\n| 10000×1000       | 1.0      | 46                 | 52            | 386              | 65          |\n| 10000×1000       | 0.5      | 76                 | 77            | 374              | 60          |\n| 10000×1000       | 0.1      | 37                 | 40            | 375              | 62          |\n\nOur algorithm achieves substantial speedups with only minor sacrifices in approximation guarantees. The speedup will be more significant once $m$ is much largerer than $n$, as sketching is known to work well in the regime where $m \\gg n$ . \n\n### W4: Constants\nWe agree with the reviewer that the constants in our current analysis primarily serve to highlight theoretical improvements. Optimizing these constants would indeed further enhance the practical applicability of our algorithm, although it would require additional effort. Nevertheless, our preliminary experiments indicate that the algorithm achieves significant improvements in runtime even without strictly adhering to the exact parameters suggested by the theoretical analysis.\n\nWe appreciate the positive assessment of our work. Thank you again for your thoughtful review.", "claims_and_evidence": "The paper’s claims are backed by Lemmas/Theorems which are proved in details in the Appendix.", "methods_and_evaluation_criteria": "Since the contribution is theoretical, and there are no experiments, the evaluation centers on computational complexity and approximation guarantees rather than empirical performance. I think this part is adequately addressed.", "theoretical_claims": "I reviewed the outlines of the key proofs (notably for Theorems 1.1 and 1.3) and I think they are Kosher. However, I skipped several proofs (for example some of the parts in the long correctness proof of Algorithm 2).", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper is well-situated in the existing literature on discrepancy minimisation. For example, it builds on the Bansal’s seminal SDP approach, The iterative partial-coloring method of Lovett & Meka, and Larsen's algorithm. The paper makes a significant contribution relative to these prior works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1) As mentioned, the theoretical improvement in runtime is substantial compared to previous methods, and is interesting. \n\n2) The paper introduces a host of technical results that might be of independent interest. \n\nWeaknesses:\n\n1) The technical exposition is very dense and may be a turn-off for readers not already very familiar with the literature on discrepancy theory\n\n2) As mentioned above, some parts of the analysis and proofs (especially regarding the correctness of the algorithm) are very subtle and could benefit from additional intuitive explanations.\n\n3) Experiments! This could've been a very easy win, and I don't see why the authors don't include even a tiny experiment for their algorithms. I understand that there is a ton of parameters to choose (various $\\varepsilon, \\delta$ to choose), but looking at the algorithm, I really think they could've implemented a variant on a toy dataset. \n\n4) The constants in the proofs are not optimised, and sometimes they're laughably huge (I get it, no one likes to optimize constants in proofs, but some constants in the papers are just absurd). I suspect if more effort was put into this, it would've easily translated into a feasible practical algorithm, but alas.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The (NP-hard) discrepancy of an m x n matrix A is the minimum, over all discrete x in {-1, 1}^n, of the infinity norm of Ax. This is a fundamental quantity in discrete mathematics, algorithms, and in ML. This work presents a combinatorial---not SDP or LP-based---O(nnz(A) + n^3)-time approximation algorithm for the discrepancy with the same approximation guarantee as recent work of Kasper Green Larsen's, optimal for “tall” matrices where m = poly(n). (As usual, "nnz" denotes the number of nonzeroes.) Using further analysis and modern fast matrix multiplication, the paper improves the runtime to O(nnz(A) + n^{2.53}). The paper identifies five areas of improvement in Larsen's algorithm and claim to improve on all of them. Some of the main ideas here are using sketching matrices and a data structure that allows batching a series of computations. This paper makes good progress on a fundamental algorithmic problem relevant to ML.
Decision: Accept (spotlight poster)