Exploiting Smooth Substructure in Non-Smooth Stochastic Optimization

在非光滑随机优化中利用光滑子结构

• 批准号: 2306322
• 负责人: Dmitriy Drusvyatskiy
• 金额: $ 30万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-15 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2306322&HistoricalAwards=false
• 关键词: Exploiting; Smooth; Substructure; Non; Stochastic

Recent years have seen an unprecedented growth of the use of large data sets in various high impact fields, such as signal processing, imaging, and artificial intelligence. The task of extracting useful information from vast amounts of data typically leads to solving large-scale optimization problems. The size of such problems poses a variety of challenges for computation and is the bottleneck for further progress in applications. The investigator aims to advance techniques of large-scale optimization, with applications throughout science and engineering. The resulting algorithms will enable discovery of trends and patterns in the observed data and will enable accurate predictions about unobserved data. The technical aspects of the project combine elements from a variety of mathematical and applied disciplines, and an effective mix of numerical experimentation, teaching, and discovery is central to the proposal. Graduate students and postdocs will participate in all aspects of the project.Statistical estimation, signal processing, and learning from data rely on solving challenging optimization problems that are large-scale, stochastic, nonsmooth, and often nonconvex. Despite such irregularity, the domains of typical optimization problems decompose into “active manifolds”, which common algorithms “identify” in finite time, thereby opening the door to second-order acceleration strategies. This project studies the stochastic subgradient method and its common variants, which power modern large-scale optimization, and its numerous applications in data science and engineering. The goal of the project is to investigate how the performance of influential stochastic algorithms benefit from active manifolds and to develop novel algorithms that exploit this structure. The strategy for achieving this goal will be based on a recently discovered family of regularity conditions---originating in stratification theory and semi-algebraic geometry---that have been shown to hold along active manifolds in concrete circumstances. Utilizing such regularity conditions for active manifolds, the investigator will develop new efficiency guarantees for the subgradient method, show that the algorithm converges only to local minimizers while bypassing all extraneous saddle points, and establish the asymptotic distribution of the stochastic gradient iterates. In parallel, the investigator will explore the use of noise injection to learn the tangent spaces to the active manifold in order to accelerate the algorithm. This approach is highly interdisciplinary, relying on techniques from nonsmooth optimization, statistics, probability, and semialgebraic geometry.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.

近年来，在各种高影响力领域，如信号处理、成像和人工智能，大数据集的使用出现了前所未有的增长。从大量数据中提取有用信息的任务通常会导致解决大规模优化问题。这类问题的规模对计算提出了各种挑战，也是应用进一步发展的瓶颈。研究人员的目标是推进大规模优化技术，在整个科学和工程中应用。由此产生的算法将能够发现观测数据中的趋势和模式，并能够准确预测未观测数据。该项目的技术方面联合收割机元素从各种数学和应用学科，和数值实验，教学和发现的有效组合是中央的建议。研究生和博士后将参与项目的各个方面。统计估计，信号处理和从数据中学习依赖于解决具有挑战性的优化问题，这些问题是大规模的，随机的，非光滑的，通常是非凸的。尽管有这种不规则性，典型的优化问题的域分解成“活动流形”，常见的算法在有限的时间内“识别”，从而打开了二阶加速策略的大门。该项目研究了随机次梯度方法及其常见变体，这些变体为现代大规模优化提供了动力，以及它在数据科学和工程中的众多应用。该项目的目标是研究有影响力的随机算法的性能如何从活动流形中受益，并开发利用这种结构的新算法。实现这一目标的战略将是基于最近发现的家庭的规律性条件-起源于分层理论和半代数几何-已被证明持有沿着积极的流形在具体情况下。利用活动流形的这种正则性条件，研究人员将为次梯度方法开发新的效率保证，证明该算法仅收敛于局部极小值，同时绕过所有无关的鞍点，并建立随机梯度迭代的渐进分布。 同时，研究人员将探索使用噪声注入来学习活动流形的切空间，以加速算法。该方法是高度跨学科的，依赖于非光滑优化，统计，概率和半代数几何的技术。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。