Document Open Access Logo

Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case

Authors Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.21.pdf
  • Filesize: 0.82 MB
  • 22 pages

Document Identifiers

Author Details

Vishwas Bhargava
  • Department of Computer Science, Rutgers University, Piscataway, NJ, USA
Ankit Garg
  • Microsoft Research, Bangalore, India
Neeraj Kayal
  • Microsoft Research, Bangalore, India
Chandan Saha
  • Indian Institute of Science, Bangalore, India

Funding

  • Bhargava, Vishwas: Research supported in part by the Simons Collaboration on Algorithms and Geometry and NSF grant CCF-1909683.

Acknowledgements

The authors would like to thank the anonymous referees for useful comments that improved the presentation of the results.

Cite As Get BibTex

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, and Chandan Saha. Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.21

Abstract

Consider a homogeneous degree d polynomial f = T₁ + ⋯ + T_s, T_i = g_i(𝓁_{i,1}, …, 𝓁_{i, m}) where g_i’s are homogeneous m-variate degree d polynomials and 𝓁_{i,j}’s are linear polynomials in n variables. We design a (randomized) learning algorithm that given black-box access to f, computes black-boxes for the T_i’s. The running time of the algorithm is poly(n, m, d, s) and the algorithm works under some non-degeneracy conditions on the linear forms and the g_i’s, and some additional technical assumptions n ≥ (md)², s ≤ n^{d/4}. The non-degeneracy conditions on 𝓁_{i,j}’s constitute non-membership in a variety, and hence are satisfied when the coefficients of 𝓁_{i,j}’s are chosen uniformly and randomly from a large enough set. The conditions on g_i’s are satisfied for random polynomials and also for natural polynomials common in the study of arithmetic complexity like determinant, permanent, elementary symmetric polynomial, iterated matrix multiplication. A particularly appealing algorithmic corollary is the following: Given black-box access to an f = Det_r(L^(1)) + … + Det_r(L^(s)), where L^(k) = (𝓁_{i,j}^(k))_{i,j} with 𝓁_{i,j}^(k)’s being linear forms in n variables chosen randomly, there is an algorithm which in time poly(n, r) outputs matrices (M^(k))_k of linear forms s.t. there exists a permutation π: [s] → [s] with Det_r(M^(k)) = Det_r(L^(π(k))).
Our work follows the works [Neeraj Kayal and Chandan Saha, 2019; Garg et al., 2020] which use lower bound methods in arithmetic complexity to design average case learning algorithms. It also vastly generalizes the result in [Neeraj Kayal and Chandan Saha, 2019] about learning depth three circuits, which is a special case where each g_i is just a monomial. At the core of our algorithm is the partial derivative method which can be used to prove lower bounds for generalized depth three circuits. To apply the general framework in [Neeraj Kayal and Chandan Saha, 2019; Garg et al., 2020], we need to establish that the non-degeneracy conditions arising out of applying the framework with the partial derivative method are satisfied in the random case. We develop simple but general and powerful tools to establish this, which might be useful in designing average case learning algorithms for other arithmetic circuit models.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Computing methodologies → Algebraic algorithms
Keywords
  • Arithemtic Circuits
  • Average-case Learning
  • Depth 3 Arithmetic Circuits
  • Learning Algorithms
  • Learning Circuits
  • Circuit Reconstruction

Metrics

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

Related Versions

