OverSketched Newton: Fast Convex Optimization for Serverless Systems
Authors:
- 10 December 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 288-297
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 or not the problem is strongly convex, we propose different iteration updates using the approximate Hessian. For both cases, we establish convergence guarantees for OverSketched Newton, and we 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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Deep Mixtures of Factor Analyzers with Common Loadings: A Novel Deep Generative Approach to Clustering2017
- Occupy the cloud2017
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic ConvergenceSIAM Journal on Optimization, 2017
- Matrix factorizations at scale: A comparison of scientific data analytics in spark and C+MPI using three case studies2016
- Sketching as a Tool for Numerical Linear AlgebraFoundations and Trends® in Theoretical Computer Science, 2014
- The tail at scaleCommunications of the ACM, 2013
- LIBSVMACM Transactions on Intelligent Systems and Technology, 2011
- MapReduceCommunications of the ACM, 2008
- Note on Convergence of MinresMultivariate Behavioral Research, 1988