Bhargava, Vishwas ;
Garg, Ankit ;
Kayal, Neeraj ;
Saha, Chandan
Learning Generalized Depth Three Arithmetic Circuits in the NonDegenerate Case
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 mvariate degree d polynomials and π_{i,j}βs are linear polynomials in n variables. We design a (randomized) learning algorithm that given blackbox access to f, computes blackboxes for the T_iβs. The running time of the algorithm is poly(n, m, d, s) and the algorithm works under some nondegeneracy conditions on the linear forms and the g_iβs, and some additional technical assumptions n β₯ (md)Β², s β€ n^{d/4}. The nondegeneracy conditions on π_{i,j}βs constitute nonmembership 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 blackbox 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 nondegeneracy 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.
BibTeX  Entry
@InProceedings{bhargava_et_al:LIPIcs.APPROX/RANDOM.2022.21,
author = {Bhargava, Vishwas and Garg, Ankit and Kayal, Neeraj and Saha, Chandan},
title = {{Learning Generalized Depth Three Arithmetic Circuits in the NonDegenerate Case}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {21:121:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17143},
URN = {urn:nbn:de:0030drops171430},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.21},
annote = {Keywords: Arithemtic Circuits, Averagecase Learning, Depth 3 Arithmetic Circuits, Learning Algorithms, Learning Circuits, Circuit Reconstruction}
}
15.09.2022
Keywords: 

Arithemtic Circuits, Averagecase Learning, Depth 3 Arithmetic Circuits, Learning Algorithms, Learning Circuits, Circuit Reconstruction 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Issue date: 

2022 
Date of publication: 

15.09.2022 