V_{j}(0,\ldots,0)=0\\}\cup\\{i\\}$. Notice that all coordinates $j\in A$ admit
$V_{j}(0,\ldots,0)=0$ and Assumption 3 is violated.

##  Appendix I Discrete-Time Dynamics

We begin with the adaptation of the Dynamics 2 to discrete-time algorithms.
The main change we need to make is to change the step 5 of Dynamics 2 to the
following $z^{(k+1)}\leftarrow z^{(k)}+D^{i}_{S}(z^{(k)})$. But then we need
also to adapt the notion of exit points as follows.

######  Definition 10 ($(\varepsilon,\gamma)$-Exit Points).

Suppose $i\in[n]$, $S\subseteq[i-1]$ and $x^{\prime}$ is a point where
coordinates in $S$ are zero-satisfied and coordinates in $[i-1]\setminus S$
are boundary-satisfied. Then $x^{\prime}$ is an exit point for epoch $(i,S)$
iff it satisfies one of the following:

  * •

(Good Exit Point): Coordinate $i$ is almost satisfied at $x^{\prime}$, i.e.,
$\lVert V_{i}(x^{\prime})\rVert\leq\varepsilon$, or $x^{\prime}_{i}=0$ and
$V_{i}(x^{\prime})<\varepsilon$, or $x^{\prime}_{i}=1$ and
$V_{i}(x^{\prime})>-\varepsilon$.

  * •

(Bad Exit Point): For some $j\in S\cup\\{i\\}$, it holds that
$(D^{i}_{S}(x^{\prime}))_{j}>0$ and $x^{\prime}_{j}=1$, or
$(D^{i}_{S}(x^{\prime}))_{j}<0$ and $x^{\prime}_{j}=0$; in other words, if the
dynamics for epoch $(i,S)$ were to continue from $x^{\prime}$ onward, they
would violate the constraints.

  * •

(Middling Exit Point): Let $x^{\prime\prime}=x^{\prime}+\gamma
D^{i}_{S}(x^{\prime})$ and for some $j\in[i-1]\setminus S$, one of the
following holds: $V(x^{\prime\prime}_{j})>0$ and $x^{\prime}_{j}=0$, or
$V(x^{\prime\prime}_{j})<0$ and $x^{\prime}_{j}=1$; in other words, if the
dynamics for epoch $(i,S)$ were to continue from $x^{\prime}$ onward, some
boundary-satisfied coordinate would become unsatisfied.

We next present our solution concept for the discrete-time dynamics.

######  Definition 11.

We say that a point $x$ is an $\alpha$-approximate solution of
$\mathrm{VI}(V,[0,1]^{n})$ if and only if $V(x)^{\top}(x-y)\leq\alpha$.

We also define $\Pi:\mathbb{R}^{n}\to[0,1]^{n}$ to be the Euclidean projection
of a vector in $\mathbb{R}^{n}$ to the hypercube $[0,1]^{n}$. In Dynamics 4 we
define our discrete-time dynamics for which we show Theorem 2.

Dynamics 4 Discrete STay-ON-the-Ridge with step size $\gamma$ and errors
$\alpha$, $\varepsilon$

1: Initially $x^{(0)}\leftarrow(0,\ldots,0)$, $i\leftarrow 1$,
$S\leftarrow\emptyset$, $m\leftarrow 0$.

2: while $x^{(m)}$ is not an $\alpha$-approximate VI solution do

3: $z^{(0)}\leftarrow x^{(m)}$

4: while $\Pi(z^{(k)})$ is not an $(\varepsilon,\gamma)$-exit point as per
Definition 10 do

5: $z^{(k+1)}\leftarrow z^{(k)}+\gamma\cdot D^{i}_{S}(z^{(k)})$

6: $k\leftarrow k+1$

7: end while

8: $x^{(m+1)}\leftarrow\Pi(z^{(k)})$

9: if $x^{(m+1)}$ is a (Good Exit Point) as in Definition 10 then

