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

机器学习和人工智能的快速成功对机器人、无线通信和传感器网络等多个领域产生了积极影响。这一成功主要是由于存储、计算能力、数据表示和算法方面的进步，这使得越来越丰富的数据集的力量得以利用。特别是，计算效率优化算法的进步在这一成功中发挥了至关重要的作用，因为现代机器学习和人工智能问题中的大多数任务都可以表述为优化程序。尽管取得了重大进展，但大多数现有的优化算法在应用于大规模机器学习中经常出现的病态问题时可能很慢。该项目提出了一个议程，以开发一类内存效率高、计算负担得起、分布式友好的二阶方法来解决现代机器学习问题。在教育方面，这个计划将为研究生和本科生提供一个刺激和创新的研究环境；它还将纳入德克萨斯大学奥斯汀分校课程教材的开发。目前用于大规模机器学习的优化算法有时效率低下，因为这些方法仅使用目标函数的一阶信息（梯度）进行操作。本项目旨在开发一类快速有效的二阶方法，利用目标函数的曲率信息来加速病态环境下的收敛。研究包括三个不同的重点：(1)开发具有可证明的快速收敛保证的内存高效增量拟牛顿方法；（II）利用准牛顿近似技术提高二阶自适应样本量算法的计算复杂度；（III）设计分布式二阶方法，在总体复杂性（凸设置）和解决方案质量（非凸设置）方面优于一阶算法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.