Exploiting Smooth Substructure in Non-Smooth Stochastic Optimization

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

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.