Document Open Access Logo

Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices

Author Prayaag Venkat

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.98.pdf
  • Filesize: 0.71 MB
  • 12 pages

Document Identifiers

Author Details

Prayaag Venkat
  • School of Engineering and Applied Sciences, Harvard University, Boston, MA, USA

Funding

  • Venkat, Prayaag: The author was supported by NSF grant CCF-1565264 and an NSF Graduate Fellowship under grant DGE1745303.

Acknowledgements

The author would like to thank Boaz Barak, Alex Wein and Ilias Zadik for helpful discussions.

Cite AsGet BibTex

Prayaag Venkat. Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 98:1-98:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.98

Abstract

In this paper, we initiate the study of the algorithmic problem of certifying lower bounds on the discrepancy of random matrices: given an input matrix A ∈ ℝ^{m × n}, output a value that is a lower bound on disc(A) = min_{x ∈ {± 1}ⁿ} ‖Ax‖_∞ for every A, but is close to the typical value of disc(A) with high probability over the choice of a random A. This problem is important because of its connections to conjecturally-hard average-case problems such as negatively-spiked PCA [Afonso S. Bandeira et al., 2020], the number-balancing problem [Gamarnik and Kızıldağ, 2021] and refuting random constraint satisfaction problems [Prasad Raghavendra et al., 2017]. We give the first polynomial-time algorithms with non-trivial guarantees for two main settings. First, when the entries of A are i.i.d. standard Gaussians, it is known that disc(A) = Θ (√n2^{-n/m}) with high probability [Karthekeyan Chandrasekaran and Santosh S. Vempala, 2014; Aubin et al., 2019; Paxton Turner et al., 2020] and that super-constant levels of the Sum-of-Squares SDP hierarchy fail to certify anything better than disc(A) ≥ 0 when m < n - o(n) [Mrinalkanti Ghosh et al., 2020]. In contrast, our algorithm certifies that disc(A) ≥ exp(-O(n²/m)) with high probability. As an application, this formally refutes a conjecture of Bandeira, Kunisky, and Wein [Afonso S. Bandeira et al., 2020] on the computational hardness of the detection problem in the negatively-spiked Wishart model. Second, we consider the integer partitioning problem: given n uniformly random b-bit integers a₁, …, a_n, certify the non-existence of a perfect partition, i.e. certify that disc(A) ≥ 1 for A = (a₁, …, a_n). Under the scaling b = α n, it is known that the probability of the existence of a perfect partition undergoes a phase transition from 1 to 0 at α = 1 [Christian Borgs et al., 2001]; our algorithm certifies the non-existence of perfect partitions for some α = O(n). We also give efficient non-deterministic algorithms with significantly improved guarantees, raising the possibility that the landscape of these certification problems closely resembles that of e.g. the problem of refuting random 3SAT formulas in the unsatisfiable regime. Our algorithms involve a reduction to the Shortest Vector Problem and employ the Lenstra-Lenstra-Lovász algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Average-case discrepancy theory
  • lattices
  • shortest vector problem

Metrics

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

