Papers

非精确SVRG方法改进约束凸优化的可行性复杂度界

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

Why we picked it

搞优化的朋友可以看看这篇:新的非精确 SVRG 方法把硬约束下 ε-SFSO 解的一阶 oracle 复杂度推到了新低。约束梯度和锥投影便宜的场景下,它比现有方法更快,做凸锥优化的研究者和工程团队都用得上。

一篇新论文研究带硬约束的约束凸有限和优化问题,目标是计算 ε-SFSO 解:约束违反被确定性地控制在 ε 以内,同时期望最优性间隙不超过 ε。此前已有的随机方差缩减一阶罚函数方法可以求解 ε-SFSO 解,但其一阶 oracle 复杂度与求解 ε-EFSO 解(期望约束违反和期望间隙均不超过 ε)的复杂度之间存在明显差距。

Body

论文提出一种非精确随机方差缩减梯度(SVRG)方法,显著改进了计算 ε-SFSO 解的此前最优一阶 oracle 复杂度。当目标函数为单一函数时,该方法退化为一种新的确定性一阶方法,用于标准凸锥优化,在目标函数梯度评估复杂度上明显低于现有方法。

在计算约束梯度和向锥投影的代价低于评估目标梯度的场景下,新方法可以胜过现有方法。论文附有初步数值实验结果验证方法性能。

Original · arXiv cs.LG

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

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\ feasible\ stochastic\ optimal$ solution, where both the expected constraint violation and the expected optimality gap are bounded by $ε$. To narrow this gap, we propose an inexact stochastic variance-reduced gradient (SVRG) method that significantly improves the previously best-known first-order oracle complexity for computing an $ε$-SFSO solution. Furthermore, when the objective consists of a single function, the proposed method reduces to a novel deterministic first-order method for solving standard convex conic optimization. It achieves a significantly lower gradient evaluation complexity with respect to the objective function compared to existing methods, and can outperform them when computing constraint gradients and projections onto the associated cone is cheaper than evaluating the objective gradient. Preliminary numerical results are presented to illustrate the performance of the proposed method.

Industry Coordinates & Source Verification

This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include SVRG, convex optimization, stochastic optimization.

Source attribution: curated from arXiv cs.LG (@Zhaosong Lu, Yifeng Xiao).