A Guide to Learning Arithmetic Circuits

Ilya Volkovich
29th Annual Conference on Learning Theory, PMLR 49:1540-1561, 2016.

Abstract

An \empharithmetic circuit is a directed acyclic graph in which the operations are {+,\times}. In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems. In particular, we show that: \beginitemize \item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds. \item General circuits and formulas can be learned efficiently with membership and equivalence queries iff they can be learned efficiently with membership queries only. \item Low-query learning algorithms for certain classes of circuits imply explicit rigid matrices. \item Learning algorithms for multilinear depth-3 and depth-4 circuits must compute square roots. \enditemize

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-volkovich16, title = {A Guide to Learning Arithmetic Circuits}, author = {Volkovich, Ilya}, booktitle = {29th Annual Conference on Learning Theory}, pages = {1540--1561}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/volkovich16.pdf}, url = {https://proceedings.mlr.press/v49/volkovich16.html}, abstract = {An \empharithmetic circuit is a directed acyclic graph in which the operations are {+,\times}. In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems. In particular, we show that: \beginitemize \item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds. \item General circuits and formulas can be learned efficiently with membership and equivalence queries iff they can be learned efficiently with membership queries only. \item Low-query learning algorithms for certain classes of circuits imply explicit rigid matrices. \item Learning algorithms for multilinear depth-3 and depth-4 circuits must compute square roots. \enditemize} }
Endnote
%0 Conference Paper %T A Guide to Learning Arithmetic Circuits %A Ilya Volkovich %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-volkovich16 %I PMLR %P 1540--1561 %U https://proceedings.mlr.press/v49/volkovich16.html %V 49 %X An \empharithmetic circuit is a directed acyclic graph in which the operations are {+,\times}. In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems. In particular, we show that: \beginitemize \item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds. \item General circuits and formulas can be learned efficiently with membership and equivalence queries iff they can be learned efficiently with membership queries only. \item Low-query learning algorithms for certain classes of circuits imply explicit rigid matrices. \item Learning algorithms for multilinear depth-3 and depth-4 circuits must compute square roots. \enditemize
RIS
TY - CPAPER TI - A Guide to Learning Arithmetic Circuits AU - Ilya Volkovich BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-volkovich16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 1540 EP - 1561 L1 - http://proceedings.mlr.press/v49/volkovich16.pdf UR - https://proceedings.mlr.press/v49/volkovich16.html AB - An \empharithmetic circuit is a directed acyclic graph in which the operations are {+,\times}. In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems. In particular, we show that: \beginitemize \item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds. \item General circuits and formulas can be learned efficiently with membership and equivalence queries iff they can be learned efficiently with membership queries only. \item Low-query learning algorithms for certain classes of circuits imply explicit rigid matrices. \item Learning algorithms for multilinear depth-3 and depth-4 circuits must compute square roots. \enditemize ER -
APA
Volkovich, I.. (2016). A Guide to Learning Arithmetic Circuits. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:1540-1561 Available from https://proceedings.mlr.press/v49/volkovich16.html.

Related Material