# A New Framework for Matrix Discrepancy:
Partial Coloring Bounds via Mirror Descent

Daniel Dadush
Centrum Wiskunde & Informatica, Amsterdam, Netherlands<EMAIL_ADDRESS>Haotian
Jiang
University of Washington, Seattle, USA<EMAIL_ADDRESS>Victor
Reis University of Washington, Seattle, USA<EMAIL_ADDRESS>
###### Abstract

Motivated by the Matrix Spencer conjecture, we study the problem of finding
signed sums of matrices with a small matrix norm. A well-known strategy to
obtain these signs is to prove, given matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$, a Gaussian measure lower bound
of $2^{-O(n)}$ for a scaling of the discrepancy body
$\\{x\in\mathbb{R}^{n}:\|\sum_{i=1}^{n}x_{i}A_{i}\|\leq 1\\}$. We show this is
equivalent to covering its polar with $2^{O(n)}$ translates of the cube
$\frac{1}{n}B^{n}_{\infty}$, and construct such a cover via mirror descent. As
applications of our framework, we show:

Matrix Spencer for Low-Rank Matrices. If the matrices satisfy
$\|A_{i}\|_{\mathrm{op}}\leq 1$ and $\mathsf{rank}(A_{i})\leq r$, we can
efficiently find a coloring $x\in\\{\pm 1\\}^{n}$ with discrepancy
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}\lesssim\sqrt{n\log(\min(rm/n,r))}$.
This improves upon the naive $O(\sqrt{n\log r})$ bound for random coloring and
proves the matrix Spencer conjecture when $rm\leq n$.

Matrix Spencer for Block Diagonal Matrices. For block diagonal matrices with
$\|A_{i}\|_{\mathrm{op}}\leq 1$ and block size $h$, we can efficiently find a
coloring $x\in\\{\pm 1\\}^{n}$ with
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}\lesssim\sqrt{n\log(hm/n)}$. This
bound was previously shown in [Levy, Ramadas and Rothvoss, IPCO 2017] under
the assumption $h\leq\sqrt{n}$, which we remove. Using our proof, we reduce
the matrix Spencer conjecture to the existence of a $O(\log(m/n))$ quantum
relative entropy net on the spectraplex.

Matrix Discrepancy for Schatten Norms. We generalize our discrepancy bound for
matrix Spencer to Schatten norms $2\leq p\leq q$. Given $\|A_{i}\|_{S_{p}}\leq
1$ and $\mathsf{rank}(A_{i})\leq r$, we can efficiently find a partial
coloring $x\in[-1,1]^{n}$ with $|\\{i:|x_{i}|=1\\}|\geq n/2$ and
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}\lesssim\sqrt{n\min(p,\log(rk))}\cdot
k^{1/p-1/q}$, where $k:=\min(1,m/n)$.

Our partial coloring bound is tight when $m=\Theta(\sqrt{n})$. We also provide
tight lower bounds of $\Omega(\sqrt{n})$ for rank-$1$ matrix Spencer when
$m=n$, and $\Omega(\sqrt{\min(m,n)})$ for $S_{2}\rightarrow S_{\infty}$
discrepancy, precluding a matrix version of the Komlós conjecture.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Overview of Our Approach
    3. 1.3 Further Related Work
  2. 2 Preliminaries
  3. 3 Our Framework for Partial Coloring
    1. 3.1 Partial Coloring via Covering Numbers
    2. 3.2 Mirror Descent: An Overview
    3. 3.3 Covering via Mirror Descent
    4. 3.4 Initialization for Spectraplex Setup: Relative Entropy Net
  4. 4 Applications of the Spectraplex Setup
  5. 5 Matrix Discrepancy for Schatten Norms
  6. 6 Lower Bound Examples for Matrix Discrepancy
    1. 6.1 Low Dimension Regime of $m=\Theta(\sqrt{n})$
    2. 6.2 Rank-$1$ Matrices and $m\geq n$
  7. A An Application of Banaszczyk’s Theorem

##  1 Introduction

Discrepancy minimization has been a well-studied area of research both in
mathematics and computer science [Cha01, Mat09]. We start with a classical
setting: given vectors $a_{1},\dots,a_{n}\in\mathbb{R}^{m}$ each satisfying
$\|a_{i}\|_{\infty}\leq 1$, the goal is to find a coloring $x\in\\{\pm
1\\}^{n}$ that minimizes the discrepancy, defined as
$\|\sum_{i=1}^{n}x_{i}a_{i}\|_{\infty}$. A seminal result of Spencer [Spe85]
improves upon the $O(\sqrt{n\log m})$ bound of a random coloring via Chernoff
and union bound:

######  Theorem 1.1 (Spencer [Spe85]).

Let $m\geq n$. Given vectors $a_{1},\dots,a_{n}\in\mathbb{R}^{m}$ with
$\|a_{i}\|_{\infty}\leq 1$, there exists $x\in\\{\pm 1\\}^{n}$ such that
$\|\sum_{i=1}^{n}x_{i}a_{i}\|_{\infty}\lesssim\sqrt{n\log(2m/n)}$.

In particular, when $m=n$, Theorem 1.1 states that the discrepancy is at most
$O(\sqrt{n})$, as opposed to the $O(\sqrt{n\log n})$ bound for a random
coloring. Spencer’s theorem is known to be tight up to constants for all
$m\geq n$ [Cha01, Mat09].

The Partial Coloring Method. All known proofs of Spencer’s theorem are
essentially based on the partial coloring method, one of the most important
and widely applied techniques in discrepancy theory. The method states that to
obtain the type of discrepancy bound in Theorem 1.1, it suffices to prove the
same bound for a partial coloring $x\in[-1,1]^{n}$ with at least $\Omega(n)$
coordinates in $\\{\pm 1\\}$. This process is then iterated over the set of
coordinates $\\{i:|x_{i}|<1\\}$ to obtain a full coloring. For Spencer-type
problems, the discrepancy of the full coloring is at most a constant factor
off from the discrepancy of the partial coloring (see Corollary 3.2).

The partial coloring method was developed in the early 80s by Beck and refined
by Spencer using the entropy method [Bec81, Spe85]. A convex geometry view of
partial coloring was developed independently by Gluskin [Glu89]. While these
original arguments used the pigeonhole principle and were non-algorithmic, a
breakthrough result of Bansal [Ban10], followed by a rich line of work [LM15,
Rot17, LRR17, ES18, RR20], gave various algorithmic versions. These recent
developments also led to new results in approximation algorithms and
differential privacy [Rot13, NTZ13, BCKL14, BN17].

Matrix Spencer Setting. A natural generalization of Spencer’s setting to
matrices is the following. Given matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$, each satisfying
$\|A_{i}\|_{\mathrm{op}}\leq 1$, the goal is to find a coloring $x\in\\{\pm
1\\}^{n}$ that minimizes $\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}$. In
particular, Spencer’s setting corresponds to the case where all matrices
$A_{i}$ are diagonal.

In the matrix Spencer setting, the non-commutative Khintchine inequality of
Lust-Piquard and Pisier [LPP91, Pis03] shows that a random coloring
$x\in\\{\pm 1\\}^{n}$ has expected discrepancy
$\mathbb{E}[\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}]\lesssim\sqrt{n\log
r}$, where each matrix $A_{i}$ has rank at most $r\leq m$. It is conjectured
that the discrepancy bound in Theorem 1.1 can be generalized as follows:

######  Conjecture 1.2 (Matrix Spencer Conjecture [Mek14, Zou12]).

Let $m\geq\sqrt{n}$. Given matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times
m}$ with $\|A_{i}\|_{\mathrm{op}}\leq 1$, there exists $x\in\\{\pm 1\\}^{n}$
such that

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{\mathrm{op}}\lesssim\sqrt{n\cdot\max(1,\log(m/n))}.$

In particular, when $\sqrt{n}\leq m\leq n$, the conjectured discrepancy bound
is $O(\sqrt{n})$. Despite significant effort, 1.2 has remained largely open,
with partial progress for block diagonal matrices [LRR17] and rank-$1$
matrices [MSS15, KLS20]. A solution to 1.2 will thus likely lead to new
techniques and insights in discrepancy theory beyond what is currently known
for vector discrepancy.

We note that in Spencer’s setting (Theorem 1.1) we may assume without loss of
generality that $m\geq n$ by the iterated rounding technique [BF81, Bár08,
LRS11]. For matrix Spencer, however, the interesting regime starts at
$m\geq\sqrt{n}$ (iterated rounding only works when $m^{2}<n$). 1.2 remains
open even when $m=n^{1/2+\varepsilon}$ for any constant $\varepsilon>0$.

Matrix Discrepancy for Schatten Norms. More generally, let111We make the
assumption that $p\leq q$ to avoid a polynomial dependence on $m$ in the
discrepancy bound. If $q<p$, then even a single matrix (i.e. $n=1$) can have
discrepancy $m^{1/q-1/p}$. $2\leq p\leq q\leq\infty$, we consider the
following matrix discrepancy setting for Schatten norms. Given matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$, each satisfying
$\|A_{i}\|_{S_{p}}\leq 1$, where $\|\cdot\|_{S_{p}}$ denotes the Schatten-$p$
norm. The goal is to find a coloring $x\in\\{\pm 1\\}^{n}$ to minimize
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}$, the $S_{p}\rightarrow S_{q}$
discrepancy. In particular, the matrix Spencer setting corresponds to the case
where $p=q=\infty$.

The diagonal case of $S_{p}\rightarrow S_{q}$ discrepancy, i.e.
$\ell_{p}\rightarrow\ell_{q}$ discrepancy for vectors, is well studied (see
[DNTT18, RR20] and the references therein). In fact, the well-known Komlós
conjecture asserts that the $\ell_{2}\rightarrow\ell_{\infty}$ discrepancy can
be upper bounded by a universal constant. For general
$\ell_{p}\rightarrow\ell_{q}$ discrepancy, Reis and Rothvoss [RR20] proves an
optimal partial coloring bound of $O(\sqrt{\min(p,\log(m/n))}\cdot
n^{1/2-1/p+1/q})$, assuming $m\geq n$ and $2\leq p\leq q\leq\infty$. It is a
natural question whether these bounds generalize to $S_{p}\rightarrow S_{q}$
discrepancy.

The Challenge in Using Partial Coloring Method for Matrix Discrepancy. Central
to the partial coloring method is to show that the discrepancy body
$D:=\\{x\in\mathbb{R}^{n}:\|\sum_{i=1}^{n}x_{i}A_{i}\|\leq t\\}$, i.e. the set
of fractional colorings with discrepancy at most $t$ under norm $\|\cdot\|$,
is “large” in some sense. A natural notion of largeness, due to Gluskin
[Glu89], is that the body $D$ has Gaussian measure at least $2^{-O(n)}$. This
measure of largeness has been adopted (sometimes implicitly) in essentially
all work on partial coloring [Ban10, LM15, Rot17, LRR17, ES18, RR20].