References

  1. Emmanuel Abbe, Shuangping Li, and Allan Sly. Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 327-338. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00041.
  2. Dorit Aharonov and Oded Regev. Lattice problems in NP cap conp. J. ACM, 52(5):749-765, 2005. URL: https://doi.org/10.1145/1089023.1089025.
  3. Dylan J. Altschuler and Jonathan Niles-Weed. The discrepancy of random rectangular matrices. Random Struct. Algorithms, 60(4):551-593, 2022. URL: https://doi.org/10.1002/rsa.21054.
  4. Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 171-180. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806715.
  5. Benjamin Aubin, Will Perkins, and Lenka Zdeborová. Storage capacity in symmetric binary perceptrons. Journal of Physics A: Mathematical and Theoretical, 52(29):294003, 2019. Google Scholar
  6. Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein. Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 410-473. PMLR, 2021. URL: http://proceedings.mlr.press/v134/bandeira21a.html.
  7. Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. Computational hardness of certifying bounds on constrained PCA problems. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 78:1-78:29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.78.
  8. Nikhil Bansal. Algorithmic aspects of combinatorial discrepancy. In A Panorama of Discrepancy Theory, pages 425-457. Springer, 2014. Google Scholar
  9. Heiko Bauke, Silvio Franz, and Stephan Mertens. Number partitioning as a random energy model. Journal of Statistical Mechanics: Theory and Experiment, 2004(04):P04003, 2004. Google Scholar
  10. Heiko Bauke and Stephan Mertens. Universality in the level statistics of disordered systems. Physical Review E, 70(2):025102, 2004. Google Scholar
  11. Stefan Boettcher and Stephan Mertens. Analysis of the karmarkar-karp differencing algorithm. The European Physical Journal B, 65(1):131-140, 2008. Google Scholar
  12. Christian Borgs, Jennifer T. Chayes, Stephan Mertens, and Chandra Nair. Proof of the local REM conjecture for number partitioning. I: constant energy scales. Random Struct. Algorithms, 34(2):217-240, 2009. URL: https://doi.org/10.1002/rsa.20255.
  13. Christian Borgs, Jennifer T. Chayes, Stephan Mertens, and Chandra Nair. Proof of the local REM conjecture for number partitioning. II. growing energy scales. Random Struct. Algorithms, 34(2):241-284, 2009. URL: https://doi.org/10.1002/rsa.20256.
  14. Christian Borgs, Jennifer T. Chayes, and Boris G. Pittel. Phase transition and finite-size scaling for the integer partitioning problem. Random Struct. Algorithms, 19(3-4):247-288, 2001. URL: https://doi.org/10.1002/rsa.10004.
  15. Karthekeyan Chandrasekaran and Santosh S. Vempala. Integer feasibility of random polytopes: random integer programs. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 449-458. ACM, 2014. URL: https://doi.org/10.1145/2554797.2554838.
  16. Moses Charikar, Alantha Newman, and Aleksandar Nikolov. Tight hardness results for minimizing discrepancy. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1607-1614. SIAM, 2011. URL: https://doi.org/10.1137/1.9781611973082.124.
  17. Bernard Chazelle. The discrepancy method - randomness and complexity. Cambridge University Press, 2001. Google Scholar
  18. William Chen, Anand Srivastav, Giancarlo Travaglini, et al. A panorama of discrepancy theory, volume 2107. Springer, 2014. Google Scholar
  19. Michael B. Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near-optimal algorithm for approximating the john ellipsoid. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 849-873. PMLR, 2019. URL: http://proceedings.mlr.press/v99/cohen19a.html.
  20. Kevin P Costello. Balancing gaussian vectors. Israel Journal of Mathematics, 172(1):145-156, 2009. Google Scholar
  21. Amit Daniely. Complexity theoretic limitations on learning halfspaces. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 105-117. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897520.
  22. Ilias Diakonikolas and Daniel Kane. Non-gaussian component analysis via lattice basis reduction. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 4535-4547. PMLR, 2022. URL: https://proceedings.mlr.press/v178/diakonikolas22d.html.
  23. Uriel Feige, Jeong Han Kim, and Eran Ofek. Witnesses for non-satisfiability of dense random 3cnf formulas. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 497-508. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.78.
  24. Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic proofs and efficient algorithm design. Found. Trends Theor. Comput. Sci., 14(1-2):1-221, 2019. URL: https://doi.org/10.1561/0400000086.
  25. David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences, 118(41):e2108492118, 2021. Google Scholar
  26. David Gamarnik and Eren C Kızıldağ. Algorithmic obstructions in the random number partitioning problem. arXiv preprint arXiv:2103.01369, 2021. Google Scholar
  27. David Gamarnik, Eren C. Kizildag, Will Perkins, and Changji Xu. Algorithms and barriers in the symmetric binary perceptron model. CoRR, abs/2203.15667, 2022. URL: https://doi.org/10.48550/arXiv.2203.15667.
  28. David Gamarnik, Eren C. Kizildag, and Ilias Zadik. Inference in high-dimensional linear regression via lattice basis reduction and integer relation detection. IEEE Trans. Inf. Theory, 67(12):8109-8139, 2021. URL: https://doi.org/10.1109/TIT.2021.3113921.
  29. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  30. Ian P. Gent and Toby Walsh. Phase transitions and annealed theories: Number partitioning as a case study. In Wolfgang Wahlster, editor, 12th European Conference on Artificial Intelligence, Budapest, Hungary, August 11-16, 1996, Proceedings, pages 170-174. John Wiley and Sons, Chichester, 1996. Google Scholar
  31. Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran. Sum-of-squares lower bounds for sherrington-kirkpatrick via planted affine planes. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 954-965. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00093.
  32. Christopher Harshaw, Fredrik Sävje, Daniel A. Spielman, and Peng Zhang. Balancing covariates in randomized experiments using the gram-schmidt walk. CoRR, abs/1911.03071, 2019. URL: http://arxiv.org/abs/1911.03071.
  33. Narendra Karmarkar and Richard M Karp. The differencing method of set partitioning. Computer Science Division (EECS), University of California Berkeley, 1982. Google Scholar
  34. Richard E. Korf. A complete anytime algorithm for number partitioning. Artif. Intell., 106(2):181-203, 1998. URL: https://doi.org/10.1016/S0004-3702(98)00086-1.
  35. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 132-145. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055485.
  36. Abba M Krieger, David Azriel, and Adam Kapelner. Nearly random designs with greatly improved balance. Biometrika, 106(3):695-701, 2019. Google Scholar
  37. Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515-534, 1982. Google Scholar
  38. Jiri Matousek. Geometric discrepancy: An illustrated guide, volume 18. Springer Science & Business Media, 1999. Google Scholar
  39. Stephan Mertens. Phase transition in the number partitioning problem. Physical Review Letters, 81(20):4281, 1998. Google Scholar
  40. Stephan Mertens. Random costs in combinatorial optimization. Physical Review Letters, 84(6):1347, 2000. Google Scholar
  41. Will Perkins and Changji Xu. Frozen 1-rsb structure of the symmetric ising perceptron. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1579-1588. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451119.
  42. Aditya Potukuchi. Discrepancy in random hypergraph models. CoRR, abs/1811.01491, 2018. URL: http://arxiv.org/abs/1811.01491.
  43. Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random csps below the spectral threshold. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 121-131. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055417.
  44. Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 29602-29615, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/f78688fb6a5507413ade54a230355acd-Abstract.html.
  45. Paxton Turner, Raghu Meka, and Philippe Rigollet. Balancing gaussian vectors in high dimension. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 3455-3486. PMLR, 2020. URL: http://proceedings.mlr.press/v125/turner20a.html.
  46. Ilias Zadik, Min Jae Song, Alexander S. Wein, and Joan Bruna. Lattice-based methods surpass sum-of-squares in clustering. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1247-1248. PMLR, 2022. URL: https://proceedings.mlr.press/v178/zadik22a.html.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact