Numerical Optimization, Formulations and Algorithms, for Machine Learning

点击翻译按钮获取中文摘要

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.**