OverSketched Newton: Fast Convex Optimization for Serverless Systems
OverSketched Newton: Fast Convex Optimization for Serverless Systems
复制标题
DOI：
10.1109/bigdata50022.2020.9378289
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Vipul Gupta;S. Kadhe;T. Courtade;Michael W. Mahoney;K. Ramchandran
中科院分区：
文献类型：
--
作者：
Vipul Gupta;S. Kadhe;T. Courtade;Michael W. Mahoney;K. Ramchandran
通过服务器系统的最新开发，用于大规模计算以及可扩展的随机矩阵算法的改进，我们开发了牛顿的牛顿，这是一种基于HESSIAN的随机优化算法，以求解大规模的凸出式凸出优化问题。从随机数字线性代数中绘制想法，以计算Hessian大约导致内置的素描方法。反对散乱的人是无服务器体系结构的特征。通过解决实际数据集上的大规模监督学习问题。 Lambda，与最新的分布式优化方案相比。
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.