References

  1. Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, and Stefano Varricchio. Learning functions represented as multiplicity automata. J. ACM, 47(3):506-530, 2000. Conference version appeared in the proceedings of FOCS 1996. Google Scholar
  2. Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. Reconstruction of depth-4 multilinear circuits. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2144-2160. SIAM, 2020. Google Scholar
  3. Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 809-822, 2021. Google Scholar
  4. Lieven De Lathauwer. A survey of tensor methods. In 2009 IEEE International Symposium on Circuits and Systems, pages 2773-2776. IEEE, 2009. Google Scholar
  5. Lance Fortnow and Adam R. Klivans. Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci., 75(1):27-36, 2009. Conference version appeared in the proceedings of COLT 2006. Google Scholar
  6. Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant equivalence test over finite fields and over q. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  7. Ankit Garg, Neeraj Kayal, and Chandan Saha. Learning sums of powers of low-degree polynomials in the non-degenerate case. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 889-899. IEEE, 2020. Google Scholar
  8. Fulvio Gesmundo and Joseph M. Landsberg. Explicit polynomial sequences with maximal spaces of partial derivatives and a question of k. mulmuley. Theory of Computing, 15(3):1-24, 2019. URL: https://doi.org/10.4086/toc.2019.v015a003.
  9. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the Chasm at Depth Four. J. ACM, 61(6):33:1-33:16, 2014. Conference version appeared in the proceedings of CCC 2013. Google Scholar
  10. Ankit Gupta, Neeraj Kayal, and Satyanarayana V. Lokam. Efficient Reconstruction of Random Multilinear Formulas. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 778-787, 2011. Google Scholar
  11. Ankit Gupta, Neeraj Kayal, and Satyanarayana V. Lokam. Reconstruction of depth-4 multilinear circuits with top fan-in 2. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 625-642, 2012. Google Scholar
  12. Ankit Gupta, Neeraj Kayal, and Youming Qiao. Random arithmetic formulas can be reconstructed efficiently. Computational Complexity, 23(2):207-303, 2014. Conference version appeared in the proceedings of CCC 2013. Google Scholar
  13. R Harshman. Foundations of the parafac procedure: Model and conditions for an explanatory factor analysis. Technical Report UCLA Working Papers in Phonetics 16, University of California, Los Angeles, Los Angeles, CA, 1970. Google Scholar
  14. Johan Håstad. Tensor Rank is NP-Complete. J. Algorithms, 11(4):644-654, 1990. Conference version appeared in the proceedings of ICALP 1989. Google Scholar
  15. Majid Janzamin, Rong Ge, Jean Kossaifi, Anima Anandkumar, et al. Spectral learning on matrices and tensors. Foundations and Trendsregistered in Machine Learning, 12(5-6):393-536, 2019. Google Scholar
  16. Erich Kaltofen and Barry M. Trager. Computing with Polynomials Given By Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators. J. Symb. Comput., 9(3):301-320, 1990. Google Scholar
  17. Zohar Shay Karnin and Amir Shpilka. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 274-285, 2009. Google Scholar
  18. Neeraj Kayal. Efficient algorithms for some special cases of the polynomial equivalence problem. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1409-1421, 2011. Google Scholar
  19. Neeraj Kayal. Affine projections of polynomials: extended abstract. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 643-662, 2012. Google Scholar
  20. Neeraj Kayal, Vineet Nair, and Chandan Saha. Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. Computational Complexity, 28(4):749-828, 2019. Google Scholar
  21. Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pages 21:1-21:61, 2017. Google Scholar
  22. Neeraj Kayal and Chandan Saha. Reconstruction of non-degenerate homogeneous depth three circuits. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 413-424, 2019. Google Scholar
  23. Adam R. Klivans and Alexander A. Sherstov. Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci., 75(1):2-12, 2009. Conference version appeared in the proceedings of FOCS 2006. Google Scholar
  24. Adam R. Klivans and Amir Shpilka. Learning restricted models of arithmetic circuits. Theory of Computing, 2(10):185-206, 2006. Conference version appeared in the proceedings of COLT 2003. Google Scholar
  25. Adam R. Klivans and Daniel A. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 216-223, 2001. Google Scholar
  26. Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3):455-500, 2009. Google Scholar
  27. Sue E Leurgans, Robert T Ross, and Rebecca B Abel. A decomposition for three-way arrays. SIAM Journal on Matrix Analysis and Applications, 14(4):1064-1083, 1993. Google Scholar
  28. Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In FOCS 2021, 2022. Google Scholar
  29. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  30. K. Pratt. Waring rank, parameterized and exact algorithms. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 806-823, 2019. URL: https://doi.org/10.1109/FOCS.2019.00053.
  31. Yaroslav Shitov. How hard is the tensor rank? arXiv, abs/1611.01559, 2016. URL: http://arxiv.org/abs/1611.01559.
  32. Gaurav Sinha. Reconstruction of real depth-3 circuits with top fan-in 2. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 31:1-31:53, 2016. Google Scholar
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 About DROPS Imprint Privacy Contact