Beyond With-replacement Sampling for Large-Scale Data Analysis and Optimization

超越大规模数据分析和优化的替换采样

基本信息

批准号：
1723085
负责人：
Mert Gurbuzbalaban
金额：
$ 12.5万
依托单位：
Rutgers University Newark
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-07-15 至 2020-12-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1723085&HistoricalAwards=false
关键词：
Beyond replacement Sampling Large Scale

项目摘要

Advances in sensing and processing technologies, communication capabilities and smart devices have enabled deployment of systems where a massive amount of data is collected to make decisions. Many key problems of interest for analyzing and processing big data result in large-scale optimization problems. For a core, very widely used optimization method, which is efficient for such problems where the data points are sampled and processed in a sequential manner, there is a large gap between the theory and practice of this method. This project is about filling this gap by providing novel performance guarantees relevant to practical problems as well as developing novel and faster variants of the optimization method. The methods and techniques developed under the scope of this project will contribute to the efficiency and mathematical foundations of optimization algorithms targeted for big data challenges, contributing to more efficient decision making for a wide variety of large-scale data analysis problems. Incremental gradient (IG) is the core, very widely used optimization method mentioned above and subsumes popular optimization methods in data analysis and machine learning practice such as stochastic gradient descent, randomized coordinate descent and Kaczmarz methods. Various performance guarantees for IG are available if data points are sampled with replacement in an independent identically distributed (i.i.d.) manner. However, these are not helpful in practical scenarios: In practice, data is often sampled in a non-i.i.d fashion without-replacement instead, as the resulting convergence is typically much faster. A first goal in this project is to study and quantify this discrepancy over an interesting class of regression problems, which has been a key open problem. Several techniques and methods are proposed for obtaining asymptotic and non-asymptotic theoretical guarantees for without-replacement sampling schemes. A second goal is to develop fast algorithms with convergence guarantees that go beyond the limitations of the i.i.d. sampling. For this purpose, a new framework for studying several alternative sampling schemes and their performance is developed. Using this framework, novel sampling schemes based on weighted without-replacement sampling and cyclic sampling that can adapt to the dataset and improve upon the performance of the traditional i.i.d. sampling in terms of limiting accuracy are developed.

传感和处理技术、通信能力和智能设备的进步使得能够部署收集大量数据以做出决策的系统。分析和处理大数据的许多关键问题都会导致大规模优化问题。对于一种应用非常广泛的核心优化方法来说，该方法对于以顺序方式采样和处理数据点的问题是有效的，但该方法的理论与实践之间存在很大差距。该项目旨在通过提供与实际问题相关的新颖性能保证以及开发新颖且更快的优化方法变体来填补这一空白。在该项目范围内开发的方法和技术将有助于提高针对大数据挑战的优化算法的效率和数学基础，有助于针对各种大规模数据分析问题做出更有效的决策。增量梯度（IG）是上述优化方法的核心，应用非常广泛，它包含了数据分析和机器学习实践中流行的优化方法，例如随机梯度下降、随机坐标下降和 Kaczmarz 方法。如果以独立同分布 (i.i.d.) 方式对数据点进行替换采样，则 IG 的各种性能保证是可用的。然而，这些在实际场景中没有帮助：在实践中，数据通常以非独立同分布的方式进行采样，而不进行替换，因为由此产生的收敛通常要快得多。该项目的第一个目标是研究和量化一类有趣的回归问题的差异，这一直是一个关键的开放问题。提出了几种技术和方法来获得无放回采样方案的渐近和非渐近理论保证。第二个目标是开发具有收敛保证的快速算法，超越独立同分布的限制。采样。为此，开发了一个用于研究几种替代抽样方案及其性能的新框架。使用该框架，基于加权无替换采样和循环采样的新颖采样方案可以适应数据集并改进传统独立同分布的性能。开发了限制精度采样。

项目成果

期刊论文数量（18）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Universally Optimal Multistage Accelerated Stochastic Gradient Method

通用最优多级加速随机梯度法

DOI：
发表时间：
2020-05
期刊：
Advances in neural information processing systems
影响因子：
0
作者：
Aybat, N;Fallah, A;Gurbuzbalaban, M;Ozdaglar, A.
通讯作者：
Ozdaglar, A.

Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise

分数欠阻尼 Langevin 动力学：在重尾梯度噪声下利用动量重新定位 SGD

DOI：
发表时间：
2020-01
期刊：
Proceedings of Machine Learning Research
影响因子：
0
作者：
Umut Simsekli; Lingjiong Zhu
通讯作者：
Lingjiong Zhu

Randomness and permutations in coordinate descent methods

坐标下降方法中的随机性和排列

DOI：
10.1007/s10107-019-01438-4
发表时间：
2018-03-22
期刊：
Mathematical Programming
影响因子：
2.7
作者：
Mert Gurbuzbalaban;A. Ozdaglar;N. D. Vanli;Stephen J. Wright
通讯作者：
Stephen J. Wright

IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method

IDEAL：不精确分散加速增强拉格朗日方法

DOI：
发表时间：
2020-06-11
期刊：
ArXiv
影响因子：
0
作者：
Yossi Arjevani;Joan Bruna;Bugra Can;M. Gürbüzbalaban;S. Jegelka;Hongzhou Lin
通讯作者：
Hongzhou Lin

Reducing Communication in Proximal Newton Methods for Sparse Least Squares Problems

减少稀疏最小二乘问题的近邻牛顿法中的通信

DOI：
10.1145/3225058.3225131
发表时间：
2018-08
期刊：
ICPP 2018 Proceedings of the 47th International Conference on Parallel Processing
影响因子：
0
作者：
Soori, Saeed;Devarakonda, Aditya;Blanco, Zachary;Demmel, James;Gurbuzbalaban, Mert;Dehnavi, Maryam Mehri
通讯作者：
Dehnavi, Maryam Mehri

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

Mert Gurbuzbalaban其他文献

Decentralized Computation of Effective Resistances and Acceleration of Distributed Optimization Algorithms.

有效阻力的分散计算和分布式优化算法的加速。

DOI：
发表时间：
2019-07-29
期刊：
arXiv: Optimization and Control
影响因子：
0
作者：
Bugra Can;Saeed Soori;N. Aybat;Maryam Mehri Dehvani;Mert Gurbuzbalaban
通讯作者：
Mert Gurbuzbalaban

Heavy-Tail Phenomenon in Decentralized SGD

去中心化 SGD 中的重尾现象

DOI：
10.48550/arxiv.2205.06689
发表时间：
2022-05-13
期刊：
ArXiv
影响因子：
0
作者：
Mert Gurbuzbalaban;Yuanhan Hu;Umut Simsekli;K. Yuan;Lingjiong Zhu
通讯作者：
Lingjiong Zhu

Fractional moment-preserving initialization schemes for training deep neural networks

用于训练深度神经网络的分数矩保持初始化方案

DOI：
发表时间：
2021-01
期刊：
Proceedings of Machine Learning Research
影响因子：
0
作者：
Mert Gurbuzbalaban; Yuanhan Hu
通讯作者：
Yuanhan Hu

Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms

随机优化算法的分形结构和泛化性质

DOI：
10.1007/s11771-016-3396-2
发表时间：
2021-06-09
期刊：
Journal of Central South University
影响因子：
4.4
作者：
A. Camuto;George Deligiannidis;Murat A. Erdogdu;Mert Gurbuzbalaban;Umut cSimcsekli;Lingjiong Zhu
通讯作者：
Lingjiong Zhu