AF: Small: Faster Algorithms for High-Dimensional Robust Statistics
AF:小:用于高维稳健统计的更快算法
基本信息
- 批准号:2122628
- 负责人:
- 金额:$ 39.1万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2022
- 资助国家:美国
- 起止时间:2022-01-01 至 2022-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
As machine learning plays a more prominent role in our society, there is a need for learning algorithms that are reliable and robust. In modern machine learning, one often needs to work with data that are high-dimensional and noisy. Recent work gave the first efficient robust estimators for several basic statistical problems, and since then, there has been a flurry of research that obtained efficient robust algorithms for many machine-learning problems. However, one major drawback of existing algorithms in the literature is that they tend to be much slower when compared to their non-robust counterparts, or they often involve parameters that require careful tuning. To address these issues, this project aims to (i) design faster and provably robust algorithms for a wide range of high-dimensional statistical and learning tasks, and (ii) explore non-convex formulations of robust estimation and analyze their optimization landscape. This project will advance the fields of computer science and statistics, and also potentially lead to useful tools for other areas. The pursuit of faster and simpler algorithms will help accelerate technology transfer into practice, stimulate systematic approaches to robustness, and provide a positive societal impact in the long run. The education plan of this project includes incorporating the materials generated from this project into graduate-level courses at the University of Illinois at Chicago (UIC), as well as training graduate and undergraduate students at UIC, which is an urban university with a diverse student population.Designing robust algorithms in high dimensions is a very challenging task. Even for the basic problem of mean estimation, when a small fraction of the input is adversarially corrupted, no efficient algorithms were known until recently. The first polynomial-time estimators with dimension-independent error guarantees were discovered in 2016. However, given the amount of data available today, polynomial-time no longer translates to scalability in practice. Motivated by the need for faster and more practical algorithms, this project focuses on two main thrusts to expand the area of algorithmic high-dimensional robust statistics. First, the investigator would like to speed up existing algorithms and develop new robust algorithms for a broader range of problems and richer families of distributions, with the ultimate goal of matching the runtime of the fastest non-robust algorithms. Second, the investigator wants to design robust estimators that can be computed via standard first-order optimization methods. The main challenge is to find an objective function whose gradient can be evaluated using basic matrix operations while proving the structural result that this objective has no bad local optima. Concretely, the investigator plans to work on these two thrusts by targeting various aspects of the following problems: (1) robust stochastic optimization, (2) robust sparse mean estimation and sparse PCA, (3) robust covariance estimation, (4) list-decodable learning, and (5) robust learning of Bayesian networks. This project is interdisciplinary and will rely on intuition and techniques from statistics, probability, linear algebra, discrete and continuous optimization, and non-convex optimization.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)探索鲁棒估计的非凸公式并分析其优化景观。该项目将推动计算机科学和统计学领域的发展,并可能为其他领域带来有用的工具。追求更快、更简单的算法将有助于加速技术转化为实践,刺激系统的鲁棒性方法,并从长远来看产生积极的社会影响。该项目的教育计划包括将该项目产生的材料纳入芝加哥(UIC)的研究生课程,以及在UIC培养研究生和本科生,UIC是一所拥有多元化学生群体的城市大学。即使对于均值估计的基本问题,当一小部分输入被逆向破坏时,直到最近才知道没有有效的算法。2016年发现了第一个具有维度无关误差保证的多项式时间估计器。然而,考虑到今天可用的数据量,多项式时间在实践中不再转化为可扩展性。出于对更快和更实用算法的需求,本项目侧重于两个主要的推力,以扩大算法的高维鲁棒统计领域。首先,研究人员希望加快现有算法的速度,并为更广泛的问题和更丰富的分布族开发新的鲁棒算法,最终目标是匹配最快的非鲁棒算法的运行时间。其次,研究者希望设计出可以通过标准的一阶优化方法计算的稳健估计量。主要的挑战是找到一个目标函数,其梯度可以使用基本矩阵运算进行评估,同时证明该目标没有坏的局部最优解的结构结果。 具体地说,研究者计划通过针对以下问题的各个方面来研究这两个方面:(1)鲁棒随机优化,(2)鲁棒稀疏均值估计和稀疏PCA,(3)鲁棒协方差估计,(4)列表可解码学习,以及(5)贝叶斯网络的鲁棒学习。该项目是跨学科的,将依赖于直觉和技术,从统计,概率,线性代数,离散和连续优化,和非凸优化。该奖项反映了NSF的法定使命,并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。
项目成果
期刊论文数量(3)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Outlier-Robust Sparse Estimation via Non-Convex Optimization
通过非凸优化的异常值稳健稀疏估计
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Cheng, Yu;Diakonikolas, Ilias;Ge, Rong;Gupta, Shivam;Kane, Daniel M.;Soltanolkotabi, Mahdi
- 通讯作者:Soltanolkotabi, Mahdi
Planning with Participation Constraints
具有参与约束的规划
- DOI:10.1609/aaai.v36i5.20462
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Zhang, Hanrui;Cheng, Yu;Conitzer, Vincent
- 通讯作者:Conitzer, Vincent
Efficient Algorithms for Planning with Participation Constraints
具有参与约束的规划的高效算法
- DOI:10.1145/3490486.3538280
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Zhang, Hanrui;Cheng, Yu;Conitzer, Vincent
- 通讯作者:Conitzer, Vincent
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Yu Cheng其他文献
Precision enhancement of three-dimensional displacement tracing for nano-fabrication based on low coherence interferometry
基于低相干干涉技术的纳米加工三维位移追踪精度提升
- DOI:
10.1364/oe.27.028324 - 发表时间:
2019 - 期刊:
- 影响因子:3.8
- 作者:
Yu Cheng;Xiangchao Zhang;He Yuan;Wei Wang;Min Xu - 通讯作者:
Min Xu
Anti-inflammatory effect of Yu-Ping-Feng-San via TGF-β1 signaling suppression in rat model of COPD
玉屏风散通过抑制 TGF-β1 信号传导抑制 COPD 大鼠模型的抗炎作用
- DOI:
- 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
Zhong-Shan Yang;Jin-Yuan Yan;Ni-Ping Han;Wei Zhou;Yu Cheng;Xiao-Mei Zhang;Ning Li;Jia-Li Yuan - 通讯作者:
Jia-Li Yuan
Preparation and catalytic performance of N-[(2-Hydroxy-3-trimethylammonium) propyl] chitosan chloride /Na2SiO3 polymer-based catalyst for biodiesel production
N-[(2-羟基-3-三甲基铵)丙基]氯化壳聚糖/Na2SiO3聚合物基生物柴油催化剂的制备及催化性能
- DOI:
10.1016/j.renene.2015.11.036 - 发表时间:
2016-04 - 期刊:
- 影响因子:8.7
- 作者:
BenQiao He;YiXuan Shao;JianXin Li;Yu Cheng - 通讯作者:
Yu Cheng
Object tracking in the complex environment based on SIFT
基于SIFT的复杂环境目标跟踪
- DOI:
10.1109/iccsn.2011.6014410 - 发表时间:
2011 - 期刊:
- 影响因子:0
- 作者:
Yu Cheng;Liu Yu;Zhang Jing;Yun Ting - 通讯作者:
Yun Ting
A Neutrophil-Inspired Supramolecular Nanogel for Magnetocaloric-Enzymatic Tandem Therapy
用于磁热酶串联疗法的中性粒细胞启发的超分子纳米凝胶
- DOI:
- 发表时间:
2020 - 期刊:
- 影响因子:0
- 作者:
Qi Zhang;Jiaojiao Wu;Jingjing Wang;Xia Wang;Chu Wu;Mengwei Chen;Qing Wu;Maciej S. Lesniak;Yongli Mi;Yu Cheng;Qigang Wang - 通讯作者:
Qigang Wang
Yu Cheng的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Yu Cheng', 18)}}的其他基金
AF: Small: Faster Algorithms for High-Dimensional Robust Statistics
AF:小:用于高维稳健统计的更快算法
- 批准号:
2307106 - 财政年份:2022
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
CNS Core: Small: Application-Oriented Scheduling for Optimizing Information Freshness in Wireless Networks
CNS 核心:小型:面向应用的调度,用于优化无线网络中的信息新鲜度
- 批准号:
2008092 - 财政年份:2020
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
Dynamic Multivariate Normative Comparison and Risk Screening for Alzheimer's Disease Progression
阿尔茨海默病进展的动态多变量规范比较和风险筛查
- 批准号:
1916001 - 财政年份:2019
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
NeTS: Small: Machine Learning Meets Wireless Network Optimization: Exploring the Latent Knowledge
NeTS:小型:机器学习遇见无线网络优化:探索潜在知识
- 批准号:
1816908 - 财政年份:2018
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
A Fundamental Study on Energy Efficient Wireless Communication Networks: Modeling, Algorithms, and Applications
节能无线通信网络的基础研究:建模、算法和应用
- 批准号:
1610874 - 财政年份:2016
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
NSF Student Travel Grant for 2016 IEEE Global Communications Conference (IEEE GLOBECOM)
2016 年 IEEE 全球通信会议 (IEEE GLOBECOM) 的 NSF 学生旅费补助
- 批准号:
1643335 - 财政年份:2016
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
NeTS: Small: Collaborative Research: Towards Reliable, Energy-Efficient, and Secure Vehicular Networks
NetS:小型:协作研究:迈向可靠、节能和安全的车辆网络
- 批准号:
1320736 - 财政年份:2014
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
Association, Regression and Diagnostic Accuracy Analyses of Competing Risks Data
竞争风险数据的关联、回归和诊断准确性分析
- 批准号:
1207711 - 财政年份:2012
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
TC: Small: Real-Time Intrusion Detection for VoIP over IEEE 802.11 Based Wireless Networks: An Analytical Approach for Guaranteed Performance
TC:小型:基于 IEEE 802.11 的无线网络的 VoIP 实时入侵检测:保证性能的分析方法
- 批准号:
1117687 - 财政年份:2012
- 资助金额:
$ 39.1万 - 项目类别:
Continuing Grant
CAREER: Exploring the Underexplored: A Fundamental Study of Optimal Resource Allocation and Low-Complexity Algorithms in Multi-Radio Multi-Channel Wireless Networks
职业:探索未开发领域:多无线电多通道无线网络中最优资源分配和低复杂度算法的基础研究
- 批准号:
1053777 - 财政年份:2011
- 资助金额:
$ 39.1万 - 项目类别:
Continuing Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
- 批准号:
2312089 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
NeTS: Small: NSF-DST: Modernizing Underground Mining Operations with Millimeter-Wave Imaging and Networking
NeTS:小型:NSF-DST:利用毫米波成像和网络实现地下采矿作业现代化
- 批准号:
2342833 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
CPS: Small: NSF-DST: Autonomous Operations of Multi-UAV Uncrewed Aerial Systems using Onboard Sensing to Monitor and Track Natural Disaster Events
CPS:小型:NSF-DST:使用机载传感监测和跟踪自然灾害事件的多无人机无人航空系统自主操作
- 批准号:
2343062 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
- 批准号:
2403559 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
オミックス解析を用いたブドウ球菌 small colony variants の包括的特徴づけ
使用组学分析全面表征葡萄球菌小菌落变体
- 批准号:
24K13443 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
- 批准号:
2332922 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
- 批准号:
2329908 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
- 批准号:
2331111 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331302 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331301 - 财政年份:2024
- 资助金额:
$ 39.1万 - 项目类别:
Standard Grant