For the setting in Theorem 1.1, the discrepancy body $D$ is a polytope defined
by the intersection of strips of the form $|\langle r_{i},x\rangle|\leq t$,
where $r_{i}\in\mathbb{R}^{n}$ are the rows of the $m\times n$ matix whose
columns are $a_{1},\dots,a_{n}$. Therefore, Šidák’s lemma [Šid67] can be
readily used to give a Gaussian measure lower bound of the form
$\gamma_{n}(D)\geq\prod_{i=1}^{m}\gamma_{n}(\\{x\in\mathbb{R}^{n}:|\langle
r_{i},x\rangle|\leq t\\})$.

In the setting of matrix discrepancy, however, the discrepancy body $D$ has an
infinite number of facets. This prevents the use of Gaussian correlation
inequalities to lower bound $\gamma_{n}(D)$. To get around this barrier and
use the partial coloring method for matrix discrepancy, one needs a different
approach for proving Gaussian measure lower bounds.

###  1.1 Our Results

We lower bound the Gaussian measure of the discrepancy body $D$ via covering
numbers for its polar $D^{\circ}$ with respect to the $\ell_{\infty}$-ball
(see Section 3.1). We then prove the desired covering number estimates using
mirror descent, the powerful convex optimization primitive of Nemirovski and
Yudin [NY83] (see Sections 3.2, 3.3 and 3.4). Our method yields the following
applications.

Matrix Spencer for Low-Rank Matrices. Our first result is the following
improvement over the $O(\sqrt{n\log r})$ bound for random coloring in the
matrix Spencer setting.

######  Theorem 1.3 (Matrix Spencer for Low-Rank Matrices).

Let $m\geq\sqrt{n}$. Given symmetric matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with $\|A_{i}\|_{\mathrm{op}}\leq
1$ and $\mathsf{rank}(A_{i})\leq r$ for all $i\in[n]$, one can efficiently
find a coloring $x\in\\{\pm 1\\}^{n}$ such that

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{\mathrm{op}}\lesssim\sqrt{n\cdot\max(1,\log(r\cdot\min(1,m/n)))}.$

When the input matrices have rank $r\lesssim n/m$, the discrepancy bound in
Theorem 1.3 is $O(\sqrt{n})$ and this proves 1.2 for low rank matrices in the
regime where $m\leq n$.

Matrix Spencer for Block Diagonal Matrices. Our second application is the
following improved matrix Spencer bound for block diagonal matrices.

######  Theorem 1.4 (Matrix Spencer for Block Diagonal Matrices).

Let $m\geq\sqrt{n}$ and $h\leq m$. Given block diagonal symmetric matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with $\|A_{i}\|_{\mathrm{op}}\leq
1$ and block size $h\times h$, one can efficiently find a coloring $x\in\\{\pm
1\\}^{n}$ with

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{\mathrm{op}}\lesssim\sqrt{n\cdot\max(1,\log(hm/n))}.$

In particular, Theorem 1.4 proves 1.2 whenever $h\lesssim n/m$. This bound was
previously proved in [LRR17] under the assumption $h\leq\sqrt{n}$, which we
remove here.

We also obtain the following reduction of 1.2 to the construction of a better
quantum relative entropy net for the spectraplex
$\mathcal{S}_{m}:=\\{X\in\mathbb{R}^{m\times m}:X\succeq
0,\mathsf{tr}(X)=1\\}$.

######  Corollary 1.5 (Better Entropy Net Implies Matrix Spencer).

Let $m\geq\sqrt{n}$. If we can find $T\subseteq\mathcal{S}_{m}$ with $|T|\leq
2^{O(n)}$ such that for each $X\in\mathcal{S}_{m}$ there exists $Y\in T$ with
$S(X\|Y)\lesssim\max(1,\log(m/n))$, where $S(X\|Y)$ is the quantum relative
entropy between $X$ and $Y$, then the matrix Spencer conjecture is true.

In particular, in the proof of Theorem 1.4, we construct a
$O(\max(1,\log(hm/n)))$-relative entropy net for the set of block diagonal
matrices on $\mathcal{S}_{m}$ with block size $h\times h$ (see Section 3.4).
Our construction of such relative entropy nets might be of independent
interest.

Matrix Discrepancy for Schatten Norms. Theorem 1.3 is a special case of the
following general matrix discrepancy bound for Schatten norms.

######  Theorem 1.6 (Matrix Discrepancy for Schatten Norms).

Let $m\geq\sqrt{n}$ and $2\leq p\leq q\leq\infty$. Given symmetric matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with $\|A_{i}\|_{S_{p}}\leq 1$
and $\mathrm{rank}(A_{i})\leq r$ for all $i\in[n]$, one can efficiently find
$x\in[-1,1]^{n}$ so that $|\\{i:|x_{i}|=1\\}|\geq n/2$ and

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{S_{q}}\lesssim\sqrt{n\cdot\min(p,\max(1,\log(rk)))}\cdot
k^{1/p-1/q},$

where we denote $k:=\min(1,m/n)$. Moreover, we can find a full coloring
$x\in\\{\pm 1\\}^{n}$ at the expense of a factor of $(1/2+1/q-1/p)^{-1}$.

Our partial coloring result in Theorem 1.6 is tight when either
$m=\Theta(\sqrt{n})$ (for which we give an alternative proof using
Banaszczyk’s result [Ban98] in Appendix A), or when $r=1$ and $m\geq n$. We
provide matching lower bounds for both cases in Sections 6.1 and 6.2. In
particular, our lower bound examples imply a tight $\Omega(\sqrt{n})$ lower
bound for rank-$1$ matrix Spencer when $m=n$.

######  Corollary 1.7 (Rank-$1$ Matrix Spencer Lower Bound).

There exist rank-$1$ symmetric matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{n\times n}$ with $\|A_{i}\|_{\mathrm{op}}\leq
1$ such that any $x\in\\{\pm 1\\}^{n}$ has
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}\gtrsim\sqrt{n}$.

Another immediate consequence of our lower bounds is an optimal
$\Omega(\sqrt{\min(m,n)})$ lower bound for $S_{2}\rightarrow S_{\infty}$
discrepancy. This is in stark contrast to the well-known Komlós conjecture for
vectors, which asserts that the $\ell_{2}\rightarrow\ell_{\infty}$ discrepancy
is $O(1)$. Corollary 1.8 states that such a conjecture is far from being true
for matrices.

######  Corollary 1.8 (Lower Bound for Matrix Komlós).

For any $m$ and $n$, there exist symmetric matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with $\|A_{i}\|_{F}\leq 1$ such
that any $x\in\\{\pm 1\\}^{n}$ has
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}\gtrsim\sqrt{\min(m,n)}$.

Finally, we propose the following generalization of 1.2:

######  Conjecture 1.9 ($S_{p}\to S_{q}$ Matrix Discrepancy).

Let $m\geq\sqrt{n}$ and $2\leq p\leq q\leq\infty$. Given matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with $\|A_{i}\|_{S_{p}}\leq 1$,
there exists $x\in\\{\pm 1\\}^{n}$ such that

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{S_{q}}\lesssim\sqrt{n\cdot\min(p,\max(1,\log(m/n)))}\cdot\min(1,m/n)^{1/p-1/q}.$

When $m=n$, the right hand side is $O(\sqrt{n})$, and for diagonal matrices
the conjecture is known to be true for any $2\leq p\leq q$. When $p=q$, the
conjecture is also known to be true for diagonal matrices for all $m$ and $n$
[RR20].

###  1.2 Overview of Our Approach

We give a brief overview of our partial coloring framework in this subsection,
and leave a more detailed discussion to Section 3.

Partial Coloring via Covering Numbers. Let
$K:=\\{x\in\mathbb{R}^{n}:\|\sum_{i=1}^{n}x_{i}A_{i}\|\leq 1\\}$ be the unit
discrepancy body222To avoid confusion when talking about discrepancy bodies,
$K$ denotes the unit discrepancy body, and $D$ denotes a scaling of $K$ by the
target discrepancy bound. and $t$ be the target discrepancy bound. A recent
refinement by Reis and Rothvoss [RR20] of Gluskin’s convex geometry approach
[Glu89] shows that whenever $\gamma_{n}(tK)\geq 2^{-O(n)}$ for any constant in
the exponent, one can efficiently find a partial coloring $x\in
O(tK)\cap[-1,1]^{n}$ with at least $n/2$ coordinates in $\\{-1,1\\}$ (see
Theorem 3.1). For settings where the target discrepancy bound is
$n^{\Omega(1)}$, we may iterate the partial coloring to find a full coloring
with the same discrepancy bound up to constants (see Corollary 3.2).

Our new approach for proving a Gaussian measure lower bound
$\gamma_{n}(tK)\geq 2^{-O(n)}$ is via the covering numbers (Definition 2.2) of
$K$ or $K^{\circ}$ with respect to the Euclidean ball $B_{2}^{n}$ or the
$\ell_{\infty}$ ball $B_{\infty}^{n}$. In particular, since
$\gamma_{n}(\sqrt{n}B_{2}^{n})$ has constant Gaussian measure, as long as
$\mathcal{N}(\sqrt{n}B_{2}^{n},tK)\leq 2^{O(n)}$, we get $\gamma_{n}(tK)\geq
2^{-O(n)}$. Using the duality of covering numbers and connections with volume,
we obtain several equivalent conditions for $\gamma_{n}(tK)\geq 2^{-O(n)}$ in
terms of covering (Lemma 3.3). The condition that we will work with is
$\mathcal{N}(K^{\circ},\frac{t}{n}B_{\infty}^{n})\leq 2^{O(n)}$, where
$K^{\circ}=\\{(\langle A_{1},U\rangle,\dots,\langle
A_{n},U\rangle):\|U\|_{*}\leq 1\\}$ is the polar discrepancy body.

Covering via Mirror Descent. We prove the covering number bound
$\mathcal{N}(K^{\circ},\frac{t}{n}B_{\infty}^{n})\leq 2^{O(n)}$ using mirror
descent, a powerful convex optimization primitive of Nemirovski and Yudin
[NY83] (see Section 3.2 for an overview). In particular, denote the linear map
$\mathcal{A}(U):=(\langle A_{1},U\rangle,\dots,\langle A_{n},U\rangle)$. We
shall assume that each $\|A_{i}\|\leq 1$. This is true for the matrix Spencer
setting with $\|\cdot\|$ being the operator norm. In the more general setting
of matrix discrepancy for Schatten norms, we have $\|A_{i}\|_{S_{p}}\leq 1$
while the norm for measuring discrepancy is $\|\cdot\|_{S_{q}}$. One can get
around this issue by leveraging known covering number estimates between
Schatten classes (Theorem 2.6).

