Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization

Abstract

In distributed second order optimization, a standard strategy is to average many local estimates, each of which is based on a small sketch or batch of the data. However, the local estimates on each machine are typically biased, relative to the full solution on all of the data, and this can limit the effectiveness of averaging. Here, we introduce a new technique for debiasing the local estimates, which leads to both theoretical and empirical improvements in the convergence rate of distributed second order methods. Our technique has two novel components: (1) modifying standard sketching techniques to obtain what we call a surrogate sketch; and (2) carefully scaling the global regularization parameter for local computations. Our surrogate sketches are based on determinantal point processes, a family of distributions for which the bias of an estimate of the inverse Hessian can be computed exactly. Based on this computation, we show that when the objective being minimized is $l_2$-regularized with parameter $\lambda$ and individual machines are each given a sketch of size $m$, then to eliminate the bias, local estimates should be computed using a shrunk regularization parameter given by ${\lambda }^{\prime }=\lambda \cdot (1-\frac{d_{\lambda }}{m})$, where $d_{\lambda }$ is the $\lambda$-effective dimension of the Hessian (or, for quadratic problems, the data matrix).

References in corpus (8)

• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• AIDE: Fast and Communication Efficient Distributed Optimization
• Exact expressions for double descent and implicit regularization via surrogate random design
• Faster Least Squares Optimization
• Correcting the bias in least squares regression with volume-rescaled sampling
• Distributed estimation of the inverse Hessian by determinantal averaging
• Distributed Sketching Methods for Privacy Preserving Regression
• Distributed Averaging Methods for Randomized Second Order Optimization