Estimating the Error of Randomized Newton Methods: A Bootstrap Approach
Estimating the Error of Randomized Newton Methods: A Bootstrap Approach
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Jessie X. T. Chen;Miles E. Lopes
中科院分区：
文献类型：
--
作者：
Jessie X. T. Chen;Miles E. Lopes
近年来，随机牛顿算法已成为大规模和分布式优化研究的热点。通常，这些方法基于“计算精度权衡”，允许用户以解决方案中的错误为代价获得可伸缩性。然而，用户不知道随机化近似产生了多少误差，这在两个方面可能是有害的：一方面，用户可能试图用理论的最坏情况误差界限来评估未知误差，但是当界限涉及未知常数时，这种方法是不切实际的，而且它经常导致过度的计算。另一方面，用户可能会以启发式的方式选择“草图大小”和停止标准，但这可能导致不可靠的结果。在这些困难的激励下，我们展示了如何使用自举来直接估计未知误差，从而防止了过度的计算，并对随机解的质量提供了更多的信心。此外，我们还表明，误差估计比现有的随机牛顿方法（如Newton SKETCH和GI - ANT）增加了很少的计算成本，并且具有良好的经验性能。
Randomized Newton methods have recently become the focus of intense research activity in large-scale and distributed optimization. In general, these methods are based on a “computation-accuracy trade-off”, which allows the user to gain scalability in exchange for error in the solution. However, the user does not know how much error is created by the randomized approximation, which can be detrimental in two ways: On one hand, the user may try to assess the unknown error with theoretical worst-case error bounds, but this approach is impractical when the bounds involve unknown constants, and it often leads to excessive computation. On the other hand, the user may select the “sketch size” and stopping criteria in a heuristic manner, but this can lead to unreliable results. Motivated by these difficulties, we show how bootstrapping can be used to directly estimate the unknown error , which prevents excessive computation, and offers more confidence about the quality of a randomized solution. Furthermore, we show that the error estimation adds little computational cost to existing randomized Newton methods (e.g. NEWTON SKETCH and GI - ANT ), and it performs well empirically.