We study SGD and Adam for estimating a rank one signal planted in matrix or tensor noise. The extreme simplicity of the problem setup allows us to isolate the effects of various factors: signal to noise ratio, density of critical points, stochasticity and initialization. We observe a surprising phenomenon: Adam seems to get stuck in local minima as soon as polynomially many critical points appear (matrix case), while SGD escapes those. However, when the number of critical points degenerates to exponentials (tensor case), then both algorithms get trapped. Theory tells us that at fixed SNR the problem becomes intractable for large $d$ and in our experiments SGD does not escape this. We exhibit the benefits of warm starting in those situations. We conclude that in this class of problems, warm starting cannot be replaced by stochasticity in gradients to find the basin of attraction. Reductionism consists of breaking down the study of complex systems and phenomena into their atomic components. While the use of stochastic gradient based algorithms has shown tremendous success at minimizing complicated loss functions arising in deep learning, our understanding of why, when and how this happens is still limited. Statements such as stochastic gradients escape from isolated critical points along the road to the best basin of attraction, or SGD generalizes better because it does not get stuck in steep local minima still need to be better understood. Can we prove or replicate these phenomena in the simplest instances of the problem? We study the behavior of stochastic gradient descent (SGD) BID11 and an adaptive variant (Adam) BID8 under a class of well studied non-convex problems. The single spiked models were originally designed for studying principal component analysis on matrices BID12 BID3 BID5 and have also been extended to higher order tensors BID10 . Adaptive stochastic optimization methods have been gaining popularity in the deep learning community thanks to fast training on some benchmarks. However, it has been observed that despite reaching a low value of the loss function, the solutions found by Adam do not generalize as well as SGD solutions do. An assumption, widely spread and adopted in the community, has been that SGD's randomness helps escaping local critical points [WRS + 17] . While the problem has been thoroughly studied theoretically [MR14, HSS15, HSSS16, BAGJ18], our contribution is to propose experimenting with this simple model to challenge claims such as those on randomized gradient algorithms in this very simple setup. It is noteworthy that the landscape of non-global critical points of these toy datasets are studied BID0 BID2 BID1 and formally linked to the neural nets empirical loss functions BID2 BID9 . For this problem, the statistical properties of the optimizers are well understood, and in the more challenging tensor situation, also the impact of (spectral) warm start has been discussed BID10 . We will examine the solutions found by SGD and Adam and compare them with spectral and power methods. This allows to empirically elucidate the existence of multiple regimes: (1) the strong signal regime where all first order methods seem to find good solutions (2) when polynomially many critical points appear, in the matrix case, SGD converges while Adam gets trapped, unless if initialized in the basin of attraction (3) in the presence of exponentially many critical points (the tensor case), all algorithms fail, unless if d is moderately small and the SNR large enough to allow for proper initialization.2 Single spiked models, and stochastic gradients We propose to study algorithms used for minimizing deep learning loss functions, at optimizing a non-convex objective on simple synthetic datasets. Studying simplified problems has the advantage that the problem's properties, and the behavior of the optimizer and the solution, can be studied rigorously. The use of such datasets can help to perform sanity checks on improvement ideas to the algorithms, or to mathematically prove or disprove intuitions. The properties of the toy data sets align with some properties of deep learning loss functions. From the optimization standpoint, the resulting tensor problems may appear to be even harder than deep learning problems. We observe that finding good solutions is hard unless if proper initialization is performed, while the value of stochasticity in gradient estimates seems too narrow and does not appear to compensate for poor initialization heuristics. Each column represents the values of those quantities along iterations of the algorithm. The prefix sp. refers to spectral initialization and l. refers to a decreasing learning weight scheduled in 1/ √ t. We observe the value of warm starting as soon as λ is large enough. Even at high SNR λ = 6, randomly initialized SGD fails while spectrally initialized SGD succeeds. Adam drifts to a non optimal critical point in that regime, even with spectral warm start.
SGD and Adam under single spiked model for tensor PCA
{"src": "scitldr-AIC_train", "paper_id": "rkl8DES3nE"}