Efficient Interpolation between Extragradient and Proximal Methods for Weak MVIs

We thank the reviewer for the feedback and address all remaining concerns below.

Extensions to the stochastic case and cohypomonotone case

These are very promising directions, but they each require their own treatment. In general our work opens up for a range of extensions:

• the special case of cohypomonotonicity
• the stochastic case
• higher order methods (see the last question)

Let us comment on the stochastic and cohypomontone case specifically.

Stochastic Even for $\rho > -1/(2L)$, the stochastic case is still not closed. The main two approaches currently are:

• Use increasing batch size (e.g. [1], [2], Diakonikolas et al. 2021, Böhm 2022)
• Use fixed batch size but make additional smoothness assumptions (Pethick et al. 2023a)

Avoiding increasing batch size is generally preferred, but it is currently unknown whether fixed batch size is possible without additional assumptions. It is thus not entirely clear which approach should be taken in the stochastic case.

Cohypomonotone The cohypomonotone case is definitely interesting (and we indeed mention it as a promising direction in the conclusion), but we politely disagree that it is more interesting, since the accelerated methods comes at a price:

• The cohypomonotone case rules out e.g. the motivating example in Diakonikolas et al. 2021.
• The accelerated methods do not enjoy the same adaptivity to error bound conditions (see Section 7)

We would rather say that both weak MVI methods and methods specialized for cohypomonotone problems are independently interesting to study. We have focused on methods for weak MVI as this already proved challenging. Hopefully, our work can inspire developments for the special case of cohypomonotone problems as well.

1. This paper only considers the deterministic case, which seems to be easier than the stochastic case considered by some other works such as [1,2].
2. Alacaoglu et al. (2024) also consider the cohypomonotone case, with an accelerated rate. The acceleration seems more interesting and challenging.

Questions:

1. "Have the authors considered the stochastic case like [1,2]. Is it possible to remove the log factor using your framework?"

Removing the logarithmic factor in the stochastic case by extending this work might indeed be possible and it is a very interesting direction. However, note the comment above, that the stochastic case is somewhat open even for $\rho > -1/(2L)$.

2. Comparison with [2] and its connection with [1]

The method in [2] indeed uses a proximal update, but is restricted to $\rho > -1/(2L)$, since no relaxation is used. In fact, our Theorem 8.1 provides a lower bound even in the deterministic setting (see Remark 8.2). Also note that the method does not include an extragradient computation, which is crucial for removing the logarithmic factor in the complexity (please see Eq. 9-10 for comparison with inexact proximal based methods).

Regarding the stochastic case, [2] indeed uses MLMC similarly to [1]. There are some subtle differences regarding parameter choices (see e.g. the comment after Estimator 4.4 in [1]).

3. "The method in this paper looks similar to [3]. What are the differences between the method in this paper and [3]?"

The approach [3] can be seen as a special case of our implicit scheme in Eq. 8 in the following sense:

• [3] is a special case of Solodov & Svaiter's HPE method (which applies to the monotone case). In [3] they specifically considers when the proximal update is approximated with a second order update.
• Recall, that our method is a generalization of Solodov & Svaiter HPE method by extending it to weak MVIs and relaxing the error condition (See e.g. our Remark 4.1 and the new Appendix B, which now contains the special cases explicitly).

Our implicit scheme Eq. 8 opens up for similarly considering higher order methods for weak MVIs.

We thank the reviewer for the feedback and address all remaining concerns below.

Overview of unification

We thank the reviewer for the suggestion. We have added an appendix (Appendix B) clarifying how to obtain existing algorithms such as the relaxed proximal point algorithm, the method of Solodov & Svaiter, AdaptiveEG+, forward-backward-forward, relaxed extragradient/extragradient+ from our unified framework. Each of the methods are presented in the notation of the paper to make the comparison clear and explicitly states the choice of parameter, approximation error, etc. We believe this should help contextualizing our unification.

Questions:

Typos in introduction

Fixed.

"If possible please introduce the halfspace method. It seems to show up without introduction and it is not clear what it means in Section 4."

We introduce the halfspace projection in two steps:

• The paragraph l. 187-192 describes the high-level idea of the projection (correcting for the inexactness of the approximate proximal update)
• The following l. 192-208 makes the exact form of our halfspace projection precise (the use of an extragradient computation)

We have reworded the paragraph l. 187-192, to make it clearer that the halfspace projection deals with the inexactness of the proximal point update.

"It is also not clear to me why the halfspace method works in getting better accuarcy?"

The main reason for why the halfspace projection method removes the logarithmic factor in the complexity is commented on at Eq. 6 in Section 4. That is, regardless of the inexactness of the proximal update, we can project onto a set that moves the iterate closer to the solutions. As a result, the errors wont accumulate in the analysis as is otherwise the case for the relaxed inexact proximal point algorithm.

Comparison with ellipsoid method

The methods are distinct, which can be seen by the fact that the halfspace projection divides the space with a hyperplane, whereas the ellipsoid method constructs an ellipsoid at every iteration.

"I dont follow what the linear convergence means. Is it for the inner loop?"

Linear convergence is established for the full algorithm (Algorithm 1) through Theorem 7.3 under the error bound condition. This assumption e.g. captures the the weak MVI lower bound example of Pethick et al. (2022), explaining the fast convergence observed in practice. This automatic adjustment when favorable structure is present is something that neither the relaxed inexact proximal point algorithm or Halpern based approaches enjoy (please see Section 7 for more detail).

We thank the reviewer for the feedback and address all remaining concerns below.

On the necessity of multiple inner loops

Section 6 is dedicated to explaining this. In short:

