Numerical Optimization, Formulations and Algorithms, for Machine Learning

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

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.