In this paper, we use Proximal Cubic regularized Newton Methods (PCNM) to optimize the sum of a smooth convex function and a non-smooth convex function, where we use inexact gradient and Hessian, and an inexact subsolver for the cubic regularized second-order subproblem. We propose inexact variants of PCNM and accelerated PCNM respectively, and show that both variants can achieve the same convergence rate as in the exact case, provided that the errors in the inexact gradient, Hessian and subsolver decrease at appropriate rates. Meanwhile, in the online stochastic setting where data comes endlessly, we give the overall complexity of the proposed algorithms and show that they are as competitive as the stochastic gradient descent. Moreover, we give the overall complexity of the proposed algorithms in the finite-sum setting and show that it is as competitive as the state of the art variance reduced algorithms. Finally, we propose an efficient algorithm for the cubic regularized second-order subproblem, which can converge to an enough small neighborhood of the optimal solution in a superlinear rate.
Table gives the overall complexity of representative algorithms in the online stochastic setting. For simplicity, in Table , we neglect the poly-logarithmic factor and use the @math notation. The existing algorithms under this setting are mainly first-order algorithms @cite_4 , which can be divided into methods that pass one sample or a fixed mini-batch samples in each iteration @cite_21 @cite_3 , and methods that use an increased sample size in each iteration @cite_20 @cite_18 @cite_5 . If we do not consider the poly-logarithmic factor, COMID @cite_21 obtains the optimal convergence rate ( @math regret) @math in the convex setting and @math in the @math -strongly convex setting. However, as shown in Table , the Inexact Proximal Gradient Method (IPGM) and Accelerated IPGM (IPGM) @cite_5 Although @cite_5 do not give the overall complexity in the online stochastic setting, we can give the complexity results in Table based on the same analysis in this paper. , which belongs to the methods with increased sample size, can not obtain the optimal rate in the convex setting. The proposed methods IPCNM and AIPCNM belongs to the methods with an increased sample size, while we use the second-order information.
@cite_18 @cite_4 @cite_21 @cite_3 @cite_5 @cite_20
1751687266 131378802 2205628031 2952975724 2061570747
Many structured data-fitting applications require the solution of an optimization problem involving a sum over a potentially large number of measurements. Incremental gradient algorithms offer inexpensive iterations by sampling a subset of the terms in the sum; these methods can make great progress initially, but often slow as they approach a solution. In contrast, full-gradient methods achieve steady convergence at the expense of evaluating the full objective and gradient on each iteration. We explore hybrid methods that exhibit the benefits of both approaches. Rate-of-convergence analysis shows that by controlling the sample size in an incremental-gradient algorithm, it is possible to maintain the steady convergence rates of full-gradient methods. We detail a practical quasi-Newton implementation based on this approach. Numerical experiments illustrate its potential benefits. We present a new method for regularized convex optimization and analyze it under both online and stochastic optimization settings. In addition to unifying previously known firstorder algorithms, such as the projected gradient method, mirror descent, and forwardbackward splitting, our method yields new analysis and algorithms. We also derive specific instantiations of our method for commonly used regularization functions, such as l1, mixed norm, and trace-norm. We consider regularized stochastic learning and online optimization problems, where the objective function is the sum of two convex terms: one is the loss function of the learning task, and the other is a simple regularization term such as l1-norm for promoting sparsity. We develop extensions of Nesterov's dual averaging method, that can exploit the regularization structure in an online setting. At each iteration of these methods, the learning variables are adjusted by solving a simple minimization problem that involves the running average of all past subgradients of the loss function and the whole regularization term, not just its subgradient. In the case of l1-regularization, our method is particularly effective in obtaining sparse solutions. We show that these methods achieve the optimal convergence rates or regret bounds that are standard in the literature on stochastic and online convex optimization. For stochastic learning problems in which the loss functions have Lipschitz continuous gradients, we also present an accelerated version of the dual averaging method. We consider the problem of optimizing the sum of a smooth convex function and a non-smooth convex function using proximal-gradient methods, where an error is present in the calculation of the gradient of the smooth term or in the proximity operator with respect to the non-smooth term. We show that both the basic proximal-gradient method and the accelerated proximal-gradient method achieve the same convergence rate as in the error-free case, provided that the errors decrease at appropriate rates.Using these rates, we perform as well as or better than a carefully chosen fixed error level on a set of structured sparsity problems. This paper presents a methodology for using varying sample sizes in batch-type optimization methods for large-scale machine learning problems. The first part of the paper deals with the delicate issue of dynamic sample selection in the evaluation of the function and gradient. We propose a criterion for increasing the sample size based on variance estimates obtained during the computation of a batch gradient. We establish an @math complexity bound on the total cost of a gradient method. The second part of the paper describes a practical Newton method that uses a smaller sample to compute Hessian vector-products than to evaluate the function and the gradient, and that also employs a dynamic sampling technique. The focus of the paper shifts in the third part of the paper to L 1-regularized problems designed to produce sparse solutions. We propose a Newton-like method that consists of two phases: a (minimalistic) gradient projection phase that identifies zero variables, and subspace phase that applies a subsampled Hessian Newton iteration in the free variables. Numerical tests on speech recognition problems illustrate the performance of the algorithms.