CIF: Small: Computationally Efficient Second-Order Optimization Algorithms for Large-Scale Learning

University Of Texas At Austin, Austin TX

Investigators

Abstract

The rapid success of machine learning and artificial intelligence has positively affected several domains such as robotics, wireless communications, and sensor networks, to name a few. This success is mostly due to advances in storage, computational power, data representation, and algorithms, which allows the power of increasingly rich datasets to be harnessed. In particular, advances in computationally efficient optimization algorithms have had a crucial role in this success, as most tasks in modern machine learning and artificial intelligence problems can be formulated as optimization programs. Despite significant progress, most existing optimization algorithms could be slow when applied to the ill-conditioned problems that often arise in large-scale machine learning. This project lays out an agenda to develop a class of memory efficient, computationally affordable, and distributed friendly second-order methods for solving modern machine learning problems. On the education front, this project will provide a stimulating and innovative research environment for both graduate and undergraduate students; it will also incorporate the development of curricular material for courses at the University of Texas at Austin. Current optimization algorithms for large-scale machine learning are inefficient at times since these methods operate using only first-order information (gradient) of the objective function. This project aims to develop a class of fast and efficient second-order methods that exploit the curvature information of the objective function to accelerate convergence in ill-conditioned settings. The research encompasses three different thrusts: (I) Developing memory efficient incremental quasi-Newton methods with provably fast convergence guarantees; (II) Improving the computational complexity of second-order adaptive sample size algorithms by leveraging quasi-Newton approximation techniques; and (III) Designing distributed second-order methods that outperform first-order algorithms both in terms of overall complexity (in convex settings) and in terms of quality of solution (in non-convex settings). This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.