For any matrix $\|U\|_{*}\leq 1$, consider minimizing the function
$f_{U}(X):=\|\mathcal{A}(X-U)\|_{\infty}$ over the dual unit ball
$B_{*}:=\\{U:\|U\|_{*}\leq 1\\}$. The function has minimum value $f_{U}(U)=0$
and since it has subgradients in $\\{\pm A_{1},\dots,\pm A_{n}\\}$ with
$\|A_{i}\|\leq 1$, the function $f_{U}(X)$ is $1$-Lipschitz with respect to
the dual norm $\|\cdot\|_{*}$. So as long as there exists a $1$-strongly
convex mirror map $\Phi$ on $B_{*}$, we can minimize $f_{U}(X)$ by starting
from some matrix $U_{0}=U_{0}(U)\in B_{*}$ and running mirror descent for $n$
steps. Denoting by $U_{s}$ the matrix in the $s$-th step, standard guarantees
for mirror descent (Theorem 3.5) yield

$\displaystyle\min_{s\in[n]}f_{U}(U_{s})=\min_{s\in[n]}f_{U}(U_{s})-f_{U}(U)\leq\sqrt{\frac{2D_{\Phi}(U,U_{0})}{n}},$
(1)

where
$D_{\Phi}(U,U_{0})=\Phi(U)-\Phi(U_{0})-\langle\nabla\Phi(U_{0}),U-U_{0}\rangle$
is the Bregman divergence. We let $T$ be the set of all matrices encountered
when running mirror descent for all possible $U\in B_{*}$, i.e.
$T:=\\{U_{s}:s\in[n],U\in B_{*}\\}$, and $T_{0}:=\\{U_{0}:U\in B_{*}\\}$ be
the set of all starting matrices. The net $\mathcal{A}(T)$ will be our
covering for $K^{\circ}$.

To see that this indeed gives a good covering, we denote
$D_{\Phi}^{\max}:=\sup_{U\in B_{*}}D_{\Phi}(U\|U_{0})$. By the definition of
the function $f_{U}$, we have from (1) that

$\displaystyle\min_{s\in[n]}\|\mathcal{A}(U)-\mathcal{A}(U_{s})\|_{\infty}\leq\sqrt{\frac{2D_{\Phi}(U,U_{0})}{n}}\leq\sqrt{\frac{2D_{\Phi}^{\max}}{n}},$

and so the dual body admits the covering
$K^{\circ}\subseteq\mathcal{A}(T)+\sqrt{2D_{\Phi}^{\max}/n}\cdot
B_{\infty}^{n}$. Thus as long as our target discrepancy bound
$t\leq\sqrt{2nD_{\Phi}^{\max}}$, we have
$\mathcal{N}(K^{\circ},\frac{t}{n}B_{\infty}^{n})\leq|T|$, which we need to
show to be at most $2^{O(n)}$.

The key observation we make here is that for our choices of the mirror maps in
Sections 4 and 5, $U_{s}$ only depends333In general, mirror descent projects
back onto the feasible set according to the Bregman divergence in each
iteration, and therefore might not satisfy this property. on the sum of the
subgradients, but not on their order. Since there are only $2n$ choices of
subgradients $\\{\pm A_{i}\\}_{i\in[n]}$ and we run mirror descent for $n$
steps, a counting argument reveals that there are at most $2^{O(n)}$ possible
sums of gradients (Lemma 3.6). So long as the starting matrices satisfy
$|T_{0}|\leq 2^{O(n)}$, we have $|T|\leq|T_{0}|\cdot 2^{O(n)}\leq 2^{O(n)}$.

A View of Mirror Descent as Refining the Net. In the diagonal case, i.e.
Spencer’s setting, we can directly build the net $T$ by repeatedly sampling
the $i$th diagonal coordinate $e_{i}e_{i}^{\top}$ proportional to its weight
in the target matrix. Since the set of diagonal matrices on the Schatten-$1$
ball has only $2m$ vertices $\\{\pm e_{i}e_{i}^{\top}\\}_{i\in[m]}$, the
approximate Carathéodory theorem (see [Ver18], Theorem 0.0.2) implies that the
image of the net $\mathcal{A}(T)$ already gives a good covering for
$K^{\circ}$, and mirror descent is not necessary in this case.

However, this argument fails beyond diagonal matrices, as the number of
vertices becomes infinite. In these more general cases, we use mirror descent
to boost a coarse net $T_{0}$ to a finer net $T$ which has a better covering
guarantee in the image space, at the expense of increasing the size of the net
by a factor of $2^{O(n)}$.

Relative Entropy Nets for the Spectraplex. For our application in Section 5 to
low-rank matrices, it suffices to take $T_{0}=\\{0\\}$. For the application in
Section 4 to block diagonal matrix Spencer, we run mirror descent on the
spectraplex $\mathcal{S}_{m}:=\\{X\in\mathbb{R}^{m\times m}:X\succeq
0,\mathsf{tr}(X)=1\\}$ and carefully construct a set $|T_{0}|\leq 2^{O(n)}$
with small $D_{\Phi}^{\max}$. Since $D_{\Phi}(X\|Y)$ is the quantum relative
entropy between $X$ and $Y$ in the spectraplex setup, we refer to such $T_{0}$
as a (quantum) relative entropy net (Definition 3.7).

We use an operator norm net for the Schatten-1 ball from [HPV17] to construct
a relative entropy net with error $O(\log(m^{2}/n))$ for the spectraplex
$\mathcal{S}_{m}$ (Lemma 3.8). When restricted to block diagonal matrices with
block size $h\times h$, we use a hybrid of this argument and the earlier
approximate Caratheodory argument to find a refined relative entropy net with
error $O(\log(hm/n))$ (Theorem 3.9). Taking $T_{0}$ to be this net in our
mirror descent framework gives Theorem 1.4. This also allows us to reduce the
matrix Spencer conjecture to the existence of a better relative entropy net
with error $O(\log(m/n))$ for the spectraplex (Corollary 1.5).

###  1.3 Further Related Work

Banaszczyk’s Approach. While the partial coloring method has been extensively
applied in discrepancy and obtains the optimal bound for many problems, for
several applications where the target discrepancy bound is $n^{o(1)}$ (e.g.
the Komlós problem or Tusnady’s problem), partial coloring is potentially sub-
optimal by a logarithmic factor. In breakthrough work, Banaszczyk [Ban98]
obtained an improvement over the partial coloring method for these
applications using deep techniques from convex geometry. While Banaszczyk’s
original proof is non-constructive, a fascinating recent line of work has
obtained algorithmic versions of Banaszczyk’s result [DGLN16, BDG16, BG17,
LRR17, BDGL18].

Matrix Spencer Conjecture and Non-commutative Random Matrix Theory. The
typical value of $\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}$ for a random
coloring has attracted significant attention in random matrix theory. For
commutative matrices, the bound
$\mathbb{E}[\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}]\lesssim\sqrt{n\log m}$
by matrix Khintchine [LPP91, Pis03] or matrix Chernoff bound [AW02] is in
general tight. It is also known to be tight for Toeplitz matrices [Mec07]. For
matrices with certain non-commutative structures (e.g. random Gaussian
matrices), improved bounds of $O(\sqrt{n})$ are known (see [Ver18, BBvH21]).
In the context of 1.2, these results imply that a random coloring already
achieves the conjectured bound when the input matrices have certain non-
commutative structures. On the other hand, by Theorem 1.1, 1.2 is known when
all the matrices commute.

Concurrent and Independent Work. In concurrent and independent work, Hopkins,
Raghavendra and Shetty [HRS21] proved a bound of
$\sqrt{n\log\left(\mathsf{tr}(\sum_{i=1}^{n}A_{i}^{2})/n^{1.5}\right)}$ for
matrix Spencer using quantum communication complexity. Their bound coincides
with ours for full rank matrices, and is slightly stronger for low-rank
matrices. However, our approach is completely different and can also be used
to show matrix discrepancy bounds for block diagonal matrices and general
Schatten norms. We believe both approaches are interesting and may lead to
further progress in resolving the matrix Spencer conjecture.

##  2 Preliminaries

#### Norms and Convex Bodies.

A convex body is a compact convex set with non-empty interior. We say a convex
set $K$ is symmetric if $x\in K$ implies $-x\in K$. We use $\|\cdot\|_{p}$ to
denote the $\ell_{p}$-norm and $\|\cdot\|_{S_{p}}$ to denote the Schatten-$p$
norm. In particular, the operator norm
$\|\cdot\|_{\mathrm{op}}=\|\cdot\|_{S_{\infty}}$ and the Frobenius norm
$\|\cdot\|_{F}=\|\cdot\|_{S_{2}}$. We use $B_{p}^{n}$ to denote the unit
$\ell_{p}$-ball in $\mathbb{R}^{n}$ and
$B_{S_{p}}^{n}:=\\{A\in\mathbb{R}^{n\times n}:\|A\|_{S_{p}}\leq 1\\}$ to
denote the unit Schatten-$p$ ball in $\mathbb{R}^{n\times n}$, with
$B_{\mathrm{op}}^{n}:=B_{S_{\infty}}^{n}$. Let $\mathbb{R}^{n}_{+}$ denote the
set of non-negative vectors in $\mathbb{R}^{n}$ and denote the simplex
$\Delta_{n}:=\\{x\in\mathbb{R}^{n}_{+}:\|x\|_{1}=1\\}$. Let
$\mathbb{S}_{+}^{n}$ (resp. $\mathbb{S}_{++}^{n}$) denote the set of positive
semidefinite (resp. positive definite) $n\times n$ matrices, and define the
spectraplex $\mathcal{S}_{n}:=\\{X\in\mathbb{S}_{+}^{n}:\mathsf{tr}(X)=1\\}$.
For a norm $\|\cdot\|$ in $\mathbb{R}^{n}$, we define the dual norm as
$\|x\|_{*}:=\sup\\{\langle y,x\rangle:y\in\mathbb{R}^{n},\|y\|\leq 1\\}$. Dual
norms are similarly defined for matrix norms.

Convex Functions. A convex function $f:\mathcal{X}\rightarrow\mathbb{R}$ is
said to be $L$-Lipschitz with respect to a norm $\|\cdot\|$ if $\|g\|_{*}\leq
L$ for all subgradients $g\in\partial f(x)$. We say that $f$ is
$\alpha$-strongly convex with respect to a norm $\|\cdot\|$ if $f(y)\geq
f(x)+g^{\top}(y-x)+\frac{\alpha}{2}\|x-y\|^{2}$, for all $x,y\in\mathcal{X}$
and all subgradients $g\in\partial f(x)$.

