Exponentially many local minima for single neurons

By Peter Auer, Mark Herbster, Manfred K. Warmuth. 1995

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

Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs (2018, background): “Even for simple networks, the number of local optima and saddle points is large and can grow exponentially in the number of parameters [1, 2, 3].”
On the Computational Efficiency of Training Neural Networks (2014, background): “As an interesting contrast, note that for very small networks (such as a single neuron with a non-convex activation function), the associated optimization problem is generally hard, and can exhibit exponentially many local (non-global) minima [5].”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “Current results are mostly pessimistic, suggesting that even training a 3-node neural network is NP-hard (Blum & Rivest, 1993), and that the objective function of a single neuron can admit exponentially many local minima (Auer et al., 1996; Safran & Shamir, 2016).”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, background): “(1)), there are many spurious local minima (e.g., [Auer et al., 1996, Swirszcz et al., 2016]).”
MLPerf Training Benchmark (2019, background): “DNN training involves many stochastic inﬂuences that manifest in substantial run-to-run variation (Choromanska et al., 2015; Gori & Tesi, 1992; Auer et al., 1996; Coleman et al., 2019 selection and the non-commutative nature of ﬂoating-point addition).”
Tracking the Best Linear Predictor (2001, methodology): “In the context of on-line learning, various formulations of these divergence functions were rst used in (Auer et al., 1995, Kivinen and Warmuth, 2001, Grove et al., 2001, Jagota and Warmuth, 1998, Azoury and Warmuth, 2001).”
The loss surface and expressivity of deep convolutional neural networks (2017, background): “It is well known that the optimization problem for training neural networks can have exponentially many local minima (Auer et al., 1996; Safran & Shamir, 2016) and NP-hardness has been shown in many cases (Blum & Rivest., 1989; Sima, 2002; Livni et al., 2014; Shamir, 2017; Shalev-Shwartz et al.,…”
Evaluating Scalable Bayesian Deep Learning Methods for Robust Computer Vision (2019, background): “Since p ( Y | X, θ ) is highly multi-modal in the parameter space for DNNs [1, 8], so is p ( θ”
On the Quality of the Initial Basin in Overspecified Neural Networks (2015, methodology): “We now extend our sample to be d-dimensional in a similar manner as did the authors in [Auer et al., 1996] as follows: For t = 1, 2 and j ∈ [d], we use the mapping xt (j) 7→ (0, . . . , 0, xt, 0, . . . , 0) where the non-zero coordinate is the jth coordinate.”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, background): “, Sol17]2. All of the problems we consider in this paper are non-convex optimization problems, as it is known that a single sigmoid with respect to square-loss has exponentially many bad local minima [AHW96]. For classical generalization and VC dimension bounds for learning neural networks we refer ”
Exploring Strategies for Training Deep Neural Networks (2009, background): “The first one is that gradient descent can easily get stuck in poor local minima (Auer et al., 1996) or plateaus of the non-convex training criterion.”
Efficient approaches for escaping higher order saddle points in non-convex optimization (2016, background): “Due to curse of dimensionality, the number of saddle points grows exponentially for many problems of interest, e.g. [Auer et al., 1996, Cartwright and Sturmfels, 2013, Auffinger et al., 2013].”
DeepHoyer: Learning Sparser Neural Network with Differentiable Scale-Invariant Sparsity Measures (2019, background): “This shall not be a big issue when applying the regularizer in a DNN training objective with the help of the recent advance in stochastic gradient descent (SGD) methods that provide satisfying results under large-scale non-convex settings [32, 33], including DNNs with non-convex objectives [34].”
Meta learning evolutionary arti ! cial neural networks (2004, background): “[8], a single node network with n training pairs and Rd inputs could end up having (n=d)d local minima.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Last but not least, we caution that, many more nonconvex problems are not benign and indeed have bad local minima; for example, spurious local minima are common even in simple neural networks with nonlinear activations [157], [158].”
Solving inverse problems using data-driven models (2019, methodology): “Affara, B. Ghanem and P. Wonka (2018), Supervised convolutional sparse coding.”
The Loss Surface of Deep and Wide Neural Networks (2017, background): “ed. In this paper we address the non-convexoptimizationproblemoftrainingafeedforwardneuralnetwork. This problem turns out to be very difﬁcult as there can be exponentially many distinct local minima (Auer et al., 1996; Safran & Shamir, 2016). It has been shown that the trainingof a networkwith a”
Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning (2019, background): “However, the loss surface for DNNs is highly multimodal (Auer et al., 1996; Choromanska et al., 2015).”
Optimization Landscape and Expressivity of Deep CNNs (2017, background): “It is well known that the optimization problem for training neural networks can have exponentially many local minima (Auer et al., 1996; Safran & Shamir, 2016) and NP-hardness has been shown in many cases (Blum & Rivest., 1989; Sima, 2002; Livni et al., 2014; Shamir, 2017; Shalev-Shwartz et al.,…”