Numerical Optimization, Formulations and Algorithms, for Machine Learning

用于机器学习的数值优化、公式和算法

• 批准号: RGPIN-2019-04067
• 负责人: Fountoulakis, Kimon
• 金额: $ 2.4万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=714127
• 关键词: Numerical; Optimization; Formulations; Algorithms; Machine

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.

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