Learning Polynomials with Neural Networks

By Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang. 2014

163 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, methodology): “The work of Andoni et al. [2014] studied the problem of learning degree-d polynomials (with real or complex coefﬁcients) using polynomial neural networks described above.”
Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “Most previous results on learning neural network are negative [39, 28, 38], or positive but with algorithms other than SGD [23, 43, 37, 14, 15, 16], or with strong assumptions on the model [1, 2].”
No bad local minima: Data independent training error guarantees for multilayer neural networks (2016, background): “Going beyond training error, [2] showed that MNNs with one hidden layer can learn low order polynomials, under a product of Gaussians distributional assumption on the input.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “[5] proves that two-layer networks can learn polynomial functions of degree r over d-dimensional inputs in sample complexityO(d).”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Andoni et al. [2014] showed that gradient descent can learn networks that are competitive with polynomial classifiers. However, these results do not imply gradient descent can find a global minimum for the empirical loss minimization problem. Finally in concurrent work, Allen-Zhu et al. [2018b] also”
On the Computational Efficiency of Training Neural Networks (2014, background): “We note that algorithms for efﬁciently learning (real-valued) sparse or low-degree polynomials has been studied in several previous works (e.g. [13, 14, 8, 2, 1]).”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “The recent empirical success of NNs has boosted their theoretical analyses (Feng et al., 2016; Balduzzi, 2016; Bal-duzzi et al., 2016; Sagun et al., 2016; Andoni et al., 2014; Arora et al., 2017; Goel et al., 2017).”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “Such over-speciﬁed networks have been considered in (Andoni et al., 2014; Livni et al., 2014) and it was shown that gradient descent can globally learn them in some cases (Andoni et al., 2014).”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “We emphasize that the main difference of those results from our results and the results of Andoni et al. [2014] is that they do not provide guarantees on the standard SGD learning algorithm.”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, background): “ for our problem. Many papers have analyzed learning of neural networks with non-linearities. The papers most closely related to this work analyze algorithms based on gradient descent. Some of these (Andoni et al., 2014; Brutzkus & Globerson, 2017; Ge et al., 2017b; Li & Yuan, 2017; Zhong et”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, background): “Also, (Andoni et al., 2014) showed a p -degree polynomial is learnable by a MNN, if the hidden layer is very large ( d 1 = Ω d 6 p 0 , typically ≫ N ) so learning the last weight layer is suf-ﬁcient.”
The loss surface and expressivity of deep convolutional neural networks (2017, background): “…to explain the apparent gap between hardness results and practical performance, many interesting theoretical results have been recently developed (Andoni et al., 2014; Sedghi & Anandkumar, 2015; Janzamin et al., 2016; Haeffele & Vidal, 2015; Gautier et al., 2016; Brutzkus & Globerson, 2017;…”
Deep & Cross Network for Ad Click Predictions (2017, background): “ere has been research [16, 17] showing that DNNs are able to approximate an arbitrary function under certain smoothness assumptions to an arbitrary accuracy, given suciently many hidden units or hidden layers.”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, background): “Recently, a spate of papers (such as [4, 11, 14, 2, 23, 15, 9, 3, 1]) provided positive results for training and learning with over-parameterized neural networks.”
Neural Collaborative Filtering vs. Matrix Factorization Revisited (2020, background): “gh they should all be representable. However, is this also true for the simple \structure" of the dot product? Similar problems turn out to be actively studied subject in machine learning theory [2, 25, 10, 1]. To our knowledge, the best theoretical bound for learning the dot product, a degree ”
Generalization Bounds for Neural Networks through Tensor Factorization (2015, background): “Previous theoretical works for training neural networks: Andoni et al. (2014) learn polynomial target functions using a two-layer neural network under Gaussian/uniform input distribution.”
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018, background): “[1] where they assume the target function is a bounded degree polynomial.”
A Provably Correct Algorithm for Deep Learning that Actually Works (2018, background): “The work of [1] shows guarantees on learning low-degree polynomials, which is again learnable via SVM or direct feature mapping.”