Polar. Given a convex set $K\subseteq\mathbb{R}^{n}$ with $0\in K$, we define
the polar of $K$ to be $K^{\circ}:=\\{y\in\mathbb{R}^{n}:\sup_{x\in K}\langle
x,y\rangle\leq 1\\}$. It is immediate from the definition that for any
constant $t>0$, $(tK)^{\circ}=\frac{1}{t}K^{\circ}$. When $K$ is closed, the
polarity theorem states that $(K^{\circ})^{\circ}=K$.

######  Lemma 2.1 (Polar of Discrepancy Set).

Given matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ and a norm
$\|\cdot\|$ in $\mathbb{R}^{m\times m}$, we define the unit discrepancy set as
$K:=\\{x\in\mathbb{R}^{n}:\|\sum_{i=1}^{n}x_{i}A_{i}\|\leq 1\\}$. Then
$K^{\prime}:=\\{(\langle A_{1},U\rangle,\dots,\langle
A_{n},U\rangle):\|U\|_{*}\leq 1\\}$ is the polar body $K^{\prime}=K^{\circ}$.

###### Proof.

By the definition of polar body, we may write

$\displaystyle(K^{\prime})^{\circ}$
$\displaystyle=\Big{\\{}x\in\mathbb{R}^{n}:\sum_{i=1}^{n}x_{i}\langle{A_{i}},{U}\rangle\leq
1,\ \forall\ U\text{ s.t. }\|U\|_{*}\leq 1\Big{\\}}$
$\displaystyle=\Big{\\{}x\in\mathbb{R}^{n}:\Big{\langle}\sum_{i=1}^{n}x_{i}A_{i},U\Big{\rangle}\leq
1,\ \forall\ U\text{ s.t. }\|U\|_{*}\leq 1\Big{\\}}$ $\displaystyle=K,$

by the definition of dual norm. It then follows from the polarity theorem that
$K^{\prime}=K^{\circ}$. ∎

Covering Numbers. We start with the definition of covering numbers.

######  Definition 2.2 (Covering Numbers).

For two convex bodies $K,T\subseteq\mathbb{R}^{n}$, we define the covering
number $\mathcal{N}(K,T)$ as the minimum number $N$ such that there exist
centers $x_{1},\dots,x_{N}\in\mathbb{R}^{n}$ with
$K\subseteq\cup_{i=1}^{N}(x_{i}+T)$, i.e. $K$ can be covered by $N$ translates
of $T$.

We need the following few standard facts about covering numbers (see
[AAGM15]).

######  Lemma 2.3 (Volume Bounds for Covering Numbers).

Given convex bodies $K,T\subseteq\mathbb{R}^{n}$. If $T$ is symmetric, we have
$\frac{\mathsf{vol}_{n}(K)}{\mathsf{vol}_{n}(T)}\leq\mathcal{N}(K,T)\leq
2^{n}\cdot\frac{\mathsf{vol}_{n}(K+\frac{T}{2})}{\mathsf{vol}_{n}(T)}$.

######  Lemma 2.4 (Symmetrization).

Let $K\subseteq\mathbb{R}^{n}$ be a convex body, then $\mathcal{N}(K-K,K)\leq
2^{O(n)}$.

######  Theorem 2.5 (Duality of Covering Numbers, [KM87]).

Given symmetric convex bodies $K,T\subseteq\mathbb{R}^{n}$, we have

$\displaystyle
2^{-\Theta(n)}\cdot\mathcal{N}(T^{\circ},K^{\circ})\leq\mathcal{N}(K,T)\leq
2^{\Theta(n)}\cdot\mathcal{N}(T^{\circ},K^{\circ}).$

We will also need the following upper bound on the covering numbers of
Schatten balls444We note that [HPV17] claims the bound only up to a constant
depending on $p$ and $q$, but their argument readily gives a universal
constant in the regime of $p,q\geq 1$..

######  Theorem 2.6 ([HPV17], Theorem 1.1).

Let $m,n\in\mathbb{N}$ and $1\leq p\leq q\leq\infty$. Then we have

$\displaystyle\mathcal{N}\Big{(}B_{S_{p}}^{m},\min\Big{(}1,\frac{m}{n}\Big{)}^{1/p-1/q}B_{S_{q}}^{m}\Big{)}\leq
2^{O(n)}.$

Gaussian Measure. We use $\gamma_{n}(\cdot)$ to denote the standard Gaussian
measure on $\mathbb{R}^{n}$. Gaussian measure is log-concave, i.e.
$\gamma_{n}(\lambda
A+(1-\lambda)B)\geq\gamma_{n}(A)^{\lambda}\gamma_{n}(B)^{1-\lambda}$ for any
compact subsets $A,B\subseteq\mathbb{R}^{n}$. In particular, by taking
$A=-x+K$ and $B=x+K$ for any $x\in\mathbb{R}^{n}$ and symmetric convex body
$K$, and $\lambda=1/2$, we have the following lemma.

######  Lemma 2.7 (Translation Decreases Gaussian Measure).

Given any symmetric convex body $K\subseteq\mathbb{R}^{n}$ and
$x\in\mathbb{R}^{n}$, we have $\gamma_{n}(K)\geq\gamma_{n}(x+K)$.

We also use the following powerful Gaussian correlation inequality.

######  Theorem 2.8 (Gaussian Correlation Inequality, [Roy14]).

Given any symmetric convex sets $K,T\subseteq\mathbb{R}^{n}$, we have
$\gamma_{n}(K\cap T)\geq\gamma_{n}(K)\cdot\gamma_{n}(T)$.

##  3 Our Framework for Partial Coloring

###  3.1 Partial Coloring via Covering Numbers

Given symmetric matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$, a norm
$\|\cdot\|$ on $\mathbb{R}^{m\times m}$ for measuring the discrepancy, and a
target discrepancy bound $t$, let
$D:=\\{x\in\mathbb{R}^{n}:\|\sum_{i=1}^{n}x_{i}A_{i}\|\leq t\\}$ be the
associated discrepancy body. The following partial coloring lemma from [RR20]
states that one can efficiently find a partial coloring with discrepancy
$O(t)$ as long as $\gamma_{n}(D)\geq 2^{-O(n)}$.

######  Theorem 3.1 ([RR20], special case of Theorem 6).

For any constant $\alpha>0$, there is a constant $c:=c(\alpha)>0$ and a
randomized polynomial time algorithm that for a symmetric convex set
$D\subseteq\mathbb{R}^{n}$ with $\gamma_{n}(D)\geq 2^{-\alpha n}$ and a shift
$y\in(-1,1)^{n}$, finds $x\in(c\cdot D)\cap[-1,1]^{n}$ so that
$x+y\in[-1,1]^{n}$ and $|\\{i\in[n]:|(x+y)_{i}|=1\\}|\geq n/2$.

We have the following corollary for full colorings. Here
$K_{S}:=K\cap\\{x\in\mathbb{R}^{n}:x_{i}=0,\forall i\notin S\\}$.

######  Corollary 3.2.

Let $K\subseteq\mathbb{R}^{n}$ be a symmetric convex set. Given a function
$f:[n]\to\mathbb{R}_{>0}$ with $\gamma_{S}(f(|S|)\cdot K_{S})\geq 2^{-O(|S|)}$
for every $S\subseteq[n]$, there exists a randomized polynomial time algorithm
to find a full coloring $x\in\\{\pm 1\\}^{n}$ so that $x\in\lambda K$, where
$\lambda\lesssim\sum_{i=0}^{\lfloor\log n\rfloor}f(n/2^{i})$. In particular,
when $f(n)\lesssim n^{\beta}$ for some $\beta\leq 1$, we have
$\lambda\lesssim\frac{1}{\beta}n^{\beta}$.

###### Proof.

Indeed, repeated iterations of Theorem 3.1 with $y_{0}:=0$ and subsequent
shifts $y_{i+1}$ being the coordinates not reaching $\\{-1,1\\}$ find
$x:=x_{0}+\dots+x_{T}\in\\{\pm 1\\}^{n}$ for $T:=\lfloor\log n\rfloor$ with
$x_{t}\in O(f(n/2^{t}))\cdot K$. When $f(n)\lesssim n^{\beta}$, the summation
is upper bounded by

$\sum_{i=0}^{\infty}(n/2^{i})^{\beta}=(1-2^{-\beta})^{-1}\cdot
n^{\beta}\lesssim\frac{1}{\beta}\cdot n^{\beta},$

and this proves the statement. ∎

We show that a $2^{-O(n)}$ Gaussian measure lower bound is equivalent to a
$2^{O(n)}$ upper bound for certain covering numbers.

######  Lemma 3.3.

The following conditions are equivalent for a symmetric convex body
$D\subseteq\mathbb{R}^{n}$:

  1. 1.

$\gamma_{n}(D)\geq 2^{-O(n)}$,

  2. 2.

$\mathcal{N}(\sqrt{n}B_{2}^{n},D)\leq 2^{O(n)}$,

  3. 3.

$\mathcal{N}(nB_{1}^{n},D)\leq 2^{O(n)}$,

  4. 4.

$\mathcal{N}(D^{\circ},\frac{1}{\sqrt{n}}B_{2}^{n})\leq 2^{O(n)}$,

  5. 5.

$\mathcal{N}(D^{\circ},\frac{1}{n}B_{\infty}^{n})\leq 2^{O(n)}$.

###### Proof.

We start by proving that condition (1) implies (2). Suppose $\gamma_{n}(D)\geq
2^{-O(n)}$, then Theorem 2.8 implies $\gamma_{n}(D^{\prime})\geq 2^{-O(n)}$,
where we define $D^{\prime}:=D\cap\sqrt{n}B_{2}^{n}$. We thus also have
$\mathsf{vol}_{n}(D^{\prime})\geq\gamma_{n}(D^{\prime})\geq 2^{-O(n)}$. Then
by Lemma 2.3, we have

$\displaystyle\mathcal{N}(\sqrt{n}B_{2}^{n},D)\leq\mathcal{N}(\sqrt{n}B_{2}^{n},D^{\prime})$
$\displaystyle\leq
2^{n}\cdot\frac{\mathsf{vol}_{n}(\sqrt{n}B_{2}^{n}+D^{\prime})}{\mathsf{vol}_{n}(D^{\prime})}\leq
2^{n}\cdot\frac{\mathsf{vol}_{n}(2\sqrt{n}B_{2}^{n})}{\mathsf{vol}_{n}(D^{\prime})}\leq
2^{O(n)}.$

We next show that condition (2) implies (1). Since
$\gamma_{n}(\sqrt{n}B_{2}^{n})=\Omega(1)$, we have $\gamma_{n}(x+D)\geq
2^{-O(n)}$ for some $x\in\mathbb{R}^{n}$. Lemma 2.7 then gives
$\gamma_{n}(D)\geq\gamma_{n}(x+D)\geq 2^{-O(n)}$.

