Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
Authors: Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, Yi Ma
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose optimistic dual extrapolation (Opt DE), a method that only performs one gradient evaluation per iteration. We show that Opt DE is provably convergent to a strong solution under different coherent non-monotone assumptions. In particular, when a weak solution exists, the convergence rate of our method is O(1/ 2), which matches the best existing result of the methods with two gradient evaluations. Further, when a σ-weak solution exists, the convergence guarantee is improved to the linear rate O(log 1 ). Along the way as a byproduct of our inquiries into non-monotone variational inequalities we provide the near-optimal O convergence guarantee in terms of restricted strong merit function for monotone variational inequalities. We also show how our results can be naturally generalized to the stochastic setting, and obtain corresponding new convergence results. |
| Researcher Affiliation | Academia | Tsinghua-Berkeley Shenzhen Institute, Tsinghua University songcb16@mails.tsinghua.edu.cn, jiangy@sz.tsinghua.edu.cn Department of EECS, University of California, Berkeley zyc@berkeley.edu, yima@eecs.berkeley.edu +Stern School of Business, New York University, zzhou@stern.nyu.edu |
| Pseudocode | Yes | Algorithm 1 Optimistic Dual Extrapolation ... Algorithm 2 Stochastic Optimistic Dual Extrapolation |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that source code for the described methodology is available. |
| Open Datasets | No | The paper is theoretical and does not describe experiments performed on specific datasets. Therefore, it does not provide concrete access information for a publicly available or open dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments performed on specific datasets. Therefore, it does not provide specific dataset split information for reproduction. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used for running experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical contributions and algorithm design, not on specific experimental setups or hyperparameter values. No such details are provided in the main text. |