OverSketched Newton: Fast Convex Optimization for Serverless Systems
This addresses the problem of efficient optimization in serverless computing environments, offering a practical improvement for distributed machine learning tasks.
The paper tackles large-scale convex optimization in serverless systems by developing OverSketched Newton, a randomized Hessian-based algorithm that uses matrix sketching for approximate Hessian computation, achieving a ~50% reduction in total running time on AWS Lambda compared to state-of-the-art distributed methods.
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.