10: if $i$ is zero-satisfied at $x{(t+1}$ then

11: Update $S\leftarrow S\cup\\{i\\}$.

12: end if

13: Update $i\leftarrow i+1$.

14: else if $x^{(m+1)}$ is a (Bad Exit Point) as in Definition 10 for $j=i$
then

15: Update $i\leftarrow i-1$ and $S\leftarrow S\setminus\\{i-1\\}$.

16: else if $x^{(m+1)}$ is a (Bad Exit Point) as in Definition 10 for $j\neq
i$ then

17: Update $S\leftarrow S\setminus\\{j\\}$.

18: else if $x^{(m+1)}$ is a (Middling Exit Point) as in Definition 10 for
$j<i$ then

19: Update $S\leftarrow S\cup\\{j\\}$.

20: end if

21: Set $m\leftarrow m+1$.

22: end while

23: return$x^{(m)}$

######  Theorem 2.

We assume Assumptions 1, 2, and 3. For every $\alpha>0$, there exist constants
$\varepsilon$, $\gamma$, $\bar{M}$, $K$ such that Dynamics 4 with step size
$\gamma$ and error $\varepsilon$ finish after $M\leq\bar{M}$ iterations of the
while-loop at line 2 and it holds that $x^{(M)}$ is an $\alpha$-approximate
solution of $\mathrm{VI}(V,[0,1]^{n})$. Additionally, for every iteration
$m\leq M$ of the while-loop in line 2, the while-loop in line 4 does at most
$K$ iterations.

###### Proof.

The main idea of the proof is to show that, for sufficiently small step size
$\gamma$, the Dynamics 4 will always stay in Euclidean distance at most
$\delta:=\alpha/\Lambda$ from the continuous-time Dynamics 2. Then, since
Dynamics 2 converge to a solution of $\mathrm{VI}(V,[0,1]^{n})$ (see Theorem
1) and since $V$ is $\Lambda$-Lipschitz we conclude that the discrete Dynamics
4 will converge to a point that is an $\alpha$-approximate solution of
$\mathrm{VI}(V,[0,1]^{n})$.

The proof of Theorem 2 boils down to showing that there exists a step size
$\gamma$ and an error $\varepsilon$ such that Dynamics 4 are always
$\alpha/\Lambda$ close to Dynamics 2. To show this we use standard tools for
the error of Euler discretized differential equations. In particular we use
the following theorem.

######  Theorem 3 (Section 1.2 of [Ise09]).

Let $y(t)\in\mathbb{R}^{n}$ be the solution to the differential equation
$\dot{y}=G(y)$ with initial condition $y(0)=w$, where $G$ is a Lipschitz map
$\mathbb{R}^{n}\to\mathbb{R}^{n}$. Let also $y^{(k+1)}=y^{(k)}+\gamma\cdot
G(y^{(k)})$, with initial condition $y^{(0)}=w^{\prime}$, with $\lVert
w-w^{\prime}\rVert_{2}\leq\zeta$. Then, for every $\eta>\zeta$ and every
$T>0$, there exists a step size $\gamma>0$ such that

$\lVert y(k\cdot\gamma)-y^{(k)}\rVert_{2}\leq\eta\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \text{ for all
}\leavevmode\nobreak\ \leavevmode\nobreak\ 0\leq k\leq T/\gamma.$

Additionally, if the above holds for some $\gamma=\bar{\gamma}$ then it also
holds for all $\gamma\leq\bar{\gamma}$.

Given that $D^{i}_{S}(x)$ is Lipschitz (see Lemma 11) we can apply Theorem 3
to the while-loop of line 4 in Dynamics 4 and inductively show that $x^{(m)}$
of Dynamics 4 is close to the corresponding point of Dynamics 2.

Let $\tau_{j}$ be the value of the $\tau_{\mathrm{exit}}$ variable after the
$j$-th time that the while-loop of line 4 in Dynamics 2 has ended. For every
$i\in\mathbb{N}$ we define $t_{i}=\sum_{j=1}^{i}\tau_{i}$. Our goal is to show
that the $\lVert x^{(m)}-x(t_{m})\rVert_{2}$ is small. We do this inductively.
For the base of our induction observe that $x^{(0)}=x(0)$. Now assume that we
have chosen a step size $\gamma_{m}$ and that we have achieved $\lVert
x^{(m)}-x(t_{m})\rVert_{2}\leq\zeta_{m}$ Also we assume as an inductive
hypothesis that before the beginning of $m$th while-loop of line 4 we have
same epoch $(i,S)$ in both the execution of Dynamics 2 and the execution of
Dynamics 4. Then, in the next execution of the while-loop of line 4 we have
that $\lVert z^{(0)}-z(0)\rVert_{2}\leq\zeta_{m}$. Also, from the proof of
Theorem 1 we know that there exists a finite $\tau_{m+1}$ such that
$z(\tau_{m+1})$ is an exit point. Hence, we can apply Theorem 3 and we get
that for every $\eta>\zeta_{m}$, there exists a step size $\Gamma_{m+1}$ such
that

$\lVert
z^{(k)}-z(k\cdot\Gamma_{m+1})\rVert_{2}\leq\zeta_{m}+\frac{\delta}{2^{m+1}}:=\zeta_{m+1}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \text{for all
}\leavevmode\nobreak\ \leavevmode\nobreak\ 0\leq
k\leq\tau_{m+1}/\Gamma_{m+1}.$

Since $x(t_{m}+\tau_{m+1})=z(\tau_{m+1})$ we get that $\lVert
x^{(m+1)}-x(t_{m+1})\rVert_{2}\leq\zeta_{m+1}$. The only thing that is missing
is to show that the update on $(i,S)$ will be the same in the continuous and
the discrete dynamics. Observe that if an exit point happens in the continuous
dynamics then due to the Lipschitzness of $V$ the same exit point has to occur
in as an $(\zeta_{m+1},\Gamma_{m+1})$-exit point in the discrete dynamics. Now
repeating the argument from the proof of Theorem 1 we can easily show that it
is impossible for more than one exit events to happen even in the discrete
case. In particular, this follows easily from Assumption 2 and Assumption 1.
Hence, the update on $(i,S)$ will be the same. Then, we set
$\gamma_{m+1}=\min\\{\gamma_{m},\Gamma_{m+1}\\}$ and due to the last sentence
of Theorem 3 we know that using the step size $\gamma_{m+1}$ in all the steps
before $m+1$ it will result only to better guarantees for the distance between
$x^{(\ell)}$ and $x(t_{\ell})$ and therefore our induction follows. At the
last iteration $M$ we will have

$\lVert
x^{(M)}-x(t_{M})\rVert_{2}\leq\zeta_{M}\leq\delta\left(\sum_{j=1}^{m}\frac{1}{2^{j}}\right)\leq\delta.$

Since $x(t_{M})$ is a solution to $\mathrm{VI}(V,[0,1]^{n})$ we have that
$x^{(M)}$ is an $\alpha$-approximate solution to $\mathrm{VI}(V,[0,1]^{n})$
and the step size that we used is $\gamma=\gamma_{M}$.

Finally, the quantities $\bar{M}$ and $K$ are bounded by the constant
$\bar{T}$ of Theorem 1 divided by $\gamma=\gamma_{m}$. ∎