Theory of Computing
-------------------
Title : Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
Authors : Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov
Volume : 15
Number : 15
Pages : 1-58
URL : https://theoryofcomputing.org/articles/v015a015
Abstract
--------
An important theorem of Banaszczyk (Random Structures & Algorithms
1998) states that for any sequence of vectors of $\ell_2$ norm at most
$1/5$ and any convex body $K$ of Gaussian measure $1/2$ in $R^n$,
there exists a signed combination of these vectors which lands inside
$K$. A major open problem is to devise a constructive version of
Banaszczyk's vector balancing theorem, i.e., to find an efficient
algorithm which constructs the signed combination.
We make progress towards this goal along several fronts. As our first
contribution, we show an equivalence between Banaszczyk's theorem and
the existence of $O(1)$-subgaussian distributions over signed
combinations. For the case of symmetric convex bodies, our equivalence
implies the existence of a _universal_ signing algorithm (i.e.,
independent of the body), which simply samples from the subgaussian
sign distribution and checks to see if the associated combination
lands inside the body. For asymmetric convex bodies, we provide a
novel _recentering procedure_, which allows us to reduce to the case
where the body is symmetric.
As our second main contribution, we show that the above framework can
be efficiently implemented when the vectors have length
$O(1/\sqrt{\log n})$, recovering Banaszczyk's results under this
stronger assumption. More precisely, we use random walk techniques to
produce the required $O(1)$-subgaussian signing distributions when the
vectors have length $O(1/\sqrt{\log n})$, and use a stochastic
gradient ascent method to implement the recentering procedure for
asymmetric bodies.
------------------
An extended abstract of this paper appeared in the Proceedings of the
20th International Workshop on Randomization and Computation, RANDOM 2016.