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

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

基本信息

批准号：
2209509
负责人：
Petros Drineas
金额：
$ 29.87万
依托单位：
Purdue University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-10-01 至 2025-09-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2209509&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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查进行评估，被认为值得支持标准。

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Sublinear Time Eigenvalue Approximation via Random Sampling

通过随机采样的次线性时间特征值近似

DOI：
发表时间：
2023-01
期刊：
and Programming (ICALP 2023
影响因子：
0
作者：
Bhattacharjee, Rajarshi;Dexter, Gregory;Drineas, Petros;Musco, Cameron;Ray, Archan
通讯作者：
Ray, Archan

On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming

线性规划不精确预测校正方法的收敛性