机器学习随机优化方法的个体收敛性研究

The stochastic optimization algorithm is one of the state-of-the-art methods for solving large-scale machine learning problems, where the focus is on whether or not the optimal convergence rate is derived and the learning structure is ensured. ..So far, various kinds of stochastic optimization algorithms have been presented for solving the regularized loss problems. However, most of them only discuss the convergence in terms of the averaged output, and even the simplest sparsity cannot be preserved. In contrast to the averaged output, the individual solution can keep the sparsity very well, and its optimal convergence rate is extensively explored as an open problem, but the individual convergence lacks stability in some algorithms. On the other hand, the commonly-used assumption about unbiased gradient in stochastic optimization often does not hold in practice. In such cases, an astonishing fact is that the bias in the convergence bound of accelerated algorithms will accumulate with the iteration, and this makes the accelerated algorithms inapplicable...In this project, the optimal individual convergence rate and its convergence stability in stochastic learning will be first investigated. Furthermore, in the biased gradient cases, the relationship between bias and individual convergence bounds will be discussed, and the strategy to reduce such bias will be explored. Moreover, the extension of individual convergence in non-convex problems will be considered. As a result, several algorithms with both optimal individual convergence rate and stability are expected, and some approximate answers to the open problem of individual convergence will be given.

随机优化方法是求解大规模机器学习问题的主流方法，其研究的焦点问题是算法是否达到最优收敛速率与能否保证学习问题的结构。..目前，人们已经对正则化损失函数问题得到了众多形式的随机优化算法，但绝大多数只是对迭代进行平均的输出方式讨论了收敛速率，甚至无法保证最为典型的稀疏结构。与之不同的是，个体解能很好保持稀疏性，其最优收敛速率已经作为open问题被广泛探索，但一些算法个体收敛缺乏稳定性。另外，随机优化普遍采用的梯度无偏假设往往是不成立的，令人惊讶的一个事实是加速方法收敛界中的偏差在有偏情形下会随迭代累积，从而无法应用。..本项目首先研究个体解的最优收敛速率及其稳定性，其次研究梯度有偏情形个体收敛界的偏差变化规律以及减少偏差的策略，还要进行在非凸学习问题中的拓广研究。期待得到一些既具有个体最优收敛速率又具有很好稳定性的算法，对个体收敛速率这一open问题给出若干比较接近的解答。

目前，人们已经对正则化损失函数问题得到了众多形式的随机优化算法，但绝大多数只是对迭代进行平均的输出方式讨论了收敛速率，甚至无法保证最为典型的稀疏结构。与之不同的是，个体解具有很好的稀疏性，其最优收敛速率已经作为open问题被广泛探索。..本项目主要围绕机器学习随机优化方法个体解的最优收敛性问题展开研究。在梯度下降方法的基础上，得到了一系列具有个体最优收敛速率的算法，对个体收敛性问题有了一些新认识和新发现，对2012年COLT会议上提出的个体收敛速率open问题给出了另一种的解答。..代表性成果如下：.（1）提出了一种求解l_{1,infinity}投影问题的高效计算方法，使其具有和l_1范数投影一样的计算代价。从计算的角度来说，这为l_{1,infinity}约束型学习问题个体解的稀疏性提供了理论保障。..（2）对于一般凸问题，提出了一种嵌入线性插值操作的投影次梯度方法，证明了其具有最优的个体收敛速率。其次，发现两种典型的动量方法（heavy-ball型和Nesterov型动量）可以与光滑情形时一样去加速收敛性，只不过对于非光滑凸优化问题的加速是关于个体收敛速率的，能使个体收敛速率达到最优并同时保证原有的平均收敛性不变。进一步，将所得结果拓广到约束和自适应的heavy-ball型动量方法。..（3）对于强凸优化问题，证明了Nesterov动量方法具有最优的个体收敛速率，并提出了几种融入投影次梯度方法的平均策略，均获得了个体收敛速率的最优性。这些算法对投影次梯度算法改动很小，但都成功去掉了投影次梯度方法最优个体收敛速率中的对数因子，获得了强凸问题的最优收敛性。..（4）在假设次梯度偏差有界的情况下，证明了Nesterov动量方法能获得稳定的个体收敛界，而当次梯度偏差按照一定速率衰减时，仍然可获得最优的个体收敛性。并且这一分析对我们提出的其它具有个体最优收敛性的算法也是适用的。..本项目共发表论文20篇，其中SCI检索10篇，EI检索18篇，包括中科院一区5篇和机器学习顶会3篇。项目所产生的成果已经被Google Scholar他引达40次以上，其中包括机器学习顶会COLT2019和顶刊IEEE TNNLS与IEEE TFS。因此，无论是从数量还是从质量和学术影响的角度来说，都圆满地完成了项目的目标。