This paper studies distributed estimation and inference for a general statistical problem with a convex loss that could be non-differentiable. For the purpose of efficient computation, we restrict ourselves to stochastic first-order optimization, which enjoys low per-iteration complexity. To motivate the proposed method, we first investigate the theoretical properties of a straightforward Divide-and-Conquer Stochastic Gradient Descent (DC-SGD) approach. Our theory shows that there is a restriction on the number of machines and this restriction becomes more stringent when the dimension @math is large. To overcome this limitation, this paper proposes a new multi-round distributed estimation procedure that approximates the Newton step only using stochastic subgradient. The key component in our method is the proposal of a computationally efficient estimator of @math , where @math is the population Hessian matrix and @math is any given vector. Instead of estimating @math (or @math ) that usually requires the second-order differentiability of the loss, the proposed First-Order Newton-type Estimator (FONE) directly estimates the vector of interest @math as a whole and is applicable to non-differentiable losses. Our estimator also facilitates the inference for the empirical risk minimizer. It turns out that the key term in the limiting covariance has the form of @math , which can be estimated by FONE.
In addition, our FONE of @math is related to a recently developed stochastic first-order approach---stochastic variance reduced gradient (SVRG, see e.g., @cite_21 @cite_10 @cite_1 and references therein). Our method subsumes SVRG as a special case. Indeed, when the @math , our iterative algorithm (non-distributed version) essentially reduces to SVRG. On the other hand, we allow a general @math vector, which does not need to be an averaged gradient (e.g., for the purpose of inference in ). Moreover, the theoretical development of SVRG requires the unbiasedness of the stochastic gradient with respect to the averaged gradient @math , the differentiability, and uniform strong convexity of the loss function @math . In contrast, our theoretical results do not require any of these conditions. In fact, the motivation for our procedure is fundamentally different from that for SVRG: our method is to provide an estimator @math with the population matrix @math for any @math ; while most SVRG literature aims to solve a finite-sum optimization problem @math for a differentiable strongly-convex @math .
@cite_1 @cite_21 @cite_10
2722088290 2107438106 2769669795
We present novel minibatch stochastic optimization methods for empirical risk minimization problems, the methods efficiently leverage variance reduced first-order and sub-sampled higher-order information to accelerate the convergence speed. For quadratic objectives, we prove improved iteration complexity over state-of-the-art under reasonable assumptions. We also provide empirical evidence of the advantages of our method compared to existing approaches in the literature. 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.