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.