OverSketched Newton: Fast Convex Optimization for Serverless Systems
From MaRDI portal
Publication:6315981
arXiv1903.08857MaRDI QIDQ6315981
Author name not available (Why is that?)
Publication date: 21 March 2019
Abstract: Motivated by recent developments in serverless systems for large-scale computation as well as improvements in scalable randomized matrix algorithms, we develop OverSketched Newton, a randomized Hessian-based optimization algorithm to solve large-scale convex optimization problems in serverless systems. OverSketched Newton leverages matrix sketching ideas from Randomized Numerical Linear Algebra to compute the Hessian approximately. These sketching methods lead to inbuilt resiliency against stragglers that are a characteristic of serverless architectures. Depending on whether the problem is strongly convex or not, we propose different iteration updates using the approximate Hessian. For both cases, we establish convergence guarantees for OverSketched Newton and empirically validate our results by solving large-scale supervised learning problems on real-world datasets. Experiments demonstrate a reduction of ~50% in total running time on AWS Lambda, compared to state-of-the-art distributed optimization schemes.
Has companion code repository: https://github.com/vvipgupta/OverSketchedNewton
This page was built for publication: OverSketched Newton: Fast Convex Optimization for Serverless Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315981)