The implication $(3)\Rightarrow(2)$ immediately follows from
$\sqrt{n}B_{2}^{n}\subseteq nB_{1}^{n}$. To prove the reverse implication
$(2)\Rightarrow(3)$, we use Lemma 2.3 to obtain

$\displaystyle\mathcal{N}(\sqrt{n}B_{1}^{n},B_{2}^{n})\leq
2^{n}\cdot\frac{\mathsf{vol}_{n}(\sqrt{n}B_{1}^{n}+B_{2}^{n})}{\mathsf{vol}_{n}(B_{2}^{n})}\leq
2^{O(n)}\cdot\frac{\mathsf{vol}_{n}(\sqrt{n}B_{1}^{n})}{\mathsf{vol}_{n}(B_{2}^{n})}\leq
2^{O(n)}.$

It thus follows that
$\mathcal{N}(nB_{1}^{n},D)\leq\mathcal{N}(nB_{1}^{n},\sqrt{n}B_{2}^{n})\cdot\mathcal{N}(\sqrt{n}B_{2}^{n},D)\leq
2^{O(n)}$.

The last two equivalences follow from the duality of covering numbers in
Theorem 2.5. ∎

For our mirror descent framework, we use the following corollary:

######  Corollary 3.4.

Given matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$, let
$K^{\circ}_{q+}:=\\{(\langle{A_{1}},{U}\rangle,\dots,\langle{A_{n}},{U}\rangle):U\in
B^{m}_{S_{q}},U\succeq 0\\}$. If we have
$\mathcal{N}(K^{\circ}_{q+},\frac{t}{n}B^{n}_{\infty})\leq 2^{O(n)}$, then we
can efficiently find a partial coloring $x\in[-1,1]^{n}$ with
$|\\{i:|x_{i}|=1\\}|\geq n/2$ and
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}\lesssim t$.

###### Proof.

Recall that $D:=\\{x\in\mathbb{R}^{n}:\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}\leq
t\\}$ denotes the discrepancy body. Since $tD^{\circ}\subseteq
K^{\circ}_{q+}-K^{\circ}_{q+}$, by Lemma 2.4 we have
$\mathcal{N}(D^{\circ},\frac{1}{n}B^{n}_{\infty})=2^{O(n)}$. The equivalence
$(1)\Leftrightarrow(5)$ in Lemma 3.3 implies $\gamma_{n}(D)\geq 2^{-O(n)}$,
and Theorem 3.1 gives the corollary. ∎

###  3.2 Mirror Descent: An Overview

The mirror descent method was introduced by Nemirovski and Yudin [NY83]. Here,
we follow the presentation in [Bub15]. Let $\mathcal{D}$ be an open subset of
$\mathbb{R}^{m}$ and $\mathcal{X}$ a subset of its closure. We fix a convex
function $f:\mathcal{X}\to\mathbb{R}$ assumed to be $L$-Lipschitz with respect
to a norm $\|\cdot\|$, and a differentiable function
$\Phi:\mathcal{D}\to\mathbb{R}$ that is $\rho$-strongly convex with respect to
$\|\cdot\|$ and has a surjective gradient
$\nabla\Phi:\mathcal{D}\to\mathbb{R}^{m}$. The mirror descent algorithm, given
a starting point $x_{0}\in\mathcal{X}\cap\mathcal{D}$, consists of the
iterations

$\displaystyle\nabla\Phi(y_{t+1}):=\nabla\Phi(x_{t})-\eta g_{t},$
$\displaystyle
x_{t+1}:=\mathrm{argmin}_{x\in\mathcal{X}\cap\mathcal{D}}D_{\Phi}(x,y_{t+1}),$

where $g_{t}\in\partial f(x_{t})$ and
$D_{\Phi}(x,y):=\Phi(x)-\Phi(y)-\nabla\Phi(y)^{\top}(x-y)$ is the Bregman
divergence. Note that $y_{t}\in\mathcal{D}$ and
$x_{t}\in\mathcal{X}\cap\mathcal{D}$ for all $t\geq 0$. We use the following
convergence guarantee:

######  Theorem 3.5 ([Bub15], Theorem 4.2).

Let $f$ be $L$-Lipschitz and $\Phi$ be $\rho$-strongly convex with respect to
$\|\cdot\|$, and $D_{\Phi}^{\max}\geq D_{\Phi}(x^{*},x_{0})$ be any upper
bound. Then the mirror descent algorithm with
$\eta:=\frac{1}{L}\sqrt{\frac{2\rho D_{\Phi}^{\max}}{T}}$ satisfies

$\displaystyle\min_{s\in[T]}f(x_{s})-f(x^{*})\leq
L\sqrt{\frac{2D_{\Phi}^{\max}}{\rho T}}.$

The Spectraplex Setup. Here we take
$\mathcal{X}:=\mathcal{S}_{m}=\\{X\in\mathbb{S}_{+}^{m}:\mathsf{tr}(X)=1\\}$.
The mirror map is $\Phi(X)=\mathsf{tr}(X\log X)$, defined on
$\mathcal{D}=\mathbb{S}_{++}^{m}$, which is $\frac{1}{2}$-strongly convex with
respect to the Schatten-$1$ norm by the quantum Pinsker inequality [Car16].
Then the convergence bound in Theorem 3.5 becomes
$2L\sqrt{\frac{S(X^{*}\|X_{0})}{T}}$, where $S(X\|Y):=\mathsf{tr}(X(\log
X-\log Y))$ is the quantum relative entropy between matrices
$X,Y\in\mathcal{S}_{m}$. The projection step corresponds to a trace
normalization, so given a starting point
$X_{0}\in\mathcal{S}_{m}\cap\mathbb{S}_{++}^{m}$, we may write in closed form

$\displaystyle X_{t+1}=\frac{\exp(\log
X_{0}-\eta\sum_{i=0}^{t}g_{i})}{\mathsf{tr}(\exp(\log
X_{0}-\eta\sum_{i=0}^{t}g_{i}))},$ (2)

for subgradients $g_{i}\in\partial f(X_{i})$.

The Schatten Norm Setup. Here we take
$\mathcal{X}=\mathcal{D}=\mathbb{R}^{m\times m}$, so that $X_{t}=Y_{t}$ for
all $t$. The mirror map is $\Phi(X):=\frac{1}{2(p-1)}\|X\|_{p}^{2}$, which is
known to be $1$-strongly convex for all $p\in(1,2]$ [BCL94]. Thus given a
starting point $X_{0}\in\mathbb{R}^{m\times m}$, we may write in closed form

$\displaystyle
X_{t+1}=\nabla\Phi^{-1}\Big{(}\nabla\Phi(X_{0})-\eta\sum_{i=0}^{t}g_{i}\Big{)},$
(3)

for subgradients $g_{i}\in\partial f(X_{i})$.

###  3.3 Covering via Mirror Descent

Given symmetric matrices $A_{1},\dots,A_{n}$ with $\|A_{i}\|\leq 1$ for all
$i\in[n]$, where the dual norm $\|\cdot\|_{*}$ is either the Schatten-1 norm
or the Schatten-$p$ norm for some $p\in(1,2]$, we apply mirror descent on
functions of the form $\displaystyle
f_{U}(X):=\max_{i\in[n]}|\langle{A_{i}},{X-U}\rangle|$ to cover the polar
discrepancy body

$\displaystyle K^{\circ}:=\\{\mathcal{A}(U):\|U\|_{*}\leq 1\\},\text{ where
}\mathcal{A}(U):=(\langle{A_{1}},{U}\rangle,\dots,\langle{A_{n}},{U}\rangle).$

Note that $f_{U}(X)=\|\mathcal{A}(X)-\mathcal{A}(U)\|_{\infty}$ and that $f$
is $1$-Lipschitz with respect to $\|\cdot\|_{*}$. The key property of such
functions is that we may always choose subgradients from the set of $2n$
matrices $\\{\pm A_{i}:i\in[n]\\}$, which allows us to upper bound the number
of different matrices encountered during the mirror descent process.

######  Lemma 3.6.

Let $\|\cdot\|_{*}$ be either $\|\cdot\|_{S_{1}}$ as in the Spectraplex Setup,
or $\|\cdot\|_{S_{p}}$ with $p\in(1,2]$ as in the Schatten Norm Setup, and
$\mathcal{X},\mathcal{D}$ be defined accordingly. Let
$T_{0}\subseteq\mathcal{X}\cap\mathcal{D}$ be a set with size $|T_{0}|\leq
2^{O(n)}$ and $K^{\circ}\supseteq K^{\prime}=\mathcal{A}(T^{\prime})$ the
convex body to be covered, where
$T^{\prime}\subseteq\mathcal{X}\cap\mathcal{D}$. If for every $U\in
T^{\prime}$ there exists a starting point $U_{0}:=U_{0}(U)\in T_{0}$ with
$D_{\Phi}(U,U_{0})\leq D_{\Phi}^{\max}$, then we can bound

$\displaystyle\mathcal{N}\Big{(}K^{\prime},\sqrt{\frac{D_{\Phi}^{\max}}{n}}B^{n}_{\infty}\Big{)}\leq
2^{O(n)}.$

###### Proof.

The key observation is that in either setup of mirror descent, the point
$X_{t}$ in (2) or (3) depends only on the starting point $U_{0}$ and on the
sum of gradients $g_{0},\dots,g_{t-1}$, but not on their order. Moreover, we
can always choose from the set of $2n$ gradients $\\{\pm A_{i}:i\in[n]\\}$ at
each step. Thus applying mirror descent to the function $f_{U}$ for all
possible $U$ with the same starting point $U_{0}$, the total number $N(U_{0})$
of points visited in $T:=n$ iterations satisfies

$\displaystyle
N(U_{0})\leq\sum_{t=0}^{n}{{t+2n-1}\choose{2n-1}}\leq(n+1)\cdot{3n\choose
n}\leq 2^{O(n)}.$

Since $|T_{0}|\leq 2^{O(n)}$, we obtain a set of $2^{O(n)}$ points
$\mathcal{U}$ such that for every $Y=\mathcal{A}(U)\in K^{\prime}$, there
exists some $\tilde{U}\in\mathcal{U}$ so that
$\|\mathcal{A}(\tilde{U})-\mathcal{A}(U)\|_{\infty}=f_{U}(\tilde{U})=f_{U}(\tilde{U})-f_{U}(U)\lesssim\sqrt{D_{\Phi}^{\max}/n}.$
∎

