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.