Balancing Gaussian vectors in high dimension

Paxton Turner, Raghu Meka, Philippe Rigollet
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3455-3486, 2020.

Abstract

Motivated by problems in controlled experiments, we study the discrepancy of random matrices with continuous entries where the number of columns n is much larger than the number of rows m. Our first result shows that if ω(1)=m=o(n), a matrix with i.i.d. standard Gaussian entries has discrepancy Θ(√n2−n/m) with high probability. This provides sharp guarantees for Gaussian discrepancy in a regime that had not been considered before in the existing literature. Our results also apply to a more general family of random matrices with continuous i.i.d. entries, assuming that m=O(n/logn). The proof is non-constructive and is an application of the second moment method. Our second result is algorithmic and applies to random matrices whose entries are i.i.d. and have a Lipschitz density. We present a randomized polynomial-time algorithm that achieves discrepancy e−Ω(log2(n)/m) with high probability, provided that m=O(√logn). In the one-dimensional case, this matches the best known algorithmic guarantees due to Karmarkar–Karp. For higher dimensions 2≤m=O(√logn), this establishes the first efficient algorithm achieving discrepancy smaller than O(√m).

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-turner20a, title = {Balancing Gaussian vectors in high dimension}, author = {Turner, Paxton and Meka, Raghu and Rigollet, Philippe}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {3455--3486}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/turner20a/turner20a.pdf}, url = {https://proceedings.mlr.press/v125/turner20a.html}, abstract = { Motivated by problems in controlled experiments, we study the discrepancy of random matrices with continuous entries where the number of columns $n$ is much larger than the number of rows $m$. Our first result shows that if $\omega(1) = m = o(n)$, a matrix with i.i.d. standard Gaussian entries has discrepancy $\Theta(\sqrt{n} \, 2^{-n/m})$ with high probability. This provides sharp guarantees for Gaussian discrepancy in a regime that had not been considered before in the existing literature. Our results also apply to a more general family of random matrices with continuous i.i.d. entries, assuming that $m = O(n/\log{n})$. The proof is non-constructive and is an application of the second moment method. Our second result is algorithmic and applies to random matrices whose entries are i.i.d. and have a Lipschitz density. We present a randomized polynomial-time algorithm that achieves discrepancy $e^{-\Omega(\log^2(n)/m)}$ with high probability, provided that $m = O(\sqrt{\log{n}})$. In the one-dimensional case, this matches the best known algorithmic guarantees due to Karmarkar–Karp. For higher dimensions $2 \leq m = O(\sqrt{\log{n}})$, this establishes the first efficient algorithm achieving discrepancy smaller than $O( \sqrt{m} )$. } }
Endnote
%0 Conference Paper %T Balancing Gaussian vectors in high dimension %A Paxton Turner %A Raghu Meka %A Philippe Rigollet %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-turner20a %I PMLR %P 3455--3486 %U https://proceedings.mlr.press/v125/turner20a.html %V 125 %X Motivated by problems in controlled experiments, we study the discrepancy of random matrices with continuous entries where the number of columns $n$ is much larger than the number of rows $m$. Our first result shows that if $\omega(1) = m = o(n)$, a matrix with i.i.d. standard Gaussian entries has discrepancy $\Theta(\sqrt{n} \, 2^{-n/m})$ with high probability. This provides sharp guarantees for Gaussian discrepancy in a regime that had not been considered before in the existing literature. Our results also apply to a more general family of random matrices with continuous i.i.d. entries, assuming that $m = O(n/\log{n})$. The proof is non-constructive and is an application of the second moment method. Our second result is algorithmic and applies to random matrices whose entries are i.i.d. and have a Lipschitz density. We present a randomized polynomial-time algorithm that achieves discrepancy $e^{-\Omega(\log^2(n)/m)}$ with high probability, provided that $m = O(\sqrt{\log{n}})$. In the one-dimensional case, this matches the best known algorithmic guarantees due to Karmarkar–Karp. For higher dimensions $2 \leq m = O(\sqrt{\log{n}})$, this establishes the first efficient algorithm achieving discrepancy smaller than $O( \sqrt{m} )$.
APA
Turner, P., Meka, R. & Rigollet, P.. (2020). Balancing Gaussian vectors in high dimension. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:3455-3486 Available from https://proceedings.mlr.press/v125/turner20a.html.

Related Material