CAREER: Embracing Local Minima and Nonsmoothness in Nonconvex Statistical Estimation: From Structures to Algorithms

职业：在非凸统计估计中拥抱局部极小值和非平滑性：从结构到算法

• 批准号: 2233152
• 负责人: Yudong Chen
• 金额: $ 54.28万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-10-01 至 2026-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2233152&HistoricalAwards=false
• 关键词: CAREER; Embracing; Local; Minima; Nonsmoothness

Optimization plays a crucial role in modern data analysis. Accurate modeling and robust analysis of complex datasets often require solving a class of optimization problems that are not smooth and may possess many low-quality solutions. These problems are challenging to solve, and there is limited understanding of the properties of solutions returned by standard algorithms. Existing approaches typically steer away from such problems or restrict to a small subset of them. This project aims to substantially broaden the class of problems for which efficient algorithms exist, and for which performance guarantees can be obtained. The project will develop new algorithms and analytical tools that are applicable in a broad range of engineering and science applications. Furthermore, the project will support an education plan that centers around the goal of bridging the disciplines of optimization and statistics at both undergraduate and graduate levels.The technical approaches of this project are based on the general principles of decoupling nonsmoothness and nonconvexity, and identifying the characteristic structures of locally optimal solutions. The research program consists of two main thrusts: (1) study a class of nonsmooth composite optimization problems and develop a framework for quantifying the average-case conditioning of the problems and the convergence rates of low-complexity algorithms; (2) consider a class of problems with coupled components, characterize the hidden structures of the local minima, and exploit these structural results to design and analyze efficient algorithms in settings where existing results fail to apply. The research in this project will cover a diverse set of important statistical and machine learning problems. The techniques developed will provide a refined analysis of the algorithmic performance for average-case problems in statistical 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.

优化在现代数据分析中起着至关重要的作用。复杂数据集的精确建模和鲁棒分析通常需要解决一类不光滑的优化问题，并且可能具有许多低质量的解。这些问题很难解决，而且人们对标准算法返回的解的性质了解有限。现有的方法通常会避开这些问题，或者只局限于其中的一小部分。该项目旨在实质性地扩大问题的类别，这些问题存在有效的算法，并且可以获得性能保证。该项目将开发适用于广泛工程和科学应用的新算法和分析工具。此外，该项目将支持一项教育计划，该计划的中心目标是在本科和研究生阶段架起优化和统计学学科的桥梁。本课题的技术方法是基于非光滑性和非凸性解耦的一般原理，识别局部最优解的特征结构。本研究主要包括两个方面的内容：(1)研究一类非光滑复合优化问题，并建立一个框架来量化问题的平均情况条件和低复杂度算法的收敛速度；(2)考虑一类具有耦合分量的问题，表征局部最小值的隐藏结构，并利用这些结构结果来设计和分析在现有结果不适用的情况下的有效算法。该项目的研究将涵盖一系列重要的统计和机器学习问题。所开发的技术将为统计设置中的平均情况问题的算法性能提供精细分析。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes

• DOI: 10.1145/3578338.3593526
• 发表时间: 2022-10
• 期刊: Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
• 作者: D. Huo;Yudong Chen;Qiaomin Xie

Low-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence

• DOI: 10.1007/s10208-020-09490-9
• 发表时间: 2021-01-28
• 期刊: FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
• 影响因子: 3
• 作者: Charisopoulos, Vasileios;Chen, Yudong;Drusvyatskiy, Dmitriy
• 通讯作者: Drusvyatskiy, Dmitriy

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

• 发表时间: 2020-02
• 作者: Qiaomin Xie;Yudong Chen;Zhaoran Wang;Zhuoran Yang

Clustering heterogeneous financial networks

集群异构金融网络

• DOI: 10.1111/mafi.12407
• 发表时间: 2023
• 期刊: Mathematical Finance
• 影响因子: 1.6
• 作者: Amini, Hamed;Chen, Yudong;Minca, Andreea;Qian, Xin
• 通讯作者: Qian, Xin

Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond

• DOI: 10.1109/tpami.2021.3097011
• 发表时间: 2022-10-01
• 期刊: IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
• 影响因子: 23.6
• 作者: Liu, Fanghui;Huang, Xiaolin;Suykens, Johan A. K.
• 通讯作者: Suykens, Johan A. K.