提出优化算法的通用不等式框架,统一分析迭代优化的正则化效应。
Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis
- 构建基于步长与距离的通用不等式,连接显式与隐式正则化。
- 将迭代次数转化为损失函数中的有效正则化系数。
- 适用于梯度下降、镜面下降及随机预测器,适合统计学习理论研究者。
我们为一阶迭代优化算法引入了‘基本不等式’,构建了一个简洁且通用的框架,用于连接隐式与显式正则化。设目标函数为 $f$,算法从初始点 $θ_0$ 出发,经过 $T$ 步迭代得到当前点 $θ_T$,该不等式以累积步长和 $θ_0$、$θ_T$、参考点 $z$ 之间的距离为变量,上界 $f(θ_T) - f(z)$。该边界将迭代次数转化为损失函数中的有效正则化系数。通过该框架,我们分析了训练动态与预测风险边界。在重新审视并改进梯度下降已有结果的基础上,进一步给出了基于Bregman散度投影的镜面下降、梯度下降与指数梯度下降训练广义线性模型,以及随机预测器的新结论。实验部分对广义线性模型进行了补充验证。
原文摘要 · Abstract (English)
We introduce \textit{basic inequalities} for first-order iterative optimization algorithms, forming a simple and versatile framework that connects implicit and explicit regularization. While related inequalities appear in the literature, we isolate and highlight a specific form and develop it as a well-rounded tool for statistical analysis. Let $f$ denote the objective function to be optimized. Given a first-order iterative algorithm initialized at $θ_0$ with current iterate $θ_T$, the basic inequality upper bounds $f(θ_T)-f(z)$ for any reference point $z$ in terms of the accumulated step sizes and the distances between $θ_0$, $θ_T$, and $z$. The bound translates the number of iterations into an effective regularization coefficient in the loss function. We demonstrate this framework through analyses of training dynamics and prediction risk bounds. In addition to revisiting and refining known results on gradient descent, we provide new results for mirror descent with Bregman divergence projection, for generalized linear models trained by gradient descent and exponentiated gradient descent, and for randomized predictors. We illustrate and supplement these theoretical findings with experiments on generalized linear models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。