标题： 凸和非凸正则化最小二乘法的草图方法及其精确保证 显示英文标题

标题： Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees

摘要： 随机算法对于解决大规模优化问题非常重要。 在本文中，我们提出了一种针对由凸或非凸正则化函数正则化的最小二乘问题的快速抽样算法，称为正则化优化抽样（SRO）。 我们的SRO算法首先生成原始数据矩阵的抽样，然后求解抽样后的问题。 与现有的随机算法不同，我们的算法在一个统一的框架中处理一般的Fréchet次可微正则化函数。 我们提出了关于原始问题和抽样问题优化结果之间近似误差的一般理论结果，适用于可以是凸或非凸的正则化最小二乘问题。 对于任意的凸正则化器，证明了近似误差的相对误差界。 重要的是，在温和条件下，通过我们的通用理论结果，还得到了通过求解抽样后的稀疏凸或非凸学习问题进行稀疏信号估计的极小极大率。 据我们所知，我们的结果是在统一理论框架下，首次展示通过抽样实现凸或非凸稀疏学习问题的极小极大率的结果之一。 我们进一步提出了一种迭代抽样算法，通过迭代调用抽样算法，将近似误差指数级地减少。 实验结果证明了所提出的SRO和迭代SRO算法的有效性。 显示英文摘要

摘要： Randomized algorithms are important for solving large-scale optimization problems. In this paper, we propose a fast sketching algorithm for least square problems regularized by convex or nonconvex regularization functions, Sketching for Regularized Optimization (SRO). Our SRO algorithm first generates a sketch of the original data matrix, then solves the sketched problem. Different from existing randomized algorithms, our algorithm handles general Frechet subdifferentiable regularization functions in an unified framework. We present general theoretical result for the approximation error between the optimization results of the original problem and the sketched problem for regularized least square problems which can be convex or nonconvex. For arbitrary convex regularizer, relative-error bound is proved for the approximation error. Importantly, minimax rates for sparse signal estimation by solving the sketched sparse convex or nonconvex learning problems are also obtained using our general theoretical result under mild conditions. To the best of our knowledge, our results are among the first to demonstrate minimax rates for convex or nonconvex sparse learning problem by sketching under a unified theoretical framework. We further propose an iterative sketching algorithm which reduces the approximation error exponentially by iteratively invoking the sketching algorithm. Experimental results demonstrate the effectiveness of the proposed SRO and Iterative SRO algorithms.