In the Schatten Norm Setup, we shall pick $K^{\prime}=K^{\circ}$ and
$T_{0}=\\{0\\}$, i.e. $U_{0}$ is always $0$. For the Spectraplex Setup, we
carefully choose a set of starting points $|T_{0}|\leq 2^{O(n)}$ which has
small $D_{\Phi}^{\max}$ with respect to
$K^{\prime}=\\{\mathcal{A}(U):U\in\mathcal{S}_{m}\\}$. Since $D_{\Phi}(X\|Y)$
is the quantum relative entropy between $X$ and $Y$ in the Spectraplex Setup,
we shall refer to the set of starting points $T_{0}$ as a (quantum) relative
entropy net for $\mathcal{S}_{m}$.

######  Definition 3.7 (Quantum Relative Entropy Net).

Given subsets $T,\mathcal{M}\subseteq\mathcal{S}_{m}$, $T$ is a relative
entropy net of $\mathcal{M}$ with error $\varepsilon$ if for any
$X\in\mathcal{M}$, we can find $Y\in T$ such that $S(X\|Y)\leq\varepsilon$.

###  3.4 Initialization for Spectraplex Setup: Relative Entropy Net

We start with the following lemma which constructs a relative entropy net on
$\mathcal{S}_{m}$ from an operator norm net.

######  Lemma 3.8 (Relative Entropy Net from Operator Norm Net).

Let $X,Y\in\mathcal{S}_{m}$ satisfies $\|X-Y\|_{\mathrm{op}}\leq\varepsilon$
for some $\varepsilon\geq 1/m$. Then
$S(X\|Y^{\prime})\leq\log(2m\varepsilon)$, where
$Y^{\prime}:=\frac{1}{2}(Y+\frac{I_{m}}{m})\in\mathcal{S}_{m}$.

###### Proof.

Recall that $\log(\cdot)$ is operator monotone and note that $X\preceq
Y+\varepsilon I_{m}$. We then have

$\displaystyle S(X\|Y^{\prime})$ $\displaystyle=\mathsf{tr}(X\cdot(\log X-\log
Y^{\prime}))$ $\displaystyle\leq\mathsf{tr}(X\cdot(\log(Y+\varepsilon
I_{m})-\log Y^{\prime}))$
$\displaystyle\leq\mathsf{tr}(X)\cdot\|\log(Y+\varepsilon I_{m})-\log
Y^{\prime}\|_{\mathrm{op}}$
$\displaystyle\leq\log\left(2\cdot\left\|\frac{Y+\varepsilon
I_{m}}{Y+\frac{I_{m}}{m}}\right\|_{\mathrm{op}}\right)\leq\log(2m\varepsilon),$

where the first inequality follows from the operator monotonicity of
$\log(\cdot)$, the second follows from matrix Hölder, and the last follows
because $\varepsilon\geq 1/m$ and $\|Y\|_{\mathrm{op}}\leq 1$. ∎

Using the lemma above, we give the following construction for relative entropy
nets on $\mathcal{S}_{m}$.

######  Theorem 3.9 (Entropy Net for Spectraplex).

Given positive integers $h,m$ and $n$ such that $m/h$ is an integer, let
$\mathcal{S}_{m}^{h}\subseteq\mathcal{S}_{m}$ be the set of $m\times m$ block
diagonal matrices on the spectraplex with block size $h\times h$. Then we can
find a relative entropy net $T$ for $\mathcal{S}_{m}^{h}$ with error at most
$\max(1,\log(2hm/n))$ and size $|T|\leq 2^{O(n)}$.

###### Proof.

By merging blocks as needed, we may assume $hm\geq n$. By Lemma 3.8, it
suffices to find an operator norm net $T^{\prime}$ with size $|T^{\prime}|\leq
2^{O(n)}$ and distance $\varepsilon=\frac{\max\\{h,\log(m/hn)\\}}{n}$. Let
$\ell:=m/h$ be the number of blocks,
$X_{1},\dots,X_{\ell}\in\mathbb{R}^{h\times h}$ denote the blocks of matrix
$X\in\mathcal{S}_{m}^{h}$, and $N:=2/\varepsilon=2n/\max\\{h,\log(\ell/n)\\}$
(we assume that $N$ is an integer). Let $Z:=\\{z\in\mathbb{Z}_{\geq
0}^{\ell}:\sum_{i=1}^{\ell}z_{i}=N\\}$, and for each $z\in Z$, we define

$T_{z}:=\\{X\in\mathcal{S}_{m}^{h}:\mathsf{tr}(X_{i})=z_{i}/N,\forall
i\in[\ell]\\}.$

It follows from a standard rounding argument that for any matrix
$X\in\mathcal{S}_{m}^{h}$, one can find a matrix $Y\in\cup_{z\in Z}T_{z}$ with
$\|X-Y\|_{\mathrm{op}}\leq 1/N=\varepsilon/2$.

We first show that $|Z|\leq 2^{O(n)}$. When $\ell\leq 2n$, we have

$\displaystyle|Z|\leq\binom{N+\ell}{\ell}\leq\binom{N+2n}{2n}\leq\binom{\frac{2n}{h}+2n}{2n}\leq
2^{O(n)}.$

When $\ell\geq 2n\geq N$, we can bound

$\displaystyle|Z|\leq\binom{N+\ell}{N}\leq\binom{2\ell}{N}\leq\binom{2\ell}{\frac{2n}{\log(\ell/n)}}\leq\left(\frac{e\ell\log(\ell/n)}{n}\right)^{\frac{2n}{\log(\ell/n)}}\leq
2^{O(n)}.$

It therefore suffices to construct an $\varepsilon/2$-operator norm net for
each $T_{z}$.

Fix an arbitrary $z\in Z$. Note that the $i$th block of the matrices in
$T_{z}$ comes from $\frac{z_{i}}{N}\cdot\mathcal{S}_{h}$. Pick
$n_{i}:=z_{i}h$, we have from Theorem 2.6 that

$\displaystyle\mathcal{N}\Big{(}\frac{z_{i}}{N}\mathcal{S}_{h},\frac{z_{i}}{N}\cdot\frac{h}{n_{i}}B_{\mathrm{op}}^{h}\Big{)}=\mathcal{N}\Big{(}\mathcal{S}_{h},\frac{h}{n_{i}}B_{\mathrm{op}}^{h}\Big{)}\leq
2^{O(n_{i})}.$

We denote this net as $\widetilde{T}_{z,i}$. It follows from the above that
for any $X_{i}\in\frac{z_{i}}{N}\mathcal{S}_{h}$, there exists
$Y_{i}\in\widetilde{T}_{z,i}$ with
$\|X_{i}-Y_{i}\|_{\mathrm{op}}\leq\frac{z_{i}}{N}\cdot\frac{h}{n_{i}}=\varepsilon/2$.
Define
$\widetilde{T}_{z}:=\\{\mathsf{diag}(Y_{1},\dots,Y_{\ell}):Y_{i}\in\widetilde{T}_{z,i}\
\forall i\in[\ell]\\}$. Then for any $X\in T_{z}$, there exists
$Y\in\widetilde{T}_{z}$ such that $\|X-Y\|_{\mathrm{op}}\leq\varepsilon/2$,
and thus $\widetilde{T}_{z}$ is indeed an $\varepsilon/2$-operator norm net
for $T_{z}$. Furthermore, the size of $\widetilde{T}_{z}$ can be upper bounded
as

$\displaystyle|\widetilde{T}_{z}|\leq\prod_{i\in[\ell]}2^{O(n_{i})}=2^{O(\sum_{i=1}^{n}z_{i}h)}=2^{O(Nh)}\leq
2^{O(n)},$

since $N\leq 2n/h$. This proves that $\widetilde{T}:=\cup_{z\in
Z}\widetilde{T}_{z}$ is an $\varepsilon$-operator norm net for
$\mathcal{S}_{m}^{h}$ and has size at most $|\widetilde{T}|\leq 2^{O(n)}$,
where we recall that $\varepsilon=\frac{\max\\{h,\log(m/hn)\\}}{n}$. Finally,
invoking Lemma 3.8, $\widetilde{T}$ can be transformed into a relative entropy
net $T$ with size $|T|\leq 2^{O(n)}$ and error at most
$\log(2m\varepsilon)\leq\log(2hm/n)$. This finishes the proof of the theorem.
∎

##  4 Applications of the Spectraplex Setup

In this section, we prove our matrix Spencer bound for block diagonal matrices
in Theorem 1.4, which we restate below.

See 1.4

###### Proof of Theorem 1.4.

By Theorem 3.9, we can find a relative entropy net $T_{0}$ of
$\mathcal{S}_{m}^{h}$ with error $D_{\Phi}^{\max}:=\max(1,\log(2hm/n))$ and
size $|T_{0}|\leq 2^{O(n)}$. Then using Lemma 3.6 with the Spectraplex Setup
for $K^{\prime}:=\mathcal{A}(\mathcal{S}_{m}^{h})$ and $T_{0}$ being the
relative entropy net, we obtain

$\displaystyle\mathcal{N}\Big{(}K^{\prime},\frac{t}{n}B_{\infty}^{n}\Big{)}\leq
2^{O(n)},$

where $t=\sqrt{n\max(1,\log(2hm/n))}$. Let $\mathbb{S}_{m}^{h}$ be the set of
$m\times m$ symmetric block diagonal matrices with block size $h\times h$.
Define convex body
$K^{\prime\prime}:=\mathcal{A}(B_{S_{1}}^{m}\cap\mathbb{S}_{m}^{h}\cap\mathbb{S}^{m}_{+})$.
We first prove that
$\mathcal{N}(K^{\prime\prime},\frac{t}{n}B_{\infty}^{n})\leq 2^{O(n)}$. Since
$\mathcal{N}(K^{\prime},\frac{t}{n}B_{\infty}^{n})\leq 2^{O(n)}$ by Theorem
3.9, we also have
$\mathcal{N}(\frac{j}{n^{2}}K^{\prime},\frac{t}{n}B_{\infty}^{n})\leq
2^{O(n)}$ for each integer $j\in[n^{2}]$. We let $H_{j}$ be the set of centers
for the minimum covering of $\frac{j}{n^{2}}K^{\prime}$ by translates of
$\frac{t}{n}B_{\infty}^{n}$ and define $H=\cup_{j\in[n^{2}]}H_{j}$. Since
$|H_{j}|\leq 2^{O(n)}$, it follows that $|H|\leq 2^{O(n)}$. For each $X\in
B_{S_{1}}^{m}$ that satisfies $X\succeq 0$, we let $\frac{j}{n^{2}}$ be the
multiple of $\frac{1}{n^{2}}$ that is closest to $\mathsf{tr}(X)$, and set
$X^{\prime}:=\frac{j}{n^{2}\mathsf{tr}(X)}\cdot X$. Then we have

$\displaystyle\|\mathcal{A}(X^{\prime})-\mathcal{A}(X)\|_{\infty}\leq\frac{1}{n^{2}}\cdot\|\mathcal{A}(X)\|_{\infty}\leq\frac{t}{n}.$

