Variance-Reduced Forward-Reflected Algorithms for Generalized Equations

The authors said, "Alacaoglu & Malitsky (2021); Beznosikov et al. (2023); Gorbunov et al. (2022a); Loizou et al. (2021) claim an oracle complexity of $O(n+ \sqrt{n} \epsilon^{-2})$ to attain an $\epsilon$ solution, but this is measured using a restricted gap function. Again, as highlighted in Cai et al. (2023); Diakonikolas (2020), this certification does not translate to the operator residual norm and is inapplicable to nonmonotone settings." However, it seems that [1] has proved the result of $O(n+ \sqrt{n } \epsilon^{-1})$ using SVRG-type algorithm for operator residual norm. How could the results in this work be competitive in that in [1]?

The authors said "However, varying parameters or incorporating double loop/inexact methods in [1] must be used to achieve improved theoretical oracle complexity. We believe that such approaches may be challenging to select parameters and to implement in practice." However, the experiments in this paper are quite weak (a synthetic experiment and a real-world experiment on logistic regression). If the proposed methods have a worse dependency on both $n$ and $\epsilon$, but the authors still claim their methods are practical, maybe they should conduct a lot of large-scale experiments to support their claim, such as GAN and adversarial training in neural networks.

[1] Cai, Xufeng, Ahmet Alacaoglu, and Jelena Diakonikolas. "Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions." The Twelfth International Conference on Learning Representations.

It seems like there are primarily two contributions over variance reduction methods for monotone problems regarding the complexity:

• The guarantee is provided in terms of the norm of the operator (of the best iterate) instead of the gap (of the averaged iterate).
• The guarantees extend to some range of weak MVIs (so beyond monotone problems)

W.1 Considering this, the main concern is that the allowed range of the parameter $\kappa$ controlling the nonmonontonicity can be restrictive and that this is not discussed in sufficient detail. Take for instance Thm. 3.1 where $\kappa \leq \mathcal O(\sqrt{\rho}/L)$:

• In the case of SAGA we have $\rho =b/(2n) \leq 1/(2n^{1/3})$ (Cor. C.2)
• in the case of SVRG we have $\rho =p/2 =1/(2n^{1/3})$ (Cor. C.1)

In either case $\kappa \leq \mathcal O (1/(Ln^{1/6}))$, so the nonmonotonicity parameter scales inversely with $n$. Additionally, the Lipschitz-averaged constant can be much larger than the Lipschitz constant ($n$-dependent). I found it very hard to parse whether there are any other dependencies on $n$, through e.g. the stepsize requirement ($\eta$) in Thm 3.1, which depends on $C$ defined in Def. 2.1, while explicitly stated in Lem. 2.1, which contains again $\rho$ through $p$. It would be very helpful if the authors could explicitly spell out the dependency. The range of $\kappa$ is particularly important considering that even extragradient and optimistic methods (without relaxation) can achieve some range of $\kappa$ (see e.g. 1 albeit for cohypomonotone problems).

W.2 The FRO estimator (l. 222) seems to be equivalent to what is used for the optimistic method in Böhm 2022, so I maybe wouldn't consider this a new construction. The construction in the constrained case (eq. 10), seems new, but in the current presentation its role is unclear. Is additionally term needed even in the monotone case or is it possible to get convergence for the norm of the operator already with FBF/FoRB based methods ala Alacaoglu & Malitsky 2021 (i.e. with $\gamma=1/2$ in the current paper)?

1. The paper is too dense and the presentation makes the readers hard to follow. For example, in Section 1.1, the finite-sum structure should not be parallel to the problem formulation (NI, NE, VIP, Minimax).

2. In the optimality certification part, the authors claim that existing stochastic methods often target special cases of NI and a better oracle complexity of $\mathcal{O}(n+\sqrt{n}\epsilon^{-2}) is measured using a restricted gap function, which can not be directly compared. However, it is not clear what is the previous state-of-the-art results for this problem. What are the previous results for NI, NE and VIP?

3. The authors use SAGA and SVRG for the variance reduced estimator, which may lead to worse oracle complexity under the cases, why not consider SPIDER?

see questions