2020/07/02 by Michał Dereziński, Burak Bartan, Dereziński, Michał +5
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2007.01327
openalex publication_date 2020/07/02 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In distributed second order optimization, a standard strategy is to average\nmany local estimates, each of which is based on a small sketch or batch of the\ndata. However, the local estimates on each machine are typically biased,\nrelative to the full solution on all of the data, and this can limit the\neffectiveness of averaging. Here, we introduce a new technique for debiasing\nthe local estimates, which leads to both theoretical and empirical improvements\nin the convergence rate of distributed second order methods. Our technique has\ntwo novel components: (1) modifying standard sketching techniques to obtain\nwhat we call a surrogate sketch; and (2) carefully scaling the global\nregularization parameter for local computations. Our surrogate sketches are\nbased on determinantal point processes, a family of distributions for which the\nbias of an estimate of the inverse Hessian can be computed exactly. Based on\nthis computation, we show that when the objective being minimized is\nl2-regularized with parameter \λ and individual machines are each\ngiven a sketch of size m, then to eliminate the bias, local estimates should\nbe computed using a shrunk regularization parameter given by\n\λ\′=\λ\⋅(1- fracd\λm), where d\λ\nis the \λ-effective dimension of the Hessian (or, for quadratic\nproblems, the data matrix).\n