NSF-BSF: AF: Collaborative Research: Small: Randomized preconditioning of iterative processes: Theory and practice

NSF-BSF：AF：协作研究：小型：迭代过程的随机预处理：理论与实践

基本信息

批准号：
2209510
负责人：
Ilse C.F. Ipsen
金额：
$ 30万
依托单位：
North Carolina State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-10-01 至 2025-09-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2209510&HistoricalAwards=false
关键词：
NSF BSF AF Collaborative Research

项目摘要

A simple way to predict the long-term movement of your stock portfolio is to graph the daily prices tracked over the past several months, and then fit a line through the graph. The slope of the line can help to predict whether the trend is for prices to increase or to decrease. This is the most basic version of a so-called `regression problem'. Regression problems, in more sophisticated forms, are mainstays in a multitude of areas, including finance, statistics, science, genetics, and engineering; and their fast solution is a must when it comes to timely diagnoses and prediction of events. The project aims to speed up the solution of regression problems through accelerators (called 'preconditioners'). The accelerators are set up very fast, by picking and choosing a few pieces at 'random' from the original problem: Think of throwing dice to determine what to pick next. Although this may sound haphazard, it is efficient because regression problems tend to have a lot of redundancy and repetition, making it difficult to miss an important piece. In addition, this is a safe way of accelerating regression problems: On the off-chance that the randomization should produce somewhat inefficient accelerators, we are still ok: The accelerator is slower, but we are still solving the original problem --just not quite as fast as expected. The project involves the design and analysis of accelerators for speeding up regression problems in a variety of practical settings, with particular attention to human genetics.Linear least squares/regression problems are of primary importance in many computational sciences, either standalone on their own or as part of a sequence in the outer iterations of an optimization method. The project involves accelerating the solution of regression problems via `dynamic' randomized preconditioners that can either change across inner iterations of a solver or else change across least squares problems in outer iterations of an optimization method. Specific optimization methods to be investigated include: (i) iteratively reweighted least squares for solving generalized linear models; (ii) interior point methods for linear programs; (iii) nonlinear least squares for training overparameterized neural networks; and (iv) high-order order orthogonal iteration for computing low-rank tensor decompositions. The project will impact many domains and pay particular attention to human genetics. The effectiveness of the methods will be validated on standard test suites, as well as large-scale matrices from the UK Biobank dataset.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）线性程序的内点方法；（iii）训练过度参数化神经网络的非线性最小二乘；（iv）用于计算低量张量分解的高阶正交迭代。该项目将影响许多领域，并特别关注人类遗传学。这些方法的有效性将在标准测试套件以及英国生物银行数据集的大规模矩阵上进行验证。该奖项反映了NSF的法定任务，并被认为是通过基金会的智力优点和更广泛影响的评估标准通过评估来获得支持的。