Numerical Optimization, Formulations and Algorithms, for Machine Learning

机器学习（ML）涉及对优化公式和算法及其实现的更强控制。局部图优化公式和算法，以及二阶方法，都着眼于更精细的结构，并且在规模上进行它们需要重新审视理论和实现问题。在这个提案中，我们两者都做了。目标1：标准的基于图的方法本质上偏向于节点之间的全局关系，因此它们难以识别小尺度和中尺度集群，这在实践中往往更有意义。这促使了局部偏颇公式的发展。我们将开发围绕目标节点集具有局部偏置解决方案的优化公式。解决方案将有大量的零远离目标节点。除了集群之外，新公式的解决方案还将用于目标节点周围的节点的个性化排序。它们还将用于将质量从目标节点路由到图中的其他节点。我们将为这些问题开发新的算法，它将计算运行时间的解决方案，这取决于最优非零的数量，而不是整个图的大小。此外，最近的机器学习数据集需要千兆字节或兆字节的内存，但机器学习应用并不一定需要高度精确的解决方案。我们不需要寻求高精度的解决方案，我们需要开发的方法在数据大小方面具有更好的可伸缩性，并且可以扩展到数千个处理器。基于这些原则，我们提出以下目标：目标2：我们将在非常非线性和非凸问题上开发比一阶方法更有效的新方法。目前，大多数研究人员都集中在ML的一阶方法上，然而，这些方法在样本或特征之间高度相关的真实世界数据集上表现不佳。新方法将以一种廉价的方式利用目标函数的曲率信息。我们的目标是将牛顿型坐标下降框架扩展到非凸问题，提高其迭代复杂度，并开发收敛于高阶平稳点的随机方法。目标3：我们将为ML问题开发新的通信避免优化算法。我们将应用新的方法来分类和回归问题，如逻辑，线性和非线性回归。随着处理器数量的增加，对于样本或特征之间具有高度相关性的数据，新方法将具有可扩展性。我们的研究将使加拿大能够在数据分析的全球舞台上竞争。这将通过论文、实施和向会议传播我们的工作来实现。此外，我们会培养具备高度就业能力的学生，因为使用数据分析工具的现代资讯科技行业需要具备这方面经验的高素质人才。

Machine learning (ML) involves having stronger control on optimization formulations and algorithms, as well as their implementations. Local graph optimization formulations and algorithms, and second-order methods, both look at finer structure, and to do them at scale requires revisiting theoretical and implementation issues. We do both in this proposal. Objective 1: standard graph-based methods are intrinsically biased towards global relationships among nodes, so they struggle to identify small- and meso-scale clusters, which are often more meaningful in practice. This motivates the development of locally-biased formulations. We will develop optimization formulations which have locally-biased solutions around a target set of nodes. The solutions will have a large number of zeros away from the target nodes. Beyond clustering, the solutions of the new formulations will be used for personalized ordering of nodes around the target nodes. They will also be used for routing mass from the target nodes to other nodes in the graph. We will develop new algorithms for these problems, which will compute the solutions with running time which depends on the number of non-zeros at optimality instead of the size of the entire graph. Moreover, recent ML datasets require giga or tera bytes of memory, but ML applications do not necessarily require highly accurate solutions. Rather than seeking high accuracy of solutions, we need to develop methods that have better scalability with respect to the size of the data and which are scalable to thousands of processors. Based on these principles, we propose the following objectives: Objective 2: we will develop new methods that are more efficient than first-order methods on very non-linear and non-convex problems. Currently, most researchers are focused on first-order methods for ML. However, these methods suffer from poor performance on real world datasets with high correlation among samples or features. The new methods will make use of curvature information of the objective function in an inexpensive manner. Our aim is to extend Newton-type coordinate descent frameworks to non-convex problems, improve their iteration complexity and develop stochastic methods that converge to higher-order stationary points. Objective 3: we will develop new communication avoiding optimization algorithms for ML problems. We will apply the new methods to classification and regression problems, such as logistic, linear and non-linear regression. The new methods will be scalable as the number of processors increases for data with high correlation among their samples or features. Our research will allow Canada to compete on the global stage for data analysis. This will be realized through papers, implementations and dissemination of our work to conferences. Moreover, we will train students who are highly employable, since modern industries in the IT sector that use data analysis tools demand high quality personnel with such experience.