← 研踪 PaperTrailarXiv:2611.23221 · v1
An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization
首次提交 2026-11-18 02:57
版本更新 2026-11-18 02:57
雷达观测 2026-11-18 12:34
摘要
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 - (-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 - 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.
作者备注:Accepted by SIAM Journal on Optimization
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 02:57 · 最新观测版本
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 - (-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 - 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.
查看此版本解读 →查看此版本原文 ↗