Beyond With-replacement Sampling for Large-Scale Data Analysis and Optimization

传感和处理技术、通信能力和智能设备的进步，使收集大量数据以做出决策的系统得以部署。分析和处理大数据的许多关键问题都会导致大规模的优化问题。作为一种核心的、应用非常广泛的优化方法，它对于数据点按顺序采样和处理的问题是有效的，但这种方法的理论与实践之间存在很大的差距。该项目旨在通过提供与实际问题相关的新颖性能保证以及开发新颖和更快的优化方法变体来填补这一空白。在该项目范围内开发的方法和技术将有助于提高针对大数据挑战的优化算法的效率和数学基础，有助于为各种大规模数据分析问题做出更有效的决策。增量梯度法（Incremental gradient， IG）是上述最核心、应用最广泛的优化方法，它包含了数据分析和机器学习实践中常用的优化方法，如随机梯度下降法、随机坐标下降法和Kaczmarz方法。如果以独立同分布（i.i.d）的方式对数据点进行替换采样，则可以获得IG的各种性能保证。然而，这些在实际场景中没有帮助：在实践中，数据通常在非i -i中采样。D的时尚而不是替换，因为最终的融合通常要快得多。该项目的第一个目标是研究和量化一类有趣的回归问题的差异，这是一个关键的开放问题。提出了几种获得无替换抽样方案的渐近和非渐近理论保证的技术和方法。第二个目标是开发具有收敛保证的快速算法，以超越i.i.d采样的限制。为此，本文提出了一个新的框架来研究几种不同的抽样方案及其性能。在此框架下，基于加权无替换采样和循环采样的新采样方案能够适应数据集，并在限制精度方面提高传统i.i.d采样的性能。

Advances in sensing and processing technologies, communication capabilities and smart devices have enabled deployment of systems where a massive amount of data is collected to make decisions. Many key problems of interest for analyzing and processing big data result in large-scale optimization problems. For a core, very widely used optimization method, which is efficient for such problems where the data points are sampled and processed in a sequential manner, there is a large gap between the theory and practice of this method. This project is about filling this gap by providing novel performance guarantees relevant to practical problems as well as developing novel and faster variants of the optimization method. The methods and techniques developed under the scope of this project will contribute to the efficiency and mathematical foundations of optimization algorithms targeted for big data challenges, contributing to more efficient decision making for a wide variety of large-scale data analysis problems. Incremental gradient (IG) is the core, very widely used optimization method mentioned above and subsumes popular optimization methods in data analysis and machine learning practice such as stochastic gradient descent, randomized coordinate descent and Kaczmarz methods. Various performance guarantees for IG are available if data points are sampled with replacement in an independent identically distributed (i.i.d.) manner. However, these are not helpful in practical scenarios: In practice, data is often sampled in a non-i.i.d fashion without-replacement instead, as the resulting convergence is typically much faster. A first goal in this project is to study and quantify this discrepancy over an interesting class of regression problems, which has been a key open problem. Several techniques and methods are proposed for obtaining asymptotic and non-asymptotic theoretical guarantees for without-replacement sampling schemes. A second goal is to develop fast algorithms with convergence guarantees that go beyond the limitations of the i.i.d. sampling. For this purpose, a new framework for studying several alternative sampling schemes and their performance is developed. Using this framework, novel sampling schemes based on weighted without-replacement sampling and cyclic sampling that can adapt to the dataset and improve upon the performance of the traditional i.i.d. sampling in terms of limiting accuracy are developed.