Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds

We consider distributed optimization methods for problems where forming the\nHessian is computationally challenging and communication is a significant\nbottleneck. We leverage randomized sketches for reducing the problem dimensions\nas well as preserving privacy and improving straggler resilience in\nasynchronous distributed systems. We derive novel approximation guarantees for\nclassical sketching methods and establish tight concentration results that\nserve as both upper and lower bounds on the error. We then extend our analysis\nto the accuracy of parameter averaging for distributed sketches. Furthermore,\nwe develop unbiased parameter averaging methods for randomized second order\noptimization for regularized problems that employ sketching of the Hessian.\nExisting works do not take the bias of the estimators into consideration, which\nlimits their application to massively parallel computation. We provide\nclosed-form formulas for regularization parameters and step sizes that provably\nminimize the bias for sketched Newton directions. Additionally, we demonstrate\nthe implications of our theoretical findings via large scale experiments on a\nserverless cloud computing platform.\n