A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> In this paper we develop a transportation network policy model that determines the equilibrium flow pattern and the transportation link tolls or taxes/subsidies in the presence of imposed transportation goals on the links of the network. The penalties (and subsidies) are functions of the deviations from the targets. The governing equilibrium conditions are shown to satisfy a variational inequality problem and existence and uniqueness results are presented using this methodology. A decomposition algorithm is proposed that resolves the problem into series of traffic network equilibrium problems and two simpler subproblems. Convergence results are also given. Finally, the algorithm is applied to numerical examples that illustrate how the model can be utilized for transportation pricing policy, as well as the numerical performance of the algorithm. This work extends recent research in spatial market policy modeling with goal targets on bipartite networks and with fixed penalties. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> The alternating direction method is one of the attractive approaches for solving linearly constrained separate monotone variational inequalities. Experience on applications has shown that the number of iterations depends significantly on the penalty parameter for the system of linear constraint equations. While the penalty parameter is a constant in the original method, in this paper we present a modified alternating direction method that adjusts the penalty parameter per iteration based on the iterate message. Preliminary numerical tests show that the self-adaptive adjustment technique is effective in practice. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> Many problems of recent interest in statistics and machine learning can be posed in the framework of convex optimization. Due to the explosion in size and complexity of modern datasets, it is increasingly important to be able to solve problems with a very large number of features or training examples. As a result, both the decentralized collection or storage of these datasets as well as accompanying distributed solution methods are either necessary or at least highly desirable. In this review, we argue that the alternating direction method of multipliers is well suited to distributed convex optimization, and in particular to large-scale problems arising in statistics, machine learning, and related areas. The method was developed in the 1970s, with roots in the 1950s, and is equivalent or closely related to many other algorithms, such as dual decomposition, the method of multipliers, Douglas–Rachford splitting, Spingarn's method of partial inverses, Dykstra's alternating projections, Bregman iterative algorithms for l1 problems, proximal methods, and others. After briefly surveying the theory and history of the algorithm, we discuss applications to a wide variety of statistical and machine learning problems of recent interest, including the lasso, sparse logistic regression, basis pursuit, covariance selection, support vector machines, and many others. We also discuss general distributed optimization, extensions to the nonconvex setting, and efficient implementation, including some details on distributed MPI and Hadoop MapReduce implementations. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> For the challenging pole balancing task we propose a system which uses raw visual input data for reinforcement learning to evolve a control strategy. Therefore we use a neural network --- a deep autoencoder --- to encode the camera images and thus the system states in a low dimensional feature space. The system is compared to controllers that work directly on the motor sensor data. We show that the performances of both systems are settled in the same order of magnitude. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> We present an alternating augmented Lagrangian method for convex optimization problems where the cost function is the sum of two terms, one that is separable in the variable blocks, and a second that is separable in the difference between consecutive variable blocks. Examples of such problems include Fused Lasso estimation, total variation denoising, and multi-period portfolio optimization with transaction costs. In each iteration of our method, the first step involves separately optimizing over each variable block, which can be carried out in parallel. The second step is not separable in the variables, but can be carried out very efficiently. We apply the algorithm to segmentation of data based on changes inmean (l_1 mean filtering) or changes in variance (l_1 variance filtering). In a numerical example, we show that our implementation is around 10000 times faster compared with the generic optimization solver SDPT3. <s> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <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> 5) Variance Reduction Methods: <s> We analyze the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from $$O(1/\sqrt{k})$$O(1/k) to O(1 / k) in general, and when the sum is strongly-convex the convergence rate is improved from the sub-linear O(1 / k) to a linear convergence rate of the form $$O(\rho ^k)$$O(?k) for $$\rho < 1$$?<1. Further, in many cases the convergence rate of the new method is also faster than black-box deterministic gradient methods, in terms of the number of gradient evaluations. This extends our earlier work Le Roux et al. (Adv Neural Inf Process Syst, 2012), which only lead to a faster rate for well-conditioned strongly-convex problems. Numerical experiments indicate that the new algorithm often dramatically outperforms existing SG and deterministic gradient methods, and that the performance may be further improved through the use of non-uniform sampling strategies. <s> BIB008 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for composite objectives where a proximal operator is used on the regulariser. Unlike SDCA, SAGA supports non-strongly convex problems directly, and is adaptive to any inherent strong convexity of the problem. We give experimental results showing the effectiveness of our method. <s> BIB009 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <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> BIB010 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> We study nonconvex finite-sum problems and analyze stochastic variance reduced gradient (SVRG) methods for them. SVRG and related methods have recently surged into prominence for convex optimization given their edge over stochastic gradient descent (SGD); but their theoretical analysis almost exclusively assumes convexity. In contrast, we prove non-asymptotic rates of convergence (to stationary points) of SVRG for nonconvex optimization, and show that it is provably faster than SGD and gradient descent. We also analyze a subclass of nonconvex problems on which SVRG attains linear convergence to the global optimum. We extend our analysis to mini-batch variants of SVRG, showing (theoretical) linear speedup due to mini-batching in parallel settings. <s> BIB011 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 5) Variance Reduction Methods: <s> Despite superior training outcomes, adaptive optimization methods such as Adam, Adagrad or RMSprop have been found to generalize poorly compared to Stochastic gradient descent (SGD). These methods tend to perform well in the initial portion of training but are outperformed by SGD at later stages of training. We investigate a hybrid strategy that begins training with an adaptive method and switches to SGD when appropriate. Concretely, we propose SWATS, a simple strategy which switches from Adam to SGD when a triggering condition is satisfied. The condition we propose relates to the projection of Adam steps on the gradient subspace. By design, the monitoring process for this condition adds very little overhead and does not increase the number of hyperparameters in the optimizer. We report experiments on several standard benchmarks such as: ResNet, SENet, DenseNet and PyramidNet for the CIFAR-10 and CIFAR-100 data sets, ResNet on the tiny-ImageNet data set and language modeling with recurrent networks on the PTB and WT2 data sets. The results show that our strategy is capable of closing the generalization gap between SGD and Adam on a majority of the tasks. <s> BIB012
Due to a large amount of redundant information in the training samples, the SGD methods are very popular since they were proposed. However, the stochastic gradient method can only converge at a sublinear rate, while the standard batch gradient descent method can achieve linear convergence rate BIB007 . How to improve SGD to the linear convergence has always been an important problem. Stochastic Average Gradient The stochastic average gradient (SAG) method BIB004 is a variance reduction method proposed to improve the convergence speed. The SAG algorithm maintains parameter d recording the sum of the latest gradients g i for each sample i, i ∈ {1, ..., M } in memory. The detailed implementation is to select a sample i t to update d randomly, and use d to update the parameter θ in iteration t: where the updated item d is calculated by replacing the old gradientĝ it in d with the new gradient g it (θ t−1 ) in iteration t. Thus, each update only needs to calculate the gradient of one sample, not the gradients of all samples. The computational overhead is no different from SGD, but the memory overhead is much larger. This is a typical way of using space for saving time. The SAG has been shown to be a linear convergence algorithm BIB004 , which is much faster than SGD, and has great advantages over other stochastic gradient algorithms. However, the SAG method is only applicable to the case where the loss function is smooth and the objective function is convex BIB004 , BIB008 , such as convex linear prediction problems. In this case, the SAG achieves a faster convergence rate than the SGD. In addition, under some specific problems, it can even deliver better convergence than the standard batch gradient descent. However, the SAG method is only applicable to the case where the loss function is smooth and the objective function is convex BIB008 , such as convex linear prediction problems. In this case, the SAG achieves a faster convergence rate than the SGD. In addition, under some specific problems, it can even deliver better convergence than the standard batch gradient descent. Stochastic Variance Reduction Gradient Since the SAG method is only applicable to smooth and convex functions and needs to store the gradient of each sample, it is inconvenient to be applied in non-convex neural networks. The stochastic variance reduction gradient (SVRG) BIB007 method was proposed to improve the performance of optimization in the complex models. The algorithm of SVRG maintains the interval average gradientμ by calculating the gradients of all samples in every w iterations instead of in each iteration: whereθ is the interval update parameter. The interval parameterμ contains the average memory of all sample gradients in the past time for each time interval w. SVRG picks uniform i t ∈ {1, ..., M } randomly, and executes gradient updates to the current parameters: The gradient is calculated up to two times in each update. After w interations,θ ← θ w , start the next w iterations. Through these update, θ t and the interval update parameter θ will converge to the optimal θ * , and thenμ → 0, and SVRG proposes a vital concept called variance reduction. This concept is related to the convergence analysis of SGD, in which it is necessary to assume that there is a constant upper bound for the variance of the gradients. This constant upper bound implies that the SGD cannot achieve linear convergence. However, in SVRG, the upper bound of variance can be continuously reduced due to the special update item g it (θ t−1 ) − g it (θ) +μ , thus achieving linear convergence BIB007 . The strategies of SAG and SVRG are related to variance reduction. Compared with SAG, SVRG does not need to maintain all gradients in memory, which means that memory resources are saved, and it can be applied to complex problems efficiently. Experiments have shown that the performance of SVRG is remarkable on a non-convex neural network BIB007 , BIB010 , BIB011 . There are also many variants of such linear convergence stochastic optimization algorithms, such as the SAGA algorithm BIB009 . 6) Alternating Direction Method of Multipliers: Augmented Lagrangian multiplier method is a common method to solve optimization problems with linear constraints. Compared with the naive Lagrangian multiplier method, it makes problems easier to solve by adding a penalty term to the objective. Consider the following example, The augmented Lagrange function for problem BIB012 is When solved by the augmented Lagrangian multiplier method, its kth step iteration starts from the given λ k , and the optimization turns out to BIB005 , the augmented Lagrange multiplier method can be relaxed to the following alternating direction method of multipliers (ADMM)  , BIB003 . Its kth step iteration starts with the given (y k , λ k ), and the details of iterative optimization are as follows: where Con x = Ax + By k − b and Con y = Ax k+1 + By − b. The penalty parameter β has a certain impact on the convergence rate of the ADMM. The larger the β value is, the greater the penalties for the constraint term. In general, a monotonically increasing sequence of {β k } can be adopted instead of the fixed β BIB001 . Specifically, an auto-adjustment criterion that automatically adjusts {β k } based on the current value of x k during the iteration was proposed, and applied for solving some convex optimization problems BIB002 ,  . The ADMM method uses the separable operators in the convex optimization problem to divide a large problem into multiple small problems that can be solved in a distributed manner. In theory, the framework of ADMM can solve most of the large-scale optimization problems. However, there are still some problems in practical applications. For example, if we use a stop criterion to determine whether convergence occurs, the original residuals and dual residuals are both related to β, and β with a large value will lead to difficulty in meeting the convergence conditions BIB006 .