Discrepancy Minimization in Input-Sparsity Time Yichuan DengZhao SongOmri Weinstein Abstract

2025-05-04 0 0 976.83KB 60 页 10玖币
侵权投诉
Discrepancy Minimization in Input-Sparsity Time
Yichuan Deng∗Zhao Song†Omri Weinstein‡
Abstract
A recent work of Larsen [Lar23] gave a faster combinatorial alternative to Bansal’s SDP
algorithm for finding a coloring x∈ {−1,1}nthat approximately minimizes the discrepancy
disc(A, x) := kAxk∞of a general real-valued m×nmatrix A. Larsen’s algorithm runs in
e
O(mn2) time compared to Bansal’s e
O(mn4.5)-time algorithm, at the price of a slightly weaker
logarithmic approximation ratio in terms of the hereditary discrepancy of A[Ban10].
In this work we present a combinatorial e
O(nnz(A) + n3) time algorithm with the same
approximation guarantee as Larsen, which is optimal for tall matrices m= poly(n). Using
a more intricate analysis and fast matrix-multiplication, we achieve e
O(nnz(A) + n2.53) time,
which breaks cubic runtime for square matrices, and bypasses the barrier of linear-programming
approaches [ES14] for which input-sparsity time is currently out of reach.
Our algorithm relies on two main ideas: (i) A new sketching technique for finding a projection
matrix with short `2-basis using implicit leverage-score sampling; (ii) A data structure for faster
implementation of the iterative Edge-Walk partial-coloring algorithm of Lovett-Meka, using
an alternative analysis that enables “lazy” batch-updates with low-rank corrections. Our result
nearly closes the computational gap between real-valued and binary matrices (set-systems), for
which input-sparsity time coloring was very recently obtained [JSS23].
∗ethandeng02@gmail.com. University of Science and Technology of China.
†zsong@adobe.com. Adobe Research.
‡omri@cs.columbia.edu. Hebrew University and Columbia University.
arXiv:2210.12468v1 [cs.DS] 22 Oct 2022
Contents
1 Introduction 3
1.1 OurResults......................................... 5
2 Technical Overview 6
2.1 Overview and barriers of Larsen’s algorithm . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 OurTechniques....................................... 7
2.2.1 Robust Analysis of [Lar23] ............................ 7
2.2.2 Overcoming Barriers 1-6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 BeatingtheCubicBarrier................................. 10
3 Preliminaries 11
3.1 Notations .......................................... 11
3.2 Definitions.......................................... 12
3.3 BasicLinearAlgebra.................................... 12
3.4 PriorResultsonHerdisc.................................. 12
3.5 PropertiesofGaussians .................................. 12
3.6 Azuma for Martingales with Subgaussian Tails . . . . . . . . . . . . . . . . . . . . . 13
3.7 SketchingMatrices ..................................... 13
3.8 JLTransform........................................ 14
3.9 SubspaceEmbedding.................................... 14
3.10ConcentrationInequality.................................. 14
3.11 Fast Rectangular Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Small Row Projection via Implicit Leverage-Score Sampling 15
4.1 OrthogonalizeSubroutine ................................. 15
4.2 Fast Sampling via Implicit LSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.1 Leverage Score Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.2 FastSubsampling.................................. 18
4.3 Fast Projecting to Small Rows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3.1 Runningtime.................................... 19
4.3.2 Correctness ..................................... 20
5 Sampling a Batch of Rank-1Terms 25
6 Discrepancy-Minimization Algorithm 29
6.1 Correctness ......................................... 29
6.2 RunningTime ....................................... 29
7 Partial Coloring 31
7.1 Fast Algorithm for Approximating Norms . . . . . . . . . . . . . . . . . . . . . . . . 31
7.2 LookforStepSize ..................................... 32
7.3 Correctness ......................................... 36
7.4 IterativeNotations ..................................... 40
7.5 Upper bound for the inner products . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.6 Upper Bound the Failure Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.7 Lower bound for the vector after projection . . . . . . . . . . . . . . . . . . . . . . . 44
7.8 LoweronExpectation ................................... 46
1
7.9 From Expectation to Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
7.10RunningTime ....................................... 47
8 Fast maintaining lazy data structure 48
8.1 MainDataStructure.................................... 48
8.2 Initialization ........................................ 49
8.3 Query ............................................ 50
8.4 Update ........................................... 52
8.5 Restart ........................................... 52
8.6 Running Time of the Maintain algorithm . . . . . . . . . . . . . . . . . . . . . . . . 53
8.7 Correctness ......................................... 54
8.8 Tighter Running Time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2
1 Introduction
Discrepancy is a fundamental notion in combinatorics and theoretical computer science. The dis-
crepancy of a real matrix A∈Rm×nwith respect to a “coloring” vector x∈ {±1}nis defined
as
disc(A, x) := kAxk∞= max
j∈[m]|(Ax)j|.
This is a natural generalization of the classic combinatorial notion of discrepancy of set-systems,
corresponding to binary matrices A∈ {0,1}m×nwhere rows represent (the indicator vector of)
msets over a ground set of [n] elements, and the goal is to find a coloring x∈ {±1}nwhich is
as “balanced” as possible simultaneously on all sets , i.e., to find disc(A) = minx∈{±1}nkAxk∞.
Discrepancy minimization has various applications in combinatorics, computational geometry, de-
randomization, rounding of integer linear programming and approximation algorithms for NP-hard
problems [Cha00], and has been studied for decades in math and TCS ([Mat99]). Most of the his-
tory of this problem was focused on the existential question of understanding the minimum possible
discrepancy achievable for various classes of matrices. For general set-systems of size n(arbitrary
n×nbinary matrices A), Spencer’s classic result [Spe85] states that disc(A)≤6√n, which is
asymptotically better than random coloring (Θ(√nlog n). More recent works have focused on re-
stricted matrix families, such as geometric matrices [Lar23] and sparse matrices ([Ban98,BF81]),
showing that it is possible to achieve o(√n) discrepancy in these restricted cases. For example, the
minimum-discrepancy coloring of k-sparse binary matrices (sparse set-systems) turn out to have
discrepancy at most O(√klog n) [Ban98].
All of these results, however, are non-constructive—they only argue about the existence of
low-discrepancy colorings—which prevents their use in algorithmic applications that rely on low-
discrepancy (partial) coloring, such as bin-packing problems [Rot13,HR17].1Indeed, the question
of efficiently finding a low-discrepancy coloring, i.e., computing disc(A), was less understood until
recently, and is more nuanced: Charikar, Newman and Nikolov [CNN11] showed it is NP-hard
to distinguish whether a matrix has disc(A) = 0 or disc(A) = Ω(√n), suggesting that (ω(1))
approximation is inevitable to achieve fast runtimes. The celebrated work of Bansal [Ban10] gave
the first polynomial-time algorithm which achieves an additive O(√n)-approximation to the optimal
coloring of general n×nmatrices, matching Spencer’s non-constructive result. Bansal’s algorithm
has approximation guarantees in terms of the hereditary discrepancy [LSV86], denoted herdisc(A),
which is the maximum discrepancy of any submatrix A0of Aobtained by deleting a subset of the
columns of A(equivalently, deleting a subset of the elements in the ground-set [n]). More formally,
Bansal [Ban10] gave an SDP-based algorithm that finds a coloring exsatisfying
disc(A, ex) = O(log(n)·herdisc(A)),
for any real matrix A, in time e
O(mn4.5) assuming state-of-art SDP solvers [JKL+20,HJS+22]. In
other words, if all submatrices of Ahave low-discrepancy colorings, then it is in fact possible (yet
still quite expensive) to find an almost-matching overall coloring.
Building on Bansal’s work, Lovett and Meka [LM15] designed a simpler algorithm for set-
systems (binary matrices A), running in e
O((n+m)3) time. The main new idea of their algorithm,
which is also central to our work, was a subroutine for repeatedly finding a partial-coloring via
random-walks (a.k.a Edge-Walk), which in every iteration “rounds” a constant-fraction of the
1If we don’t have a polynomial constructive algorithm, then we can’t approximate solution for bin packing in
polynomial. This is common in many problems (in integer programming) where we first relax it to linear programming
and then rounding it back to an integer solution.
3
coordinates of a fractional-coloring to an integral one in {−1,1}(more on this in the next section).
Followup works by Rothvoss [Rot17] and Eldan-Singh [ES14] extended these ideas to the real-
valued case, and developed faster convex optimization frameworks for obtaining low-discrepancy
coloring, the latter requiring O(log n)linear programs instead of a semidefinite program [Ban10],
assuming a value oracle to herdisc(A).2In this model, [ES14] yields an O∗(max{mn+n3,(m+n)w})
time approximate discrepancy algorithm via state-of-art (tall) LP solvers [BLSS20]. This line of
work, however, has a fundamental setback for achieving input-sparsity time, which is a major open
problem for (high-accuracy) LP solvers [BCLL18]. 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-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 limitations have been very recently over-
come in the breakthrough work of Jain, Sah and Sawhney [JSS23], who gave an e
O(n+nnz(A))-time
coloring algorithm for binary matrices A∈ {−1,1}m×n, with near optimal (O(√nlog(m/n))) dis-
crepancy. While their approach, too, was based on convex optimization, their main observation
was that an approximate LP solver, using first-order methods, in fact suffices for a logarithmic
approximation. Unfortunately, the algorithm of [JSS23] 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 [JSS23] to matrices with entries
in range, say, [−R, R], guarantees that a uniformly random vector would only have discrepancy
e
O(poly(R)·√n) on the “heavy” rows, and this term would also govern the approximation ratio
achieved by their algorithm.
By contrast, a concurrent result of Larsen [Lar23] gave a purely combinatorial (randomized)
algorithm which is not as fast, but handles general real matrices, and makes a step toward practical
coloring algorithms. Larsen’s algorithm improves Bansal’s SDP from O(mn4.5) to e
O(mn2+n3)
time, at the price of a slightly weaker approximation guarantee: For any A∈Rm×n, [Lar23] finds
a coloring ex∈ {−1,+1}nsuch that disc(A, ex) = O(herdisc(A)·log n·log1.5m).
The last two exciting recent developments naturally raise the question of whether input-sparsity
time discrepancy-minimization is achievable for general (real-valued) matrices. In fact, this was
one of the main open questions raised in a 2018 workshop on Discrepancy Theory and Integer
Programming [Dad18].
References Methods Running Time
[Ban10] SDP [JLSW20,HJS+22]mn4.5
[ES14]* (Step 1: Theorem 1.3) + (Step 2: LP [JSWZ21] ) mω+m2+1/18
[ES14]* (Step 1: Theorem 1.3) + (Step 2: LP [BLSS20]) mn +n3
[ES14]* (Step 1: Theorem 1.3) + (Step 2: LP [LS14]) nnz(A)√n+n2.5
[Lar23] Combinatorial mn2+n3
Ours (Theorem 1.1) (Step 1: Theorem 1.3) + (Step 2: Lemma 7.14) nnz(A) + n2.53
Table 1: Progress on approximate discrepancy-minimization algorithms of real-valued m×nma-
trices (m≥n). For simplicity, we ignore no(1) and poly(log n) factors in the table. “[ES14]*” refers
to a (black-box) combination of our Theorem 1.3 with [ES14] and using state-of-art LP solvers for
square and tall matrices [LS14,BLSS20,JSWZ21].
2[ES14]’s LP requires an upper-bound estimate on herdisc(A)for each of the O(log n) sequential LPs, hence
standard exponential-guessing seems too expensive: the number of possible “branches” is >2O(log n).
4
摘要：

DiscrepancyMinimizationinInput-SparsityTimeYichuanDeng*ZhaoSong„OmriWeinstein…AbstractArecentworkofLarsen[Lar23]gaveafastercombinatorialalternativetoBansal'sSDPalgorithmfor ndingacoloringx2f1;1gnthatapproximatelyminimizesthediscrepancydisc(A;x):=kAxk1ofageneralreal-valuedmnmatrixA.Larsen'salgorithm...

展开>> 收起<<
Discrepancy Minimization in Input-Sparsity Time Yichuan DengZhao SongOmri Weinstein Abstract.pdf

共60页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：60 页 大小：976.83KB 格式：PDF 时间：2025-05-04

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 60
评分 收藏
分享
立即下载
客服
关注