无参数随机优化有多自由？
内容提要
该文综述随机优化算法，涵盖无导数算法、1范数正则化、凸与非凸随机优化、核随机梯度下降、局部复杂度度量、非光滑非凸正则化、约束随机复合优化及亚指数噪声在线凸优化，分析收敛速度与查询复杂度，提出多种高效算法并验证性能。
延伸解读
无导数优化的查询复杂度
文章指出，在无梯度信息的凸随机优化中，强凸平滑函数和非凸平滑函数所需的查询次数至少满足二次比例关系。这意味着无导数方法在查询复杂度上存在固有下界，但同时也发现，对于二次函数，即使没有梯度信息，也能在平方次询问内达到O(1/T)的误差率，这为无导数优化提供了理论上的效率保证。
非凸非光滑优化的算法进展
针对非凸非光滑的有限和问题，文章提出了快速随机算法，可获得常数迷你批量的收敛性，并证明其比批量近端梯度下降更快。此外，对于非光滑非凸正则化下的平滑非凸损失，提出的两种随机梯度算法在收敛复杂度上优于现有技术，并在经验风险最小化中比较了实际表现。
约束随机复合优化的新框架
文章提出了一种随机梯度框架，用于解决具有无限线性包含约束的随机复合凸优化问题。该框架使用平滑和同伦技术处理约束，无需矩阵投影，数值实验表明其达到了最先进的实用性能。这为处理复杂约束的随机优化问题提供了新思路。
在线凸优化与亚指数噪声
针对涉及亚指数噪声的无约束在线凸优化问题，文章设计了参数自由的BANCO算法，并证明其具有最优性能。该算法被应用于局部随机梯度下降和多次对数定律，展示了在噪声环境下的适应性和理论保证，为在线学习场景提供了有效工具。
Q&A
无导数随机优化在强凸平滑和非凸平滑函数上的查询复杂度下界是什么？
对于强凸平滑函数和非凸平滑函数，所需的查询次数至少要实现二次比例尺度关系。
对于二次函数，无梯度信息的随机优化能达到怎样的误差率？
即使没有梯度信息，也可以在平方次的询问内实现 O(1/T) 的误差率。
基于核的随机梯度下降算法有什么特点？
该算法在训练过程中进行模型选择，不需任何形式的交叉验证或参数调整，并利用在线学习理论在数据相关性方面进行正则化的估计，证明了标准光滑性假设下的最优收敛速度。
针对非凸非光滑有限和问题，提出的快速随机算法有什么优势？
该算法可获得常数迷你批量的收敛性，其变种比批量近端梯度下降更快，并在非凸非光滑函数的一个子类中证明全局线性收敛率。
随机凸优化中的局部复杂度度量是什么？
局部复杂度度量是针对随机凸优化问题提出的，给出了与优化固有几何概念相对应的统计难度的收敛结果，并基于Nesterov的对偶平均方法和Riemannian方法开发出完全在线的适应性最优收敛算法。
BANCO算法用于解决什么类型的问题？
BANCO算法用于解决涉及亚指数噪声的无约束在线凸优化问题，是一种巴拿赫空间参数自由OCO算法，具有最优的性能表现，并应用于局部随机梯度下降算法以及多次对数定律的应用。
