Towards a constructive version of Banaszczyk's vector balancing theorem

Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
10 Downloads (Pure)

Abstract

An important theorem of Banaszczyk (Random Structures & Algorithms-98) states that for any sequence of vectors of ℓ2 norm at most 1/5 and any convex body K of Gaussian measure 1/2 in ℝ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/√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/√log n), and use a stochastic gradient ascent method to implement the recentering procedure for asymmetric bodies.

Original languageEnglish
Title of host publicationApproximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
EditorsKlaus Jansen, Claire Mathieu, José D.P. Rolim, Chris Umans
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)978-3-95977-018-7
DOIs
Publication statusPublished - 1 Sep 2016
Event19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 - Paris, France
Duration: 7 Sep 20169 Sep 2016

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume60
ISSN (Print)1868-8969

Conference

Conference19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
CountryFrance
CityParis
Period7/09/169/09/16

Keywords

  • Convex Geometry
  • Discrepancy
  • Vector Balancing

Cite this

Dadush, D., Garg, S., Lovett, S., & Nikolov, A. (2016). Towards a constructive version of Banaszczyk's vector balancing theorem. In K. Jansen, C. Mathieu, J. D. P. Rolim, & C. Umans (Eds.), Approximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016 [28] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 60). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.28
Dadush, Daniel ; Garg, Shashwat ; Lovett, Shachar ; Nikolov, Aleksandar. / Towards a constructive version of Banaszczyk's vector balancing theorem. Approximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. editor / Klaus Jansen ; Claire Mathieu ; José D.P. Rolim ; Chris Umans. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{721446b4dad84fbc85ac7dff413bfb2f,
title = "Towards a constructive version of Banaszczyk's vector balancing theorem",
abstract = "An important theorem of Banaszczyk (Random Structures & Algorithms-98) states that for any sequence of vectors of ℓ2 norm at most 1/5 and any convex body K of Gaussian measure 1/2 in ℝ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/√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/√log n), and use a stochastic gradient ascent method to implement the recentering procedure for asymmetric bodies.",
keywords = "Convex Geometry, Discrepancy, Vector Balancing",
author = "Daniel Dadush and Shashwat Garg and Shachar Lovett and Aleksandar Nikolov",
year = "2016",
month = "9",
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2016.28",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Jansen, {Klaus } and Mathieu, {Claire } and Rolim, {Jos{\'e} D.P.} and Chris Umans",
booktitle = "Approximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016",

}

Dadush, D, Garg, S, Lovett, S & Nikolov, A 2016, Towards a constructive version of Banaszczyk's vector balancing theorem. in K Jansen, C Mathieu, JDP Rolim & C Umans (eds), Approximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016., 28, Leibniz International Proceedings in Informatics (LIPIcs), vol. 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016, Paris, France, 7/09/16. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.28

Towards a constructive version of Banaszczyk's vector balancing theorem. / Dadush, Daniel; Garg, Shashwat; Lovett, Shachar; Nikolov, Aleksandar.

Approximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. ed. / Klaus Jansen; Claire Mathieu; José D.P. Rolim; Chris Umans. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. 28 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 60).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Towards a constructive version of Banaszczyk's vector balancing theorem

AU - Dadush, Daniel

AU - Garg, Shashwat

AU - Lovett, Shachar

AU - Nikolov, Aleksandar

PY - 2016/9/1

Y1 - 2016/9/1

N2 - An important theorem of Banaszczyk (Random Structures & Algorithms-98) states that for any sequence of vectors of ℓ2 norm at most 1/5 and any convex body K of Gaussian measure 1/2 in ℝ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/√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/√log n), and use a stochastic gradient ascent method to implement the recentering procedure for asymmetric bodies.

AB - An important theorem of Banaszczyk (Random Structures & Algorithms-98) states that for any sequence of vectors of ℓ2 norm at most 1/5 and any convex body K of Gaussian measure 1/2 in ℝ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/√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/√log n), and use a stochastic gradient ascent method to implement the recentering procedure for asymmetric bodies.

KW - Convex Geometry

KW - Discrepancy

KW - Vector Balancing

UR - http://www.scopus.com/inward/record.url?scp=84990833497&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2016.28

DO - 10.4230/LIPIcs.APPROX-RANDOM.2016.28

M3 - Conference contribution

AN - SCOPUS:84990833497

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - Approximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016

A2 - Jansen, Klaus

A2 - Mathieu, Claire

A2 - Rolim, José D.P.

A2 - Umans, Chris

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

ER -

Dadush D, Garg S, Lovett S, Nikolov A. Towards a constructive version of Banaszczyk's vector balancing theorem. In Jansen K, Mathieu C, Rolim JDP, Umans C, editors, Approximation, randomization, and combinatorial optimization: algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. 28. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.28