https://scholars.lib.ntu.edu.tw/handle/123456789/635664
標題: | NEW FIRST-ORDER ALGORITHMS for STOCHASTIC VARIATIONAL INEQUALITIES | 作者: | KEVIN DOWHON HUANG Zhang, Shuzhong |
關鍵字: | minimax saddle-point | stochastic first-order method | variational inequality | zeroth-order method | 公開日期: | 1-十二月-2022 | 卷: | 32 | 期: | 4 | 來源出版物: | SIAM Journal on Optimization | 摘要: | In this paper, we propose two new solution schemes to solve the stochastic strongly monotone variational inequality (VI) problems: the stochastic extra-point solution scheme and the stochastic extra-momentum solution scheme. The first one is a general scheme based on updating the iterative sequence and an auxiliary extra-point sequence. In the case of a deterministic VI model, this approach includes several state-of-the-art first-order methods as its special cases. The second scheme combines two momentum-based directions: the so-called heavy-ball direction and the optimism direction, where only one projection per iteration is required in its updating process. We show that if the variance of the stochastic oracle is appropriately controlled, then both schemes can be made to achieve optimal iteration complexity of \scrO \bigl(\kappa ln \bigl(1\epsilon\bigr) \bigr) to reach an \epsilon -solution for a strongly monotone VI problem with condition number \kappa . As a specific application to stochastic VI, we demonstrate how to incorporate a zeroth-order approach for solving stochastic minimax saddle-point problems in our schemes, where only noisy and biased samples of the objective can be obtained, with a total sample complexity of \scrO \bigl(\kappa\epsilon\bigr) |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/635664 | ISSN: | 10526234 | DOI: | 10.1137/21M1441778 |
顯示於: | 工業工程學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。