“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。
地址：https://zhuanlan.zhihu.com/p/375082271
广义正则对偶平均(generalized regularized dual averaging (gRDA))算法是对正则对偶平均(RDA)算法的推广。迄今为止正则对偶平均算法在online学习、强化学习等方面已经得到了众多应用。假设我们收集到了独立同分布的数据 ，其中N表示所有可能的观测数目， 是我们所关心的未知参数，定义损失函数 ，则我们的目标是求解最优解 使得损失函数 达到最小，等价于求解方程 的根。一般我们可以选取 ，其中 表示损失函数 的梯度或者次梯度。随机梯度下降(SGD)算法是通过下述迭代过程近似 ：其中 表示步长。选择合适的步长对该优化算法的解路径起着至关重要的作用。在后面如无特别说明我们简单的用 表示 .尽管目前已经有很多文献研究了随机梯度下降算法，但当未知参数 自身存在某种结构时，随机梯度下降算法的效果并不能让人满意。为了解决这个问题，Xiao (2010) 提出了正则对偶平均(RDA)算法，其目的是通过如下迭代过程近似目标最优解：在RDA中， 表示累积梯度， 为常数， 是事先确定的严格凸的正则化函数，其作用是用来稳定迭代求解的过程，而 是惩罚函数，选取不同的惩罚函数可以求得不同结构的解。事实上RDA可以看作对两项进行交互迭代：通过极小化累积梯度的同时施加正则化函数 稳定求解过程，同时加入惩罚项 使得到解具有一定结构。如果我们令 ,则RDA就退化为SGD，因此我们可以将RDA看为SGD的一种推广，其既能保持SGD的优良性质，还解决了SGD无法处理具有系数结构参数的问题。最简单的情形，我们可以选取L1惩罚函数 ，Xiao (2010)已经证明在这种惩罚函数下可以得到稀疏解。尽管RDA目前已经得到了广泛应用，但是Chao & Cheng (2019) 证明了在某些重要的情形下，RDA得到的解太过于激进，容易导致有偏估计，这与SGD的结果相反。为了解决这个缺陷，Chao & Cheng (2019)经过仔细研究发现，在RDA中惩罚函数前的因子 是趋于无穷大的(尽管 是固定的数)，这一点导致了对于参数惩罚的太过激进，从而得到有偏估计。为了解决这个问题，Chao & Cheng (2019)提出了广义正则对偶平均（gRDA）算法，通过将RDA中惩罚函数的因子 表示为能够根据时间进行调整的tuning函数 。gRDA是通过迭代求解下述问题得到目标最优解的近似：其中 是确定的函数。很明显如果 则gRDA就转化为RDA。 是我们事先选取的初值，可以从均值为0的正态分布或均匀分布中随机选取。一般我们可以选取 ，其中 是超参数，需要通过数据驱动的方式选取最优的值，也可以事先给定； 表示算法终止后得到的解达到最优解 的某个小领域内所需时间的均值。 . Chao & Cheng (2019)通过一个数据例子表明在 时gRDA的效果不错，并且他们建议可以选取 . 下图是他们文章中根据上述选取的值或函数，对CIFAR-10图像分类数据的结果：当然，给出具体的理论结果来指导tuning函数 的选取是十分有必要的: 即tuning函数 满足什么条件时，利用gRDA算法得到的结果具有良好的性质(与最优解相差不大)。Chao & Cheng (2019)的主要贡献也正是对这一点进行了系统的理论研究。下面我们给出gRDA的随机镜像下降(stochastic mirror descent, SMD)的表示形式，这对gRDA的理论分析和求解上都很有效。定义如果假定 为凸函数， 为严格凸函数，并且这两个函数的是下半连续，则 是可微的，其导数为其中 . 通过上述两个式子，我们就可以迭代求解得到gRDA的解序列。最后，我们简单说一下 和 的一些常见选择。一般选取 为严格凸函数即可，常见的有 其中A为正定矩阵。而对于 ,一般选取为 的 范数，例如 等，当然还有其它的选择关于gRDA更多的细节大家可以阅读Chao & Cheng (2019)的文章，他们还给出了该算法的Python实现，GitHub链接为：https://github.com/donlan2710/gRDA-Optimizer.Xiao L. (2010) Dual averaging methods for regularized stochastic learning and online
optimization. Journal of Machine Learning Research, 11:2543–2596.Chao S. and Cheng G. (2019) A generalization of regularized dual averaging and its dynamics. arXiv: 1909.10072v1.
本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。
“强基固本”历史文章
更多强基固本专栏文章，
请点击文章底部“阅读原文”查看
分享、点赞、在看，给个三连击呗！