• The goal is to satisfy the error condition $- \langle \varepsilon^k, \bar v^k \rangle \leq \sigma \Vert \bar v^k\Vert^2$.
• If the approximation error, $\varepsilon^k$, of the proximal update goes to zero then this error condition will trivially be satisfied.
• Section 6.1 show that the error condition can be satisfied for one step of the inner prox solver (but this puts a restriction on $\rho>-1/2L$).
• More inner loops leads to a smaller inexactness $\varepsilon^k$, so the error condition becomes easier to satisfy, which in turn puts a looser requirement on $\rho$ (see Section 6.2).

We hope this helps clarify the benefit of multiple inner steps.

Extending the range of $\rho$

To clarify, Appendix G mentioned in Section 8 is concerned with single-step approximation methods (which are restricted to $\rho > -\gamma/2$). For those methods it is interestingly possible to relax the Lipschitz condition (and in effect the condition on the stepsize $\gamma$). We are not claiming that we can extend $\rho$ beyond $-1/L$.

Application to real-world problems

The work is theoretical in nature and follows a long list of previous theoretical works in this space (e.g. [1,2,3,4]), where it is the practice to not include any experience. In contrast, we verify our theoretical findings on a toy example.

With that said, Algorithm 1 is designed with practical concerns in mind:

• removing the logarithmic factor is important in practice, where a logarithm could otherwise make a method multiple times slower
• The method automatically adapts when favorable structure is present (Section 7)
• the method automatically selects the number of inner steps and the stepsize $\alpha_k$ (which otherwise would need to be tuned)

We hope these points help clarify the practical relevance of our contributions, even within the theoretical focus of this work.

[1] https://openreview.net/pdf?id=lWy2lCTyJa

[2] https://openreview.net/pdf?id=EK7fuAMNoI

[3] https://arxiv.org/pdf/2011.00364

[4] https://arxiv.org/pdf/2210.13831

Unified notation

We are using the following convention:

• When presenting algorithms (and the associated theorems) we state parameters of the algorithm as a function of the problem parameters (e.g. specify $\gamma$ based on $\rho$)
• When discussing the range of $\rho$ we explicitly state as function of problem parameters (e.g. the introduction and remarks such as Remark 4.1, Remark 5.2).

For consistency we now also mention the range of $\rho$ in Remark 6.4 (after stating the complexity result). We hope this clarifies the choice of presentation.

We thank the reviewer for the feedback and address all remaining concerns below.

Significance

The paper solves an open problem stated by at least two different groups (see e.g. [1] and [2]). Furthermore, the solution seems to be nonobvious, as there is a range of work either not getting the full range of $\rho$ [Fan et al. 2023] or suffering the additional log factor [Alacaoglu et al. 2024, Lee and Kim 2024]. The work addresses a fundamental question about the limits of first-order methods in nonmonotone problems by obtaining what has been theorized to be the largest range of $\rho$ and best complexities for weak MVI. It thus seems interesting to the optimization for machine learning community.

In addition:

• Our work provides a unification of many existing methods (we have now included an explicit list in Appendix B)
• We provide linear convergence (i.e. exponential convergence) under the error bound condition. This is e.g. satisfied by the weak MVI lower bound example in [Pethick et al. (2022)].
• Algorithm 1 does not need to prespecify the number of inner steps $n$ or the stepsize $\alpha_k$ in contrast with relaxed inexact proximal based methods (see Remark 6.4)

Clarify the relationship with existing methods

We have added an appendix (Appendix B) clarifying how to obtain existing algorithms such as the relaxed proximal point, the method of Solodov & Svaiter, AdaptiveEG+, forward-backward-forward, relaxed extragradient/extragradient+ from our unified framework. Each of the methods are presented in the notation of the paper to make the comparison clear.

"The placement of Algorithm 1 feels distant from Section 6."

We have moved the algorithm to the section titled "Algorithmic construction" (Section 4).

Questions:

1. "The authors refer to the halfspace projection as an error correction step. When comparing Eqs. 9 and 10, if we substitute the first equality condition from Eq. 8 into Eq. 9, we get $z^{k+1} = (1-\lambda_k) z^k + \lambda_k (z^k - \bar{v}^k - \epsilon^k)$. Can we interpret the error correction as eliminating the explicit error term $\epsilon^k$ in Eq. 10 through an additional operator evaluation $\bar{v}^k \in \gamma S \bar{z}^k$? Consequently, although the calculation of $\bar{z}^k$ involves this error term, it only appears implicitly, and with the error condition, it ensures Fejér monotonicity."

Yes, the fact that $\varepsilon^k$ does not explicitly appear in the update of $z^{k+1}$ is one way of intuitively understanding why we can eventually ensure Fejér monotonicity. Conversely, it also shows why relaxed inexact proximal point suffers the logarithmic factor in the complexity.

2. "Why is the parameter $\lambda_{k}$ considered within $(0,2)$?"

Instead of only considering $\lambda_k=1$ we consider the wider range $(0,2)$ for two reasons:

• Mainly, it allows us to absorb adaptive $\alpha_k$ into $\lambda_k$, which is necessary for capturing the constant stepsize case (see Section 6.3).
• Overrelaxation (i.e. $\lambda_k \in (1,2)$) has been shown to be beneficial in practice (see e.g. [3]), so it is useful to have guarantees for the extended range.

[3] https://arxiv.org/pdf/1603.05398

3. Does $\alpha_k$ have an upper bound?

Yes, by rewriting

$\alpha_k = 1 + \langle\bar v, \varepsilon\rangle/\Vert\bar v\Vert^2 + \delta/\gamma \leq 1 + \Vert\bar v\Vert \Vert \varepsilon\Vert/\Vert\bar v\Vert^2 + \delta/\gamma = 1 + \delta/\gamma$

where we have used Cauchy-Schwarz and minimized with $\varepsilon=0$.