A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> In this paper, the deterministic global optimization algorithm, αBB (α-based Branch and Bound) is presented. This algorithm offers mathematical guarantees for convergence to a point arbitrarily close to the global minimum for the large class of twice-differentiable NLPs. The key idea is the construction of a converging sequence of upper and lower bounds on the global minimum through the convex relaxation of the original problem. This relaxation is obtained by (i) replacing all nonconvex terms of special structure (i.e., bilinear, trilinear, fractional, fractional trilinear, univariate concave) with customized tight convex lower bounding functions and (ii) by utilizing some α parameters as defined by Maranas and Floudas (1994b) to generate valid convex underestimators for nonconvex terms of generic structure. In most cases, the calculation of appropriate values for the α parameters is a challenging task. A number of approaches are proposed, which rigorously generate a set of α parameters for general twice-differentiable functions. A crucial phase in the design of such procedures is the use of interval arithmetic on the Hessian matrix or the characteristic polynomial of the function being investigated. Thanks to this step, the proposed schemes share the common property of computational tractability and preserve the global optimality guarantees of the algorithm. However, their accuracy and computational requirements differ so that no method can be shown to perform consistently better than others for all problems. Their use is illustrated on an unconstrained and a constrained example. ::: ::: The second part of this paper (Adjiman et al., 1998) is devoted to the discussion of issues related to the implementation of the αBB algorithm and to extensive computational studies illustrating its potential applications. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> The use of networks allows the representation of a variety of important engineering problems. The treatment of a particular class of network applications, the process synthesis problem, is exposed in this paper. Process Synthesis seeks to develop systematically process flowsheets that convert raw materials into desired products. In recent years, the optimization approach to process synthesis has shown promise in tackling this challenge. It requires the development of a network of interconnected units, the process superstructure, that represents the alternative process flowsheets. The mathematical modeling of the superstructure has a mixed set of binary and continuous variables and results in a Mixed-Integer optimization model. Due to the nonlinearity of chemical models, these problems are generally classified as Mixed-Integer Nonlinear Programming (MINLP) problems. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> Bagging predictors is a method for generating multiple versions of a predictor and using these to get an aggregated predictor. The aggregation averages over the versions when predicting a numerical outcome and does a plurality vote when predicting a class. The multiple versions are formed by making bootstrap replicates of the learning set and using these as new learning sets. Tests on real and simulated data sets using classification and regression trees and subset selection in linear regression show that bagging can give substantial gains in accuracy. The vital element is the instability of the prediction method. If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> In this work we propose a convex relaxation approach for computing minimal partitions. Our approach is based on rewriting the minimal partition problem (also known as Potts model) in terms of a primal dual Total Variation functional. We show that the Potts prior can be incorporated by means of convex constraints on the dual variables. For minimization we propose an efficient primal dual projected gradient algorithm which also allows a fast implementation on parallel hardware. Although our approach does not guarantee to find global minimizers of the Potts model we can give a tight bound on the energy between the computed solution and the true minimizer. Furthermore we show that our relaxation approach dominates recently proposed relaxations. As a consequence, our approach allows to compute solutions closer to the true minimizer. For many practical problems we even find the global minimizer. We demonstrate the excellent performance of our approach on several multi-label image segmentation and stereo problems. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> A major assumption in many machine learning and data mining algorithms is that the training and future data must be in the same feature space and have the same distribution. However, in many real-world applications, this assumption may not hold. For example, we sometimes have a classification task in one domain of interest, but we only have sufficient training data in another domain of interest, where the latter data may be in a different feature space or follow a different data distribution. In such cases, knowledge transfer, if done successfully, would greatly improve the performance of learning by avoiding much expensive data-labeling efforts. In recent years, transfer learning has emerged as a new learning framework to address this problem. This survey focuses on categorizing and reviewing the current progress on transfer learning for classification, regression, and clustering problems. In this survey, we discuss the relationship between transfer learning and other related machine learning techniques such as domain adaptation, multitask learning and sample selection bias, as well as covariate shift. We also explore some potential future issues in transfer learning research. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge. In the alternating minimization approach, the low-rank target matrix is written in a bi-linear form, i.e. $X = UV^\dag$; the algorithm then alternates between finding the best $U$ and the best $V$. Typically, each alternating step in isolation is convex and tractable. However the overall problem becomes non-convex and there has been almost no theoretical understanding of when this approach yields a good result. In this paper we present first theoretical analysis of the performance of alternating minimization for matrix completion, and the related problem of matrix sensing. For both these problems, celebrated recent results have shown that they become well-posed and tractable once certain (now standard) conditions are imposed on the problem. We show that alternating minimization also succeeds under similar conditions. Moreover, compared to existing results, our paper shows that alternating minimization guarantees faster (in particular, geometric) convergence to the true matrix, while allowing a simpler analysis. <s> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> Stochastic gradient descent is popular for large scale optimization but has slow convergence asymptotically due to the inherent variance. To remedy this problem, we introduce an explicit variance reduction method for stochastic gradient descent which we call stochastic variance reduced gradient (SVRG). For smooth and strongly convex functions, we prove that this method enjoys the same fast convergence rate as those of stochastic dual coordinate ascent (SDCA) and Stochastic Average Gradient (SAG). However, our analysis is significantly simpler and more intuitive. Moreover, unlike SDCA or SAG, our method does not require the storage of gradients, and thus is more easily applicable to complex problems such as some structured prediction problems and neural network learning. <s> BIB007 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> Deep neural nets with a large number of parameters are very powerful machine learning systems. However, overfitting is a serious problem in such networks. Large networks are also slow to use, making it difficult to deal with overfitting by combining the predictions of many different large neural nets at test time. Dropout is a technique for addressing this problem. The key idea is to randomly drop units (along with their connections) from the neural network during training. This prevents units from co-adapting too much. During training, dropout samples from an exponential number of different "thinned" networks. At test time, it is easy to approximate the effect of averaging the predictions of all these thinned networks by simply using a single unthinned network that has smaller weights. This significantly reduces overfitting and gives major improvements over other regularization methods. We show that dropout improves the performance of neural networks on supervised learning tasks in vision, speech recognition, document classification and computational biology, obtaining state-of-the-art results on many benchmark data sets. <s> BIB008 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> We present a simple regularization technique for Recurrent Neural Networks (RNNs) with Long Short-Term Memory (LSTM) units. Dropout, the most successful technique for regularizing neural networks, does not work well with RNNs and LSTMs. In this paper, we show how to correctly apply dropout to LSTMs, and show that it substantially reduces overfitting on a variety of tasks. These tasks include language modeling, speech recognition, image caption generation, and machine translation. <s> BIB009 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> Alternating Minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for Alternating Minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-convex in nature. We give a new algorithm based on Alternating Minimization that provably recovers an unknown low-rank matrix from a random subsample of its entries under a standard incoherence assumption. Our results reduce the sample size requirements of the Alternating Minimization approach by at least a quartic factor in the rank and the condition number of the unknown matrix. These improvements apply even if the matrix is only close to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in the dimension of the matrix and, in a broad range of parameters, gives the strongest sample bounds among all subquadratic time algorithms that we are aware of. Underlying our work is a new robust convergence analysis of the well-known Power Method for computing the dominant singular vectors of a matrix. This viewpoint leads to a conceptually simple understanding of Alternating Minimization. In addition, we contribute a new technique for controlling the coherence of intermediate solutions arising in iterative algorithms based on a smoothed analysis of the QR factorization. These techniques may be of interest beyond their application here. <s> BIB010 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> We give the first algorithm for Matrix Completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix in the running time. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise. <s> BIB011 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> We develop a general framework for proving rigorous guarantees on the performance of the EM algorithm and a variant known as gradient EM. Our analysis is divided into two parts: a treatment of these algorithms at the population level (in the limit of infinite data), followed by results that apply to updates based on a finite set of samples. First, we characterize the domain of attraction of any global maximizer of the population likelihood. This characterization is based on a novel view of the EM updates as a perturbed form of likelihood ascent, or in parallel, of the gradient EM updates as a perturbed form of standard gradient ascent. Leveraging this characterization, we then provide non-asymptotic guarantees on the EM and gradient EM algorithms when applied to a finite set of samples. We develop consequences of our general theory for three canonical examples of incomplete-data problems: mixture of Gaussians, mixture of regressions, and linear regression with covariates missing completely at random. In each case, our theory guarantees that with a suitable initialization, a relatively small number of EM (or gradient EM) steps will yield (with high probability) an estimate that is within statistical error of the MLE. We provide simulations to confirm this theoretically predicted behavior. <s> BIB012 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> We provide a general theory of the expectation-maximization (EM) algorithm for inferring high dimensional latent variable models. In particular, we make two contributions: (i) For parameter estimation, we propose a novel high dimensional EM algorithm which naturally incorporates sparsity structure into parameter estimation. With an appropriate initialization, this algorithm converges at a geometric rate and attains an estimator with the (near-)optimal statistical rate of convergence. (ii) Based on the obtained estimator, we propose new inferential procedures for testing hypotheses and constructing condence intervals for low dimensional components of high dimensional parameters. For a broad family of statistical models, our framework establishes the rst computationally feasible approach for optimal estimation and asymptotic inference in high dimensions. Our theory is supported by thorough numerical results. <s> BIB013 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factorized optimization problem. The goal of this problem is to provide a general theoretical framework for understanding when such methods work well, and to characterize the nature of the resulting fixed point. We provide a simple set of conditions under which projected gradient descent, when given a suitable initialization, converges geometrically to a statistically useful solution. Our results are applicable even when the initial solution is outside any region of local convexity, and even when the problem is globally concave. Working in a non-asymptotic framework, we show that our conditions are satisfied for a wide range of concrete models, including matrix regression, structured PCA, matrix completion with real and quantized observations, matrix decomposition, and graph clustering problems. Simulation results show excellent agreement with the theoretical predictions. <s> BIB014 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in $O(1/\varepsilon)$ iterations for smooth objectives, and stochastic gradient descent that converges in $O(1/\varepsilon^2)$ iterations for objectives that are sum of smooth functions. We provide the first improvement in this line of research. Our result is based on the variance reduction trick recently introduced to convex optimization, as well as a brand new analysis of variance reduction that is suitable for non-convex optimization. For objectives that are sum of smooth functions, our first-order minibatch stochastic method converges with an $O(1/\varepsilon)$ rate, and is faster than full gradient descent by $\Omega(n^{1/3})$. We demonstrate the effectiveness of our methods on empirical risk minimizations with non-convex loss functions and training neural nets. <s> BIB015 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> We propose a simple and scalable non-convex method for low-rank PSD matrix problems with a generic (strongly) convex objective $f$, and additional matrix norm constraints. Such criteria appear in quantum state tomography and phase retrieval applications, among others. However, without careful design, existing methods quickly run into time and memory bottlenecks, as problem dimensions increase. To remedy these shortcomings, we propose the Projected Factored Gradient Descent (ProjFGD) algorithm, that operates on the low-rank factorization of the variable space. Such factorization imputes non-convexity in the optimization; nevertheless, we show that our method favors local linear convergence rate in the non-convex factored space, for a class of convex norm-constrained problems. We build our theory on a novel descent lemma, that extends recent results on the unconstrained version of the problem. Our findings are supported by empirical evidence on quantum state tomography and sparse phase retrieval applications. <s> BIB016 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Insufficient Data in Training Deep Neural Networks: <s> A vast majority of machine learning algorithms train their models andperform inference by solving optimization problems. In order to capturethe learning and prediction problems accurately, structural constraintssuch as sparsity or low rank are frequently imposed or else the objectiveitself is designed to be a non-convex function. This is especially trueof algorithms that operate in high-dimensional spaces or that trainnon-linear models such as tensor models and deep networks.The freedom to express the learning problem as a non-convex optimizationproblem gives immense modeling power to the algorithmdesigner, but often such problems are NP-hard to solve. A popularworkaround to this has been to relax non-convex problems to convexones and use traditional methods to solve the convex relaxed optimizationproblems. However this approach may be lossy and neverthelesspresents significant challenges for large scale optimization.On the other hand, direct approaches to non-convex optimizationhave met with resounding success in several domains and remain themethods of choice for the practitioner, as they frequently outperformrelaxation-based techniques - popular heuristics include projected gradientdescent and alternating minimization. However, these are oftenpoorly understood in terms of their convergence and other properties.This monograph presents a selection of recent advances that bridgea long-standing gap in our understanding of these heuristics. We hopethat an insight into the inner workings of these methods will allow thereader to appreciate the unique marriage of task structure and generativemodels that allow these heuristic techniques to provably succeed.The monograph will lead the reader through several widely used nonconvexoptimization techniques, as well as applications thereof. Thegoal of this monograph is to both, introduce the rich literature in thisarea, as well as equip the reader with the tools and techniques neededto analyze these simple procedures for non-convex problems. <s> BIB017
In general, deep learning is based on big data sets and complex models. It requires a large number of training samples to achieve good training effects. But in some particular fields, finding a sufficient amount of training data is difficult. If we do not have enough data to estimate the parameters in the neural networks, it may lead to high variance and overfitting. There are some techniques in neural networks that can be used to reduce the variance. Adding L 2 regularization to the objective is a natural method to reduce the model complexity. Recently, a common method is dropout BIB008 . In the training process, each neuron is allowed to stop working with a probability of p, which can prevent the synergy between certain neurons. M subnets can be sampled like bagging by multiple puts and returns BIB003 . Each expected result at the output layer is calculated as where p(M i ) is the probability of the ith subnet. Dropout can prevent overfitting and improve the generalization ability of the network, but its disadvantage is increasing the training time as each training changes from the full network to a sub-network BIB009 . Not only overfitting but also some training details will affect the performance of the model due to the complexity of the deep neural network model. The improper selection of the learning rate and the number of iterations in the SGD will make the model unable to converge, which makes the accuracy of model fluctuate greatly. Besides, taking an inappropriate black box of neural network construction may result in training not being able to continue, so selecting an appropriate neural network model is particularly important. These impacts are even greater when data are insufficient. The technology of transfer learning BIB005 can be applied to build networks in the scenario of insufficient data. Its idea is that the models trained from other data sources can be reused in similar target fields after certain modifications and improvements, which dramatically alleviates the problems caused by insufficient datasets. Moreover, the advantages brought by transfer learning are not limited to reducing the need for sufficient training data, but also can avoid overfitting effectively and achieve better performance in general. However, if target data is not as relevant to the original training data, the transferred model does not bring good performance. Meta learning methods can be used for systematically learning parameter initialization, which ensures that training begins with a suitable initial model. However, it is necessary to ensure the correlation between multiple tasks for meta-training and tasks for meta-testing. Under the premise of models with similar data sources for training, transfer learning and meta learning can overcome the difficulties caused by insufficient training data in new data sources, but these methods usually introduce a large number of parameters or complex parameter adjustment mechanisms, which need to be further improved for specific problems. Therefore, using insufficient data for training deep neural networks is still a challenge. 2) Non-convex Optimization in Deep Neural Network: Convex optimization has good properties and a comprehensive set of tools are open to solve the optimization problem. However, many machine learning problems are formulated as non-convex optimization problems. For example, almost all the optimization problems in deep neural networks are nonconvex. Non-convex optimization is one of the difficulties in the optimization problem. Unlike convex optimization, there may be innumerable optimum solutions in its feasible domain in non-convex problems. The complexity of the algorithm for searching the global optimal value is NP-hard BIB015 . In recent years, non-convex optimization has gradually attracted the attention of researches. The methods for solving non-convex optimization problems can be roughly divided into two types. One is to transform the non-convex optimization into a convex optimization problem, and then use the convex optimization method. The other is to use some special optimization method for solving non-convex functions directly. There is some work on summarizing the optimization methods for solving non-convex functions from the perspective of machine learning BIB017 . 1) Relaxation method: Relax the problem to make it become a convex optimization problem. There are many relaxation techniques, for example, the branch-andbound method called αBB convex relaxation BIB001 , BIB002 , which uses a convex relaxation at each step to compute the lower bound in the region. The convex relaxation method has been used in many fields. In the field of computer vision, a convex relaxation method was proposed to calculate minimal partitions BIB004 . For unsupervised and semi-supervised learning, the convex relaxation method was used for solving semidefinite programming  . 2) Non-convex optimization methods: These methods include projection gradient descent BIB014 , BIB016 , alternating minimization BIB006 , BIB010 , BIB011 , expectation maximization algorithm BIB012 , BIB013 and stochastic optimization and its variants BIB007 .