As $\mathsf{tr}(X^{\prime})=\frac{j}{n^{2}}$, we can also find $Y\in H_{j}$
with $\|\mathcal{A}(X^{\prime})-Y\|_{\infty}\leq\frac{t}{n}$. Therefore,
$\|\mathcal{A}(X)-Y\|_{\infty}\leq\frac{2t}{n}$, and it follows that
$K^{\prime\prime}\subseteq H+\frac{2t}{n}B_{\infty}^{n}$. This implies
$\mathcal{N}(K^{\prime\prime},\frac{t}{n}B_{\infty}^{n})\leq 2^{O(n)}$.

Next note that the dual discrepancy body
$K^{\circ}:=\mathcal{A}(B_{S_{1}}^{m})=\mathcal{A}(B_{S_{1}}^{m}\cap\mathbb{S}_{m}^{h})$
since each $A_{i}\in\mathbb{S}_{m}^{h}$. We have
$K^{\circ}=K^{\prime\prime}-K^{\prime\prime}$, so using Lemma 2.4 we get
$\mathcal{N}(K^{\circ},K^{\prime\prime})\leq 2^{O(n)}$. Thus

$\displaystyle\mathcal{N}\Big{(}K^{\circ},\frac{t}{n}B_{\infty}^{n}\Big{)}\leq\mathcal{N}(K^{\circ},K^{\prime\prime})\cdot\mathcal{N}\Big{(}K^{\prime\prime},\frac{t}{n}B_{\infty}^{n}\Big{)}\leq
2^{O(n)},$

and $\gamma_{n}(tK)\geq 2^{-O(n)}$ by using Lemma 3.3. Corollary 3.2 then
gives a full coloring $x\in\\{\pm 1\\}^{n}$ with discrepancy
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{\mathrm{op}}\leq O(t)$. This finishes the proof
of the theorem. ∎

The analysis above also shows that if we can improve the bound in Theorem 3.9
to $O(\log(m/n))$ for any block size $h$, then the matrix Spencer conjecture
is true.

See 1.5

##  5 Matrix Discrepancy for Schatten Norms

In this section, we prove the following generalization of Theorem 1.3 for
arbitrary Schatten norms by using a different regularizer for mirror descent.

See 1.6

We first use mirror descent to prove the following covering lemma.

######  Lemma 5.1.

Let $m\geq\sqrt{n}$, $2\leq p\leq q<\infty$, $k:=\min(1,m/n)$,
$t:=\sqrt{(p-1)n}\cdot k^{1/p-1/q}$ and $q^{*}:=q/(q-1)$. Given symmetric
matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with
$\|A_{i}\|_{S_{p}}\leq 1$, we have

$\displaystyle\mathcal{N}\Big{(}\mathcal{A}(B^{m}_{S_{q^{*}}}),\frac{t}{n}B^{n}_{\infty}\Big{)}\leq
2^{O(n)}.$

###### Proof.

Denote $p^{*}:=p/(p-1)$. Theorem 2.6 implies
$\mathcal{N}(\mathcal{A}(B^{m}_{S_{q^{*}}}),k^{1/q^{*}-1/p^{*}}\mathcal{A}(B^{m}_{S_{p^{*}}}))\leq
2^{O(n)}$, so it suffices to show

$\displaystyle\mathcal{N}\Big{(}\mathcal{A}(B^{m}_{S_{p^{*}}}),\sqrt{\frac{p-1}{n}}B^{n}_{\infty}\Big{)}\leq
2^{O(n)}.$

This is a direct consequence of Lemma 3.6 with norm $\|\cdot\|_{S_{p^{*}}}$,
as the Bregman divergence is
$D_{\Phi}(U,0)=\Phi(U)\leq\frac{1}{2(p^{*}-1)}=\frac{p-1}{2}$ for
$\|U\|_{S_{p^{*}}}\leq 1$. ∎

Lemma 5.1 together with Lemma 3.3 immediately gives the following weaker
measure bound, which we then bootstrap to prove the stronger bound in Theorem
1.6.

######  Corollary 5.2.

Let $m\geq\sqrt{n}$, $2\leq p\leq q<\infty$ and $k:=\min(1,m/n)$. Given
symmetric matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with
$\|A_{i}\|_{S_{p}}\leq 1$, define the convex body

$\displaystyle
K:=\Big{\\{}x\in\mathbb{R}^{n}:\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{S_{q}}\leq
1\Big{\\}}.$

Then $\gamma_{n}(\sqrt{(p-1)n}\cdot k^{1/p-1/q}\cdot K)\geq 2^{-O(n)}$.

###### Proof of Theorem 1.6.

Let $p_{0}:=\max(2,\log(2rk))$. For $p\leq p_{0}$ the result follows directly
from Corollary 5.2, so we may assume $p\geq p_{0}$. Also note that we may
assume $rk\geq 1$ since we can increase smaller values of $r$ without changing
the bound on the right side. Remark that $\|A_{i}\|_{S_{p_{0}}}\leq
r^{1/p_{0}-1/p}\|A_{i}\|_{S_{p}}\leq r^{1/p_{0}-1/p}$ since the matrices have
rank at most $r$. Corollary 5.2 then implies that the convex body

$\displaystyle\sqrt{p_{0}n}\cdot k^{1/p_{0}-1/q}\cdot r^{1/p_{0}-1/p}\cdot K$

has Gaussian measure $2^{-O(n)}$. Since $\sqrt{p_{0}n}\cdot
k^{1/p_{0}-1/q}\cdot r^{1/p_{0}-1/p}\lesssim\sqrt{p_{0}n}\cdot k^{1/p-1/q}$ by
the choice of $p_{0}$, it follows that

$\displaystyle\gamma_{n}(\sqrt{n\max(1,\log(rk))}\cdot k^{1/p-1/q}\cdot K)\geq
2^{-O(n)},$

so that Theorem 3.1 and Corollary 3.2 yield the partial coloring and full
coloring, respectively. The factor $(1/2+1/p-1/q)^{-1}$ comes from the
contribution of the exponent of $n$ in the geometric sum, analogous to the
second part of Corollary 3.2. ∎

##  6 Lower Bound Examples for Matrix Discrepancy

In this section, we give a few examples to illustrate the tightness of our
results in Theorem 1.6 for various regimes of the dimension $m$ and rank $r$
of the input matrices.

###  6.1 Low Dimension Regime of $m=\Theta(\sqrt{n})$

In the regime of $m=\Theta(\sqrt{n})$, we have
$k=\min(1,m/n)=\Theta(1/\sqrt{n})$ and $r\leq O(\sqrt{n})$ and our partial
coloring bound in Theorem 1.6 is thus $O(n^{1/2+1/2q-1/2p})$. This bound is
tight up to constants due to the following example555Thanks to Aleksandar
Nikolov for suggesting this construction..

######  Lemma 6.1 (Example: $m=\sqrt{n}$).

Let $m=\sqrt{n}$ be a power of $2$, and $2\leq p\leq q\leq\infty$. There exist
matrices666These matrices can easily be made symmetric in
$\mathbb{R}^{2m\times 2m}$. $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with
$\|A_{i}\|_{S_{p}}\leq 1$ such that
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}\gtrsim n^{1/2+1/2q-1/2p}$ for any
partial coloring $x\in\\{\pm 1\\}^{n}$ with $|\\{i:|x_{i}|=1\\}|\geq n/2$.

###### Proof.

The idea is to construct an orthogonal basis on $\mathbb{R}^{m\times m}$ with
$\|A_{i}\|_{F}^{2}=m$. Let $H\in\mathbb{R}^{m\times m}$ be the Walsh-Hadamard
matrix, and $D_{1},\dots,D_{m}$ be diagonal matrices with
$(D_{i})_{j,j}:=H_{i,j}$. Let $P_{1},\dots,P_{m}$ be disjoint permutation
matrices, i.e. each $P_{i}$ permutes the standard orthonormal basis
$\\{e_{1},\dots,e_{m}\\}$ and each pair $P_{i}$, $P_{j}$ have disjoint non-
zero entries. For instance, we may take $(P_{i})_{j,k}:=1$ if $j-k\equiv i\mod
m$ and $0$ otherwise. We then define the $n$ matrices $A_{i+mj}:=D_{i}P_{j}$
for $i,j\in[m]$. Note that these matrices form an orthogonal basis of
$\mathbb{R}^{m\times m}$, so for any partial coloring $x\in\\{\pm 1\\}^{n}$
with $|\\{i:|x_{i}|=1\\}|\geq n/2$, we have

$\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}^{2}_{F}=\mathsf{tr}\left(\left(\sum_{i=1}^{n}x_{i}A_{i}\right)^{2}\right)=m\cdot\sum_{i=1}^{n}x_{i}^{2}\geq
mn/2.$

By Hölder’s inequality, this implies that

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{S_{q}}\geq
m^{1/q-1/2}\cdot\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{F}\gtrsim
n^{1/2+1/2q}.$

Also note that each matrix $A_{i}$ has all singular values equal to $1$, and
therefore $\|A_{i}\|_{S_{p}}=m^{1/p}=n^{1/2p}$. Scaling the matrices $A_{i}$
down by a factor of $n^{1/2p}$ proves the lemma. ∎

###  6.2 Rank-$1$ Matrices and $m\geq n$

In the regime of $r=1$ and $m\geq n$, we may assume wlog that $p=2$. Then the
discrepancy bound in Theorem 1.3 is $O(\sqrt{n})$. This bound is again tight
up to a constant factor.

######  Lemma 6.2 (Example: $r=1$ and $m=n$).

Let $2\leq q\leq\infty$. There exist symmetric rank-$1$ matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{n\times n}$ with $\|A_{i}\|_{F}\leq 1$ such
that any partial coloring $x\in[-1,1]^{n}$ with $|\\{i:|x_{i}|=1\\}|\geq n/2$
satisfies

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{S_{q}}\geq\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{\mathrm{op}}\gtrsim\sqrt{n}.$

###### Proof.

For each $i\in[n-1]$, we define the rank-$1$ matrices
$A_{i}:=\frac{1}{2}(e_{i}+e_{n})(e_{i}+e_{n})^{\top}$ for $i\in[n]$, where
$e_{i}\in\mathbb{R}^{n}$ is the unit vector with a single $1$ in the $i$th
coordinate and $0$ elsewhere, and $A_{n}=0$. Note that each $\|A_{i}\|_{F}=1$
by definition. For any partial coloring $x\in[-1,1]^{n}$ with
$|\\{i:|x_{i}|=1\\}|\geq n/2$, we have

$\displaystyle\sum_{i=1}^{n}x_{i}A_{i}=\frac{1}{2}\cdot\left(\begin{matrix}x_{1}&0&\cdots&0&x_{1}\\\
0&x_{2}&\cdots&0&x_{2}\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&x_{n-1}&x_{n-1}\\\
x_{1}&x_{2}&\cdots&x_{n-1}&\sum_{i=1}^{n-1}x_{i}\end{matrix}\right).$

