Gradient Sliding Schemes for Large-scale Optimization and Data Analysis

数字数据收集技术的快速进步导致数据集的大小和复杂性显著增加，有时被称为大数据。优化模型与新颖的统计分析相结合，在分析这些复杂的数据集方面已被证明是卓有成效的。然而，由这些应用产生的优化问题通常涉及非光滑分量，这会显著降低现有优化算法的收敛速度。此外，复杂的数据集非常大，并且通常分布在不同的存储位置，因此通常认为在算法的每次迭代中可以完全遍历整个数据集的假设是不现实的。梯度滑动方案不需要这种假设，因此非常适合于大数据优化。这项研究的目的是通过设计、分析和实现一类使用梯度滑动格式的新型优化算法来解决这些计算挑战。这些新的优化算法的有效性将通过解决图像处理和机器学习中的问题来验证。梯度滑动算法是一阶方法，除了在可行集上投影等辅助操作外，还专门使用一阶信息(梯度和函数值)。与已有的一阶方法相比，梯度滑动法可以跳过梯度的计算，同时仍然保持了求解不同类型大规模优化问题的最优收敛性质。这项研究还将研究一类新的条件梯度滑动方法，这种方法在每次迭代中都需要线性优化，而不是在可行集上进行更复杂的投影。这些算法有望在梯度计算次数和解线性最优化子问题的次数方面表现出最优的收敛速度。此外，还将研究适用于并行/分布式计算的这些梯度滑动算法的随机变体。当应用于数据分析时，这些算法可以将遍历数据集的次数、与所涉及的矩阵-向量乘法相关的计算成本以及分布式数据集的通信成本减少数量级。

The rapid advances in technology for digital data collection have led to significant increases in the size and complexity of data sets, sometimes known as big data. Optimization models, when combined with novel statistical analysis, have been proven fruitful in analyzing these complex datasets. However, optimization problems arising from these applications often involve nonsmooth components that can significantly slow down the convergence of existing optimization algorithms. Moreover, the complex datasets are so big and often distributed over different storage locations that the usual assumption that an entire dataset can be completely traversed in each iteration of the algorithm is unrealistic. Gradient sliding schemes do not require this assumption and hence are ideally suited for optimization with big data. The research aims at tackling these computational challenges through the design, analysis, and implementation of a novel class of optimization algorithms using gradient sliding schemes. The effectiveness of these new optimization algorithms will be demonstrated by solving problems in image processing and machine learning.The gradient sliding algorithms are first-order methods that use first-order information (gradients and function values) exclusively in addition to some auxiliary operations, such as projection over the feasible set. As opposed to existing first-order methods, gradient sliding methods can skip the computation of gradients from time to time, while still preserving the optimal convergence properties for solving different types of large-scale optimization problems. This research will also study a new class of conditional gradient sliding methods that require a linear optimization rather than a more involved projection over the feasible set in each iteration. These algorithms are expected to exhibit optimal rate of convergence in terms of both the number of gradient computations and the number of times for solving the linear optimization subproblem. Moreover, randomized variants of these gradient sliding algorithms which are amenable to parallel/distributed computing will also be studied. When applied to data analysis, these algorithms can reduce, by orders of magnitude, the number of traverses through the datasets, the computational cost associated with the involved matrix-vector multiplications, as well as the communication costs for the distributed datasets.