Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

Authors Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.28.pdf
  • Filesize: 486 kB
  • 12 pages

Document Identifiers

Author Details

Daniel Dadush
Shashwat Garg
Shachar Lovett
Aleksandar Nikolov

Cite AsGet BibTex

Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.28

Abstract

An important theorem of Banaszczyk (Random Structures & Algorithms 1998) states that for any sequence of vectors of l_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.
Keywords
  • Discrepancy
  • Vector Balancing
  • Convex Geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. David Applegate and Ravi Kannan. Sampling and integration of near log-concave functions. In Proceedings of the 23rd annual ACM symposium on Theory of Computing, pages 156-163, 1991. Google Scholar
  2. Wojciech Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures Algorithms, 12(4):351-360, 1998. Google Scholar
  3. Wojciech Banaszczyk. On series of signed vectors and their rearrangements. Random Struct. Algorithms, 40(3):301-316, 2012. URL: http://dx.doi.org/10.1002/rsa.20373.
  4. Nikhil Bansal. Constructive algorithms for discrepancy minimization. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science FOCS 2010, pages 3-10. IEEE Computer Soc., Los Alamitos, CA, 2010. Google Scholar
  5. Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An algorithm for Komlós conjecture matching Banaszczyk’s bound. To appears in FOCS, 2016. Google Scholar
  6. Franck Barthe, Olivier Guédon, Shahar Mendelson, and Assaf Naor. A probabilistic approach to the geometry of the lⁿ_p-ball. Ann. Probab., 33(2):480-513, 2005. Google Scholar
  7. József Beck. Roth’s estimate of the discrepancy of integer sequences is nearly sharp. Combinatorica, 1(4):319-325, 1981. Google Scholar
  8. József Beck and Tibor Fiala. "Integer-making" theorems. Discrete Appl. Math., 3(1):1-8, 1981. Google Scholar
  9. Boris Bukh. An improvement of the Beck-Fiala theorem. CoRR, abs/1306.6081, 2013. Google Scholar
  10. Bernard Chazelle. The discrepancy method. Cambridge University Press, Cambridge, 2000. Randomness and complexity. Google Scholar
  11. William Chen, Anand Srivastav, Giancarlo Travaglini, et al. A Panorama of Discrepancy Theory, volume 2107. Springer, 2014. Google Scholar
  12. Ben Cousins and Santosh Vempala. A cubic algorithm for computing Gaussian volume. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1215-1228. ACM, New York, 2014. Google Scholar
  13. Ronen Eldan and Mohit Singh. Efficient algorithms for discrepancy minimization in convex sets. CoRR, abs/1409.2913, 2014. Google Scholar
  14. Esther Ezra and Shachar Lovett. On the Beck-Fiala conjecture for random set systems. Electronic Colloquium on Computational Complexity (ECCC), 22:190, 2015. Google Scholar
  15. Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh. Discrepancy without partial colorings. In Approximation, randomization, and combinatorial optimization, volume 28 of LIPIcs. Leibniz Int. Proc. Inform., pages 258-273. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014. Google Scholar
  16. L. Lovász, J. Spencer, and K. Vesztergombi. Discrepancy of set-systems and matrices. European J. Combin., 7(2):151-160, 1986. URL: http://dx.doi.org/10.1016/S0195-6698(86)80041-5.
  17. László Lovász and Santosh Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 57-68, 2006. Google Scholar
  18. Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges. SIAM J. Comput., 44(5):1573-1582, 2015. Preliminary version in FOCS 2012. Google Scholar
  19. Jiří Matoušek. Geometric discrepancy, volume 18 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1999. An illustrated guide. Google Scholar
  20. Aleksandar Nikolov. The Komlós conjecture holds for vector colorings. arXiv preprint arXiv:1301.4039, 2013. Google Scholar
  21. Aleksandar Nikolov and Kunal Talwar. Approximating hereditary discrepancy via small width ellipsoids. In Symposium on Discrete Algorithms, SODA, pages 324-336, 2015. Google Scholar
  22. Thomas Rothvoss. Constructive discrepancy minimization for convex sets. In 55th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2014, pages 140-145. IEEE Computer Soc., Los Alamitos, CA, 2014. Google Scholar
  23. Joel Spencer. Six standard deviations suffice. Trans. Amer. Math. Soc., 289(2):679-706, 1985. Google Scholar
  24. Joel Spencer. Ten lectures on the probabilistic method, volume 52. SIAM, 1987. Google Scholar
  25. Aravind Srinivasan. Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), pages 692-701. ACM, New York, 1997. Google Scholar
  26. Michel Talagrand. Regularity of Gaussian processes. Acta Math., 159(1-2):99-149, 1987. URL: http://dx.doi.org/10.1007/BF02392556.
  27. Michel Talagrand. Upper and lower bounds for stochastic processes, volume 60 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer, Heidelberg, 2014. Modern methods and classical problems. URL: http://dx.doi.org/10.1007/978-3-642-54075-2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail