加速的随机方差减少优化方法及理论研究

In recent years, research on stochastic variance reduced optimization (e.g., SVRG) has made exciting progress. It has been proved that they can obtain much better oracle complexities than deterministic optimization methods. However, accelerated stochastic variance reduction algorithms (e.g., Katyusha) have complicated algorithm designs, which lead to a much higher per-iteration complexity. In this project, we will propose a simple momentum accelerated stochastic variance reduction gradient (ASVRG) algorithm. We also prove that ASVRG can attain the best-known convergence rates and oracle complexities, which are consistent with those of Katyusha. In particular, ASVRG has a much lower per-iteration complexity than Katyusha, thus it converges much faster than Katyusha in practice. For solving large-scale machine learning problems, we will also propose the first accelerated parallel asynchronous stochastic variance reduction algorithm. Since the proposed algorithm is a sparse, asynchronous, lock-free and parallel approach, its convergence analysis will be a challenging problem. Finally, we will propose the first momentum accelerated distributed stochastic variance reduced gradient algorithm, which can achieve nearly linear speedups, and is in some cases more than several orders of magnitude faster than other distributed algorithms. .The contributions of this project will not only enrich and develop the research for stochastic variance reduction optimization in theory and algorithms, but also provide theoretical support for stochastic optimization in the applications of engineering and science.

近年来，随机方差减少优化(如SVRG)取得了令人兴奋的进步，已证明了可获得比确定性方法更好的Oracle复杂度。然而，存在的加速算法(如Katyusha)一般都有较复杂的迭代形式，使得它们往往有较高的迭代复杂度。本课题将提出一种简单动量加速的随机方差减少算法，并证明可获得如Katyusha一样的理论收敛率和Oracle复杂度。特别是有比Katyusha低很多的迭代复杂度，所以提出算法的实际收敛速度比Katyusha快很多。为了求解大规模的机器学习问题，本课题还将提出第一种加速的稀疏异步平行算法。由于提出的并行算法采用无锁异步扰动的稀疏近似更新，所以其收敛性分析将是一个挑战性问题。最后，我们还将提出第一种加速的分布式随机方差减少算法，将获得接近线性的加速比，以及收敛速度有时会提高几个数量级。.本项目将丰富和发展随机方差减少算法的研究，也将为随机优化在工程科学中的应用提供理论支持。

随着互联网和硬件技术的快速发展，现在需要处理的数据规模在急剧增加，并且有着与日俱增的趋势。大规模的机器学习、深度学习及各种新的学习范式问题(例如连续学习、对抗学习、元学习、自动机器学习等问题)的规模也变得越来越大。特别是基于超参数学习的机器学习优化问题，不但包含大数据集训练大模型的问题，还有超参数的同步优化问题。传统的优化算法例如梯度下降法只能满足常规问题的求解，如线性回归。但当问题规模变得更大，普通的梯度下降法就会面临很多局限，特别在大规模机器学习问题的求解中，随机优化将占据着不可替代的地位。近年来，随着大数据带动下机器学习、计算机视觉、智能信号处理等人工智能领域的迅猛发展，大规模随机优化算法的研究变得更加重要。.该项目主要研究内容是应用于大规模机器学习的机器学习优化算法，包括无约束和等式约束的问题，也包括凸的和非凸的问题等。具体的研究内容包括如下：加速的随机方差减少梯度算法和随机方差减小梯度的ADMM算法及其算法理论分析研究；稀疏近似的快速随机方差减少梯度算法与其收敛性理论分析；异步扰动更新的加速随机方差减少梯度算法及收敛特性理论分析；分布式的加速随机方差减少梯度算法研究。.已在大规模机器学习随机优化算法及理论分析方面进行了深入的研究，例如无约束随机优化、等式约束随机优化、稀疏并行随机优化、联邦学习与分布式随机计算等。申请人完成了很多研究成果，提出了一系列创新思路、方法和理论框架等，发表/录用了30余篇高质量学术论文，其中中科院一区或CCF A类期刊（例如TPAMI、TNNLS、TIFS、TKDE等）论文15篇和CCF A类国际会议（例如ICML、NeurIPS、AAAI、IJCAI、ACM MM等）论文13篇。培养硕士7名，培养/联合培养博士3名。该项目的研究成极大地丰富和发展随机方差减少算法的研究，也将为随机优化在工程科学中的应用提供理论支持。例如我们提出了第一种加速的分布式随机方差减少算法，将获得接近线性的加速比，以及实际收敛速度可提高几个数量级。