[论文] An inexact stochastic variance-reduced gradient method for constrained...
研究领域: ML 作者: Zhaosong Lu, Yifeng Xiao 发布时间: 2026-11-17 arXiv: 2611.23221
论文概要
研究领域: ML 作者: Zhaosong Lu, Yifeng Xiao 发布时间: 2026-11-17 arXiv: 2611.23221
中文摘要
本文研究带约束的凸有限和优化问题。许多实际应用中,约束为必须满足的硬约束,因此理想近似解必须(几乎)满足全部约束。我们关注计算 ε-确定性可行随机最优(ε-SFSO)解:约束违反确定性有界于 ε,期望最优间隙至多为 ε。现有随机方差缩减一阶惩罚方法可计算 ε-SFSO 解,但其复杂度与 ε-期望可行解之间仍有显著差距。我们提出不精确随机方差缩减梯度(SVRG)方法,显著改进了计算 ε-SFSO 解的最优一阶预言机复杂度。当初始函数为单一函数时,该方法退化为一种新颖的确定性一阶方法,梯度评估复杂度显著低于现有方法。
原文摘要
In this paper, we study a class of constrained convex finite-sum optimization problems. In many practical applications, all or some of the constraints are hard constraints that represent imperative requirements. Consequently, any desirable approximate solution must (nearly) satisfy these constraints. Motivated by this, we focus on computing an \(ε\)-\(surely\ feasible\ stochastic\ optimal\) (\(ε\)-SFSO) solution, in which the constraint violation is deterministically bounded by \(ε\), and the expected optimality gap is at most \(ε\). While a recently proposed stochastic variance-reduced first-order penalty method can compute an \(ε\)-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an \(ε\)-SFSO solution and that for computing an \(ε\)-$expected\ feasi...
*自动采集于 2026-11-19*
#论文 #arXiv #ML #小凯