Linearly convergent stochastic algorithms for optimization and linear systems.
详细信息
文摘
Stochastic first-order methods are fundamental methods that have shown renewed popularity in a variety of settings,especially machine learning. This dissertation considers several methods of this type,for optimization and linear algebra tasks,with a special focus on methods that are well suited to efficient implementation on modern multicore computers. Novel convergence results are presented for this setting,along with estimated on the number of cores that can be used in the computation without significant degradation of efficiency (the "potential parallelism"). Chapter 2 describes an asynchronous parallel stochastic coordinate descent method for convex smooth minimization. In the unconstrained case,sublinear convergence rate is proved for the weakly convex case,linear convergence for the essentially strongly convex case,and potential parallelism of O(n1/2 ) for both cases where n is the problem dimension. For the case of bound constraints,similar complexity is proved,but with potential parallelism of O(n1/4 ). Chapter 3 extends the parallel mechanism in Chapter 2 to solve the composite objective function consisting of a smooth function plus a separable nonsmooth function. In contrast to previous analysis in Chapter 2,the mode of asynchronous computation accounts for the "inconsistent" read situation. Despite the complications arising from "inconsistency",the method achieves a linear convergence rate on functions that satisfy an optimal strong convexity property and a sublinear rate on weakly convex functions with potential parallelism of O(n 1/4 ). Chapter 4 considers the linear algebra problem Ax ＝ b,under the assumption of feasibility. The randomized Kaczmarz algorithm is parallelized in the same asynchronous parallel mechanism as Chapter 2. We prove a linear convergence rate and show that the potential parallelism is O(m),where m is the number of rows in A. Chapter 5 considers the same problem as Chapter 4 - Ax ＝ b - but discusses an acceleration of the Kaczmarz approach (for serial implementation) using Nesterov-type acceleration scheme. In all chapters,computational experience is reported to back up our claims concerning convergence rate and parallel efficiency.