It then follows that

$\displaystyle\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}\Big{\|}_{\mathrm{op}}\geq\Big{\|}\sum_{i=1}^{n}x_{i}A_{i}e_{n}\Big{\|}_{2}\gtrsim\sqrt{n}.$

This completes the proof of the lemma. ∎

As an immediate corollary of Lemma 6.2, we obtain an $\Omega(\sqrt{n})$ lower
bound for matrix Spencer when $m=n$ and all matrices are rank-$1$.

See 1.7

Another immediate consequence of Lemma 6.2 is a lower bound of
$\Omega(\sqrt{\min(m,n)})$ for Schatten-$2$ to operator norm discrepancy,
which is the generalization of the Komlós problem to matrices. This shows that
the Komlós conjecture, which states that the $\ell_{2}$ to $\ell_{\infty}$
vector discrepancy is upper bounded by a universal constant, cannot be true
for matrices.

See 1.8

## Acknowledgements

We thank Aleksandar Nikolov for insightful discussions and for suggesting the
lower bound example when $m=\sqrt{n}$. We thank Thomas Rothvoss, Sivakanth
Gopi and Mehtaab Sawhney for helpful discussions.

##  Appendix A An Application of Banaszczyk’s Theorem

We give an alternative simpler proof of the $O(m^{1+1/q-1/p})$ bound for
$S_{p}$ to $S_{q}$ matrix discrepancy when $m=O(\sqrt{n})$ using the following
theorem of Banaszczyk [Ban98].

######  Theorem A.1 (Banaszczyk [Ban98]).

Let $K\subseteq\mathbb{R}^{m}$ be a convex body with $\gamma_{m}(K)\geq 1/2$.
Then for any vectors $v_{1},\dots,v_{n}\in\mathbb{R}^{m}$ with
$\|v_{i}\|_{2}\leq 1$, there exists $x\in\\{\pm 1\\}^{n}$ such that
$\sum_{i=1}^{n}x_{i}v_{i}\in 5K$.

Applying Theorem A.1 to a suitable scaling of the operator norm ball
immediately gives the following matrix discrepancy bound.

######  Corollary A.2.

Let $2\leq p\leq q\leq\infty$. Given matrices
$A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with $\|A_{i}\|_{S_{p}}\leq 1$,
there exists $x\in\\{\pm 1\\}^{n}$ such that
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}\lesssim m^{1+1/q-1/p}$.

###### Proof.

Note that $\|A_{i}\|_{S_{p}}\leq 1$ implies $\|A_{i}\|_{S_{2}}\leq
m^{1/2-1/p}$. It is well-known that $\gamma_{m}(4m^{1/2}\cdot
B_{\mathrm{op}}^{m})\geq 1/2$ (see Theorem 7.3.1 of [Ver18]). Thus, Theorem
A.1 yields some $x\in\\{\pm 1\\}^{n}$ such that $\sum_{i=1}^{n}x_{i}A_{i}\in
O(m^{1-1/p})\cdot B_{\mathrm{op}}^{m}$. It follows that
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}\leq O(m^{1+1/q-1/p})$. ∎

######  Corollary A.3 (Matrix Komlós).

Given matrices $A_{1},\dots,A_{n}\in\mathbb{R}^{m\times m}$ with
$\|A_{i}\|_{F}\leq 1$, there exists $x\in\\{\pm 1\\}^{n}$ such that
$\|\sum_{i=1}^{n}x_{i}A_{i}\|_{S_{q}}\lesssim\sqrt{\min(m,n)}$, matching the
lower bound in Corollary 1.8.

###### Proof.

It suffices to take the best between a random coloring, which has discrepancy
$O(\sqrt{n})$, and that of Corollary A.2. ∎

## References

  * [AAGM15] Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D Milman.  Asymptotic geometric analysis, Part I, volume 202.  American Mathematical Soc., 2015.
  * [AW02] Rudolf Ahlswede and Andreas Winter.  Strong converse for identification via quantum channels.  IEEE Transactions on Information Theory, 48(3):569–579, 2002.
  * [Ban98] Wojciech Banaszczyk.  Balancing vectors and gaussian measures of n-dimensional convex bodies.  Random Structures & Algorithms, 12(4):351–360, 1998.
  * [Ban10] Nikhil Bansal.  Constructive algorithms for discrepancy minimization.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 3–10. IEEE, 2010.
  * [Bár08] Imre Bárány.  On the power of linear dependencies.  In Building bridges, pages 31–45. Springer, 2008.
  * [BBvH21] Afonso S Bandeira, March T Boedihardjo, and Ramon van Handel.  Matrix concentration inequalities and free probability.  arXiv preprint arXiv:2108.06312, 2021.
  * [BCKL14] Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, and Shi Li.  Better algorithms and hardness for broadcast scheduling via a discrepancy approach.  In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 55–71. SIAM, 2014.
  * [BCL94] Keith Ball, Eric A Carlen, and Elliott H Lieb.  Sharp uniform convexity and smoothness inequalities for trace norms.  Inventiones Mathematicae, 115(1):463–482, 1994.
  * [BDG16] Nikhil Bansal, Daniel Dadush, and Shashwat Garg.  An algorithm for komlós conjecture matching banaszczyk’s bound.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 788–799. IEEE, 2016.
  * [BDGL18] Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett.  The gram-schmidt walk: a cure for the banaszczyk blues.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 587–597. ACM, 2018.
  * [Bec81] József Beck.  Roth’s estimate of the discrepancy of integer sequences is nearly sharp.  Combinatorica, 1(4):319–325, 1981.
  * [BF81] József Beck and Tibor Fiala.  “integer-making” theorems.  Discrete Applied Mathematics, 3(1):1–8, 1981.
  * [BG17] Nikhil Bansal and Shashwat Garg.  Algorithmic discrepancy beyond partial coloring.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 914–926. ACM, 2017.
  * [BN17] Nikhil Bansal and Viswanath Nagarajan.  Approximation-friendly discrepancy rounding.  In A Journey Through Discrete Mathematics, pages 89–114. Springer, 2017.
  * [Bub15] Sébastien Bubeck.  Convex optimization: Algorithms and complexity, 2015.
  * [Car16] Eric A. Carlen.  A remainder term for hölder’s inequality for matrices and quantum entropy inequalities, 2016.
  * [Cha01] Bernard Chazelle.  The discrepancy method: randomness and complexity.  Cambridge University Press, 2001.
  * [DGLN16] Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov.  Towards a constructive version of banaszczyk’s vector balancing theorem.  arXiv preprint arXiv:1612.04304, 2016.
  * [DNTT18] D. Dadush, A. Nikolov, K. Talwar, and N. Tomczak-Jaegermann.  Balancing vectors in any norm.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 1–10, 2018.
  * [ES18] Ronen Eldan and Mohit Singh.  Efficient algorithms for discrepancy minimization in convex sets.  Random Structures & Algorithms, 53(2):289–307, 2018.
  * [Glu89] Efim Davydovich Gluskin.  Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces.  Mathematics of the USSR-Sbornik, 64(1):85, 1989.
  * [HPV17] Aicke Hinrichs, Joscha Prochno, and Jan Vybiral.  Entropy numbers of embeddings of schatten classes.  Journal of Functional Analysis, 273(10):3241–3261, 2017.
  * [HRS21] Samuel B Hopkins, Prasad Raghavendra, and Abhishek Shetty.  Matrix discrepancy from quantum communication.  arXiv preprint arXiv:2110.10099, 2021.
  * [KLS20] Rasmus Kyng, Kyle Luh, and Zhao Song.  Four deviations suffice for rank 1 matrices.  Advances in Mathematics, 375:107366, 2020.
  * [KM87] Hermann König and Vitali D Milman.  On the covering numbers of convex bodies.  In Geometrical Aspects of Functional Analysis, pages 82–95. Springer, 1987.
  * [LM15] Shachar Lovett and Raghu Meka.  Constructive discrepancy minimization by walking on the edges.  SIAM Journal on Computing, 44(5):1573–1582, 2015.
  * [LPP91] Françoise Lust-Piquard and Gilles Pisier.  Non commutative khintchine and paley inequalities.  Arkiv för matematik, 29(1):241–260, 1991.
  * [LRR17] Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss.  Deterministic discrepancy minimization via the multiplicative weight update method.  In International Conference on Integer Programming and Combinatorial Optimization, pages 380–391. Springer, 2017.
  * [LRS11] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh.  Iterative methods in combinatorial optimization, volume 46.  Cambridge University Press, 2011.
  * [Mat09] Jiri Matousek.  Geometric discrepancy: An illustrated guide, volume 18.  Springer Science & Business Media, 2009.
  * [Mec07] Mark Meckes.  On the spectral norm of a random Toeplitz matrix.  Electronic Communications in Probability, 12(none):315 – 325, 2007\.
  * [Mek14] Raghu Meka.  Discrepancy and beating the union bound.  2014\.
  * [MSS15] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava.  Interlacing families ii: Mixed characteristic polynomials and the kadison—singer problem.  Annals of Mathematics, pages 327–350, 2015.
  * [NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang.  The geometry of differential privacy: the sparse and approximate cases.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 351–360, 2013.
  * [NY83] Arkadi Semenovič Nemirovski and David Borisovich Yudin.  Problem complexity and method efficiency in optimization.  1983\.
  * [Pis03] Gilles Pisier.  Introduction to operator space theory, volume 294.  Cambridge University Press, 2003.
  * [Rot13] Thomas Rothvoss.  Approximating bin packing within o (log opt* log log opt) bins.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 20–29. IEEE, 2013.
  * [Rot17] Thomas Rothvoss.  Constructive discrepancy minimization for convex sets.  SIAM Journal on Computing, 46(1):224–234, 2017.
  * [Roy14] Thomas Royen.  A simple proof of the gaussian correlation conjecture extended to multivariate gamma distributions.  arXiv preprint arXiv:1408.1028, 2014.
  * [RR20] Victor Reis and Thomas Rothvoss.  Vector balancing in lebesgue spaces.  arXiv preprint arXiv:2007.05634, 2020.
  * [Šid67] Zbyněk Šidák.  Rectangular confidence regions for the means of multivariate normal distributions.  Journal of the American Statistical Association, 62(318):626–633, 1967.
  * [Spe85] Joel Spencer.  Six standard deviations suffice.  Transactions of the American mathematical society, 289(2):679–706, 1985.
  * [Ver18] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [Zou12] Anastasios Zouzias.  A matrix hyperbolic cosine algorithm and applications.  In International Colloquium on Automata, Languages, and Programming, pages 846–858. Springer, 2012.