基于随机线搜索的过参数化模型优化的收敛条件
内容提要
本文提出了一种结合确定性方法与贝叶斯优化的概率线性搜索算法，利用高斯过程代理优化目标，消除了随机梯度下降学习率的定义。研究了多种算法的收敛性与复杂度，展示了在非凸问题中实现线性收敛率的有效性，并提出了新算法 AdaSPS 和 AdaSLS，以改进超参数化模型的训练效果。
延伸解读
概率线搜索如何消除学习率依赖
文章提出用高斯过程代理目标函数，并基于Wolf条件的概率信念监控下降，从而构建概率线搜索算法。这种方法直接处理随机梯度，不再需要手动定义SGD的学习率，为随机优化提供了一种自适应步长机制。
过参数化模型下SGD的指数收敛条件
对于过参数化模型，当损失函数为凸或满足Polyak-Lojasiewicz条件时，常数步长SGD可实现指数收敛。这一结论表明，在特定非凸函数类中，SGD也能获得快速收敛，但依赖于损失函数的几何性质。
AdaSPS与AdaSLS：非插值设置下的收敛保证
新算法AdaSPS和AdaSLS结合随机Polyak步长与随机线搜索，在非插值设置下保证收敛，并维持凸和强凸函数的次线性与线性收敛速度。引入方差缩减后，梯度评估达到O(ε)次优性，改进了原有O(1/ε^2)的收敛速度。
线搜索方法的复杂度与确定性方法相当
基于随机一阶模型和方向的线搜索方法，其评估复杂度与使用确定性精确模型的对应方法相同，仅增加一个依赖于概率模型质量的常数。这意味着概率模型并未显著增加计算负担，保持了实际可行性。
Q&A
什么是概率线性搜索算法？
概率线性搜索算法结合了确定性方法与贝叶斯优化，使用高斯过程代理优化目标，消除了对随机梯度下降学习率的定义。
AdaSPS 和 AdaSLS 有什么特点？
AdaSPS 和 AdaSLS 是新提出的算法，保证在非插值设置下的收敛，并改进了超参数化模型的训练效果。
如何实现随机梯度下降的确定性收敛率？
通过使用线性搜索技术自动设置步长的随机梯度下降算法，可以实现凸和强凸函数的确定性收敛率。
该研究如何评估算法的收敛速度？
研究展示了基于随机一阶模型的线搜索方法的全局收敛速度，并评估了其复杂度与确定性模型相同。
引入方差缩减技术有什么好处？
方差缩减技术改进了非插值区域的收敛速度，达到了 O（ε）次优性，提升了算法的效率。
随机梯度下降在大型过度参数化模型中的表现如何？
在大型过度参数化模型中，常数步长下的随机梯度下降可以实现指数收敛，尤其在损失函数为凸函数时。
