Adaptive Step Size For First Order Stochastic Optimization

Increased storage capacity has lead to an exponential growth in the size and form of data,thereby,more and more fields have put forward the requirements of high-speed processing for mass data.Because of its low computational cost and fast speed,first-order methods have become a mainstream method for dealing with this challenging problem.The rapid growth of convex optimization optimization problems in signal processing and machine learning has further increased the popularity of first-order methods.Especially,first-order stochastic optimization has become the main method for large-scale learning because of the less computational cost,faster speed and easier expansion.However,these advan-tages do not comes for free,the stochastic estimate in stochastic optimization has a non-vanishing variance.For example,the convergence rate is sub-linear even if the function to be minimized is strongly convex and smooth.Along the line of reducing variance,there exists a huge stochastic optimization works that have been received more attention.As a way to speed up stochastic optimization problems,mini-batch algorithm inherits the superiority of stochastic gradient.In addition,it can effectively reduce the variance of the algorithm.One of the major issues in mini-batch algorithms is how to choose an appropriate step size while running the algorithm.Because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space,the traditional line search technique does not apply for mini-batch algorithms.The common practice in mini-batch algorithms is either to use a diminishing step size,or to tune a step size manually.There are time consuming in practice and in general,little guidance is provided about good choices.This thesis discusses mini-batch algorithms for minimizing composite functions by step size selection rule.The main work and innovation of this thesis are as follows:1.We first introduce the BB method into the state of the art mini-batch method(mini-batch semi-stochastic gradient descent(mS2GD)method),thereby obtaining a new batch algorithm that we call mS2GD-BB.We theoretically prove that the mS2GD-BB algorith-m linearly converges with the optimization in expectation.In addition,we analyze the complexity of mS2GD-BB and show that it achieves the same level as the state of the art stochastic optimization.2.The BB method depends on the full gradient of objective function,therefore,it takes a lot of computational cost.In addition,it cannot update step size immediately.Motivated by this gap,we propose an improved BB method,which use batch samples to approx-imate the so called secant equation.We incorporate the improved BB method into the state of the art mini-batch algorithm,mS2GD,thereby,obtaining another new batch al-gorithm:mS2GD-RBB.We prove the linear convergence of mS2GD-RBB and analyze the complexity of mS2GD-RBB.To further show the effectiveness of the improved BB method,we introduce it into the Acc-Prox-SVRG method obtaining another new method:Acc-Prox-SVRG-RBB.3.Further,we propose to use hypergradient to compute online step size for mini-batch algorithms.Specifically,we incorporate online step size into another advanced mini-batch algorithms,mini-batch nonconvex SVRG(MSVRG),thereby generating a new method,MSVRG-OSS.We prove the convergence of MSVRG-OSS and analyze its complexity.4.We incorporate the BB step size and the RBB step size into the deterministic and stochastic methods which has the frame of Nesterov's acceleration technique.We also prove the convergence of new proposed methods and show their complexity.Numerical experiments show the effectiveness of the proposed methods.