III: Small: Effective Convex Solvers for Machine Learning

许多大规模的机器学习问题都被描述为优化问题，其中一定程度的错误或损失是通过适当的训练语料库来最小化的。真正的问题有太多的数据点，无法放入一台计算机中。因此，数据和/或计算必须分布在计算机网络上。通常，解决极大问题的唯一实用方法是所谓的分裂方法，但它们的收敛特性极不稳定：有时非常快，有时非常慢，其方式可能很难预测。这个项目的目标是更好地理解收敛行为，并利用这种理解来构造具有更一致收敛性质的加速算法。这将允许将机器学习技术应用于更广泛的问题类别。分裂方法(或更准确地说，交替方向方法)基于这样的思想，即一般的凸优化问题可以被分成两个或多个部分，每个部分都可以比整体问题更容易解决。这些方法依次循环所有变量，对每个变量子集进行优化，其余变量保持不变。所提出的工作建立在利用某些矩阵算子的特征结构对一个简单的模型问题进行初步分析的基础上。该项目致力于将这种分析扩展到更一般的问题，以及使用成熟的矩阵特征值问题的计算技术开发更快的解算器。成功的衡量标准将是开发出的理论的普适性，以及在实际问题上观察到的收敛行为的改善。有了更快的解算器，在全球范围的社交网络(如Facebook或Twitter)中发现主要影响区域可能在适度的计算机平台上变得实用。同样的道理也适用于跟踪视频序列中的疾病传播和人。有了高效的解算器，跟踪软件可以部署在本地硬件上，而不需要高性能的中央服务器。这将导致无数领域的进步，如数据挖掘、压缩传感、推荐系统、信号处理、缺失数据补偿、大规模社会、生物或计算机网络的分析、图像重建、去噪和分类。这项研究的结果将在机器学习、数据挖掘和优化的主要期刊和会议上的论文中传播，以及通过万维网(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.