III: Small: Effective Convex Solvers for Machine Learning

许多大规模机器学习问题被表述为优化问题，其中一些误差或损失的度量是在合适的训练语料库上最小化的。真正的问题有太多的数据点，单台计算机无法容纳。因此，数据和/或计算必须分布在计算机网络上。通常，解决超大问题的唯一实用方法是所谓的分裂方法，但它们的收敛性质变化很大：有时非常快，有时非常慢，很难预测。该项目的目标是更好地理解收敛行为，并利用这种理解来构建具有更一致收敛性质的加速算法。这将允许将机器学习技术应用于更广泛的问题类别。拆分方法（或者更准确地说是交替方向方法）基于这样一种思想，即一般的凸优化问题可以拆分为两个或多个部分，与作为一个整体的问题相比，每个部分的解决都要容易得多。这些方法依次循环遍历所有变量，对变量的每个子集进行优化，使其余部分保持不变。提出的工作建立在一个简单的模型问题的初步分析，使用某些矩阵算子的特征结构。该项目致力于将这种分析扩展到更一般的问题，以及使用成熟的矩阵特征值问题的计算技术开发更快的求解器。成功与否将根据所发展的理论的普遍性和在实际问题上观察到的收敛行为的改进来衡量。有了更快的求解器，在全球规模的社交网络（如Facebook或Twitter）中发现有影响力的主要区域可以在普通的计算机平台上实现。这同样适用于跟踪疾病传播和视频序列中的人。有了高效的求解器，跟踪软件就可以部署在本地硬件上，而不需要高性能的中央服务器。这将导致无数领域的进步，如数据挖掘、压缩感知、推荐系统、信号处理、缺失数据输入、大规模社会、生物或计算机网络分析、图像重建、去噪和分类。这项研究的结果将在机器学习、数据挖掘和优化领域的主要期刊和会议上发表论文，并通过WWW (http://www-users.cs.umn.edu/~boley/ML-Optimization).The)以软件包的形式传播，该项目取决于不同学科和应用领域之间的互动，这将吸引来自研究生和本科水平的各种背景的学生。一些研究任务适合作为线性代数、优化、数据挖掘、机器学习等课程的项目，并且适合本科生和研究生共同开发。本科生，包括女性和代表性不足群体的成员，将看到数学算法在解决他们感兴趣的实际问题方面的价值。

Many large scale machine learning problems are formulated as optimization problems, in which some measure of error or loss is to be minimized over a suitable training corpus. Real problems have too many data points to fit in a single computer. Hence the data and/or computation must be distributed over a network of computers. Often the only practical methods for extremely large problems are so-called splitting methods, but their convergence properties are extremely variable: sometimes very fast, sometimes very slow, in ways that can be hard to predict. The goal of this project is to gain a better understanding of the convergence behavior and to use this understanding to construct accelerated algorithms with more consistent convergence properties. This will allow the application of machine learning techniques to a much wider class of problems.Splitting methods (or more precisely alternating direction methods) are based on the idea that a general convex optimization problem can be split into two or more parts, each of which can be solved much more easily compared to the problem as a whole. The methods cycle through all the variables in turn, optimizing over each subset of variables leaving the rest fixed. The proposed work builds on a preliminary analysis of a simple model problem using the eigen-structure of certain matrix operators. The project is devoted to extending this analysis to more general problems, as well as developing faster solvers using well-established computational technologies for the matrix eigenvalue problem. Success will be measured in terms of the generality of the theory developed and the improvements in the observed convergence behavior on real problems.With faster solvers, discovery of major regions of influence in a global-scale social network (e.g. Facebook or Twitter) could become practical on modest computer platforms. The same holds for tracking disease propagation and people in video sequences. With efficient solvers, tracking software could be deployed on local hardware without the need for high-powered central servers. This will lead to advances in countless areas such data mining, compressive sensing, recommender systems, signal processing, missing data imputation, analysis of large scale social, biological or computer networks, image reconstruction, denoising and classification.The results of this research are to be disseminated in papers in the principal journals and conferences in machine learning, data mining, and optimization as well as in the form of software packages via the WWW (http://www-users.cs.umn.edu/~boley/ML-Optimization).The project depends on the interaction between different disciplines and applications areas, which will attract students from a variety of backgrounds at both the graduate and undergraduate level. Some research tasks are suitable as projects in classes on linear algebra, optimization, data mining, machine learning and are to be developed for both undergraduate and graduate students. Undergraduate students, including women and members of underrepresented groups, will see the value of mathematical algorithms to solve real problems of interest to them.