text:
\subsubsection*{\bibname}}
\usepackage{bm,xcolor}
\usepackage{colortbl}
\usepackage{cases}
\usepackage{CJK}
\usepackage{indentfirst}
\usepackage{booktabs}
\usepackage{arydshln}
\usepackage{tabularx}
\usepackage{multirow}
\newcolumntype{Y}{>{\centering\arraybackslash}X}
\usepackage{tcolorbox}
\usepackage{xr-hyper}

\usepackage{placeins}
\usepackage{makecell}

\input{math_commands.tex}
\input{defs.tex}
\usepackage{xcolor}
\definecolor{DarkGreen}{rgb}{0.1,0.5,0.1}
\definecolor{DarkRed}{rgb}{0.5,0.1,0.1}
\definecolor{DarkBlue}{rgb}{0.1,0.1,0.5}
\definecolor{DarkYellow}{rgb}{.79,.79,0}
\usepackage{hyperref}
\hypersetup{
    unicode=false,
    pdftoolbar=true,
    pdfmenubar=true,
    pdffitwindow=false,
    pdfnewwindow=true,
    colorlinks=true,
    linkcolor=DarkBlue,
    citecolor=DarkGreen,
    filecolor=DarkRed,
    urlcolor=DarkBlue,
    pdftitle={},
    pdfauthor={},
}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\argmin}[1]{arg\underset{#1}{min}}
\newcommand{\sol}[1]{\mathcal{S}^\star_{#1}}
\usepackage[inline, shortlabels]{enumitem}
\usepackage{ mathrsfs }
\usepackage{dsfont}
\usepackage{subfigure}
\usepackage{algorithm,algorithmic}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{extarrows}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{amsthm}
\theoremstyle{plain}
\newtheorem{lm}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{asmp}{Assumption}
\newtheorem{eg}{Example}
\newtheorem{crl}{Corollary}
\newtheorem{rmk}{Remark}

\begin{document}
\thispagestyle{plain}
\pagestyle{plain}

\twocolumn[

\aistatstitle{Revisiting the ACVI Method for Constrained Variational Inequalities}

\aistatsauthor{ Tatjana Chavdarova$^\star$ \And Matteo Pagliardini$^\star$ \And Tong Yang$^\star$ \And Michael I. Jordan}

\aistatsaddress{ UC Berkeley \And  UC Berkeley and EPFL \And Peking University \And UC Berkeley}
]

\begin{abstract}
  \textit{ACVI} is a recently proposed first-order method for solving variational inequalities (VIs) with general constraints.~\citet{acvi} showed that the gap function of the last iterate decreases at a rate of $\mathcal{O}(\frac{1}{\sqrt{K}})$ when the operator is $L$-Lipschitz, monotone, and at least one constraint is active.
  In this work, we show that the same guarantee holds when only assuming that the operator is monotone.
  To our knowledge, this is the first analytically derived last-iterate convergence rate for general monotone VIs, and overall the only one that does not rely on the assumption that the operator is $L$-Lipschitz.
  Furthermore, when the sub-problems of ACVI are solved approximately, we show that by using a standard warm-start technique the convergence rate stays the same, provided that the errors decrease at appropriate rates.
  We further provide empirical analyses and insights on its implementation for the latter case.
\end{abstract}

\section{Introduction}\label{sec:intro}

Variational Inequalities (VIs) are a class of problems that generalize standard minimization problems, including constrained optimization problems, to problems such as finding equilibria in zero-sum games and general-sum games~\citep{cottle_dantzig1968complementary,vonneumann1947gametheory,rockafellar1970monotone}.
The (constrained) VI problem seeks a point ${\bm{x}}^\star \in \mathcal{X}$ such that:
\begin{equation} \label{eq:cvi} \tag{cVI}
  \langle {\bm{x}}-{\bm{x}}^\star, F({\bm{x}}^\star) \rangle \geq 0, \quad \forall {\bm{x}} \in \mathcal{X} \,,
  \vspace{-.2em}
\end{equation}
where $\mathcal{X}$ is a subset of the Euclidean $n$-dimensional space $\mathbb{R}^n$, and where $F\colon \mathcal{X}\mapsto \mathbb{R}^n$ is a continuous map.
Their generality is owing to the fact that $F$ is a \emph{vector field} in the general case, in sharp contrast to standard minimization, where $F\equiv \nabla f$ is restricted to only represent \emph{gradient} fields.
The increased expressivity underlies their practical relevance to a wide range of emerging applications in machine learning, such as
\textit{(i)} multi-agent games~\citep{goodfellow2014generative,vinyals2017starcraft},
\textit{(ii)} robustification of single-objective problems, which yields min-max formulations~\citep{szegedy2014intriguing,NEURIPS2020_02f657d5,causal2020,anchorRegression}, and
\textit{(iii)} statistical approaches to modeling complex multi-agent dynamics in stochastic and adversarial environments.

Such generality comes, however, at a price, in that solving for equilibria is significantly more challenging than solving for optima. In particular, the Jacobian of $F$ is no longer symmetric in the general case, which implies possible rotational trajectories in the parameter spaces~\citep{korpelevich1976extragradient}, which can lead to limit cycles~\citep{hsieh2021limits}.
Moreover, in sharp contrast to standard minimization, the last iterate can be quite far from the solution even though the average iterate converges to the solution~\citep{chavdarova2019}.
This has motivated recent efforts to focus specifically on convergence analysis of the \emph{last iterate} of the VI optimization methods.  Indeed, if the last iterate does not converge to the solution in some theoretical settings, then there is no hope that such a method will converge in highly nonconvex settings such as GANs or multi-agent reinforcement learning~\citep{goodfellow2014generative,vinyals2017starcraft}.
Despite substantial recent progress in this regard~\citep[see, e.g.,][see also \S~\ref{sec:related_works}]{tseng1995,daskalakis2018training,diakonikolas2020halpern,golowich2020last,chavdarova2021hrdes,gorbunov2022extra}, currently, an analytical derivation of the rate of convergence of the last-iterate of the first-order VI methods for the large class of monotone VIs (defined in \S~\ref{sec:preliminaries}) is still missing.
This hinders the advancement of the VI methods, for example, hindering the development of accelerated methods.
All of the known rates of convergence for monotone VIs assume that the operator satisfies the globally Lipschitz condition (see \S~\ref{sec:related_works}).
Since some applications do not satisfy this assumption~\citep[see for example the discussion in][]{patel2022}, it is an important challenge to derive  last-iterate convergence rates while relying solely on the monotonicity of the operator $F$.

Motivated by the lack of a first-order method for the~\ref{eq:cvi} problem with general constraints,~\citet{acvi} recently proposed the \textit{\textbf{A}DMM-based Interior Point Method for \textbf{C}onstrained \textbf{VI}s} (ACVI), a first-order, primal-dual method for solving~\ref{eq:cvi}.
ACVI generalizes the \emph{alternating direction method of multipliers} (ADMM) method~\citep{glowinskiMarroco1975,gabayAndMercier1976dual}, an algorithmic paradigm that is central to large-scale optimization~\citep{boyd2011admm,ryan2017admm}, but which has been little explored in the~\ref{eq:cvi} context.
\citet{acvi} showed  that the gap function of the last iterate of ACVI decreases at a rate of $\mathcal{O}(\frac{1}{\sqrt{K}})$ when the operator is $L$-Lipschitz, monotone, and at least one constraint is active. It is, however, an open problem to determine if the method converges while assuming only that the operator is monotone. Moreover, in some cases, the sub-problems of ACVI may be cumbersome to solve analytically. Hence, a natural question that arises is if we can show convergence when sub-problems are solved approximately, and in particular understanding what assumptions are needed for the approximation errors.

In summary, our focus is the following two questions:
\begin{itemize}
\item \emph{Does the last iterate of ACVI converge
when the operator is monotone, and not necessarily $L$-Lipschitz}?
\item \emph{Does ACVI converge when the sub-problems are solved approximately}?
\end{itemize}

In this paper, we answer the former question affirmatively. More precisely, we prove that the last iterate of ACVI converges at a rate of $\mathcal{O}(\frac{1}{\sqrt{K}})$ in terms of the standard gap function even when assuming only the monotonicity of the operator.  The core of our analysis lies in identifying a relationship between the reference point of the gap function and a KKT point that ACVI targets implicitly (i.e., it does not appear explicitly in the ACVI algorithm). This allows us to show that ACVI explicitly works to decrease the gap function at each iteration.
The argument further allows us to determine a convergence rate by making it possible to upper bound the gap function. This is in contrast to the approach of~\citet{acvi} who upper bound the iterate distance, and then the gap function, an approach that requires a Lipschitz assumption. To the best of our knowledge, this is the first convergence rate for monotone VIs that does not rely on an $L$-Lipschitz assumption on the operator $F$.

To address the latter question, we exploit a key property of the ACVI algorithm---namely, the homotopic structure of ACVI as it smoothly transitions to the original problem, a homotopy that inherently arises from its origin as an interior-point method.
Moreover, due to the alternating updates of the two sets of parameters of ACVI (${\bm{x}}$ and ${\bm{y}}$; see Algorithm~\ref{alg:inexact_acvi}), the sub-problems change negligibly, with the changes proportional to the step sizes.
This motivates the standard \emph{warm-start} technique where, at every iteration, instead of initializing at random, we initialize the corresponding optimization variable with the approximate solution found at the previous iteration.
We refer to the resulting algorithm as \emph{inexact ACVI}.
Furthermore, inspired by the work of~\citet{schmidt2011convergence}, which focuses on the proximal gradient method for standard minimization, we prove that inexact ACVI converges with the same rate of  $\mathcal{O}(\frac{1}{\sqrt{K}})$, under a sufficient condition that the errors decrease at appropriate rates.
We evaluate inexact ACVI empirically on 2D and high-dimensional games and show how multiple inexact but computationally cheap iterations can yield faster wall-clock convergence than fewer exact ones.

Finally, we provide a detailed study of a special case of the problem class that ACVI can solve. In particular, we focus on the case when the inequality constraints are simple, in the sense that projection on those inequalities is fast to compute.
Such problems arise relatively often in machine learning; e.g., whenever the constraint set is an $L_p$-ball, with $p \in \{1,2,\infty\}$ as in adversarial training \citep{GoodfellowSS14}.
We show that the same convergence rate holds for this variant of ACVI.
Moreover, we show empirically that when using this method on the problem of training a constrained GAN on the MNIST~\citep{mnist} dataset we find that it convergences  faster than the projected variants of the standard VI methods.

In summary, our main contributions are as follows:
\begin{itemize}
    \item We show that the gap function of the last iterate of ACVI~\citep[][Algorithm $1$ therein]{acvi} decreases at a rate of  $\mathcal{O}(\frac{1}{\sqrt{K}})$ for monotone variational inequalities, \emph{without} relying on the assumption that the operator is  $L$-Lipschitz.
    \item We combine a standard warm-start technique with ACVI, and propose a precise variant of ACVI with approximate solutions, named \emph{inexact ACVI}---see Algorithm~\ref{alg:inexact_acvi}. We show that inexact ACVI recovers the same rate of convergence as ACVI, provided that the errors decrease at appropriate rates.
    \item We propose a variant of ACVI designed for the cases when the inequality constraints are relatively simple so that the projection is fast to compute--see Algorithm~\ref{alg:log_free_acvi}. We derive a corollary of the former result, which guarantees the convergence; moreover, the central path is not needed in this case, which simplifies the convergence analysis.
    \item Empirically, we:
    \textit{(i)} verify the benefits of warm-start of the inexact ACVI;
    \textit{(ii)} observe that I-ACVI can be faster than other methods by taking advantage of cheaper approximate steps;
    \textit{(iii)} train a constrained GAN on MNIST and show the projected version of ACVI is faster to converge than other methods; and
    \textit{(iv)} provide visualizations contrasting the different ACVI variants.
\end{itemize}

\section{Related Works}\label{sec:related_works}

\noindent\textbf{Last-iterate convergence of first-order methods on VI-related problems.}
It is known that the last and average iterate can be quite far apart for algorithms that aim to solve VIs; see examples in~\citep{chavdarova2019}.
Thus, an extensive line of work has focused on establishing last-iterate convergence for bilinear or strongly monotone games~\citep[see, e.g., ][]{tseng1995,malitsky2015,facchinei2003finite,daskalakis2018training,liang2018interaction,gidel19-momentum,azizian20tight,thekumparampil2022lifted,alacaoglu2022}.  We note also the work of~\citet{diakonikolas2020halpern}, who focuses on cocoercive operators.
Continuous-time analyses have also been important in the study of last-iterate convergence, particularly through the use of Lyapunov functions~\citep{ryu2019ode,bot2020,rosca2021,chavdarova2021hrdes,bot2022fast}.
For monotone VIs,
\textit{(i)}~\citet{golowich2020last,golowich2020noregret} established a lower bound of is  $\mathcal{O}(\frac{1}{ \tilde{p} \sqrt{K}})$ for $\tilde{p}$-\textit{stationary canonical linear iterative}  ($\tilde{p}$-SCLI) first-order methods~\citep{arjevani2016pscli};
\textit{(ii)} \citet{golowich2020last} obtained a rate in terms of the gap function relying on first- and second-order smoothness of $F$,
\textit{(iii)}~\citet{gorbunov2022extra} and~\citet{gorbunov2022}  obtained a rate of $\mathcal{O}(\frac{1}{K})$ for extragradient~\citep{korpelevich1976extragradient} and optimistic GDA~\citep{popov1980}, respectively---in terms of
reducing the squared norm of the operator, relying on first-order smoothness of $F$---while using computer-assisted proof, and
\textit{(iv)}~\citet{golowich2020last} and~\citet{chavdarova2021hrdes} provided a best-iterate rate for OGDA while assuming first-order smoothness of $F$.
\citet{daskalakis2019constrained} focused on zero-sum convex-concave constrained problems and provided an asymptotic convergence guarantee for the last iterate of the \textit{optimistic multiplicative weights update} (OMWU) method.
For constrained and monotone VIs with $L$-Lipschitz operator,~\citet{cai2022constrVI} recently showed that both the last iterate of extragradient and of optimistic GDA have a rate of convergence that matches the lower bound, using a computer-aided proof.
~\citet{gidel2017fwolfe} considered strongly convex-concave zero-sum games with \emph{strongly} convex constraint set and analyzed the convergence of the Frank-Wolfe method~\citep{frankWolfe1956,jaggi2013,lacosteJaggi2015}.

\noindent\textbf{Interior point methods for VIs.}
Interior point (IP) methods are a broad class of algorithms for solving problems that are constrained by general inequality and equality constraints. One of the most commonly used classes of IP methods is the primal-dual interior point method with a logarithmic barrier.
IP methods are typically solved using Newton's method, which iteratively approaches the solution from within the feasible region.
Several works extend IP methods for constrained VI problems. Among these,~\citet[Chapter $7$,][]{Nesterov1994InteriorpointPA} studies their extension to VI problems, while relying on Newton's method.
Further, an extensive line of works discusses specific settings~\citep[e.g.,][]{chen1998global,qi2002smoothing,qi2000new,fan2010interior}.
On the other hand,~\citet{goffin19971} described a second-order cutting-plane method for solving pseudomonotone VIs with linear inequalities.
Nonetheless, although these methods enjoy fast convergence in terms of the number of iterations, each iteration requires computing second-order derivatives, which becomes computationally prohibitive for large-scale problems.
Recently,~\citet{acvi} derived the aforementioned ACVI method which combines
interior-point methods and the ADMM method, resulting in a first-order method that is able to handle general constraints.

\section{Preliminaries}\label{sec:preliminaries}

\noindent\textbf{Notation.}
We use bold small and bold capital letters to denote vectors and matrices, respectively.
Curly capital letters denote sets.
We let $[n]$ denote $\{1, \dots, n\}$ and let ${\bm{e}}$ denote vector of all 1's.
The Euclidean norm of ${\bm{v}}$ is denoted by $\norm{{\bm{v}}}$, the inner product in Euclidean space by $\langle\cdot,\cdot\rangle$, and
$\odot$ denotes element-wise product.

\noindent\textbf{Problem.}
The constraint set $\mathcal{C}\subseteq \mathcal{X}$ is defined as an intersection of finitely many inequalities and linear equalities:
\begin{equation}\tag{CS}
    \mathcal{C}=\left\{ {\bm{x}} \in  \mathbb{R}^n| \varphi_i ({\bm{x}}) \leq 0, i \in [m], \,\,{\bm{C}}{\bm{x}}={\bm{d}} \right\} \label{eqK},
\end{equation}
where each $\varphi_i : \mathbb{R}^n \mapsto \mathbb{R}$,
${\bm{C}} \in \mathbb{R}^{p \times n}$,
${\bm{d}}\in \mathbb{R}^p$,
where $rank (  {\bm{C}}  ) =p$ is the rank of ${\bm{C}}$.
With abuse of notation, let $\varphi$ be the concatenated $\varphi_i(\cdot), i\in[m]$.
We assume that each of the inequality constraints is  convex and assume
$ \varphi_i \in C^1 (\mathbb{R}^n), i \in [m] $.
We define the following sets:
\begin{equation*}
\begin{split}
    & \mathcal{C}_\leq \triangleq \left\{ {\bm{x}}\in  \mathbb{R}^n \left| \varphi({\bm{x}}) \leq \boldsymbol{0} \right. \right\}, \\
    & \mathcal{C}_< \triangleq \left\{ {\bm{x}}\in  \mathbb{R}^n \left| \varphi({\bm{x}}) < \boldsymbol{0} \right. \right\},   \text{ and } \\
    & \mathcal{C}_= \triangleq \{{\bm{y}} \in \mathbb{R}^n|{\bm{C}} {\bm{y}} = {\bm{d}}\} \,;
\end{split}
\end{equation*}
thus the \textit{relative} interior of $\mathcal{C}$ is $ \textit{int}\ \mathcal{C}\triangleq \mathcal{C}_<  \cap  \mathcal{C}_=$.
We make the standard assumptions that $ \textit{int}\ \mathcal{C} \neq \emptyset $ and that $\mathcal{C}$ is compact.

In the following, we list the definitions and assumptions we refer to later on.
We define these for a general domain $\mathcal{S}$, and by setting $\mathcal{S} \equiv \mathbb{R}^n$ and $\mathcal{S} \equiv \mathcal{X}$, these refer to the unconstrained and constrained settings, respectively.

\begin{definition}[monotone operators]\label{def:monotone}
An operator $F\colon\mathcal{X}\supseteq \mathcal{S}
\to \mathbb{R}^n $ is monotone on $\mathcal{S}$ if:
$$
    \langle {\bm{x}}-{\bm{x}}', F({\bm{x}})-F({\bm{x}}') \rangle \geq 0, \quad \forall {\bm{x}}, {\bm{x}}' \in \mathcal{S}\,.
$$
\end{definition}

We will use the standard \emph{gap function} as a convergence measure, which requires $\mathcal{S}$ to be compact for it to be defined.

\begin{definition}[gap function]\label{def:gap}
Given a candidate point ${\bm{x}}'\in \mathcal{X}$
and a map $F\colon\mathcal{X}\supseteq \mathcal{S}\to \mathbb{R}^n$ where $\mathcal{S}$ is compact, the gap function $\mathcal{G}: \mathbb{R}^n\to\mathbb{R}$ is defined as:
$$
\mathcal{G}({\bm{x}}', \mathcal{S}) \triangleq \underset{{\bm{x}}\in\mathcal{S}}{\max} \langle F({\bm{x}}'), {\bm{x}}' - {\bm{x}} \rangle \,.
$$
\end{definition}

\begin{definition}[$\sigma$-approximate solution]\label{def:approx_x}
Given a map $F\colon \mathcal{X}\to \mathbb{R}^n$ and a positive scalar $\sigma$, ${\bm{x}}\in\mathcal{X}$ is said to be a $\sigma$-approximate solution of $F({\bm{x}})=\mathbf{0}$ if $\norm{F({\bm{x}})}\leq\sigma$.
\end{definition}

Since the ${\bm{y}}$ sub-problem of ACVI is a standard minimization, we will  also rely on the following definition.

\begin{definition}[$\varepsilon$-minimizer]\label{def:subopt}
Given a minimization  problem
$ \underset{{\bm{x}}}{\min} \,\,h({\bm{x}})$, s.t. ${\bm{x}}\in\mathcal{S}$,
and a fixed positive scalar $\varepsilon$, a point $\hat{{\bm{x}}}\in\mathcal{S}$ is said to be an $\varepsilon$-minimizer if:
\begin{equation*}
    h(\hat{{\bm{x}}})\leq h({\bm{x}})+\varepsilon,\,\, \quad \forall {\bm{x}}\in\mathcal{S}.
\end{equation*}
\end{definition}

Appendix~\ref{app:background} provides additional background, including a presentation of the KKT system for~\eqref{eq:cvi}, guarantees under which the central path exists, and some additional VI definitions that are helpful for the discussion.

\begin{figure*}[!htbp]
  \centering
  \begin{subfigure}[ACVI]{
  \includegraphics[width=0.23\linewidth,clip]{pics/central-path-pics/acvi_y_cp_cbilinear_k200_l150_exact_delta0.5_.pdf}
  }
  \end{subfigure}
  \begin{subfigure}[I-ACVI, $K=20,\ell=2$]{
  \includegraphics[width=0.23\linewidth,trim={0cm .0cm 0cm .0cm},clip]{pics/central-path-pics/acvi_y_cp_cbilinear_k20_l2_inexact_delta0.5_.pdf}
  }
  \end{subfigure}
  \begin{subfigure}[I-ACVI, $K=10,\ell=2$]{
  \includegraphics[width=0.23\linewidth,clip]{pics/central-path-pics/acvi_y_cp_cbilinear_k10_l2_inexact_delta0.5_.pdf}
  }
  \end{subfigure}
  \begin{subfigure}[I-ACVI, $K=5,\ell=2$]{
  \includegraphics[width=0.23\linewidth,clip]{pics/central-path-pics/acvi_y_cp_cbilinear_k5_l2_inexact_delta0.5_.pdf}
  }
  \end{subfigure}
 \caption{
 \textbf{Convergence of  ACVI, and I-ACVI with different parameters on the~\eqref{eq:2d-bg} problem}: \emph{illustrations with the central path} (depicted in yellow). For all the methods, we show the ${\bm{y}}$-iterates, initialized at the same point.
 Each subsequent bullet on the trajectory depicts the (exact or approximate) solution at the end of the inner loop (when $k \equiv K-1$).
 The Nash equilibrium (NE) of the game is represented by a yellow star, and the constraint set is the interior of the red square. \textbf{Fig. (a)}: As we decay $\mu_t$, the solutions of the inner loop of ACVI follow the central path.
 As $\mu_t \rightarrow 0$ the solution of the inner loop of ACVI converges to the NE.
 \textbf{Fig. (b, c, d)}:
 When ${\bm{x}}$ and ${\bm{y}}$ sub-problems are both solved approximately (see the I-ACVI algorithm) with a finite $K$ and $\ell$, the iterates might not converge as the approximation error increases (and $K$ decreases).
 See \S~\ref{sec:experiments} for a discussion.
 }
 \label{fig:acvi-c-bilin-y}
\end{figure*}

\begin{algorithm*}[!htb]
    \caption{Inexact ACVI (I-ACVI) pseudocode.}
    \label{alg:inexact_acvi}
    \begin{algorithmic}[1]
        \STATE \textbf{Input:}  operator $F\colon\mathcal{X}\to \mathbb{R}^n$, constraints ${\bm{C}}{\bm{x}} = {\bm{d}}$ and  $\varphi_i({\bm{x}}) \leq 0, i = [m]$,
        hyperparameters $\mu_{-1},\beta>0, \delta\in(0,1)$,
        inner optimizers $\mathcal{A}_{\bm{x}}$ (e.g. EG, GDA, OGDA) and $\mathcal{A}_{\bm{y}}$ (GD), for the ${\bm{x}}$ and ${\bm{y}}$ sub-problems, resp.;
        number of outer and inner loop iterations $T$ and $K$, resp.
        \STATE \textbf{Initialize:} ${\bm{y}}^{(0)}_0\in \mathbb{R}^n$, ${\bm{\lambda}}_0^{(0)}\in \mathbb{R}^n$
        \STATE ${\bm{P}}_c \triangleq {\bm{I}} - {\bm{C}}^\intercal ({\bm{C}} {\bm{C}}^\intercal )^{-1}{\bm{C}}$ \hfill \mbox{where} ${\bm{P}}_c \in \mathbb{R}^{n\times n}$
        \STATE ${\bm{d}}_c \triangleq {\bm{C}}^\intercal({\bm{C}} {\bm{C}}^\intercal)^{-1}{\bm{d}}$  \hfill \mbox{where} ${\bm{d}}_c \in \mathbb{R}^n$
        \FOR{$t=0, \dots, T-1$}
                \STATE $\mu_t = \delta \mu_{t-1}$
        \FOR{$k=0, \dots, K-1$}
            \STATE Set ${\bm{x}}^{(t)}_{k+1}$ to be a $\sigma_{k+1}$-approximate solution
            of: ${\bm{x}} + \frac{1}{\beta} {\bm{P}}_c F({\bm{x}}) - {\bm{P}}_c {\bm{y}}_k^{(t)} + \frac{1}{\beta}{\bm{P}}_c{\bm{\lambda}}_k^{(t)} - {\bm{d}}_c = \boldsymbol{0}$ (w.r.t. ${\bm{x}}$),  through running $\ell_{\bm{x}}^{(t)}$ steps of $\mathcal{A}_{\bm{x}}$ \label{alg-ln:x-sol-i}, where each time ${\bm{x}}$ is initialized to be the solution of the previous step ${\bm{x}}_{k}^{(t)}$
        \STATE Set ${\bm{y}}_{k+1}^{(t)}$ to be an $\varepsilon_{k+1}$-minimizer of $\min_{{\bm{y}}} - \mu \sum_{i=1}^m \log \big( -\varphi_i ({\bm{y}}) \big) + \frac{\beta}{2} \norm{{\bm{y}}-{\bm{x}}_{k+1}^{(t)} - \frac{1}{\beta}{\bm{\lambda}}_k^{(t)}}^2$, obtained through running $\ell_{\bm{y}}^{(t)}$ steps of $\mathcal{A}_{\bm{y}}$, where each time ${\bm{y}}$ is initialized to be the solution of the previous step ${\bm{y}}_{k}^{(t)}$
        \STATE
        $
            {\bm{\lambda}}_{k+1}^{(t)}={\bm{\lambda}}_k^{(t)}+\beta ( {\bm{x}}_{k+1}^{(t)}-{\bm{y}}_{k+1}^{(t)})
        $
        \ENDFOR
        \STATE $({\bm{y}}^{(t+1)}_0, {\bm{\lambda}}^{(t+1)}_0 ) \triangleq ({\bm{y}}^{(t)}_{K}, {\bm{\lambda}}^{(t)}_{K} )$
        \ENDFOR
    \end{algorithmic}
\end{algorithm*}

\section{Convergence of Exact and Inexact ACVI for Monotone VIs}
In this section we present our main theoretical results:
\textit{(i)} the rate of convergence of the last iterate of ACVI under the assumption that the operator $F$ is monotone; and
\textit{(ii)} the corresponding convergence rate when the sub-problems are solved approximately.  In the latter case we analyze the \emph{inexact ACVI algorithm}, which is stated in Algorithm~\ref{alg:inexact_acvi}; see Appendix~\ref{app:background} for a presentation of the ACVI algorithm.
For simplicity, we will state both of these results for a fixed $\mu_{-1}$, but these theorems  hold without knowing the exact value of $\mu_{-1}$, as discussed in Appendix~\ref{app:proof_thm_log_free_rate} in \citep{acvi}. Thus, both algorithms are parameter-free.

\subsection{Last-iterate convergence of exact ACVI}

\begin{thm}[Last-iterate convergence rate of ACVI---Algorithm $1$ in~\citep{acvi}]\label{thm:exact_acvi}
Given a continuous operator $F\colon \mathcal{X}\to \mathbb{R}^n$, assume:
(i) F is monotone on $\mathcal{C}_=$, as per Def.~\ref{def:monotone}; (ii) either $F$ is strictly monotone on $\mathcal{C}$ or one of $\varphi_i$ is strictly convex. Let $({\bm{x}}_K^{(t)}, {\bm{y}}_K^{(t)}, {\bm{\lambda}}_K^{(t)})$ denote the last iterate of ACVI,
run with sufficiently small $\mu_{-1}$. Then $\forall t \in [T]$ and $\forall K \in {\mathbb N}_+$, it holds that:
\begin{equation} \notag
    \mathcal{G}({\bm{x}}_{K},\mathcal{C})\leq  \mathcal{O} (\frac{1}{\sqrt{K}}) \,, \text{ and } \\
    \norm{{\bm{x}}_K-{\bm{y}}_K}\leq \mathcal{O} (\frac{1}{\sqrt{K}}) \,.
\end{equation}

\end{thm}

Appendix~\ref{app:proofs} gives specific details on the constants that appear in the rates,  as well as the proof of Theorem~\ref{thm:exact_acvi}.

\subsection{Last-iterate convergence rate of inexact ACVI}

For some problems, the equation in line 8, or the convex optimization problem in line 9 of ACVI---Algorithm~\ref{alg:acvi}---may not have an analytic solution (or the exact solution may be expensive to obtain). Here we consider solving these two problems approximately, using warm-starting.
This technique requires that at each iteration, we set the initial variable ${\bm{x}}$ and ${\bm{y}}$  to be the solution at the previous step when solving the ${\bm{x}}$ and ${\bm{y}}$ sub-problems, respectively; see the detailed description in Algorithm~\ref{alg:inexact_acvi}.
The following Theorem---inspired by~\citep{schmidt2011convergence}---establishes that when the errors in the calculation of the sub-problems satisfy certain conditions, the last-iterate convergence rate of inexact ACVI recovers that of (exact) ACVI.

\begin{thm}[Last-iterate convergence rate of Inexact ACVI (I-ACVI)]\label{thm:inexact_acvi}
Given a continuous operator $F\colon \mathcal{X}\to \mathbb{R}^n$, assume:
(i) F is monotone on $\mathcal{C}_=$, as per Def.~\ref{def:monotone};
(ii) either $F$ is strictly monotone on $\mathcal{C}$ or one of $\varphi_i$ is strictly convex; and
(iii) $F$ is $L$-Lipschitz on $\mathcal{X}$, that is, $\norm{F({\bm{x}}) - F({\bm{x}}')} \leq L \norm{{\bm{x}}-{\bm{x}}'}$, for all ${\bm{x}}, {\bm{x}}' \in \mathcal{X}$ and some $L > 0$.
Let $({\bm{x}}_K^{(t)}, {\bm{y}}_K^{(t)}, {\bm{\lambda}}_K^{(t)})$ denote the last iterate of Algorithm~\ref{alg:inexact_acvi}, run with sufficiently small $\mu_{-1}$; and  let
$\sigma_k$ and $\varepsilon_k$ denote the approximation errors at step $k$ of lines 8 and 9 (as per Def.~\ref{def:approx_x} and~\ref{def:subopt}), respectively.
Further, suppose:
\begin{equation*}
    \lim_{K\rightarrow\infty}\frac{1}{\sqrt{K}}\sum_{k=1}^{K+1}(k(\sqrt{\varepsilon_k}+\sigma_k))<+\infty\,.
\end{equation*}
Then for all $ t \in [T]$ and $ K \in {\mathbb N}_+$, it holds that:
\begin{equation*}
    \mathcal{G}({\bm{x}}_{K},\mathcal{C})\leq  \mathcal{O} (\frac{1}{\sqrt{K}})\,, \text{ and }
    \norm{{\bm{x}}^K-{\bm{y}}^K}\leq \mathcal{O} (\frac{1}{\sqrt{K}})\,.
\end{equation*}
\end{thm}

Note that---as is also the case for Theorem~\ref{thm:exact_acvi}---Theorem~\ref{thm:inexact_acvi} gives a nonasymptotic convergence guarantee. More precisely, while the condition involving  the sequences $\{{\epsilon}_k\}_{k=1}^{K+1}$ and $\{\sigma_k\}_{k=1}^{K+1}$ requires the given expression to be summable, the convergence rate is nonasymptotic as it holds for any $K$.
Appendix~\ref{app:proofs} gives specific details on the constants that appear in the convergence rates of Theorem~\ref{thm:inexact_acvi} and provides its proof.
Appendix~\ref{app:implementation} discusses further details of the implementation of Algorithm~\ref{alg:inexact_acvi}, and we will present an extensive analysis of the effect of warm-starting later in \S~\ref{sec:experiments}.

\section{Specialization of ACVI for Simple Inequality Constraints}\label{sec:acvi_simple_ineq}

While ACVI is able to handle general constraints, it is a relatively common scenario in machine learning applications that the inequality constraints are fairly simple, in the sense that the projection can be computed cheaply. This is the case when we have $L_\infty$-ball constraints for which the projection can be obtained through simple clipping.
Projections onto the $L_2$ and $L_1$-balls can also be obtained efficiently, through simple normalization for $L_2$ and a $\mathcal{O}\big(n\log(n)\big)$ algorithm for $L_1$~\citep{duchiprojl1}.

In those cases, the ${\bm{y}}$ sub-problem of ACVI can be replaced by projection onto the set defined by the inequalities. On the other hand, the ${\bm{x}}$ sub-problem can still take into account the equality constraints in the general case; or if there are no equality constraints, it is easy to see that such problem setting will only simplify the ${\bm{x}}$ sub-problem since ${\bm{P}}_c\equiv{\bm{I}}$, and ${\bm{d}}_c\equiv\mathbf{0}$.

In this section, we specifically focus on this special case in which there are simple inequalities.

\noindent\textbf{The P-ACVI Algorithm: omitting the $\log$ barrier}.
Suppose that the given inequality constraints can be satisfied with a projection  $\Pi_\leq(\cdot)\colon \mathbb{R}^n \rightarrow \mathcal{C}_\leq$ that is fast to compute.
In that case, we no longer need the $\log$ barrier, hence we omit the use of $\mu$ and remove the outer loop of  ACVI over $t\in[T]$.
By differentiating the remaining expression of the ${\bm{y}}$ sub-problem with respect to ${\bm{y}}$ and setting it to zero, we obtain:
\begin{align*}
    \argmin{{\bm{y}}} \ \frac{\beta}{2} \norm{ {\bm{y}} - {\bm{x}}_{k+1} - \frac{1}{\beta} {\bm{\lambda}}_k }^2
    = {\bm{x}}_{k+1} + \frac{1}{\beta} {\bm{\lambda}}_k
    \,.
\end{align*}
This implies that line $9$ of the exact ACVI algorithm (given in Appendix~\ref{app:background}) can be replaced with the solution of the ${\bm{y}}$ sub-problem \emph{without} the inequality constraints, and then projecting so as to satisfy the inequality constraints. We have:
\begin{equation*}
    {\bm{y}}_{k+1} = \Pi_\leq({\bm{x}}_{k+1}+\frac{1}{\beta}{\bm{\lambda}}_k) \,,
\end{equation*}
where the inequality constraints $\varphi_i(\cdot)$ are included in the projection.
We present the resulting procedure in detail in Algorithm~\ref{alg:log_free_acvi}, which we referr to as \emph{P-ACVI} as it uses projection.
In this scenario with simple $\varphi_i$, the ${\bm{y}}$ sub-problem is always solved exactly; nonetheless, when in addition the ${\bm{x}}$ sub-problem is solved approximately, we refer to this combination of P-ACVI and I-ACVI as  \emph{PI-ACVI}.

\begin{figure}[!htbp]
  \centering
  \begin{subfigure}[${\bm{x}}_k$ of PI-ACVI]{
  \includegraphics[width=0.45\linewidth,clip]{pics/iacvi_x_l20_c_bilin_.pdf}
  }
  \end{subfigure}
  \begin{subfigure}[${\bm{y}}_k$ of PI-ACVI]{
  \includegraphics[width=0.45\linewidth,trim={0cm .0cm 0cm .0cm},clip]{pics/iacvi_y_l20_c_bilin_.pdf}
  }
  \end{subfigure}
 \caption{\textbf{Intermediate iterates of PI-ACVI (Algorithm~\ref{alg:log_free_acvi}) on the 2D minmax game \eqref{eq:2d-bg}}. The boundary of the constraint set is shown in red. \textbf{Fig. (b)} depicts the ${\bm{y}}_k$ (from line $7$ in Algorithm~\ref{alg:log_free_acvi}) which we obtain through projections. In \textbf{Fig. (a)}, each spiral corresponds to iteratively solving the ${\bm{x}}_k$ sub-problem for $\ell=20$ steps (line $6$ in Algorithm~\ref{alg:log_free_acvi}).
 Jointly, these two trajectories of ${\bm{x}}$ and ${\bm{y}}$ iterates illustrate the ACVI dynamics: the two unconstrained ${\bm{x}}$ and a constrained ${\bm{y}}$ ``collaborate'' and eventually converge to the same point.
 Additional similar experiments that include other methods as well are available in Appendix~\ref{app:experiments}.}
 \label{fig:acvi-logfree-2d}
\end{figure}

\begin{algorithm}[!htb]
    \caption{P-ACVI: ACVI with simple inequalities.}
    \label{alg:log_free_acvi}
    \begin{algorithmic}[1]
        \STATE \textbf{Input:}  operator $F\colon\mathcal{X}\to \mathbb{R}^n$, constraints ${\bm{C}}{\bm{x}} = {\bm{d}}$ and projection operator $\Pi_\leq$ for the inequality constraints,
        hyperparameter $\beta>0$, and
        number of iterations $K$.
        \STATE \textbf{Initialize:} ${\bm{y}}_0\in \mathbb{R}^n$, ${\bm{\lambda}}_0\in \mathbb{R}^n$
        \STATE ${\bm{P}}_c \triangleq {\bm{I}} - {\bm{C}}^\intercal ({\bm{C}} {\bm{C}}^\intercal )^{-1}{\bm{C}}$ \hfill \mbox{where} ${\bm{P}}_c \in \mathbb{R}^{n\times n}$
        \STATE ${\bm{d}}_c \triangleq {\bm{C}}^\intercal({\bm{C}} {\bm{C}}^\intercal)^{-1}{\bm{d}}$  \hfill \mbox{where} ${\bm{d}}_c \in \mathbb{R}^n$
        \FOR{$k=0, \dots, K-1$}
            \STATE Set ${\bm{x}}_{k+1}$ to be the  solution of: ${\bm{x}} + \frac{1}{\beta} {\bm{P}}_c F({\bm{x}}) - {\bm{P}}_c {\bm{y}}_k + \frac{1}{\beta}{\bm{P}}_c{\bm{\lambda}}_k - {\bm{d}}_c = \boldsymbol{0}$ (w.r.t. ${\bm{x}}$) \label{alg-ln:x-sol-lf}
        \STATE ${\bm{y}}_{k+1} = \Pi_\leq({\bm{x}}_{k+1}+\frac{1}{\beta}{\bm{\lambda}}_k)$
        \STATE
        $
            {\bm{\lambda}}_{k+1}={\bm{\lambda}}_k+\beta ( {\bm{x}}_{k+1}-{\bm{y}}_{k+1})
        $
        \ENDFOR
    \end{algorithmic}
\end{algorithm}

\begin{figure*}[!htbp]
  \centering
  \begin{subfigure}[fixed error]{
  \includegraphics[width=0.25\linewidth,clip]{pics/acvi_hd_bilinear_time_main_w_legend_.pdf}
  \label{subfig:hdbg_cpu_vs_err}
  }
  \end{subfigure}
  \begin{subfigure}[rotational intensity]{
  \includegraphics[width=0.25\linewidth,trim={0cm .0cm 0cm .0cm},clip]{pics/acvi_hd_bilinear_eta_no_legend.pdf}
  \label{subfig:hdbg_rotational_intensity}
  }
  \end{subfigure}
  \begin{subfigure}[I-ACVI: effect of $K_0, K_+$ on number of iterations]{
  \includegraphics[width=0.4\linewidth,trim={0cm .0cm 0cm .0cm},clip]{pics/acvi_hdb_effect_of_k0.pdf}
  \label{subfig:hdbg_k0_k+_i-acvi}
  }
  \end{subfigure}
 \caption{
 \textbf{Comparison between I-ACVI, (exact) ACVI, and the projection-based algorithms on the high-dimensional \eqref{eq:high_dim_bg} problem.}
 \textbf{Fig. (a)}:  CPU time (in seconds; $y$-axis) to reach a given relative error ($x$-axis); while the rotational intensity is fixed to $\eta=0.05$ in \eqref{eq:high_dim_bg} for all methods.
 \textbf{Fig. (b)}: Number of iterations to reach a relative error of $0.02$ for varying values of the rotational intensity $\eta$ ($x$-axis). We fix the maximum number of iterations to $50$.

 \textbf{Observations from (a) \& (b) jointly}:
 While I-ACVI requires more iterations to converge relative to ACVI---from (b), it converges faster in terms of wall-clock time---from (a).

 \textbf{Fig. (c)}: joint impact of the number of inner-loop iterations $K_0$ at $t=0$, and different choices of inner-loop iterations for $K_+$ at any $t>0$, on the number of iterations needed to reach a fixed relative error of $10^{-4}$.
 Interestingly, we observe that irrespective of the selection of $K_+$, I-ACVI converges fast if $K_0$ is large enough.
 For instance, $(K_0=130, K_+=1)$ converges faster than $(K_0=20, K_+=20)$.

 We fix $\ell=10$ for all the experiments, in all (a), (b), and (c).
 See \S~\ref{sec:experiments} and Appendix~\ref{app:implementation} for discussion and details on the hyperparameters, respectively.
 }
 \label{fig:acvi-time-hdb}
\end{figure*}

\noindent\textbf{Last-iterate convergence of P-ACVI}.
The following theorem shows that the P-ACVI---Algorithm~\ref{alg:log_free_acvi}---has the same last-iterate rate as ACVI.
Given the proof of Theorem~\ref{thm:exact_acvi}---which focuses on a more general setting than P-ACVI---its proof follows readily; see Appendix~\ref{app:proofs} for details. We state it as a separate theorem, as it cannot be deduced directly from the statement of the former.

\begin{thm}[Last-iterate convergence rate of P-ACVI---Algorithm~\ref{alg:log_free_acvi}]\label{thm:log_free_rate}
Given a continuous operator $F\colon \mathcal{X}\to \mathbb{R}^n$, assume F is monotone on $\mathcal{C}_=$, as per Def.~\ref{def:monotone}. Let $({\bm{x}}_K, {\bm{y}}_K, {\bm{\lambda}}_K)$ denote the last iterate of Algorithm~\ref{alg:log_free_acvi}. Then for all $K \in {\mathbb N}_+$, it holds that:
\begin{equation}\label{eq:lf_rate} \notag
    \mathcal{G}({\bm{x}}_{K},\mathcal{C})\leq  \mathcal{O} (\frac{1}{\sqrt{K}})\,, \text{ and } \norm{{\bm{x}}^K-{\bm{y}}^K}\leq \mathcal{O} (\frac{1}{\sqrt{K}})\,.
\end{equation}
\end{thm}

\begin{rmk}
Notice that Theorem~\ref{thm:log_free_rate} requires fewer assumptions than Theorem.~\ref{thm:exact_acvi}.
This follows from the fact that the central path is removed in the P-ACVI Algorithm. Hence, assumption \textit{(ii)} in Theorem~\ref{thm:exact_acvi}---which is used to guarantee the existence of the central path (see Appendix~\ref{app:background})---is no longer needed.
\end{rmk}

\section{Experiments}\label{sec:experiments}

\noindent\textbf{Methods.}
We compare ACVI, Inexact-ACVI (I-ACVI), and Projected-Inexact-ACVI (PI-ACVI) with projected variants of Gradient Descent Ascent (P-GDA), Extragradient~\citep{korpelevich1976extragradient} (P-EG), Optimistic-GDA~\citep{popov1980} (P-OGDA), and Lookahead-Minmax~\citep{Zhang2019,chavdarova2021lamm} (P-LA).
For simplicity, we always use GDA as an inner optimizer for I-ACVI, PI-ACVI, and P-ACVI.

\noindent\textbf{Problems.}
We study the empirical performance of the above methods on three different problems:
\begin{itemize}[leftmargin=*,topsep=-1ex, itemsep=0ex]
    \item \textit{2D bilinear game}: a version of the bilinear game with $L_\infty$ constraints:
    \begin{align}\label{eq:2d-bg}\tag{2D-BG}
        &\min_{x_1 \in \bigtriangleup}\ \max_{x_2 \in \bigtriangleup} \ x_1 x_2 \,,
    \end{align}
    where $\bigtriangleup {=} \{ x \in \mathbb{R} | -0.4 \leq x \leq 2.4 \}$.
    \item \textit{High-dimensional bilinear game}: a bilinear game where each player is a $500$-dimensional vector. The iterates are constrained to the probability simplex. A parameter $\eta \in (0,1)$ controls the rotational component of the game (when $\eta=1$ the game is a potential game,  when $\eta=0$ the game is a Hamiltonian game):
    \begin{align}\tag{HBG}\label{eq:high_dim_bg}
        \underset{{\bm{x}}_1\in \bigtriangleup}{\min}\underset{{\bm{x}}_2\in \bigtriangleup}{\max} \eta {\bm{x}}_1^\intercal {\bm{x}}_1+\left( 1 - \eta \right) {\bm{x}}_1^\intercal {\bm{x}}_2- \eta {\bm{x}}_2^\intercal{\bm{x}}_2  \,, \\
        \quad
        \bigtriangleup {=} \{
        {\bm{x}}_i \in \mathbb{R}^{500}|{\bm{x}}_i \geq \boldsymbol{0}, \text{ and },{\bm{e}}^\intercal{\bm{x}}_i=1
        \}  \,. \nonumber
    \end{align}
    \item \textit{MNIST}. We train GANs on the MNIST~\citep{mnist} dataset. Similarly to \citet{acvi}, we use linear inequality constraints and no equality constraints, as follows:
    \begin{align}\tag{C-GAN}\label{eq:c-gan}
        &\min_{G \in \bigtriangleup_{{\bm{\theta}}}} \max_{D \in \bigtriangleup_{{\bm{\zeta}}}} \hspace{0.5em} \mathop{\mathbb{E}}_{{\bm{s}} \sim p_{d}} [\log{D({\bm{s}})}] + \mathop{\mathbb{E}}_{{\bm{z}}\sim p_z}[\log(1{-}D(G({\bm{z}})))],  \\
        &\text{where } \bigtriangleup_{{\bm{\theta}}} {=} \{{\bm{\theta}} | {\bm{A}}_1 {\bm{\theta}} \leq {\bm{b}}_1 \}, \ \bigtriangleup_{{\bm{\zeta}}} {=} \{{\bm{\zeta}} | {\bm{A}}_2 {\bm{\zeta}} \leq {\bm{b}}_2 \}  \,, \nonumber
    \end{align}
    with $p_z$, $p_d$ respectively the noise and data distributions, and where ${\bm{\theta}}$ and ${\bm{\zeta}}$ are the parameters of the generator and discriminator, respectively. $D$ and $G$ are the Generator and Discriminator functions, parameterized with ${\bm{\theta}}$ and ${\bm{\zeta}}$, respectively.  ${\bm{A}}_i\in \mathbb{R}^{100\times n_i}$ and ${\bm{b}}_i \in \mathbb{R}^{n_i}$, where $n_i$ is the number of parameters of $D$ or $G$.
\end{itemize}
See Appendix~\ref{app:implementation} for further details on the implementation.

\subsection{Inexact ACVI}

\paragraph{2D bilinear game.} In Fig.~\ref{fig:acvi-c-bilin-y}, we compare exact and inexact ACVI on the 2D bilinear game.
Rather than solving the sub-problems of I-ACVI until we reach appropriate accuracy of the solutions of the sub-problems, herein we fix the $K$ and $\ell$ number of iterations in I-ACVI.
We observe how I-ACVI can converge following the central path when the inner loop of I-ACVI over $k\in[K]$ is solved with sufficient precision. The two parameters influencing the convergence of the iterates to the central path are $K$ and $\ell$, where the latter is the number of iterations to solve the two sub-problems (line $8$ and line $9$ in Algorithm~\ref{alg:inexact_acvi}). Fig.~\ref{fig:acvi-c-bilin-y} shows that some relatively small values such as $K=20$ and $\ell=2$ are sufficient for convergence for this purely rotational game.
Nonetheless, as $K$ and $\ell$ decrease further, the iterates of I-ACVI may not converge.
This is in line with the sufficient condition presented in Theorem~\ref{thm:inexact_acvi}, which indicates that the sum of errors will be bounded only if $K$ is large. Hence, larger $K$ implies a smaller error.

\paragraph{HD bilinear game.} In Fig.~\ref{subfig:hdbg_cpu_vs_err} and Fig.~\ref{subfig:hdbg_rotational_intensity} we compare I-ACVI with ACVI and the projection-based algorithms, on the \eqref{eq:high_dim_bg} problem.
We observe that both ACVI and I-ACVI outperform the remaining baselines significantly, in terms of speed of convergence measured in both CPU time and the number of iterations.
Moreover, while I-ACVI requires more iterations than ACVI to reach a given relative error, those iterations are computationally much cheaper relative to solving exactly each sub-problem; hence, I-ACVI converges much faster than any other method.
Fig.~\ref{subfig:hdbg_k0_k+_i-acvi} is intended to show that the sub-problems of I-ACVI are suitable for warm-starting.
Interestingly, we observe that the choice of the number of iterations at the first step $t=0$ is relatively important.
Since at each iteration we initialize the variables at the previous solution, the convergence is improved if we solve the sub-problems as accurately as possible at $t=0$ because that decreases the initial error---which in turn helps to decrease the error of all subsequent iterations due to the warm-starting and the fact that the sub-problems change slowly. We will revisit this observation later in \S~\ref{subsec:warmup}.

\subsection{Projected-Inexact-ACVI}

\paragraph{2D bilinear game.} In Fig.~\ref{fig:acvi-logfree-2d} we show the dynamics of Projected Inexact ACVI (PI-ACVI) on the 2D game defined by~\eqref{eq:2d-bg}. Compared to ACVI in Fig.~\ref{fig:acvi-c-bilin-y}, the iterates converge to the solution without following the central path. A comparison with other optimizers is available in Appendix~\ref{app:experiments}.

\paragraph{MNIST.} In Fig.~\ref{fig:mnist_logfree-fid} we compare PI-ACVI and baselines on the \eqref{eq:c-gan} game trained on the MNIST dataset.
The projections are obtained using the greedy projection algorithm \citep{beck2017first}.
Since ACVI was derived primarily for handling general constraints, a natural question that arises is how it (and its variants) perform when the projection is fast to compute.
We observe that although the projection is fast to compute for these experiments, PI-ACVI still converges faster relative to the projection-based methods.
Moreover, it gives more consistent improvements over the standard GDA baseline, compared to the projected extragradient method, which improves upon GDA in cases when the rotational component of $F$ is large.

\subsection{Effect of Warm-up on I-ACVI and PI-ACVI}\label{subsec:warmup}

\paragraph{I-ACVI.}
The illustrative experiments in  Fig.~\ref{fig:acvi-c-bilin-y} motivate increasing the selected number of iterations $K$ only at the first iteration $t=0$---which we denote with $K_0$, so as to ensure that the early iterates are close to the central path. As a reminder, the $K$ steps (corresponding to the loop line $7$ in Algorithm~\ref{alg:inexact_acvi}) are bringing the iterates closer to the central path as $K \rightarrow \infty$ (see Appendix~\ref{app:proofs} for details).
After those $K_0$ steps, $\mu$ is decayed, which moves the solution of the problem along the central path.

For I-ACVI, from Fig.~\ref{subfig:hdbg_k0_k+_i-acvi}---where $\ell$ is fixed to $10$---we observed that regardless of the selected value of $K_+$ (that is selected $K$ at any $t>0$), it can be compensated by a large enough $K_0$.

\begin{figure}
  \centering
  \begin{subfigure}[FID, lower is better]{
  \includegraphics[width=0.48\linewidth,trim={0.25cm .25cm .29cm .25cm},clip]{pics/pi-acvi_mnist-fid_no_legend_1500s.pdf}
  }
  \end{subfigure}
  \begin{subfigure}[IS, higher is better]{
  \includegraphics[width=0.453\linewidth,trim={0.25cm .25cm .29cm .25cm},clip]{pics/pi-acvi_mnist-is_w_legend_1500.pdf}
  }
  \end{subfigure}
  \caption{\textbf{Experiments on the \eqref{eq:c-gan} game}, using GDA, EG, and Projected Inexact ACVI (PI-ACVI) on the MNIST dataset. All curves are averaged over $4$ seeds. \textbf{Fig. (a)}: Frechet Inception Distance (FID, lower is better)
  given CPU wall-clock time. \textbf{Fig. (b)}: Inception Score (IS, higher is better) given CPU wall-clock time. For both metrics, we observe how PI-ACVI is converging faster than EG and GDA. Moreover, we see that using a large $\ell$ for the first iteration (noted $\ell_0$) can give a significant advantage. The two PI-ACVI curves use the same $\ell_+=20$.
 }\label{fig:mnist_logfree-fid}
\end{figure}

\paragraph{PI-ACVI.} We similarly study the impact of the warmup technique for the PI-ACVI method (Algorithm~\ref{alg:log_free_acvi}). Compared to I-ACVI, this method omits the outer loop over $t\in[T]$.
Hence, instead of varying $K_0$, we experiment with increasing the first $\ell$ at iteration $k=0$, denoted by $\ell_0$.
In Fig.~\ref{fig:mnist_logfree-fid} we solve the constrained MNIST problem with PI-ACVI using either $\ell_0=500$ or $\ell_0=100$, $\ell_+$ is set to $20$ in both cases. We observe that using a larger $\ell_0$ leads to notably faster convergence.

\paragraph{Overall conclusion.} We consistently observed that using a large $K_0$ or I-ACVI, or large $l_0$ for PI-ACVI, aids the convergence.
On the other hand, $l$ and $K_+$ for I-ACVI, or $l_+$ for PI-ACVI have a lesser influence.
See Appendix~\ref{app:experiments} for additional experiments and discussions.

\section{Conclusion}\label{sec:conclusion}

In this paper, we revisit the state-of-the-art ACVI method derived to handle general constraints in the setting of constrained variational inequality problems.
We showed that the last iterate of ACVI converges at a rate of order $\mathcal{O}(1/\sqrt{K})$ for monotone VIs. Our theoretical result is novel in that it does not rely on a first-order smoothness assumption for the operator.
As the sub-problems of ACVI cannot always be solved in closed form and may need to be solved approximately, we also studied an inexact ACVI (I-ACVI) algorithm that uses warm-starting for its sub-problems.
We show that the last iterate of I-ACVI recovers the same convergence rate as ACVI for monotone VIs, provided that the errors stay bounded.
Motivated by machine learning applications, we focused on the special case in which the inequality constraints are simple in the sense that, their projection is fast to compute.
We derived a variant of ACVI, referred to as P-ACVI, and showed that P-ACVI converges with a $\mathcal{O}(1/\sqrt{K})$ rate.
Finally, our experiments
\textit{(i)} provided insights into the dynamics of I-ACVI when the sub-problems are solved approximately:
\textit{(ii)} we showed the impact of the warm-start technique, and
\textit{(iii)} we demonstrated the advantages of these ACVI variants relative to the standard projection-based algorithms.

\subsubsection*{Acknowledgements}
We acknowledge support from the Swiss National Science Foundation (SNSF), grant P2ELP2\_199740, and from the Mathematical Data Science program of the Office of Naval Research under grant number N00014-18-1-2764.

redpajama_set_name: RedPajamaArXiv