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.

近年来，在各种高影响场（例如信号处理，成像和人工智能）中使用大型数据集的使用前所未有。从大量数据中提取有用信息的任务通常导致解决大规模优化问题。此类问题的大小构成了各种计算挑战，是用于进一步进展的瓶颈。研究人员旨在推进大规模优化的技术，并在整个科学和工程中进行应用。所得的算法将在观察到的数据中发现趋势和模式，并可以对未观察到的数据进行准确的预测。该项目的技术方面结合了各种数学和应用学科的要素，以及数值实验，教学和发现的有效组合是该建议的核心。研究生和博士后将参与项目的各个方面。统计学上的估计，信号处理和从数据中学习取决于解决挑战优化问题，这些问题是大规模，随机，非平滑且通常是非convex的。尽管存在这种不规则性，但典型优化问题的领域仍将其分解为“主动流形”，这些算法在有限的时间内“识别”了常见的算法，从而打开了二阶加速策略的大门。该项目研究了随机亚级别方法及其常见变体，这些变体能力现代大规模优化及其在数据科学和工程中的众多应用。该项目的目的是研究有影响力的随机算法的性能如何受益于主动流形，并开发利用这种结构的新型算法。实现这一目标的策略将基于最近发现的规律性条件的家族 - 在分层理论和半代数几何形状中阐明，这些几何形状已被证明在具体情况下沿着主动歧管持续存在。利用这种规律性条件为主动流形，研究者将为亚级别方法开发新的效率保证，表明该算法仅收敛于局部最小化器，同时绕过所有外部鞍点，并确定随机梯度迭代率的不对称分布。同时，研究者将探索使用噪声注入的使用，以学习到活动歧管上的切线空间，以加速算法。这种方法是高度跨学科的，依赖于非平滑优化，统计，概率和血清几何形状的技术。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子优点和更广泛的影响审查标准的评估来评估。