hiw3c 日报精选
arXiv cs.AI/CL/LG 网页快照

一种用于约束凸有限和优化的不精确随机方差降低梯度方法

原文标题 · An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

作者: Zhaosong Lu, Yifeng Xiao | 在本文中,我们研究一类约束性凸有限和优化问题。在许多实际应用中,所有或部分约束为硬约束,代表强制性要求。因此,任何理想的近似解必须(几乎)满足这些约束。基于这一动机,我们重点研究计算一个$ε$-确定性可行随机最优($ε$-SFSO)。

来源:arXiv cs.AI/CL/LG · arxiv.org

正文为英文,可一键机器翻译(仅首次需要等待)

Mathematics > Optimization and Control

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

Abstract: 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 $\epsilon$-$surely\ feasible\ stochastic\ optimal$ ($\epsilon$-SFSO) solution, in which the constraint violation is deterministically bounded by $\epsilon$, and the expected optimality gap is at most $\epsilon$. While a recently proposed stochastic variance-reduced first-order penalty method can compute an $\epsilon$-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an $\epsilon$-SFSO solution and that for computing an $\epsilon$-$expected\ feasible\ stochastic\ optimal$ solution, where both the expected constraint violation and the expected optimality gap are bounded by $\epsilon$. 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 $\epsilon$-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.

Submission history

Access Paper:

Current browse context:

References & Citations

BibTeX formatted citation

Bookmark

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .