Timezone: »

 
Poster
Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
Michal Derezinski · Burak Bartan · Mert Pilanci · Michael Mahoney

Thu Dec 10 09:00 PM -- 11:00 PM (PST) @ Poster Session 6 #1857
in Poster Session 7 »
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(1-\frac{d_\lambda}{m})$, where $d_\lambda$ is the $\lambda$-effective dimension of the Hessian (or, for quadratic problems, the data matrix).
Keywords: Reinforcement Learning · Reinforcement Learning and Planning

Author Information

Michal Derezinski (UC Berkeley)
Burak Bartan (Stanford University)
Mert Pilanci (Stanford)
Michael Mahoney (UC Berkeley)

More from the Same Authors