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

CIF：小型：用于大规模学习的计算高效的二阶优化算法

• 批准号: 2007668
• 负责人: Aryan Mokhtari
• 金额: $ 50万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007668&HistoricalAwards=false
• 关键词: CIF; Small; Computationally; Efficient; Second

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.

机器学习和人工智能的快速成功对几个领域（例如机器人技术，无线通信和传感器网络）等数字产生了积极影响。这一成功主要是由于存储，计算能力，数据表示和算法的进步，这使得可以利用日益丰富的数据集的功能。特别是，计算高效优化算法的进步在这一成功中起着至关重要的作用，因为现代机器学习和人工智能问题中的大多数任务都可以作为优化程序提出。尽管取得了重大进展，大多数现有的优化算法将应用于大规模机器学习中经常出现的条件不足的问题时可能会很慢。该项目提出了一个议程，以开发一类记忆效率，计算负担得起和分布式友好的二阶方法，以解决现代机器学习问题。在教育方面，该项目将为研究生和本科生提供刺激性和创新的研究环境。它还将在德克萨斯大学奥斯汀分校的课程中开发课程的课程材料。大规模机器学习的当前优化算法有时效率低下，因为这些方法仅使用目标函数的一阶信息（梯度）运行。该项目旨在开发一类快速有效的二阶方法，以利用目标函数的曲率信息，以在不良条件的设置中加速收敛。该研究包括三种不同的推力：（i）开发具有可证明快速收敛保证的记忆有效增量准牛顿方法； （ii）通过利用准Newton近似技术来改善二阶自适应样本量算法的计算复杂性； （iii）设计分布的二阶方法，在整体复杂性（在凸面设置中）和解决方案质量方面（在非convex设置中）都超过了一阶算法。这一奖项反映了NSF的法定任务，并且认为通过基金会的知识优点和广泛的crietia crietia crietia crietia criperia criperia criperia criperia criperia criperia cristeria均值得通过评估。

项目成果

Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood

• 发表时间: 2022-02
• 作者: Qiujiang Jin;Alec Koppel;K. Rajawat;Aryan Mokhtari

Stochastic Quasi-Newton Methods

• DOI: 10.1109/jproc.2020.3023660
• 发表时间: 2020-09
• 期刊: Proceedings of the IEEE
• 影响因子: 20.6
• 作者: Aryan Mokhtari;Alejandro Ribeiro

High-Dimensional Nonconvex Stochastic Optimization by Doubly Stochastic Successive Convex Approximation

• DOI: 10.1109/tsp.2020.3033354
• 发表时间: 2020
• 期刊: IEEE Transactions on Signal Processing
• 影响因子: 5.4
• 作者: Aryan Mokhtari;Alec Koppel

Second-Order Optimality in Non-Convex Decentralized Optimization via Perturbed Gradient Tracking

• 发表时间: 2020
• 作者: Isidoros Tziotis;C. Caramanis;Aryan Mokhtari

Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach

• 发表时间: 2021-06
• 作者: Qiujiang Jin;Aryan Mokhtari