of 4. We prove the lemma by induction on \(t\); the base case, for \(t=5\), is proved in 21 in 7 and here we focus on the induction step. For this, fix any \(t \geq 5\) and assume the that the lemma holds for \(w_t\); we will prove the claim for \(w_{t+1}\).

First, for \(\ell_1\), note that, by the hypothesis of the induction, for every \(2\leq k\leq T\), \({w_t}^{(k)}=c\eta u_0\) for \(c\leq\frac{1}{2}\), thus, by 5, for every \(i\), \(\nabla \ell_{1}(w_t,V_i)=0\).

For \(\ell_2\), we know that, for every \(i\), \[\begin{align} {\br[1]{\nabla \ell_{2}(w_t,(V_i,j_i))}}^{(k)}=\begin{cases} - \phi(V_i,j_{i}) &\quad k={0};\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\] For \(\ell_{3}\), using the hypothesis of the induction, which implies that \({w_t}^{(1)}=c\eta u_0\) for \(|c|\leq1\) and \({w_{t}}^{({{0}})}=\frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i)\), by 6, we get that, \[\begin{align} {\br[1]{\nabla \ell_{3}(w_t)}}^{(k)}=\begin{cases} \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_{i}) &\quad k={0};\\ -\frac{\epsilon}{4T^2}u_0 &\quad k=1;\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\] For \(\ell_4\), by the hypothesis of the induction we know that \({w_t}^{(1)}=\br[1]{-\frac{3}{8}+\frac{(t-2)}{4}\frac{\epsilon}{T^2}}\eta u_0\), thus, \({w_t}^{(1)}=c\eta u_0\) for \(-\frac{3}{8}c\leq 0\). Then the conditions of 7 hold for \(m=t-2\), thus, it holds that, \[\begin{align} {\br[1]{\nabla \ell_4(w_{t})}}^{(k)} = \begin{cases} \frac{3}{8}u_0 &\quad k=t-2;\\ -\frac{1}{2}u_0 &\quad k=t-1;\\ 0 &\quad \text{otherwise} .\end{cases} \end{align}\] Combining all together, we get that, \[\begin{align} {\br[1]{\nabla \widehat{F}(w_t)}}^{(k)}=\begin{cases} -\frac{\epsilon}{4T^2} u_{0} &\quad k=1;\\ \frac{3}{8} u_{0} &\quad k=t-2; \\ -\frac{1}{2} u_{0} &\quad k=t-1; \\ 0 &\quad \text{otherwise}, \end{cases} \end{align}\] where \(u_0\in U \setminus \bigcup_{i=1}^n V_i\), and the lemma follows. ◻

of 3 (\(m=1\) case). We prove the theorem under the condition that \(\cE\) occurs. First, in 22 in appendix 7 we know that for every \(t\), we have that \(\|w_t\|\leq 1\).

Next, \(w_T\) is as in ?? . Now, we notice that if a vector \(v\in U\) is in a set \(V\subseteq U\), it holds that \(\max_{u\in V} \langle u, v\rangle=1\). However, if \(v\notin V\), it holds that \(\max_{u\in V} \langle u,v\rangle=\frac{1}{8}\). As a result, by the fact that every vector for a fresh pair \((V,j)\sim D\), \(u_0\in U\) is in \(V\) with probability \(\frac{1}{2}\), the following holds: \[\begin{align} \E_V\sqrt{\sum_{k=2}^T\max\cbr{ \frac{3\eta}{32}, \max_{u\in V} \langle u,{w_T}^{(k)}\rangle }^2} &\geq \E_V\sqrt{\sum_{k=2}^{T-3}\max\cbr{ \frac{3\eta}{32}, \max_{u\in V} \langle u,{w_T}^{(k)}\rangle }^2} \\&= \E_V\sqrt{(T-4)\max\cbr{ \frac{3\eta}{32}, \max_{u\in V} \langle u, \frac{\eta}{8}u_{0}\rangle }^2} \\&= \frac{\eta\sqrt{T-4}}{8}\E_V\max\cbr{ \frac{3}{4}, \max_{u\in V} \langle u, u_{0}\rangle } \\&\geq \frac{\eta\sqrt{T-4}}{8}\left(\frac{3}{4}\Pr(u_{0}\notin V) + \Pr(u_{0}\in V)\right) \\&= \frac{7\eta}{64}\sqrt{T-4} . \end{align}\] Moreover, we notice that for every \(t\), \(V\subseteq U\) and \(j\in[n^2]\), \(\ell_2(w_t, (V,j))\geq-\|{w_{t}}^{({{0}})}\|\geq -\eta\), \(\ell_3(w_t)\geq \delta_1\) and \(\ell_4(w_t)\geq \delta_2\), thus, it holds that \[\begin{align} F(w_T) &\geq \frac{7\eta}{64}\sqrt{T}+\delta_1+\delta_2-\eta \geq \eta\left(\frac{7}{64}\sqrt{T}-1\right) ;\\ F(w_*) &\leq F(0) \leq \frac{3\eta}{32}\sqrt{T}+\eta . \end{align}\] Then, since \(T\) is assumed large enough so that \(2 \leq \frac{1}{128} \sqrt{T}\), we conclude \[\begin{align} F(w_T) - F(w_*) \geq \eta \br{ \frac{1}{64}\sqrt{T}-2 } \geq \frac{\eta}{128}\sqrt{T} . &\qedhere \end{align}\] ◻

of 10. We assume that \(\cE'\) holds and prove the lemma by induction on \(t\). We begin from the basis of the induction, \(t=4\), which is proved in 26 in 8. Now, we assume the hypothesis of the induction, that the lemma holds for iteration \(t\) and turn to show the required for iteration \(t+1\).

First, we notice that for every \(2\leq k\leq t-1\), \({w_t}^{(k)}=c\eta u_k\) for \(c\leq \frac{1}{2}\) and every such \(u_k\) holds \(u_k\in \bigcap_{i=1}^{k-1}V_i\cap \bigcap_{i=k}^{n}\overline{V_i}\), and for every \(t\leq k\leq T\), \({w_t}^{(k)}=0\). Then, by 11, we have that \(\nabla\ell^{\text{SGD}}_1(w_t,V_t)=0.\)

Second, \(\ell^{\text{SGD}}_3\) is a linear function, thus, \[\nabla {\ell^{\text{SGD}}_3(w_t,V_t)}^{(s)}=\begin{cases} -\frac{1}{n^3}u_1 &s=1 \\ -\frac{1}{4n^2}\phi(V_t,1)& s= {0},1 \\0 & \text{otherwise}.\end{cases}\] Third, For \(\ell^{\text{SGD}}_2(w_t,V_t)\), we notice for \(m=t-1\geq 3\) it holds that \({w_t}^{(1)}=c\eta u_1\) for \(-\frac{3}{8}\leq c\leq 0\) and \(u_1\in U\), for every \(2\leq k\leq m-1\), \({w_t}^{(k)}=\frac{1}{8}\eta u_k\) such that every \(u_k\) holds \(u_k\in \bigcap_{t=1}^{k-1}V_t\cap \bigcap_{t=k}^{n}\overline{V_t}\), \({w_t}^{(m)}=\frac{1}{2}\eta u_m\) where \(u_m\) holds \(u_m\in \bigcap_{t=1}^{m-1}V_t\cap \bigcap_{i=m}^{n}\overline{V_t}\), and for every \(m+1\leq k\leq T\), \({w}^{(k)}=0\). Moreover, \(w_t\) holds \({w}^{(0,m)}=\frac{\eta}{4n}\psi^*_m\), \(\|{w_t}^{(0,1)}\|\leq \eta\) and for every \(k\notin \{m,1\}\), \({w_t}^{(0,k)}=0\). Then, by 12, we get that, we have for \(k\neq 0\), \[\begin{align} {\nabla \ell^{\text{SGD}}_2(w_t,V_t)}^{(k)}= \begin{cases} \frac{3}{8} u_{t-1} &\quad k=t-1 \\ -\frac{1}{2} \alpha(\psi_{t-1}^*) &\quad k=t \\ 0 &\quad k\notin \{t-1,t\} \end{cases} \end{align}\] and, \[\begin{align} {\nabla \ell^{\text{SGD}}_2(w_t,V_t)}^{({0}, k)}= \begin{cases} \frac{1}{4n^2}\sum_{i=1}^{t-1}\phi(V_i,i)&\quad k= m \\ -\frac{1}{4n^2}\sum_{i=1}^{t}\phi(V_i,i)&\quad k= m+1 \\ 0&\quad k\notin \{m,m+1\}. \end{cases} \end{align}\] Now, by 23, for \(j=\argmin_{i}\{i:v_i \in \bigcap_{i=1}^{t-1} V_i\}\), we get that \[\begin{align} \alpha(\psi_{t-1}^*)=v_{j}\in \bigcap_{i=1}^{t-1} V_i. \end{align}\] We notice that \(\bigcap_{i=1}^{t-1} V_i=P_t\) and thus \(\alpha(\psi_{t-1}^*)=J_t\). Then, by \(\cE'\), \(\alpha(\psi_{t-1}^*)\) also holds \(\alpha(\psi_{t-1}^*)\in S_{t}\). Combining the above together, we get, for \(u_t=\alpha(\psi_{t-1}^*)\in P_t\cap S_t\), \[\begin{align} {\nabla f(w_t,V_t)}^{(k)}= \begin{cases} - \frac{1}{n^3}u_1&\quad k=1\\ \frac{3}{8} u_{t-1} &\quad k=t-1 \\ -\frac{1}{2} u_{t} &\quad k=t \\ 0 &\quad k\notin \{1,t-1,t\}, \end{cases} \end{align}\] and, \[\begin{align} {\nabla f(w_t,V_t)}^{({0}, k)}= \begin{cases} -\frac{1}{4n^2}\phi(V_3,1) &\quad k=1 \\ \frac{1}{4n^2}\sum_{i=1}^{t-1}\phi(V_i,i)&\quad k=t-1 \\ -\frac{1}{4n^2}\sum_{i=1}^{t}\phi(V_i,i)&\quad k=t \\ 0&\quad k\notin \{1,t-1,t\}, \end{cases} \end{align}\] and the lemma follows. ◻

of 5. Let \(\overline{w_{T,m}}\) be the \(m\)-suffix average of \(GD\) when is applied on \(\widehat{F}\). Let \(\overline{w_*}=\argmin_w F(w)\). By 14, we know that, with probability of at least \(\frac{1}{6}\), \(\cE\) occurs and \(w_{T,m}=\overline{w_{T,m}}\). Then, by 3 and 32, \[\begin{align} \frac{\eta}{3200}\sqrt{T}&\leq F(\overline{w_{T,m}})-F(\overline{w_*}) \\&=F(w_{T,m})-F(\overline{w_*}) \\&\leq \tilde{F}(w_{T,m})+5\delta-\tilde{F}(\overline{w_*})+5\delta \\&\leq \tilde{F}(w_{T,m})+5\delta-\tilde{F}(w_*)+5\delta, \end{align}\] and, \[\begin{align} \tilde{F}(w_{T,m})-\tilde{F}(w_*)&\geq \frac{\eta}{3200}\sqrt{T}-\frac{10\eta\epsilon}{128T^2} \\&\geq \frac{\eta}{3200}\sqrt{T}-\frac{\eta}{10T^2} \\&\geq \frac{\eta}{6400}\sqrt{T}. \end{align}\] ◻

of 1. We know that \(\eta\leq \frac{1}{5\sqrt{T}}\). First, by 5, we know that for Unprojected \(GD\) and \(d_1=178nT+2n^2\), there exist a distribution \(\mathcal{D}\) over a probability space \(Z\), a constant \(C_1\) and a loss function \(\tilde{f}:\R^{d_1}\times Z\to \R\) such that, with probability of at least \(\frac{1}{6}\), \[\tilde{F}(w_{T,m})-\tilde{F}(w_*)\geq C_1\eta\sqrt{T.}\] Second, by 35, we know that for Unprojected \(GD\) and \(d_2=\max(25\eta^2T^2,1)\), there exist a constant \(C_2\) and a deterministic loss function \(\tilde{f}^{\text{OPT}}:\R^{d_2}\to \R\) such that \[\tilde{f}^{\text{OPT}}(w_{T,m})-\tilde{f}^{\text{OPT}}(w_*)\geq C_2\min\left(1,\frac{1}{\eta T}\right)\] Now, let \(C=\frac{1}{2}\min \left(C_1, C_2\right)\). If \(\eta\geq T^{-\frac{3}{4}}\), then, \(\eta\sqrt{T}\geq \min(1,\frac{1}{\eta T})\), and we get, \[\tilde{F}(w_{T,m})-\tilde{F}(w_*)\geq C\left(\eta\sqrt{T} +\min\left(1,\frac{1}{\eta T}\right)\right)\geq C\left( \min\left(1,\eta\sqrt{T}+\frac{1}{\eta T}\right)\right).\] Otherwise, we get that, \[\tilde{f}^{\text{OPT}}(w_{T,m})-\tilde{f}^{\text{OPT}}(w_*)\geq C\left(\eta\sqrt{T} +\min\left(1,\frac{1}{\eta T}\right)\right)\geq C\left( \min\left(1,\eta\sqrt{T}+\frac{1}{\eta T}\right)\right).\] Since in both cases, by 35 5, \(w_t\in \mathbb{B}^{d}\) for every \(t\in[T]\), the theorem is applicable also for Projected GD. ◻

of 6. Let \(\overline{w_{n,m}}\) be the \(m\)- suffix average of \(SGD\) when is applied on \(f^{\text{SGD}}\) and let \(\overline{\widehat{w}_*}=\argmin_w \widehat{F}^{\text{SGD}}(w)\). By 16, we know that, with a probability \(\frac{1}{2}\) ,\(w_{n,m}=w^\text{SGD}_{n,m}\). Then, by 4 and 32, \[\begin{align} \frac{\eta}{64000}\sqrt{n}&\leq \widehat{F}^{\text{SGD}}(\overline{w_{n,m}})-\widehat{F}^{\text{SGD}}(\overline{\widehat{w}_*}) \\&=\widehat{F}^{\text{SGD}}(w_{n,m})-\widehat{F}^{\text{SGD}}(\overline{\widehat{w}_*}) \\&\leq \widehat{\tilde{F}}^{\text{SGD}}(w_{n,m})+4\delta-\widehat{\tilde{F}}^{\text{SGD}}(\overline{\widehat{w}_*})+4\delta \\&\leq \widehat{\tilde{F}}^{\text{SGD}}(w_{n,m})+4\delta-\widehat{\tilde{F}}^{\text{SGD}}(\widehat{w}_*)+4\delta, \end{align}\] and, \[\begin{align} \widehat{\tilde{F}}^{\text{SGD}}(w_{n,m})-\widehat{\tilde{F}}^{\text{SGD}}(\widehat{w}_*)&\geq \frac{\eta}{64000}\sqrt{n}-\frac{\eta\epsilon}{4n^3} \\&\geq \frac{\eta}{64000}\sqrt{n}-\frac{\eta}{4n^3} \\&\geq \frac{\eta}{128000}\sqrt{n}. \end{align}\] ◻

proof of 2. We know that \(T=n\) and \(\eta\leq \frac{1}{5\sqrt{T}}\). First, by 6, we know that for Unprojected \(SGD\) and \(d_1=712n^2\log n+2n^2\), there exist a distribution \(\mathcal{D}^{\text{SGD}}\) over a probability space \(Z\), a constant \(C_1\) and a loss function \(\tilde{f}^{\text{SGD}}:\R^{d_1}\times Z\to \R\) such that, with probability of at least \(\frac{1}{2}\), \[\widehat{\tilde{F}}^{\text{SGD}}(w_{T,m})-\widehat{\tilde{F}}^{\text{SGD}}(\widehat{w}_*)\geq C_1\eta\sqrt{T.}\] Second, by 35, we know that for Unprojected \(SGD\) and \(d_2=\max(25\eta^2T^2,1)\), there exist a constant \(C_2\) and a deterministic loss function \(\tilde{f}^{\text{OPT}}:\R^{d_2}\to \R\) such that \[\tilde{f}^{\text{OPT}}(w_{T,m})-\tilde{f}^{\text{OPT}}(\widehat{w}_*)\geq C_2\min\left(1,\frac{1}{\eta T}\right)\] Now, let \(C=\frac{1}{2}\min \left(C_1, C_2\right)\). If \(\eta\geq T^{-\frac{3}{4}}\), then, \(\eta\sqrt{T}\geq \min(1,\frac{1}{\eta T})\), and we get, \[\widehat{\tilde{F}}^{\text{SGD}}(w_{T,m})-\widehat{\tilde{F}}^{\text{SGD}}(\widehat{w}_*)\geq C\left(\eta\sqrt{T} +\min\left(1,\frac{1}{\eta T}\right)\right)\geq C\left( \min\left(1,\eta\sqrt{T}+\frac{1}{\eta T}\right)\right).\] Otherwise, we get that, \[\tilde{f}^{\text{OPT}}(w_{T,m})-\tilde{f}^{\text{OPT}}(\widehat{w}_*)\geq C\left(\eta\sqrt{T} +\min\left(1,\frac{1}{\eta T}\right)\right)\geq C\left( \min\left(1,\eta\sqrt{T}+\frac{1}{\eta T}\right)\right).\] Since in both cases, by 35 6, \(w_t\in \mathbb{B}^{d}\) for every \(t\in[T]\), the theorem is applicable also for Projected SGD. ◻

of 1. Let \(r=2^{\frac{-d'}{178}}\). For every \(1\leq i\leq r\) and \(1\leq j\leq d'\) we define the random variable \(u_i^j\) be a random variable to be \(\frac{1}{\sqrt{d'}}\) with probability \(\frac{1}{2}\) and \(-\frac{1}{\sqrt{d'}}\) with probability \(\frac{1}{2}\). Then, for every \(1\leq i\leq r\), we define the vector \(u_i\) which its \(j\)th entry is \(u_i^j\) and look at the set \(U=\{u_1,u_2,...u_{r}\}\). This set will hold the required property with positive probability. First, for every \(i\neq k\), \(\langle u_i,u_k\rangle\) are sums of \(d\) random variables that taking values in \([-\frac{1}{d'},\frac{1}{d'}]\) with \(\E\langle u_i,u_k\rangle=0\). Then by Hoeffding’s inequality, \[\begin{align} Pr(|\langle u_i,u_k\rangle|\geq \frac{1}{8})&\leq 2e^{\frac{-2\left(\frac{1}{8}\right)^2}{d'\cdot \frac{4}{d'^2}}}=2e^{-\frac{d'}{128}} \end{align}\] Then, by union bound on the \(\binom{r}{2}\) pairs of vectors in \(U\), \[\begin{align} Pr(\exists i,k \;|\langle u_i,u_k\rangle|\geq \frac{1}{8})&\leq 2e^{-\frac{d'}{128}}\cdot \binom{r}{2}< 2e^{-\frac{d'}{128}}\cdot \frac{1}{2}r^2\leq 1. \end{align}\] ◻

Proof. First, we consider an arbitrary enumeration of \(P(U)=\{V^1,...V^{|P(U)|}\}\) and define \(g:P(U)\to \R^2\), \(g(V^i)= \left(\sin\left(\frac{2\pi i}{|P(U)|}\right),\cos\left(\frac{2\pi i}{|P(U)|}\right)\right)\). Now, we refer to a vector \(a\in \R^{2n^2}\) as a concatenation of \(n^2\) vectors in \(\R^2\), \({a}^{(1)},...,{a}^{(n^2)}\). Then, we define \(\delta=1-\cos\left(\frac{2\pi}{|P(U)|}\right)\), \(\epsilon=\frac{\delta}{n^2}\) and \[{\phi(V,j)}^{(i)}= \left\{ \begin{array}{cc} g(V) & i=j \\ 0 & \text{otherwise} \end{array} \right.\] As a result, for every \(V^i,j\) it holds that \[\begin{align} \|\phi(V^i,j)\|=\|g(V^i)\|=\sqrt{\sin\left(\frac{2\pi i}{|P(U)|}\right)^2+\cos\left(\frac{2\pi i}{|P(U)|}\right)^2}=1 \end{align}\] Moreover, if \(j_1\neq j_2\), \[\begin{align} \langle \phi(V^i,j_1),\phi(V^i,j_2)\rangle =0, \end{align}\] and if \(i>k\), \[\begin{align} \langle \phi(V^i,j),\phi(V^k,j)\rangle=&\langle g(V^i), g(V^k)\rangle \\&=\sin\left(\frac{2\pi i}{|P(U)|}\right)\sin\left(\frac{2\pi k}{|P(U)|}\right) + \cos\left(\frac{2\pi i}{|P(U)|}\right)\cos\left(\frac{2\pi k}{|P(U)|}\right) \\&=\cos\left(\frac{2\pi (i-k)}{|P(U)|}\right) \\&\leq \cos\left(\frac{2\pi}{|P(U)|}\right)\\&=1-\delta \end{align}\] We notice that \(0<\delta< 1\). Now, we consider an arbitrary enumeration of \(U=\{v_1,...v_{|U|}\}\), and define the following set \(\Psi\subseteq \R^{2n^2}\) and the following two mappings \(\sigma: R^{2n^2}\to P(U), \alpha: R^{2n^2}\to U\), \[\Psi = \{ \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i): \forall i\; V_i\;\subseteq U,\;j_i\in [n^2] \text{ and } i\neq l \implies j_i\neq j_\ell\}\] Note that, for every \(\psi \in \Psi\), \[\|\psi\|=\|\frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\|\leq \frac{1}{n}\sum_{i=1}^n \|\phi(V_i,j_i)\|=1.\] Then, for every \(a\in \R^{2n^2}\) and \(j\in[n^2]\), we denote the index \(q(a,j)\in [|P(U)|]\) as \[q(a,j)=\argmax_{r}\langle g(V_r), {a}^{(j)}\rangle,\] and define the following mapping \(\sigma:\R^{2n^2}\to P(U)\), \[\sigma(a)=\bigcup_{j=1,{a}^{(j)}\neq 0}^{n^2}V_{q(a,j)}.\] Moreover, for every \(a\in \R^{2n^2}\), we denote the index \(p(a)\in [|U|]\) as \[p(a)=\argmin_{i}\{i:v_i \in U\setminus\sigma(a)\},\] and define the following mapping \(\alpha:\R^{2n^2}\to U\), \[\alpha(a)=\left\{\begin{array}{cc} v_{|U|} & \sigma(a)=U \\ v_{p(a)} & \sigma(a)\neq U \end{array}\right..\]

Now, Let \(V_1,\ldots, V_n\subseteq U\) and \(j_1,...j_n\) that are sampled uniformly from \([n^2]\), We prove the last part of the lemma under the condition that \(j_i\neq j_k\) for \(i\neq k\). \(\psi^*=\frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\) holds \[\begin{align} \langle \psi^*, \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\rangle&= \langle \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i), \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\rangle \\&= \frac{1}{n^2}\sum_{i=1}^n\langle \phi(V_i,j_i),\phi(V_i,j_i)\rangle \\&= \frac{1}{n} \\& > \frac{7}{8n} \end{align}\] For \(\psi=\frac{1}{n}\sum_{l=1}^n \phi(V'_l,j'_l)\) such that \(\psi\neq \psi^*\), there are at most \(n\) pairs \(i, l\) such that \(\langle \phi(V'_i,j'_i),\phi(V'_l,j'_l)\rangle\neq 0\). thus, there exists a pair \((V'_r,j'_r)\) that \((V'_r,j'_r)\notin \{(V_i,j_i) : i\in [n]\}\). and for every \(i\), \(\langle \phi(V_i,j_i),\phi(V'_l,j'_l)\rangle\leq 1-\delta\). As a result, \[\begin{align} \langle \psi, \frac{1}{n}\sum_{l=1}^n \phi(V_i,j_i)\rangle&= \langle \frac{1}{n}\sum_{i=1}^n \phi(V'_l,j'_l), \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\rangle \\&=\frac{1}{n^2}\sum_{i=1}^n\sum_{l=1}^n\langle \phi(V_i,j_i),\phi(V'_l,j'_l)\rangle \\&\leq \frac{1}{n^2}\left( 1-\delta+\sum_{i=1,i\neq r}^n 1\right) \\&\leq \frac{1}{n^2}(1-\delta+n-1)\\&= \frac{1}{n}-\frac{\delta}{n^2} \\&= \langle \psi^*, \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\rangle-\epsilon \end{align}\] Furthermore, since if all \(j_i\) are distinct, for every \(i\) it holds that, \({\frac{1}{n}\sum_{i=1}^n\phi=(V_i,i)}^{(j_i)}=\frac{1}{n}g(V_i)\), thus, \[\begin{align} q\left(\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_i),j_i\right)&=\argmax_{r}\langle g(V_r), {\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_i)}^{(j_i)}\rangle \\&=\argmax_{r}\langle g(V_r), \frac{1}{n}g(V_i)\rangle \\&=i, \end{align}\] and we get, \[\begin{align} \sigma (\psi^*)&=\sigma \left(\frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\right)\\ &=\bigcup_{j=1,{\frac{1}{n}\sum_{i=1}^n\phi(V_l,j_i)}^{(j)}\neq 0}^{n^2}V_{q\left(\frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i),j\right)} \\&=\bigcup_{i=1}^{n}V_{q\left(\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_i),j_i\right)} _{i=1}^n\}} \\&=\bigcup_{i=1}^{n}V_{i} \end{align}\] Finally, assuming that \(\bigcup_{i=1}^nV_i\neq U\), \[\alpha(\psi^*)= v_{p(a)} \in U\setminus\bigcup_{i=1}^{n}V_{i}.\] ◻

of 2. We prove that \(\ell_{1},\ell_{2}\) and \(\ell_{4}\) are convex and \(1\)-Lipschitz and \(\ell_{3}\) is convex and \(1 2\)-Lipschitz.

First, by 1 17 for every \(u\in U\) and \(V\in P(U)\), \(j\in[n^2]\), it holds that \(\|u\|=1\), \(\|\phi(V,j)\|=1\). Then, \(\ell_{2}\) is a \(1\)-Lipschitz linear function, and \(\ell_{4}\) is a maximum over \(1\)-Lipschitz linear functions, thus, both functions are convex and \(1\)-Lipschitz. Moreover, for every possible \(\psi\in \Psi\) \[\|\psi\|=\|\frac{1}{n}\sum_{l=1}^n\phi(V_l)\|\leq \frac{1}{n}\sum_{l=1}^n\|\phi(V_l)\|=1.\] thus, \(\ell_{3}\) is a maximum over \(2\)-Lipschitz linear functions, thus, it is convex and \(2\)-Lipschitz. Now, for \(\ell_{1}\), for every set \(V\subseteq U\), let \(\alpha_V(w)\in \R^{T-1}\) to be the vector which its \(k\)’th coordinate is \({\alpha_V(w)}^{(k)}=\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u{w}^{(k+1)}\rangle \right)\) and prove convexity and \(1\)-Lipshitzness. For establishing convexity, observe \[\begin{align} &\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{(\lambda x + (1-\lambda) y)}^{(k)}\rangle \right)^2} \\&= \sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \left(\lambda \langle u,{x}^{(k)}\rangle +(1-\lambda)\langle u,{ y}^{(k)}\rangle\right) \right)^2} \\&\leq \sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \left(\lambda \langle u,{x}^{(k)}\rangle\right) +\max_{u\in V}\left((1-\lambda)\langle u,{ y}^{(k)}\rangle\right) \right)^2}\\&\leq \sqrt{\sum_{k=2}^T \left( \lambda\max\left(\frac{3\eta}{32}, \max_{u\in V} \left( \langle u,{x}^{(k)}\rangle\right)\right) +(1-\lambda)\max\left(\frac{3\eta}{32},\max_{u\in V}\langle u,{ y}^{(k)}\rangle\right) \right)^2} \\& =\|\lambda \alpha_V(x) +(1-\lambda)\alpha_V(y)\|_2 \\& \leq \lambda\|\alpha_V(x)\|_2 +(1-\lambda)\alpha_V(y)\|_2\\& = \lambda \sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u{x}^{(k)}\rangle \right)^2}+(1-\lambda)\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u{y}^{(k)}\rangle \right)^2}. \end{align}\] For \(1\)-Lipschitzness, for every \(w\in \R^d\) and sub-gradient \(g(w,V)\in \partial \ell_1(w,V)\), there exists a sub gradient \(h(w,V)\in \partial\left(\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u{w}^{(k)}\rangle \right)^2\right)\) such that \[\begin{align} \|g(w,V)\|= \frac{\|h(w,V)\|}{2\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u{w}^{(k)}\rangle \right)^2}} =\frac{\|h(w,V)\|}{2\sqrt{\sum_{k=2}^T{{\alpha_V(w)}^{(k)}}^{2}}}. \end{align}\] Moreover, for every \(k\) and sub gradient \(b_{k,V}(w)\in \partial \left( {\alpha_V(w)}^{(k)}\right)\) we denote \(r_{k,V}(w)\in R^d\) the vector with \({r_{k,V}(w)}^{(k)}=b_{k,V}(w)\) and for \(j\neq k\), \({r_{k,V}(w)}^{(j)}=0\). Then, for every sub gradient \(h(w,V)\in \partial\left(\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u{w}^{(k)}\rangle \right)^2\right)\), there exists \(T-1\) such vectors \(r_{k,V}(w)\in R^d\) (\(2\leq k\leq T\)) such that, \[\begin{align} h(w,V)=2 \sum_{k=2}^{T} r_{k,V}(w){\alpha_V(w)}^{(k)} \end{align}\] As a result, by the fact that every sub gradient of \(b_{k,V}(w)\in \partial \left( {\alpha_V(w)}^{(k)}\right)\) is either 0 or \(\lambda_1 u_1 +\lambda_2 u_2+\ldots+\lambda_p u_p\) for \(\sum_{i}\lambda_i\leq 1\), such that for all every \(j,k\), \(u_j\in U\) and \({\alpha_V(w)}^{(k)}=\langle u_j,\vecpart{w}^{k}\rangle\), combining by the facts that for distinct \(k,k'\), \(r_{k,V},r_{k',V}\) are orthogonal, it holds, for \(u_j^2,\ldots u_j^{T}\in U\) such that for every \(k\), \({\alpha_V(w)}^{(k)}=\langle u_j^k,{w}^{(k)}\rangle\), \[\begin{align} \|h(w,V)\|&=\|2 \sum_{k=2}^{T} r_{k,V}(w){\alpha_V(w)}^{(k)}\rangle\| \\&=\|2 \sum_{k=2,b_{k,V}}^{T} r_{k,V}(w){\alpha_V(w)}^{(k)}\rangle\| \\&= 2\|\sum_{k=2}^{T} r_{k,V} \langle u_j^k,{w}^{(k)}\rangle\|. \end{align}\] Now, we denote \(c_j^k(w)\in R^d\) the vector with \({c_j^k(w)}^{(k)}=u_j^k\) and for \(j\neq k\), \({c_j^k(w)}^{(j)}=0\), and, \[\begin{align} \|h(w,V)\|&=2\|\sum_{k=2}^{T} r_{k,V} \langle c_j^k,w\rangle\| \\&\leq 2\sqrt{\langle \sum_{k=2}^{T} r_{k,V} \langle c_j^k,w\rangle, \sum_{l=2}^{T} r_{l,V} \langle c_j^l,w\rangle\rangle} \\&= 2\sqrt{\sum_{k=2}^{T}\|r_{k,V}\|^2 \langle c_j^k ,w\rangle^2} \\&\leq 2\sqrt{\sum_{k=2}^{T}\langle u_j^k ,{w}^{(k)}\rangle^2} \\&=2\sqrt{\sum_{k=2}^T{{\alpha_V(w)}^{(k)}}^{2}}. \end{align}\] The lemma follows. ◻

of 3. By the fact that every \(V_i\) and \(j_i\) are independent, it is enough to show that \[\Pr\left(\bigcup_{i=1}^nV_i\neq U_{d '}\right)\geq\frac{1}{2},\]and,\[\Pr\left(\text{for every k\neq l, j_k\neq j_l}\right)\geq \frac{1}{3}.\] For the former, for every \(u\in U_{d'}\), since \(V_i\) are sampled independently and every vector \(u\in U_{d'}\) is in every \(V_i\) with probability \(\frac{1}{2}\), \[\begin{align} \Pr\left(u \in\bigcup_{i=1}^nV_i \right)&= 1-\Pr\left(u \notin\bigcup_{i=1}^nV_i \right)=1-2^{-n}, \end{align}\] thus, since by 1, \(|U_{d'}|\geq \frac{d'}{178}=n\) , it holds that, \[\begin{align} \Pr\left(\bigcup_{i=1}^nV_i =U_{d'} \right) &= \Pr\left(\forall u\in U_{d'} \;u \in\bigcup_{i=1}^nV_i \right) \\ &= \left(1-2^{-n}\right)^{|U_{d'}|} \\&\leq \left(1-2^{-n}\right)^{2^\frac{d'}{178}} \\&= \left(1-2^{-n}\right)^{2^n} \\ &\leq \frac{1}{e} \\&<\frac{1}{2} . \end{align}\] We conclude, \[\Pr\left(\bigcup_{i=1}^nV_i\neq U_{d'}\right)\geq \frac{1}{2} .\] For the latter, since all \(j_i\)s are sampled independently, for a single pair \(k\neq l\), it holds that \[\Pr(j_k\neq j_l)=1-\frac{1}{n^2}\] As a result, \[\Pr\left(\text{for every k\neq l, j_k\neq j_l}\right)=\left(1-\frac{1}{n^2}\right)^{\frac{n(n-1)}{2}}\geq \left(1-\frac{1}{n^2}\right)^\frac{n^2}{2}\geq \frac{1}{\sqrt{2e}}\geq \frac{1}{e}. \qedhere\] ◻

of 5. For the first part, we know that, for every \(2\leq k\leq T\), \({w}^{(k)}=c\eta u_0\) for \(c\leq \frac{1}{2}\). In addition, by the facts that \(u_0\in U\setminus \bigcup_{i=1}^n V_i\) and that for every \(u\neq v\in U\), it holds that \(\langle u,v\rangle\leq \frac{1}{8}\), we get for every \(i\), \(\max_{u\in V_i}\langle u_0,u\rangle\leq \frac{1}{8}\), thus, for every \(i\) and \(k\geq 2\), \[\begin{align} \max_{u\in V_i} u{w}^{(k)}=\max_{u\in V_i}\langle u,c\eta u_{0}\rangle \leq\frac{1}{8}\cdot c\eta\leq\frac{\eta}{16}. \end{align}\]

For the second part, for every sub-gradient \(g(w,V_i)\in \partial \ell_1(w,V_i)\), there exists a sub gradient \(h(w,V_i)\in \partial\left(\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u{w}^{(k)}\rangle \right)^2\right)\) such that \[\begin{align} g(w,V_i)= \frac{h(w,V_i)}{2\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V_i} \langle u{w}^{(k)}\rangle \right)^2}} . \end{align}\] Then, since for every \(k\), it holds that \(\max_{u\in U} \langle {w}^{(k)}, u_0 \rangle\leq \frac{\eta}{16}\), every such sub-gradient \(h(w,V_i)\) is zero, \(\nabla \ell_{1}(w,V_i)=0\). ◻

of 6. First, for the first part, by 17, the fact that for every \(\psi\), \(\|\alpha(\psi)\|\leq 1\), and by \(\|{w}^{(1)}\|\leq \eta\), for every \(\psi\in \Psi\), \(\psi^*=\frac{1}{n}\sum_{i=1}^n \phi(V_i,j_{i})\) holds, \[\begin{align} \langle{w}^{({{0}})}, \psi^*\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi^*), {w}^{(1)}\rangle &\geq \langle\frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_{i}), \psi^*\rangle - \frac{\eta \epsilon}{4} \\&\geq \eta\langle\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_{i}), \psi^*\rangle - \frac{\eta \epsilon}{4} \\&\geq \eta\langle\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_{i}), \psi\rangle +\eta\epsilon -\frac{\eta \epsilon}{4} } \\&= \eta\langle\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_{i}), \psi\rangle +\frac{\eta\epsilon}{2}+\frac{\eta \epsilon}{4} \\&> \langle{w}^{({{0}})}, \psi\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi), {w}^{(1)}\rangle + \frac{\eta\epsilon}{4}, \end{align}\] thus, \[\begin{align} \arg\max_{\psi\in \Psi} \left(\langle{w}^{({{0}})}, \psi\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi), {w}^{(1)}\rangle\right)=\psi^*=\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_{i}). \end{align}\] For the second part, by the fact that \(\epsilon<\frac{1}{n}\) and 17, \[\begin{align} \langle{w}^{({{0}})}, \psi^*\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi^*), {w}^{(1)}\rangle \geq \frac{7\eta}{8n}-\frac{\eta}{4n} > \frac{\eta}{2n}+\frac{\eta}{16n}=\delta_1+\frac{\eta}{16n}. \end{align}\] Now, by \(\cE\), for \(u_0=\alpha(\psi^*)\), which is the \(u\) with the minimal index in \(U\setminus\bigcup_{i=1}^n V_i\), \[\begin{align} \alpha(\psi^*)=u_0\in U\setminus\bigcup_{i=1}^n V_i. \end{align}\] As a result, by the fact that the maximum is attained uniquely at \(\psi^*\), we derive that, \[\begin{align} {\nabla \ell_{3}(w)}^{(k)}=\begin{cases} \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_{i}) &\quad k={0}\\ -\frac{1}{4}\frac{\epsilon}{T^2}u_0 &\quad k=1\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\] ◻

of 7. We show that the maximum is attained uniquely at \(k=m\) and \(u=u_0\). For \(k=1\) and every \(u\in U\), \[\begin{align} \frac{3}{8}\langle u,{w_t}^{(1)}\rangle-\frac{1}{2}\langle u,{w_t}^{(2)}\rangle=\frac{3}{8}\langle u,c\eta u_0\rangle-\frac{1}{2}\langle u,\frac{\eta}{8}u_0\rangle\leq \frac{9\eta}{512}+\frac{\eta}{128}=\frac{13\eta}{512}. \end{align}\] Moreover, for every \(2\leq k\leq m-2\) and every \(u\in U\), \[\begin{align} \frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle u,{w}^{(k+1)}\rangle=\frac{3}{8}\langle u,\frac{\eta}{8}u_{0}\rangle-\frac{1}{2}\langle u,\frac{\eta}{8}u_{0}\rangle\leq \frac{3\eta}{64}+\frac{\eta}{128}=\frac{7\eta}{128}. \end{align}\] For \(k= m-1\) and every \(u\in U\), \[\begin{align} \frac{3}{8}\langle u,{w}^{(m-1)}\rangle-\frac{1}{2}\langle u,{w}^{(m)}\rangle=\frac{3}{8}\langle u,\frac{\eta}{8}u_{0}\rangle-\frac{1}{2}\langle u,\frac{\eta}{2}u_{0}\rangle\leq \frac{3\eta}{64}+\frac{\eta}{32}=\frac{5\eta}{64}. \end{align}\] For \(k=m\) and \(u=u_{0}\), \[\begin{align} \frac{3}{8}\langle u,{w}^{(m)}\rangle-\frac{1}{2}\langle u,{w}^{(m+1)}\rangle=\frac{3}{8}\langle u_0,\frac{\eta}{2}u_{0}\rangle-\frac{1}{2}\langle u_0,0\rangle= \frac{3\eta}{16}. \end{align}\] For \(k=m\) and \(u\neq u_0\), \[\begin{align} \frac{3}{8}\langle u,{w}^{(m)}\rangle-\frac{1}{2}\langle u',{w}^{(m+1)}\rangle=\frac{3}{8}\langle u,\frac{\eta}{2}u_{0}\rangle-\frac{1}{2}\langle u',0\rangle\leq \frac{3\eta}{128}. \end{align}\] For every \(m+1\leq k< T-1\) and every \(u\in U\), \[\begin{align} \frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle u',{w}^{(k+1)}\rangle=0. \end{align}\] Moreover, since \(T\geq 4,\eta<1,\epsilon<1\), \(\delta_1\leq \frac{3\eta}{1024}\), and \[\frac{3}{8}\langle u,{w}^{(m)}\rangle-\frac{1}{2}\langle u,{w}^{(m+1)}\rangle=\frac{3\eta}{16}>\delta_2+\frac{\eta}{64}.\] We derive that, \[\begin{align} {\nabla \ell_4(w)}^{(k)}= \begin{cases} \frac{3}{8}u_0 &\quad k=m\\ -\frac{1}{2}u_0 &\quad k=m+1\\ 0 & \text{otherwise} .\end{cases} \end{align}\] ◻

Proof. For \(t=1\), \(w_1=0\). By 5 we know that for every \(i\), \(\nabla\ell_{1}(w_1,V_i)=0\). Moreover, by the fact that \(\delta_1,\delta_2>0\) the maximum in \(\ell_3\) and \(\ell_4\) is attained in \(\delta_1\) and \(\delta_2\), respectively, thus we get that \[\nabla\ell_{3}(w_1)=\nabla\ell_{4}(w)=0\] As a result, \[\begin{align} {\nabla \widehat{F}(w_1)}^{(k)}=\frac{1}{n}\sum_{i=1}^n{\nabla \ell_{2}(w_1,(V_i,j_i))}^{(k)}=\begin{cases} -\frac{1}{n}\sum_{i=1}^n(V_i,j_{i}) &\quad k={0}\\ 0 &\quad \text{otherwise}, \end{cases} \end{align}\] and, \[\begin{align} {w_2}^{(k)}=\begin{cases} \frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i) &\quad k={0}\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\] ◻

Proof. By 18, \({w_2}^{(1)},...{w_2}^{(T)}=0\), thus, by 5, we know that for every \(i\), \(\nabla \ell_{1}(w_1,V_i)=0\). Moreover, by the fact that \(\delta_2>0\), we get that \(\nabla \ell_{4}(w_2)=0\). For \(\ell_{3}(w_2)\), by 6, using the fact that \({w_2}^{(1)}=0\) and \({w_{2}}^{({{0}})}=\frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i)\), we get that \[\begin{align} {\nabla \ell_{3}(w_2)}^{(k)}=\begin{cases} \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_{i}) &\quad k={0}\\ -\frac{1}{4}\frac{\epsilon}{T^2}u_0 &\quad k=1\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\]

For \(\ell_{2}(w_2)\), for every \(i\), the gradient is \[\begin{align} {\nabla \ell_{2}(w_2,(V_i,j_i))}^{(k)}=\begin{cases} -\phi(V_i,j_{i}) &\quad k={0}\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\]

Combining all together, we conclude that, for \(u_0\in U\setminus \bigcup_{i=1}^{n}V_{i}\), it holds that, \[\begin{align} {\nabla \widehat{F}(w_2)}^{(k)}= \begin{cases} -\frac{1}{4}\frac{\epsilon}{T^2}u_0 &\quad k=1\\ 0 &\quad 2\leq k\leq T \\ 0 &\quad k={0} ,\end{cases} \end{align}\] and \[\begin{align} {w_3}^{(k)}= \begin{cases} \frac{\eta}{4}\frac{\epsilon}{T^2}u_0&\quad k=1\\ 0 &\quad 2\leq k\leq T\\ \frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i) &\quad k={0} .\end{cases} \end{align}\] ◻

Proof. We start with \(\ell_{1},\ell_{2},\ell_{3}\). For \(\ell_1\), by 19, for every \(2\leq k\leq T\), \({w_3}^{(k)}=0\), thus, by 5, we know that for every \(i\), \(\nabla\ell_{1}(w_1,V_i)=0\). For \(\ell_2\), we know that, for every \(i\), \[\begin{align} {\nabla \ell_{2}(w_3,(V_i,j_i))}^{(k)}=\begin{cases} - \phi(V_i,j_{i}) &\quad k={0}\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\] For \(\ell_{3}\), by 6, using the fact that \({w_3}^{(1)}=c\eta u_0\) for \(|c|\leq1\) and \({w_{3}}^{({{0}})}=\frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i)\), we get that, \[\begin{align} {\nabla \ell_{3}(w_3)}^{(k)}=\begin{cases} \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_{i}) &\quad k={0}\\ -\frac{1}{4}\frac{\epsilon}{T^2}u_0 &\quad k=1\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\]

Now, for \(\ell_{4}\), we show that the maximum is attained uniquely in \(k=1\) and \(u=u_0\): For \(k\neq 1\), for every \(u\in U\) \[\frac{3}{8}\langle u,{w_3}^{(k)}\rangle-\frac{1}{2}\langle u,{w_3}^{(k+1)}\rangle=0.\] For \(k=1\) and \(u\neq u_0\), \[\begin{align} \frac{3}{8}\langle u,{w_3}^{(k)}\rangle-\frac{1}{2}\langle u,{w_3}^{(k+1)}\rangle&=\frac{3}{8}\langle u,{w_3}^{(1)}\rangle-\frac{1}{2}\langle u,{w_3}^{(2)}\rangle\\&=\frac{3}{8}\langle u,\frac{\eta}{4}\frac{\epsilon}{T^2}u_0\rangle \\&\leq \frac{3\eta}{256}\frac{\epsilon}{T^2} \end{align}\] For \(k=1\) and \(u= u_0\), \[\begin{align} \frac{3}{8}\langle u,{w_3}^{(k)}\rangle-\frac{1}{2}\langle u,{w_3}^{(k+1)}\rangle&=\frac{3}{8}\langle u_0,{w_3}^{(1)}\rangle-\frac{1}{2}\langle u_0,{w_3}^{(2)}\rangle\\&=\frac{3}{8}\langle u_0,\frac{\eta}{4}\frac{\epsilon}{T^2}u_0\rangle \\&= \frac{3\eta}{32}\frac{\epsilon}{T^2}\\&>\delta_2 \end{align}\] We derive that, \[\begin{align} {\nabla \ell_4(w_3)}^{(k)}= \begin{cases} \frac{3}{8}u_0 &\quad k=1\\ -\frac{1}{2}u_0 &\quad k=2\\ 0 &\quad 3\leq k\leq T \\ 0 &\quad k={0} .\end{cases} \end{align}\] Combining all together, we get that, \[\begin{align} {\nabla \widehat{F}(w_3)}^{(k)}= \begin{cases} \frac{3}{8}u_0 -\frac{1}{4}\frac{\epsilon}{T^2}u_0 &\quad k=1\\ -\frac{1}{2}u_0 &\quad k=2\\ 0 &\quad 3\leq k\leq T \\ 0 &\quad k={0} ,\end{cases} \end{align}\] and \[\begin{align} {w_4}^{(k)}= \begin{cases} -\frac{3\eta}{8}u_0+\frac{\eta}{2}\frac{\epsilon}{T^2}u_0&\quad k=1\\ \frac{\eta}{2}u_0 &\quad k=2\\ 0 &\quad 3\leq s\leq T \\ \frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i) &\quad k={0} ,\end{cases} \end{align}\] where \(u_0\in U\setminus \bigcup_{i=1}^n V_i\). ◻

Proof. We begin with \(\ell_{1},\ell_{2},\ell_{3}\). Note that, by 20, for every \(2\leq k\leq T\), \({w_4}^{(k)}=c\eta u_0\) for \(c\leq\frac{1}{2}\), thus, by 5, for every \(i\), \(\nabla \ell_{1}(w_4, V_i)=0\). For \(\ell_2\), we know that, for every \(i\), \[\begin{align} {\nabla \ell_{2}(w_4,(V_i,j_i))}^{(k)}=\begin{cases} - \phi(V_i,j_{i}) &\quad k={0}\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\] For \(\ell_{3}\), by 6, using 20, where we showed that \({w_4}^{(1)}=c\eta u_0\) for \(|c|\leq1\) and \({w_{4}}^{({{0}})}=\frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i)\), we get that, \[\begin{align} {\nabla \ell_{3}(w_4)}^{(k)}=\begin{cases} \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_{i}) &\quad k={0}\\ -\frac{1}{4}\frac{\epsilon}{T^2}u_0 &\quad k=1\\ 0 &\quad \text{otherwise}. \end{cases} \end{align}\]

It is left to calculate \(\nabla \ell_{4}(w_4)\). We show that the maximum is attained uniquely at \(k=2\) and \(u=u_0\). First, \[\begin{align} \frac{3}{8}\langle u,\frac{\eta}{2}\frac{\epsilon}{T^2} u_0\rangle= \frac{3\eta}{16}\frac{\epsilon}{T^2}\langle u,u_0\rangle \leq \frac{3\eta}{16T^2}, \end{align}\] thus, since \(T\geq 4\), \[\begin{align} \frac{3}{8}\langle u,{w_4}^{(1)}\rangle-\frac{1}{2}\langle u,{w_4}^{(2)}\rangle=\frac{3}{8}\langle u,-\frac{3\eta}{8}u_0+\frac{\eta}{2}\frac{\epsilon}{T^2}u_0\rangle-\frac{1}{2}\langle u,\frac{\eta}{2}u_0\rangle\leq \frac{9\eta}{512}+\frac{\eta}{32}+\frac{9\eta}{256}=\frac{43\eta}{512}<\frac{3\eta}{16}. \end{align}\] For \(k=2\) and \(u=u_{0}\), \[\begin{align} \frac{3}{8}\langle u,{w_4}^{(2)}\rangle-\frac{1}{2}\langle u,{w_4}^{(3)}\rangle=\frac{3}{8}\langle u_0,\frac{\eta}{2}u_{0}\rangle-\frac{1}{2}\langle u_0,0\rangle= \frac{3\eta}{16}(> \delta_2). \end{align}\] For \(k=2\) and \(u\neq u_{t-2}\), \[\begin{align} \frac{3}{8}\langle u,{w_4}^{(2)}\rangle-\frac{1}{2}\langle u',{w_3}^{(3)}\rangle=\frac{3}{8}\langle u,\frac{\eta}{2}u_{0}\rangle-\frac{1}{2}\langle u,0\rangle\leq \frac{3\eta}{128}. \end{align}\] For every \(3\leq k\leq T-1\), \[\begin{align} \frac{3}{8}\langle u,{w_4}^{(k)}\rangle-\frac{1}{2}\langle u',{w_4}^{(k+1)}\rangle=0. \end{align}\] We derive that, \[\begin{align} {\nabla \ell_4(w_4)}^{(k)}= \begin{cases} \frac{3}{8}u_0 &\quad k=2\\ -\frac{1}{2}u_0 &\quad k=3\\ 0 &\quad 3\leq k\leq T \\ 0 &\quad k={0} .\end{cases} \end{align}\] Combining all together, we get that, \[\begin{align} {\nabla \widehat{F}(w_4)}^{(k)}=\begin{cases} -\frac{1}{4}\frac{\epsilon}{T^2} u_{0} & k=1\\ \frac{3}{8} u_{0} &\quad k=2 \\ -\frac{1}{2} u_{0} &\quad k=3 \\ 0 &\quad 4\leq k\leq T \\ 0 & k={0} \end{cases} \end{align}\] and \[\begin{align} {w_{5}}^{(k)}=\begin{cases} -\frac{3}{8}\eta u_{0}+ \frac{3\eta}{4}\frac{\epsilon}{T^2}u_0 & k=1\\ \frac{1}{8}\eta u_{0} &\quad k=2 \\ \frac{1}{2}\eta u_{0} &\quad k=3 \\ 0 &\quad 4\leq s\leq T \\ \frac{1}{n}\sum_{i=1}^n\phi(V_i,j_i) & k={0}, \end{cases} \end{align}\] where \(u_0\in U \setminus \bigcup_{i=1}^n V_i\). ◻

Proof. If \(\cE\) holds, by 18 19 20 4, we know that for every \(t\geq 2\), \(\|{w_t}^{(1)}\|\leq \frac{\eta}{2}\), \(\|{w_t}^{(t-1)}\|\leq \frac{\eta}{2}\) and for every \(k\in\{2,\ldots,t-2\}\), \(\|{w_t}^{(t-1)}\|\leq \frac{\eta}{8}\). As a result, \[\begin{align} \norm{w_t}^2 &\leq \sum_{i=1}^d w_t[i]^2 \\&\leq \sum_{k=0}^T \|{w_t}^{(k)}\|^{2} \\&< 2\cdot \left(\frac{\eta}{2}\right)^{2}+ (T-3)\left(\frac{\eta}{8}\right)^{2}+\norm[2]{ \frac{\eta}{n}\sum_{i=1}^n\phi(V_i,j_i) }^2 \\&\leq \frac{\eta^2}{2} + \frac{\eta^2(T-3)}{64}+\eta^2 \\&\leq \frac{1}{64}+\frac{3}{2T} {\sqrt{T}}} \\&\leq 1 \end{align}\] ◻

of 3. By 3, with probability of at least \(\frac{1}{6}\), \(\cE\) occurs and by 4, it holds for every \(2\leq k\leq T-3\) that, \[\begin{align} \label{suff95exp} {w_{T,m}}^{(k)}=\frac{1}{m}\sum_{i=1}^m{w_{T-i+1}}^{(k)}&=\begin{cases} \frac{\eta}{8}u_0 & k\leq T-m-2\\ \frac{1}{m}\left(\frac{\eta}{2}+\frac{\eta}{8}(T-k-2)\right)u_0 & k\geq T-m-1 \end{cases} \\&=\begin{cases} \frac{\eta}{8} u_0& k\leq T-m-2\\ \frac{\eta(T-k+2)}{8m}u_0 & k\geq T-m-1 \end{cases} \notag \end{align}\tag{15}\] Then, we denote \(\mathbb{\alpha}_V\in \R^{T-4}\) the vector which its \(k\)th entry is \(\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k+1)}\rangle \right)\). By the fact that every vector \(u\in U\) is in \(V\) with probability \(\frac{1}{2}\), the following holds, \[\begin{align} \E_V\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right)^2}&\geq \E_V\sqrt{\sum_{k=2}^{T-3}\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right)^2} \\&= \E_V\sqrt{\sum_{k=1}^{T-4}\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k+1)}\rangle \right)^2} \\&=\E_V \|\alpha_V\| \\&\geq \|\E_V \alpha_V\| \\&=\sqrt{\sum_{k=2}^{T-3 }\left(\E_V \max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right) \right)^2} \end{align}\] Then, by 15 , \[\begin{align} &\E_V\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right)^2}\\&\geq \sqrt{\sum_{k=2}^{T-m-2}\left(\E_V \max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right) \right)^2+\sum_{k=T-m-1}^{T-3 }\left(\E_V \max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right) \right)^2} \\&\geq \sqrt{\sum_{k=2}^{T-m-2}\left(\E_V \max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,\frac{\eta}{8}u_0\rangle \right) \right)^2+\sum_{k=T-m-1}^{T-3 }\left(\E_V \max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,\frac{\eta(T-k+2)}{8m}u_0\rangle \right) \right)^2} \\&= \frac{\eta}{8}\sqrt{\sum_{k=2}^{T-m-2}\left(\E_V \max\left(\frac{3}{4}, \max_{u\in V} \langle u,u_0\rangle \right) \right)^2+\sum_{k=T-m-1}^{T-3 }\left(\E_V \max\left(\frac{3}{4}, \frac{T-k+2}{m} \max_{u\in V} \langle u,u_0\rangle \right) \right)^2} \\&\geq \frac{\eta}{8}\sqrt{\sum_{k=2}^{T-m-2}\left(\E_V \max\left(\frac{3}{4}, \max_{u\in V} \langle u,u_0\rangle \right) \right)^2+\sum_{k=T-m-1}^{T-3 }\left(\E_V \max\left(\frac{3}{4}, \frac{T-k+2}{T} \max_{u\in V} \langle u,u_0\rangle \right) \right)^2} \\&= \frac{\eta}{8}\sqrt{\sum_{k=2}^{T-m-2}\left(\E_V \max\left(\frac{3}{4}, \max_{u\in V} \langle u,u_0\rangle \right) \right)^2+\sum_{k=1}^{m-1 }\left(\E_V \max\left(\frac{3}{4}, \frac{k+4}{T} \max_{u\in V} \langle u,u_0\rangle \right) \right)^2} \end{align}\] Now, treating each of the term separately, with probability \(\frac{1}{2}\) on \(V\), \(\max_{u\in V} \langle u,u_0\rangle\leq \frac{1}{8}\) (otherwise it is \(1\)), thus, \[\begin{align} \E_V \max\left(\frac{3}{4}, \max_{u\in V} \langle u,u_0\rangle \right)=\frac{1}{2}\cdot \frac{3}{4} + \frac{1}{2}\cdot 1=\frac{7}{8} \end{align}\] Moreover, if \(k\leq \frac{3T}{4}-4\) \[\begin{align} \E_V \max\left(\frac{3}{4}, \frac{k+4}{T}\max_{u\in V} \langle u,u_0\rangle \right)=\frac{3}{4}, \end{align}\] otherwise, \[\begin{align} \E_V \max\left(\frac{3}{4}, \frac{k+4}{T}\max_{u\in V} \langle u,u_0\rangle \right)&\geq\frac{1}{2}\max\left(\frac{3}{4}, \frac{k+4}{T}\right)+ \frac{1}{2}\cdot \frac{3}{4} \\&\geq \frac{3}{8}+ \frac{k+4}{2T} \end{align}\] Then, we get, if \(m\geq T-3\), (note that it implies \(l-1 \geq \frac{3T}{4}-4\)), \[\begin{align} &\E_V\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right)^2}\\&\geq \frac{\eta}{8}\sqrt{\sum_{k=1}^{m-1 }\left(\E_V \max\left(\frac{3}{4}, \frac{k+4}{T} \max_{u\in V} \langle u,u_0\rangle \right) \right)^2} \\&\geq\frac{\eta}{8}\sqrt{\sum_{k:1\leq k\leq \frac{3T}{4}-4}\frac{9}{16} +\sum_{k:\frac{3T}{4}-4< k\leq m-1}\left( \frac{3}{8}+ \frac{k+4}{2T}\right)^2} \\&\geq \frac{\eta}{8}\sqrt{\sum_{k:1\leq k\leq \frac{3T}{4}-4}\frac{9}{16} +\sum_{k:\frac{3T}{4}< k\leq T}\left( \frac{3}{8}+ \frac{k}{2T}\right)^2} \\&\geq \frac{\eta}{8}\sqrt{\frac{27T-144}{64} +\sum_{k:\frac{3T}{4}< k\leq T}\left( \frac{9}{64}+ \frac{3k}{8T}\right)} \\&\geq \frac{\eta}{8}\sqrt{\frac{27T-144}{64} +\left( \frac{9T}{256}+ \frac{3}{8T}\sum_{k:\frac{3T}{4}< k\leq T}k \right)} \\&\geq \frac{\eta}{8}\sqrt{\frac{27T-144}{64} +\left( \frac{9T}{256}+ \frac{3T^2}{16T}-\frac{3(\frac{3T}{4}+1)^2}{16T} \right)} {2}\leq\sum_{i=1}^ni^2\leq \frac{(i+1)^2}{2}} \\&= \frac{\eta}{8}\sqrt{\frac{27T-144}{64} +\left( \frac{9T}{256}+\frac{3T}{16}-\frac{27T}{256}-\frac{3}{16T}-\frac{9}{32} \right)} \\&= \frac{\eta}{8}\sqrt{\frac{148T}{256}-\frac{45}{32} -\frac{3}{16T} } \\&\geq \frac{\eta}{8}\sqrt{\frac{147T}{256}}{32}+\frac{3}{16T}\leq \frac{T}{256}} \\&\geq \frac{3\eta}{32}\cdot \frac{101\sqrt{T}}{100}. \end{align}\] Otherwise, if \(m< T-4\), by similar arguments, \[\begin{align} &\E_V\sqrt{\sum_{k=2}^T\max\left(\frac{3\eta}{32}, \max_{u\in V} \langle u,{w_{T,m}}^{(k)}\rangle \right)^2} \\&\geq \frac{\eta}{8}\sqrt{\sum_{k=2}^{T-m-2}\left(\E_V \max\left(\frac{3}{4}, \max_{u\in V} \langle u,u_0\rangle \right) \right)^2+\sum_{k=T-m-1}^{T-3 }\left(\E_V \max\left(\frac{3}{4}, \frac{T-k+2}{T} \max_{u\in V} \langle u,u_0\rangle \right) \right)^2} \\&\geq \frac{\eta}{8}\sqrt{\sum_{k=2}^{T-m-2}\left(\frac{7}{8}\right)^2+\sum_{k:1\leq k\leq \frac{3T}{4}-4}\frac{9}{16} +\sum_{k:\frac{T}{2}< k\leq m+3}\left( \frac{3}{8}+ \frac{k}{2T}\right)^2} \\&= \frac{\eta}{8}\sqrt{\sum_{k=m+4}^{T}\left(\frac{7}{8}\right)^2+\sum_{k:1\leq k\leq \frac{3T}{4}-4}\frac{9}{16} +\sum_{k:\frac{T}{2}< k\leq m+3}\left( \frac{3}{8}+ \frac{k}{2T}\right)^2} \\&\geq \frac{\eta}{8}\sqrt{\sum_{k:1\leq k\leq \frac{3T}{4}-4}\frac{9}{16} +\sum_{k:\frac{3T}{4}< k\leq T}\left( \frac{3}{8}+ \frac{k}{2T}\right)^2} {8}+\frac{k}{2T}\leq \frac{7}{8}} \\&\geq \frac{3\eta}{32}\cdot \frac{101\sqrt{T}}{100}. \end{align}\] Moreover, we notice that for every \(t\), \(\ell_2(w_t)\geq-\|{w_{t}}^{({{0}})}\|\geq -\eta\), \(\ell_3(w_t)\geq \delta_1\) and \(\ell_4(w_t)\geq \delta_2\), thus, it holds that, \[\begin{align} F(w_{T,l})\geq \frac{303\eta}{3200}\sqrt{T}+\delta_1+\delta_2-\eta &\geq \eta\left(\frac{303}{3200}\sqrt{T}-1\right) \end{align}\] and \[\begin{align} F(w_*)&\leq \frac{3\eta}{32}\sqrt{T}+\eta \end{align}\] Then, with probability of at least \(\frac{1}{6}\), \[\begin{align} F(w_{T,l})-F(w_*) &\geq \eta (\frac{303}{3200}\sqrt{T}-2-\frac{3}{32}\sqrt{T}) \\&\geq \eta (\frac{303}{3200}\sqrt{T}-\frac{302}{3200}\sqrt{T}) {3200}\sqrt{T}} \\&= \frac{\eta}{3200}\sqrt{T}. \end{align}\] ◻

of 23. The construction is similar to 17. First, we consider an arbitrary enumeration of \(P(U)=\{V^1,...V^{|P(U)|}\}\) and define \(g:P(U)\to \R^2\), \(g(V^i)= \left(\sin\left(\frac{2\pi i}{|P(U)|}\right),\cos\left(\frac{2\pi i}{|P(U)|}\right)\right)\). Here, we refer to a vector \(a\in \R^{2n}\) as a concatenation of \(n\) vectors in \(\R^2\), \({a}^{(1)},...,{a}^{(n)}\). Then, we define \(\delta=1-\cos\left(\frac{2\pi}{|P(U)|}\right)\), \(\epsilon=\frac{\delta}{n^2}\) and \[{\phi(V,j)}^{(i)}= \left\{ \begin{array}{cc} g(V) & i=j \\ 0 & \text{otherwise} \end{array} \right.\] As a result, for every \(V_i,j\) it holds that \[\begin{align} \|\phi(V^i,j)\|=\|g(V^i)\|=\sqrt{\sin\left(\frac{2\pi i}{|P(U)|}\right)^2+\cos\left(\frac{2\pi i}{|P(U)|}\right)^2}=1 \end{align}\] Moreover, if \(j_1\neq j_2\), \[\begin{align} \langle \phi(V^i,j_1),\phi(V^i,j_2)\rangle =0, \end{align}\] and if \(i>k\), \[\begin{align} \langle \phi(V^i,j),\phi(V^k,j)\rangle=&\langle g(V^i), g(V^k)\rangle \\&=\sin\left(\frac{2\pi i}{|P(U)|}\right)\sin\left(\frac{2\pi k}{|P(U)|}\right) + \cos\left(\frac{2\pi i}{|P(U)|}\right)\cos\left(\frac{2\pi k}{|P(U)|}\right) \\&=\cos\left(\frac{2\pi (i-k)}{|P(U)|}\right) \\&\leq \cos\left(\frac{2\pi}{|P(U)|}\right)\\&=1-\delta \end{align}\] We notice that \(0<\delta< 1\). Now, we consider an arbitrary enumeration of \(U=\{v_1,...v_{|U|}\}\), and define the following sets \(\Psi_1,\ldots\Psi_n\subseteq \R^{2n}\) and the following two mappings \(\sigma: R^{2n}\to P(U), \alpha: R^{2n}\to U\), \[\Psi_k = \{ \frac{1}{n}\sum_{i=1}^k \phi(V_i,i): \forall i\; V_i\;\subseteq U\}\] Note that, for every \(\psi \in \Psi\), \[\|\psi\|=\|\frac{1}{n}\sum_{i=1}^k \phi(V_i,j_i)\|\leq \frac{1}{n}\sum_{i=1}^k \|\phi(V_i,j_i)\|\leq 1.\]

Then, for every \(a\in \R^{2n}\) and \(j\in[n]\), we denote the index \(q(a,j)\in [|P(U)|]\) as \[q(a,j)=\argmax_{r}\langle g(V_r), {a}^{(j)}\rangle,\] and define the following mapping \(\sigma:\R^{2n}\to P(U)\), \[\sigma(a)=\bigcap_{j=1,{a}^{(j)}\neq 0}^{n}V_{q(a,j)}.\] Moreover, for every \(a\in \R^{2n}\), we denote the index \(p(a)\in [|U|]\) as \[p(a)=\argmin_{i}\{i:v_i \in \sigma(a)\},\] and define the following mapping \(\alpha:\R^{2n^2}\to U\), \[\alpha(a)=\left\{\begin{array}{cc} v_{|U|} & \sigma(a)=\emptyset \\ v_{p(a)} & \sigma(a)\neq \emptyset \end{array}\right..\] Note that for every \(a\in \R^{2n}\), \(\alpha(a)\in U\), thus, \(\|\alpha(a)\|\leq 1\).

Now, Let \(V_1,\ldots, V_n\subseteq U\), \(k\in[n]\) and \(\psi^*_k=\frac{1}{n}\sum_{i=1}^k \phi(V_i,i)\). Then, \[\begin{align} \langle \psi^*, \frac{1}{n}\sum_{i=1}^k \phi(V_i,i)\rangle&= \langle \frac{1}{n}\sum_{i=1}^k \phi(V_i,i), \frac{1}{n}\sum_{i=1}^k \phi(V_i,i)\rangle \\&= \frac{1}{n^2}\sum_{i=1}^k\langle \phi(V_i,i),\phi(V_i,i)\rangle \\&= \frac{k}{n^2} \end{align}\] For \(\psi=\frac{1}{n}\sum_{i=1}^k \phi(V'_i,i)\) such that \(\psi\neq \psi^*\), there exists a index \(r\) such that \(V'_r\neq V_r\) ,thus, \[\begin{align} \langle \psi, \frac{1}{n}\sum_{l=1}^k \phi(V_i,i)\rangle&= \langle \frac{1}{n}\sum_{i=1}^k \phi(V'_i,i), \frac{1}{n}\sum_{i=1}^k \phi(V_i,i)\rangle \\&=\frac{1}{n^2}\sum_{i=1}^k\langle \phi(V_i,i),\phi(V'_i,i)\rangle \\&\leq \frac{1}{n^2}\left(1-\delta+\sum_{i=1,i\neq r}^k 1 \right) \\&\leq \frac{1}{n^2}(1-\delta+k-1)\\&= \frac{k}{n^2}-\frac{\delta}{n^2} \\&= \langle \psi^*_k, \frac{1}{n}\sum_{i=1}^n \phi(V_i,j_i)\rangle-\epsilon \end{align}\] Furthermore, it holds that, \({\frac{1}{n}\sum_{i=1}^n\phi(V_i,i)}^{(i)}=\frac{1}{n}g(V_i)\), thus, \[\begin{align} q\left(\frac{1}{n}\sum_{i=1}^k\phi(V_i,i),i\right)&=\argmax_{r}\langle g(V_r), {\frac{1}{n}\sum_{i=1}^k\phi(V_i,i)}^{(i)}\rangle \\&=\argmax_{r}\langle g(V_r), \frac{1}{n}g(V_i)\rangle \\&=i, \end{align}\] thus, we get, \[\begin{align} \sigma (\psi^*)&=\sigma \left(\frac{1}{n}\sum_{i=1}^k\phi(V_i,i)\right)\\ &=\bigcap_{j=1,{\frac{1}{n}\sum_{i=1}^k\phi(V_i,i)}^{(j)}\neq 0}^{n}V_{q({\frac{1}{n}\sum_{i=1}^k\phi(V_i,i)}^{(j)},j)} \\&=\bigcap_{j=1}^{k}V_{q(\frac{1}{n}\sum_{i=1}^k\phi(V_i,i),j)}\\&=\bigcap_{i=1}^{k}V_{i} \end{align}\] Then, assuming that \(\bigcap_{i=1}^kV_i\neq \emptyset\), and let and \(m=\argmin_{i}\{i:v_i \in \bigcap_{i=1}^kV_i\)}, \(p(a)=m\) and, \[\alpha(\psi^*)= v_{m} \in \bigcap_{i=1}^{k}V_{i}.\] ◻

of 8. First, \(\ell^{\text{SGD}}_1\) is convex and \(1\)-Lipschitz by the fact that \(\ell^{\text{SGD}}_1=\ell_1\) and 2. Moreover, by 23, \(\ell^{\text{SGD}}_2\) is a maximum over \(1\)-Lipschitz linear functions, thus, \(\ell^{\text{SGD}}_2\) is convex and \(1\)-Lipschitz. Finally, \(\ell^{\text{SGD}}_3\) is a summation of two \(1\)-Lipschitz linear functions, thus, \(\ell^{\text{SGD}}_3\) is convex and \(2\)-Lipschitz. Combining all together, we get the lemma. ◻

of 9. First, by union bound, \[\begin{align} \Pr\left(\forall t\in[n] \;P_t\neq \emptyset \text{ and } J_t \in S_t \right)\geq\frac{1}{2}&=1- Pr\left(\exists t \;P_t= \emptyset \text{ or } J_t \notin S_t \right) \\&\geq 1- \sum_{t=1}^n Pr\left(P_t= \emptyset \text{ or } \left(P_t\neq \emptyset \text{ and }J_t \notin S_t\right) \right) \\&\geq 1- \sum_{t=1}^n \Pr\left(P_t= \emptyset\right) -\sum_{t=1}^n\Pr\left(P_t\neq \emptyset \text{ and }J_t \notin S_t\right) \\&= 1- \sum_{t=1}^n\Pr\left(P_t= \emptyset\right) -\sum_{t=1}^n\Pr\left(P_t\neq \emptyset\right)\Pr\left(J_t \notin S_t | P_t\neq \emptyset\right). \end{align}\] Now, for every \(v_l\in U\), \[\begin{align} \Pr(v_l \notin \bigcap_{i=1}^{t-1} V_i)= 1- \Pr(v_l \notin \bigcap_{i=1}^{t-1} V_i)=1-\delta^{t-1}, \end{align}\] and, \[\begin{align} \Pr\left(v_l \notin S_t \right)=1- (1-\delta)^{n-t+1}\leq 1-(1-\delta)^n. \end{align}\] Then, \[\begin{align} \Pr\left(P_t= \emptyset\right)&=\Pr\left(\bigcap_{i=1}^t V_i =\emptyset\right) \\&= \Pr(\forall v_l\in U \;w\notin \bigcap_{i=1}^t V_i) \\&= (1-\delta^{t-1})^{|U|} \\&\leq (1-\delta^n)^{|U|}. \end{align}\] Moreover, by the fact that for every \(t\), \(P_t\) is independent of \(V_{t+1},...V_n\), \[\begin{align} Pr\left(P_t\neq \emptyset\right)\Pr\left(J_t \notin S_t | P_t\neq \emptyset\right)&= \sum_{l:v_l\in U} \Pr\left(P_t\neq \emptyset\right)\Pr\left(v_l \notin S_t | P_t\neq \emptyset\right)\Pr(J_t=v_l) \\&= \sum_{l:v_l\in U} \Pr\left(P_t\neq \emptyset\right)\Pr\left(v_l \notin S_t \right)\Pr(J_t=v_l) \\&\leq 1- (1-\delta)^n \end{align}\] Combining all of the above, we get that, \[\begin{align} &\Pr(\forall t\in[n] \;P_t\neq \emptyset \text{ and } J_t \in S_t)\\&= 1- \sum_{t=1}^n \Pr\left(P_t= \emptyset\right) -\sum_{t=1}^n\Pr\left(P_t\neq \emptyset\right)\Pr\left(J_t \notin S_t | P_t\neq \emptyset\right) \\&\geq 1- n (1-\delta^n)^{|U|}- n\left(1- (1-\delta)^n\right). \end{align}\] For \(\delta=\frac{1}{4n^2}\), by the fact that \(|U|\geq 2^{\frac{d'}{178}}=2^{4n\log(n)}=n^{4n}\), \[|U|\delta^{n}\geq n^{4n}n^{-2n}4^{-n}\geq n^{2n}4^{-n}\geq \log(4n)\] \[\begin{align} \Pr\left(\forall t\in[n] \;P_t\neq \emptyset \text{ and } J_t \in S_t \right)\geq\frac{1}{2} &\geq 1- n (1-\delta^\frac{n}{500})^{|U|}- n\left(1- (1-\delta)^n\right) \\&\geq 1- n e^{-|U|\delta^\frac{n}{500}}- n\left(1- (1-n\delta)\right) \\&\geq 1- n e^{-\log(4n)}- n^2\delta \\&\geq 1- \frac{1}{4} -\frac{1}{4} \\&= \frac{1}{2} . \end{align}\] ◻

of 11. First, by the fact that for every \(t\leq k\leq T\), \({w}^{(k)}=0\), for every such \(k\), \[\max_{u\in V_t} \langle u,{w}^{(k)}\rangle=0<\frac{3\eta}{32},\] For \(2\leq k\leq t-1\), \({w}^{(k)}=c\eta u_k\), where \(c\leq \frac{1}{2}\) and every \(u_k\in \bigcap_{i=k}^T\overline{V_i}\subseteq \overline{V_{t}}\), thus, \[\max_{u\in V_t} \langle u,{w}^{(k)}\rangle\leq\frac{\eta}{2}\cdot \frac{1}{8}<\frac{3\eta}{32}.\] We derive that \(\nabla \ell^{\text{SGD}}_1(w_t,V_t)= 0\). ◻

of 12. First, we show that the maximum of \(\ell^{\text{SGD}}_2(w,V)\) is attained with \(k=m\) and \(u=u_m\). For \(k\geq m+1\), for every \(u\in U\) and \(\psi\in \Psi_k\), \[\begin{align} &\frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle \alpha(\psi),{w}^{(k+1)}\rangle +\langle{w}^{( {0},k)},\frac{1}{4n}\psi\rangle -\langle{w}^{( {0},k+1)},\frac{1}{4n}\psi\rangle+\langle {w}^{({0},k+1)},-\frac{1}{4n^2}\phi(V,k+1)\rangle=0 . \end{align}\] For \(k=1\), for every \(u\in U\) and \(\psi\in \Psi_1\), by 23, we know that for every \(\psi,V,j\), \(\|\psi\|,\|\phi(V,j)\|\leq 1\), and \(\alpha(\psi)\in U\), thus, \[\begin{align} &\frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle \alpha(\psi),{w}^{(k+1)}\rangle +\langle{w}^{( {0},k)},\frac{1}{4n}\psi\rangle -\langle{w}^{( {0},k+1)},\frac{1}{4n}\psi\rangle+\langle {w}^{({0},k+1)},-\frac{1}{4n^2}\phi(V,k+1)\rangle \\&=\frac{3c}{8}\langle u_1,u\rangle -\frac{\eta}{16}\langle u_2,\alpha(\psi)\rangle + \langle{w}^{( {0},k)},\frac{1}{4n}\psi\rangle - 0+ 0 \\&\leq \frac{9\eta}{512} +\frac{\eta}{128} +\frac{\eta}{4n} \\& < \frac{\eta}{8}. \end{align}\] For \(2\leq k\leq m-2\), for every \(u\in U\) and \(\psi\in \Psi_k\), by 23, we know that for every \(\psi,V,j\), \(\|\psi\|,\|\phi(V,j)\|\leq 1\), and \(\alpha(\psi)\in U\), thus, \[\begin{align} &\frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle \alpha(\psi),{w}^{(k+1)}\rangle +\langle{w}^{( {0},k)},\frac{1}{4n}\psi\rangle -\langle{w}^{( {0},k+1)},\frac{1}{4n}\psi\rangle+\langle {w}^{({0},k+1)},-\frac{1}{4n^2}\phi(V,k+1)\rangle \\&=\frac{3}{64}\langle u_k,u\rangle -\frac{\eta}{16}\langle u_{k+1},\alpha(\psi)\rangle +0 - 0+ 0 \\&\leq \frac{3\eta}{64} +\frac{\eta}{16} \\& < \frac{\eta}{8} . \end{align}\] For \(k= m-1\), for every \(u\in U\) and \(\psi\in \Psi_{k}\), by 23, we know that for every \(\psi,V,j\), \(\|\psi\|,\|\phi(V,j)\|\leq 1\), and \(\alpha(\psi)\in U\), thus, \[\begin{align} &\frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle \alpha(\psi),{w}^{(k+1)}\rangle +\langle{w}^{( {0},k)},\frac{1}{4n}\psi\rangle -\langle{w}^{( {0},k+1)},\frac{1}{4n}\psi\rangle+\langle {w}^{({0},k+1)},-\frac{1}{4n^2}\phi(V,k+1)\rangle \\&=\frac{3}{64}\langle u_k,u\rangle -\frac{\eta}{4}\langle u_{k+1},\alpha(\psi)\rangle +0 - \langle {w}^{( {0},k+1)},\frac{1}{4n}\psi\rangle+ \langle {w}^{( {0},k+1)},\frac{1}{4n^2}\phi(V,m)\rangle \\&\leq \frac{3\eta}{64}+\frac{\eta}{32}+\frac{1}{16n^2}+\frac{1}{16n^3} \\& < \frac{\eta}{8} . \end{align}\]

For \(k=m\), \(u\neq u_{m}\) and every \(\psi\in \Psi_{m}\), by 23, we know that for every \(\psi,V,j\), \(\|\psi\|,\|\phi(V,j)\|\leq 1\), and \(\alpha(\psi)\in U\), thus, \[\begin{align} &\frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle \alpha(\psi),{w}^{(k+1)}\rangle +\langle{w}^{( {0},k)},\frac{1}{4n}\psi\rangle -\langle{w}^{( {0},k+1)},\frac{1}{4n}\psi\rangle+\langle {w}^{({0},k+1)},-\frac{1}{4n^2}\phi(V,k+1)\rangle\\&=\frac{3}{8}\langle u,{w}^{(k)}\rangle+\langle \frac{1}{4n}\psi,{w}^{({0},k)}\rangle \\&=\frac{3}{8}\langle u,\frac{\eta}{2}u_{m}\rangle+\langle \frac{1}{4n}\psi,{w}^{({0}, k)} \rangle \\&\leq \frac{3\eta}{128}+\frac{\eta}{16n^2}\\&<\frac{\eta}{32} . \end{align}\] For \(k=m\), \(u=u_{m}\) and every \(\psi\in \Psi_{m}\), by 23, we know that for every \(\psi,V,j\), \(\|\psi\|,\|\phi(V,j)\|\leq 1\), and \(\alpha(\psi)\in U\), thus, \[\begin{align} &\frac{3}{8}\langle u,{w}^{(k)}\rangle-\frac{1}{2}\langle \alpha(\psi),{w}^{(k+1)}\rangle +\langle{w}^{( {0},k)},\frac{1}{4n}\psi\rangle -\langle{w}^{( {0},k+1)},\frac{1}{4n}\psi\rangle+\langle {w}^{({0},k+1)},-\frac{1}{4n^2}\phi(V,k+1)\rangle \\&=\frac{3}{8}\langle u,{w_t}^{(k)}\rangle+\langle \frac{1}{4n}\psi,{w_t}^{({0},k)}\rangle\\&=\frac{3}{8}\langle u,\frac{\eta}{2}u_{m}\rangle+\langle \frac{1}{4n}\psi,{w_t}^{({0},k)}\rangle \\&\geq \frac{3\eta}{16}-\frac{\eta}{16n^2}\\&>\frac{5\eta}{32} \\&>\delta_1. \end{align}\]

Second, we show that when \(k=m\) and \(u=u_m\), the maximum among \(\psi\in \Psi_{m}\) is attained uniquely in \(\psi^*_{m}=\frac{1}{n}\sum_{t=1}^{m}\phi(V_t,t)\). For any \(\psi\in \Psi_m\), with \(\psi\neq \psi^*_{m}\), by 23, for \(k=m\), \(u=u_m\), \[\begin{align} &\frac{3}{8}\langle u,{w}^{(m)}\rangle-\frac{1}{2}\langle \alpha(\psi^*_{m}),{w}^{(m+1)}\rangle +\langle{w}^{( {0},m)},\frac{1}{4n}\psi^*_{m}\rangle -\langle{w}^{( {0},m+1)},\frac{1}{4n}\psi^*_{m}\rangle+\langle {w}^{({0},m+1)},-\frac{1}{4n^2}\phi(V,m+1)\rangle\\&=\frac{3}{8}\langle u,{w}^{(m)}\rangle+\langle \frac{1}{4n}\psi^*_{m},{w}^{({0},m)}\rangle \\&=\frac{3\eta}{16}+\frac{\eta}{16n^2}\langle \psi^*_{m},\frac{1}{n}\sum_{t=1}^{m}\phi(V_t,t)\rangle \\&\geq \frac{3\eta}{16}+\frac{\eta}{16n^2}\langle \psi,\frac{1}{n}\sum_{t=1}^{m}\phi(V_t,t)\rangle +\frac{\eta\epsilon}{16n^2}\\&= \frac{3}{8}\langle u,{w}^{(k)}\rangle+\langle \frac{1}{4n}\psi,{w}^{({0},m)}\rangle +\frac{\eta\epsilon}{16n^2} \\&=\frac{3}{8}\langle u,{w}^{(m)}\rangle-\frac{1}{2}\langle \alpha(\psi),{w}^{(m+1)}\rangle +\langle{w}^{( {0},m)},\frac{1}{4n}\psi\rangle -\langle{w}^{( {0},m+1)},\frac{1}{4n}\psi\rangle+\langle {w}^{({0},m+1)},-\frac{1}{4n^2}\phi(V,m+1)\rangle+\frac{\eta\epsilon}{16n^2} \end{align}\] We derive that, \[\begin{align} {\nabla \ell^{\text{SGD}}_2(w,V)}^{(k)}= \begin{cases} \frac{3}{8} u_{m} &\quad k=m \\ -\frac{1}{2} \alpha(\psi_{m}^*) &\quad k=m+1 \\ 0 &\quad k\notin \{m,m+1\} \end{cases} \end{align}\] \[\begin{align} {\nabla \ell^{\text{SGD}}_2(w,V)}^{({0}, k)}= \begin{cases} \frac{1}{4n^2}\sum_{t=1}^{m}\phi(V_t,t)&\quad k= m \\ -\frac{1}{4n^2}\sum_{t=1}^{m}\phi(V_t,t)-\frac{1}{4n^2}\phi(V,m+1)&\quad k= m+1 \\ 0&\quad k\notin \{m,m+1\}. \end{cases} \end{align}\] ◻

Proof. \(w_1=0\), thus, for every \(k\), \[\max_{u\in V_1} \langle u,{w_1}^{(k)}\rangle=0<\frac{3\eta}{32},\] and we derive that \(\nabla \ell^{\text{SGD}}_1(w_1,V_1)= 0\). By the same argument, \(\nabla \ell^{\text{SGD}}_2(w_1,V_1)= 0\) (where the maximum is attained uniquely in \(\delta_2\)). Moreover, \(\ell^{\text{SGD}}_3\) is a linear function, then, we get that, \[\begin{align} {\nabla \ell^{\text{SGD}}_3(w_1,V_1)}^{(k)}=\begin{cases} -\frac{1}{n^3}u_1 &\quad k=1 \\ 0 &\quad k\geq 2 \end{cases}, \end{align}\] and, \[\begin{align} {\nabla \ell^{\text{SGD}}_3(w_1,V_1)}^{(0,k)}=\begin{cases} -\frac{1}{4n^2}\phi(V_1,1) &\quad k=1 \\ 0 &\quad k\neq 1, \end{cases} \end{align}\] and the lemma follows. ◻

Proof. First, by the fact that for every \(2\leq k\leq T\), \({w_2}^{(k)}=0\), for every such \(k\), \[\max_{u\in V_2} \langle u,{w_2}^{(k)}\rangle=0<\frac{3\eta}{32},\] and we derive that \(\nabla \ell^{\text{SGD}}_1(w_2,V_2)= 0\).

Moreover, \(\ell^{\text{SGD}}_3\) is a linear function, thus, \[\begin{align} {\ell^{\text{SGD}}_3(w_2,V_2)}^{(k)}=\begin{cases} \frac{\eta}{n^3}u_1 &\quad k=1 \\ 0 &\quad k\geq 2 \end{cases}, \end{align}\] and, \[\begin{align} {\ell^{\text{SGD}}_3(w_2,V_2)}^{(k)}=\begin{cases} \frac{\eta}{4n^2}\phi(V_2,1) &\quad k=1 \\ 0 &\quad k\neq 1. \end{cases} \end{align}\] For \(\ell^{\text{SGD}}_2(w_2,V_2)\), we get by the fact that for every \(k\geq 1\), \({w_2}^{(k+1)}={w_2}^{({0},k+1)}=0\), \[\begin{align} \ell^{\text{SGD}}_2(w_2,V_2)=\max\left(\delta_2,\max_{ k\in[n-1],u\in U,\psi\in \Psi_k}\left(\frac{3}{8}\langle u,{w_2}^{(k)}\rangle+\langle \frac{1}{4n}\psi,{w_2}^{({0},k)}\rangle\right)\right) \end{align}\] As a first step, we show that the the maximum is attained with \(k=1\) and \(u=u_1\), For \(k\neq 1\), for every \(u\in U\) and \(\psi\in \Psi_k\),\[\frac{3}{8}\langle u,{w_2}^{(k)}\rangle+\langle \frac{1}{4n}\psi,{w_2}^{({0},k)}\rangle=0.\] For \(k=1\), \(u\neq u_1\) and every \(\psi\in \Psi_1\), by the fact that \(\|\psi\|,\|\phi(V_1,1)\|\leq 1\), \[\frac{3}{8}\langle u,{w_2}^{(k)}\rangle+\langle \frac{1}{4n}\psi,{w_2}^{({0},k)}\rangle\leq \frac{3\eta}{64n^3}+\frac{\eta}{16n^3}=\frac{7\eta}{64n^3}<\frac{3\eta}{16n^3}.\] For \(k=1\), \(u=u_1\) and every \(\psi\in \Psi_1\), by the fact that \(\|\psi\|,\|\phi(V_1,1)\|\leq 1\), \[\frac{3}{8}\langle u,{w_2}^{(k)}\rangle+\langle \frac{1}{4n^2}\psi,{w_2}^{({0},k)}\rangle\geq\frac{3\eta}{8n^3}-\frac{\eta}{16n^3} > \frac{3\eta}{16n^3}>\delta_1.\]

As a second step we show that the maximum among \(\psi\in \Psi_1\) is attained uniquely in \(\psi^*_1=\frac{1}{n}\phi(V_1,1)\). For any \(\psi\in \Psi_1\), with \(\psi\neq \psi^*_1\). By 23, for \(k=1\), \(u=u_1\), \[\begin{align} \frac{3}{8}\langle u,{w_2}^{(k)}\rangle+\langle \frac{1}{4n}\psi^*_1,{w_2}^{({0},k)}\rangle&=\frac{3\eta}{8n^3}+\langle \frac{1}{4n}\psi^*_1,\frac{\eta}{4n^2}\phi(V_1,1)\rangle \\&=\frac{3\eta}{8n^3}+\frac{\eta}{16n^2}\langle \psi^*_1,\frac{1}{n}\phi(V_1,1)\rangle \\&\geq \frac{3\eta}{8n^3}+\frac{\eta}{16n^2}\langle \psi,\frac{1}{n}\phi(V_1,1)\rangle+\frac{\eta\epsilon}{16n^2} \\&= \frac{3}{8}\langle u,{w_2}^{(k)}\rangle+\langle \frac{1}{4n}\psi,{w_2}^{({0},k)}\rangle +\frac{\eta\epsilon}{16n^2} \end{align}\] We got that the maximum is uniquely attained at \(k=1, u=u_1, \psi=\frac{1}{n}\phi(V_1,1)\). Now, by 23, for \(j=\argmin_{i}\{i:v_i \in V_1\}\), we get that \[\begin{align} \alpha(\psi)=v_{j}\in V_1. \end{align}\] We notice that \(V_1=P_2\) and thus \(\alpha(\psi)=J_2\). Then, by \(\cE'\), \(\alpha(\psi)\) also holds \(\alpha(\psi)\in S_{2}\). Combining the above together, we get, for \(u_2=\alpha(\psi)\in P_2\cap S_2\), \[\begin{align} {\nabla f(w_2,V_2)}^{(k)}= \begin{cases} \frac{3}{8}u_{1} - \frac{1}{n^3}u_1&\quad k=1\\ -\frac{1}{2} u_{2} &\quad k=2 \\ 0 &\quad k\geq 3 \end{cases} \end{align}\] and, \[\begin{align} {\nabla f(w_2,V_2)}^{(0,k)}= \begin{cases}\frac{1}{4n^2}\phi(V_1,1)-\frac{1}{4n^2}\phi(V_2,1) &\quad k= 1 \\ -\frac{1}{4n^2}\phi(V_1,1) -\frac{1}{4n^2}\phi(V_2,2)&\quad k= 2 \\ 0&\quad k\geq 3, \end{cases} \end{align}\] and the lemma follows. ◻

of 13. First, differentiability can be derived immediately from 27. Second, for \(5\)-Lipschitzness, for every \((V,j)\in Z\), we define \(\tilde{f}_{V,j}:\R^d\to\R\) as \(\tilde{f}_{V,j}(w)\eqq\tilde{f}(w,(V,j))\). By the \(5\)-Lipschitzness of \(f\) with respect to its first argument and Jensen Inequality, for every \(x,y\in \R^d\), it holds that \[\begin{align} |\tilde{f}_{V,j}(x)-\tilde{f}_{V,j}(y)|&=\left|\E_{v\in\delta B}\left(f_{V,j}(y+v)\right)-\E_{v\in\delta B}\left(f_{V,j}(w+v)\right)\right| \\&=\left|\E_{v\in\delta B}\left(f_{V,j}(x+v)-f_{V,j}(y+v)\right)\right| \\&\leq \E_{v\in\delta B}\left|\left(f_{V,j}(x+v)-f_{V,j}(y+v)\right)\right| \\&\leq 5|x-y|. \end{align}\] Third, for convexity, by the convexity of \(f\) for every \(x,y\in \R^d\) and \(\alpha\in[0,1]\), \[\begin{align} \tilde{f}_{V,j}\left(\alpha x + (1-\alpha )y\right)&= \E_{v\in\delta B}\left(f_{V,j}(\alpha x + (1-\alpha )y+v)\right) \\&= \E_{v\in\delta B}\left(f_{V,j}(\alpha (x+v) + (1-\alpha )(y+v))\right) \\&\leq \E_{v\in\delta B}\left(\alpha f_{V,j}(x+v) + (1-\alpha )f_{V,j}(y+v))\right) \\&= \alpha \E_{v\in\delta B}\left(f_{V,j}(x+v)\right) + (1-\alpha )\left(\E_{v\in\delta B}f_{V,j}(y+v)\right) \\&=\alpha \tilde{f}_{V,j}(x) +(1-\alpha) \tilde{f}_{V,j}(y). \end{align}\] ◻

Proof. First, for every \(r\) and \(v\in\mathbb{B}\), by Cauchy-Schwartz Inequality, \[\langle a_r,x_0+\delta v\rangle=\langle a_r,x_0\rangle+\langle a_r,\delta v\rangle\leq \zeta_2+\delta<\zeta_1\] Then, \[\max (\zeta_1, \max_{1\leq r\leq l}\langle a_r,x_0+\delta v\rangle)=\zeta_1,\] and \[h(x_0+\delta v)=g(\max (\zeta_1, \max_{1\leq r\leq l}\langle a_r,x_0+\delta v\rangle)=g(\zeta_1).\] As a result, \[\begin{align} \tilde{h}(x_0)&= \E_{v\sim\mathcal{D}_{\mathbb{B}}}\left[h(x_0+\delta v)\right]= g(\zeta_1) \end{align}\] and by 27, \[\begin{align} \nabla \tilde{h}(x_0)&= \frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[h(x_0+\delta v)v\right]\\&= \frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[g\left(\max (\zeta_1, \max_{1\leq r\leq l}\langle a_r,x_0+\delta v\rangle\right)v\right] \\&=\frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[g(\zeta_1)v\right] \\&=\frac{d}{\delta}g(\zeta_1)\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[v\right] \\&=0 \end{align}\] ◻

Proof. First, for every \(k,r\) and \(u\in\mathbb{B}^{d}\), by Cauchy-Schwartz Inequality, \[\langle a_r,{x_0}^{(k)}+\delta u\rangle=\langle a_r,{x_0}^{(k)}\rangle+\langle a_r,\delta u\rangle\leq \zeta_2+\delta<\zeta_1\] Then, \[g({x_0}^{(k)}+\delta u)=\max (\zeta_1, \max_{1\leq r\leq l}\langle a_r,{x_0}^{(k)}+\delta u\rangle)=\zeta_1,\] and for every \(v\in \mathbb{B}\),\[h(x_0+\delta v)=\sqrt{\sum_{k=1}^Kg(\max (\zeta_1, \max_{1\leq r\leq l}\langle a_r,{x_0}^{(k)}+\delta {v}^{(k)}\rangle)}=\zeta_1\sqrt{K}.\] As a result, \[\begin{align} \tilde{h}(x_0)&= \E_{v\sim\mathcal{D}_{\mathbb{B}}}\left[h(x_0+\delta v)\right]= \zeta_1\sqrt{K}. \end{align}\] Now, by 27, \[\begin{align} \nabla \tilde{h}(x_0)&= \frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[h(x_0+\delta v)v\right]\\&= \frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[\left(\sqrt{\sum_{k=1}^{K}\left(\max (\zeta_1, \max_{1\leq r\leq l}\langle a_r,{x_0}^{(k)}+\delta {v}^{(k)}\rangle\right)^2}\right)\cdot v\right] \\&=\frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[\zeta_1\sqrt{K}v\right] \\&=\frac{d}{\delta}\zeta_1\sqrt{K}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[v\right] \\&=0. \end{align}\] ◻

Proof. First, by Cauchy-Schwartz Inequality, \[\begin{align} \max\left(\zeta_3,\max_{r\neq r_0}\langle a_r,x_0+\delta v\rangle\right)&\leq\max\left(\zeta_3,\max_{r\neq r_0}\langle a_r,x_0\rangle+\max_{r\neq r_0}\langle\delta v,a_r\rangle\right)\\&\leq \max\left(\zeta_3,\zeta_2+G\delta\right) \\&\leq \max\left(\zeta_3,\zeta_2\right)+G\delta\\&<\frac{1}{2}(\zeta_1+\max\left(\zeta_3,\zeta_2)\right), \end{align}\] and for \(r_0\), \[\langle a_{r_{0}},x_0+\delta v\rangle=\langle a_{r_{0}},x_0\rangle+\langle\delta v,a_{r_{0}}\rangle\geq \zeta_1-G\delta>\frac{1}{2}\left(\zeta_1+\max\left(\zeta_2,\zeta_3\right)\right).\] We derive that for every \(v\in \mathbb{B}\), \[h(x_0+\delta v)=\max\left(\zeta_3,\max_{1\leq r\leq l}\langle a_r,x+\delta v\rangle\right))=\langle a_{r_{0}},x+\delta v\rangle.\] and that the maximum is attained in \(r_0\). Then, \[\begin{align} \tilde{h}(x_0)&= \E_{v\sim\mathcal{D}_{\mathbb{B}}}\left[h(x_0+\delta v)\right]\\&= \E_{v\sim\mathcal{D}_{\mathbb{B}}}\left[\langle a_{r_{0}},x_0+\delta v\rangle\right] \\&=\langle a_{r_{0}},x_0+\delta \E_{v\sim\mathcal{D}_{\mathbb{B}}}v\rangle \\&=\langle a_{r_{0}},x_0\rangle \end{align}\] and by 27, \[\begin{align} \nabla\tilde{h}(x_0)&= \frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[\max\left(\zeta_3,\left(\max_{1\leq r\leq l}\langle a_r,x_0+\delta v\rangle\right)\right)v\right] \\&=\frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[\left(\langle a_{r_{0}},x_0+\delta v\rangle\right)v\right] \\&=\langle a_{r_{0}},x_0\rangle\frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[v\right]+\frac{d}{\delta}\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[\langle a_{r_{0}},\delta v\rangle v\right] \\&=0+d a_{r_{0}}^T\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[ v v^T\right] \\&=d a_{r_{0}}^T\E_{v\sim\mathcal{D}_{\mathbb{S}}}\left[ v v^T\right]. \end{align}\] Now, we define random variables \(Y_1,\ldots,Y_d\in \R\),\(X_1,\ldots,X_d\in \R\) and \(Y\in R^d\) such that \(X_i\sim N(0,1)\) (where \(N(0,1)\) is the normal univariate distribution with expectation 0 and variance \(1\)), \(Y_i=\frac{x_i}{\sqrt{\sum_{i=1}^d}X_i^2}\). By 28, we get, for the standard basis vectors \(e_1\ldots e_d\), \[\begin{align} \nabla\tilde{h}(x)&=d a_{r_{0}}^T\E_{Y_1,\ldots,Y_d}\left[\sum_{i=1}^d Y_i^2e_ie_i^T\right] \\&=d a_{r_{0}}^T\sum_{i=1}^d \E_{Y_i}\left[Y_i^2\right] e_ie_i^T \\&=d a_{r_{0}}^T\sum_{i=1}^d \E_{X_i}\left[\frac{X_i^2}{\sum_{l=1}^d X_l^2}\right] e_ie_i^T \\&=d a_{r_{0}}^T\sum_{i=1}^d \frac{1}{d}e_ie_i^T \\&=a_{r_{0}} \end{align}\] ◻

of 14. We assume that \(\cE\) (10 ) holds and show 14 under this event. We prove the claim by induction on \(t\). For \(t=1\), it is trivial. Now, we assume that \(w_t=\tilde{w}_t\).

For \(\ell_1\), in every \(t\), by the proofs of 18 19 20 21 and 4, it can be observed that for every \(i\in[n]\), \(k\geq 2\), \(\max_{t}\max_{u \in V_i}\langle u,{w_t}^{(k)}\rangle\leq \frac{\eta}{16}\), thus, in every iteration the term that gets the maximal value is \(\frac{3\eta}{32}\). Then, by 30 and the hypothesis of the induction, for every \(i\), \[\begin{align} \nabla \tilde{\ell}_1(\tilde{w}_t,V_i)&=\nabla\tilde{\ell}_1(w_{t},V_i) =0 =\nabla \ell_1(w_{t},V_i). \end{align}\]

For \(\tilde{\ell}_2\) and every \(w\in \R^d\), \(V\subseteq U\) and \(j\in[n^2]\), by linearity of expectation, \[\begin{align} \tilde{\ell}_2(w,(V,j))&=\E_{v\in\delta B}\left(\langle {w}^{({{0}})}+{v}^{({{0}})},-\phi(V,j)\rangle\right) \\&=\ell_2(w,(V,j))+\left(\langle \E_{v\in\delta B}{v}^{({{0}})},-\phi(V,j)\rangle\right) \\&=\ell_2(w,(V,j)) \end{align}\] Then, we derive that for every \(w\) and \(i\), \(\nabla\tilde{\ell}_2(w,(V_i,j_i))=\nabla\ell_2(w,(V_i,j_i))\).

For \(\tilde{\ell}_3\), which is a \(2\)-Lipschitz linear function, for \(t=1\), by the proof of 18, the term that gets the maximal value is \(\delta_1\). Moreover, it can be observed that for such \(t\), and every \(\psi\in\Psi\), \[\max_{\psi\in \Psi} \left(\langle{w}^{({{0}})}_1, \psi\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi), {w_1}^{(1)}\rangle \right)=0.\] Then, we can apply 29, and get by the hypothesis of the induction, \[\begin{align} \nabla \tilde{\ell}_3(\tilde{w}_1)&=\nabla\tilde{\ell}_3(w_{1}) =0 =\nabla \ell_3(w_{1}). \end{align}\] If \(t\geq 2\), it can be observed that \[\begin{align} \ell_3(w_{t})&=\max\left(\delta_2,\max_{\psi\in \Psi} \left(\langle{w}^{({{0}})}_t, \psi\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi), {w_t}^{(1)}\rangle \right)\right)\\&=\max_{\psi\in \Psi} \left(\langle{w}^{({{0}})}_t, \psi\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi), {w_t}^{(1)}\rangle \right) \end{align}\] Then, by the proofs of 19 20 21 and 4, the maximal value of \(\langle{w}^{({{0}})}, \psi\rangle - \frac{1}{4}\frac{\epsilon}{T^2}\langle \alpha(\psi), {w}^{(1)}\rangle\) is attained in \(\psi=\psi^*\) and the difference from the second maximal possible value of this term is at most \(\frac{\epsilon}{2T^2}\). As a result, using the fact that this maximum is also larger than \(\delta_2\) by at least \(\frac{\eta}{8n}\) (which is also larger than \(\delta\)), we can apply 31 and get by the hypothesis of the induction that, \[\begin{align} {\nabla \tilde{\ell}_3(\tilde{w}_t)}^{(k)}&={\nabla\tilde{\ell}_3(w_{t})}^{(k)} \\&=\begin{cases} \frac{1}{n}\sum_{i=1}^n\phi(V_i,j_i) &\quad k={0}\\ -\frac{\epsilon}{4T^2}\alpha(\frac{1}{n}\sum_{i=1}^n\phi(V_i,j_i) )&\quad k=1\\ 0 &\quad \text{otherwise} \end{cases} \\&={\nabla \ell_3(w_{t})}^{(k)}. \end{align}\]

For \(\tilde{\ell}_4\), for \(t\in \{1,2\}\), by the proofs of 18 19, the term that gets the maximal value is \(\delta_2\). Moreover, it can be observed that for every such \(t\), and every \(k\in[T-1\)] and \(u\in U\), \[\frac{3}{8}\langle u,{w_t}^{(k)}\rangle-\frac{1}{2}\langle u,{w_t}^{(k+1)}\rangle=0.\] Then, we can apply 29, and get by the hypothesis of the induction, \[\begin{align} \nabla \tilde{\ell}_4(\tilde{w}_t)&=\nabla\tilde{\ell}_4(w_{t}) =0 =\nabla \ell_4(w_{t}). \end{align}\] For \(t=3\), it can be observed by the proof of 20 that, \[\begin{align} \ell_4(w_{t})&=\max\left(\delta_2,\max_{k\in [T-1], u \in U}\left(\frac{3}{8}\langle u,{w_t}^{(k)}\rangle-\frac{1}{2}\langle u,{w_t}^{(k+1)}\rangle\right)\right)\\&=\max_{k\in [T-1], u \in U}\left(\frac{3}{8}\langle u,{w_t}^{(k)}\rangle-\frac{1}{2}\langle u,{w_t}^{(k+1)}\rangle\right) \end{align}\] Moreover, the maximal value is \(\frac{3\eta\epsilon}{32T^2}\) and is attained in \(k_0=1,u=u_0=\alpha(\psi^*)\). The second maximal possible value of this term is \(\delta_2=\frac{3\eta\epsilon}{64T^2}\), then, by the fact that \(\delta<\frac{3\eta\epsilon}{32T^2}-\frac{3\eta\epsilon}{64T^2}=\frac{3\eta\epsilon}{64T^2}\), we can apply 31 and get by the hypothesis of the induction that \[\begin{align} {\nabla \tilde{\ell}_4(\tilde{w}_t)}^{(k)}&={\nabla\tilde{\ell}_4(w_{t})}^{(k)} \\&=\begin{cases} \frac{3}{8}u_0 &\quad k=1\\ -\frac{1}{2}u_0 &\quad k=2\\ 0 &\quad \text{otherwise} \end{cases} \\&={\nabla \ell_4(w_{t})}^{(k)}. \end{align}\] For \(t\geq 4\), it can be observed by the proofs of 4 21 that, \[\begin{align} \ell_4(w_{t})&=\max\left(\delta_2,\max_{k\in [T-1], u \in U}\left(\frac{3}{8}\langle u,{w_t}^{(k)}\rangle-\frac{1}{2}\langle u,{w_t}^{(k+1)}\rangle\right)\right)\\&=\max_{k\in [T-1], u \in U}\left(\frac{3}{8}\langle u,{w_t}^{(k)}\rangle-\frac{1}{2}\langle u,{w_t}^{(k+1)}\rangle\right) \end{align}\] Moreover, the maximal value is \(\frac{3\eta}{16}\) and is attained in \(k_0=t-2,u=u_0=\alpha(\psi^*)\). The second maximal possible value of this term is smaller then \(\frac{5\eta}{64}\), then we can apply again 31 and get by the hypothesis of the induction that \[\begin{align} {\nabla \tilde{\ell}_4(\tilde{w}_t)}^{(k)}&={\nabla\tilde{\ell}_4(w_{t})}^{(k)} \\&=\begin{cases} \frac{3}{8}u_0 &\quad k=t-2\\ -\frac{1}{2}u_0 &\quad k=t-1\\ 0 &\quad \text{otherwise} \end{cases} \\&={\nabla \ell_4(w_{t})}^{(k)}. \end{align}\]

In conclusion, we proved that \(\nabla \widehat{F}(w_t)=\nabla \widehat{\tilde{F}}(\tilde{w}_t)\), thus, by the hypothesis of the induction, \[w_{t+1} = w_t - \nabla \widehat{F}(w_t)=\tilde{w}_t - \nabla \widehat{\tilde{F}}(\tilde{w}_t)=\tilde{w}_{t+1}\] ◻

Proof. By the fact that \(f\) is \(G\)-Lipschitz, \[\begin{align} |\tilde{f}(x)-f(x)|&= |\E_{v\sim\mathcal{D}_{\mathbb{B}}}\left[f(x+\delta v)\right]-f(x)|\\&\leq |\E_{v\sim\mathcal{D}_{\mathbb{B}}}\left[f(x)\right]+G\delta\E_{v\sim\mathcal{D}_{\mathbb{B}}}+\left[\|v\|\right]-f(x)| \\&=G\delta\E_{v\sim\mathcal{D}_{\mathbb{B}}}\left[\|v\|\right] \\&\leq G\delta \end{align}\] ◻

of 15. First, differentiability can be derived immediately from 27. Second, for \(4\)-Lipschitzness, for every \(V\in Z\), we define \(\tilde{f}^{\text{SGD}}_{V}:\R^d\to\R\) as \(\tilde{f}^{\text{SGD}}_{V}(w)\eqq\tilde{f}^{\text{SGD}}(w,V)\). By the \(5\)-Lipschitzness of \(f^{\text{SGD}}\) with respect to its first argument and Jensen Inequality, for every \(x,y\in \R^d\), it holds that \[\begin{align} |\tilde{f}^{\text{SGD}}_{V}(x)-\tilde{f}^{\text{SGD}}_{V}(y)|&=\left|\E_{v\in\delta B}\left(f^{\text{SGD}}_{V}(y+v)\right)-\E_{v\in\delta B}\left(f^{\text{SGD}}_{V}(w+v)\right)\right| \\&=\left|\E_{v\in\delta B}\left(f^{\text{SGD}}_{V}(x+v)-f^{\text{SGD}}_{V}(y+v)\right)\right| \\&\leq \E_{v\in\delta B}\left|\left(f^{\text{SGD}}_{V}(x+v)-f^{\text{SGD}}_{V}(y+v)\right)\right| \\&\leq 4|x-y|. \end{align}\] Third, for convexity, by the convexity of \(f^{\text{SGD}}\) for every \(x,y\in \R^d\) and \(\alpha\in[0,1]\), \[\begin{align} \tilde{f}^{\text{SGD}}_{V}\left(\alpha x + (1-\alpha )y\right)&= \E_{v\in\delta B}\left(f^{\text{SGD}}_{V}(\alpha x + (1-\alpha )y+v)\right) \\&= \E_{v\in\delta B}\left(f^{\text{SGD}}_{V}(\alpha (x+v) + (1-\alpha )(y+v))\right) \\&\leq \E_{v\in\delta B}\left(\alpha f^{\text{SGD}}_{V}(x+v) + (1-\alpha )f_{V}(y+v))\right) \\&= \alpha \E_{v\in\delta B}\left(f^{\text{SGD}}_{V}(x+v)\right) + (1-\alpha )\left(\E_{v\in\delta B}f^{\text{SGD}}_{V}(y+v)\right) \\&=\alpha \tilde{f}^{\text{SGD}}_{V}(x) +(1-\alpha) \tilde{f}^{\text{SGD}}_{V,j}(y). \end{align}\] ◻

of 16. We assume that \(\cE'\) (12 ) holds and prove 16 under this event. We prove the claim by induction on \(t\). For \(t=1\), it is trivial. Now, we assume that \(w_t=\tilde{w_t}\). First, for \(\tilde{\ell}^{\text{SGD}}_3\) and every \(w\) and \(V\), by linearity of expectation, \[\begin{align} \tilde{\ell}^{\text{SGD}}_3(w,V)&=\E_{v\in\delta B}\left(\langle {w}^{({0},1)}+{v}^{({0},1)},-\frac{1}{4n^2}\phi(V,1)\rangle -\langle \frac{1}{n^3} u_1, {w}^{(1)}+{v}^{(1)}\rangle\right)\\&=\ell^{\text{SGD}}_3(w,V)+\left(\langle \E_{v\in\delta B}{v}^{({0},1)},-\frac{1}{4n^2}\phi(V,1)\rangle -\langle \frac{1}{n^3} u_1, \E_{v\in\delta B}{v}^{(1)}\rangle\right) \\&=\ell^{\text{SGD}}_3(w,V) \end{align}\] Then, we derive that for every \(w\), \(\nabla\tilde{\ell}^{\text{SGD}}_3(w,V)=\nabla\ell^{\text{SGD}}_3(w,V)\). Now, for \(r\in\{1,2\}\) we show that in each term \(\tilde{\ell}^{\text{SGD}}_r(w_t,V_t)\), the argument that gives the maximum value is the same as \(\ell^{\text{SGD}}_r(w_t,V_t)\).

For \(\tilde{\ell}^{\text{SGD}}_1(w_t,V_t)\), in every \(t\), by the proofs of 24, 25 and 10, the maximal value is \(\frac{3\eta}{32}\). Moreover, it can be observed that for every \(k\geq 2\), \(\max_{t}\max_{u \in V_t}\langle u,{w_t^\text{SGD}}^{(k)}\rangle\leq \frac{\eta}{16}\). Then, by 30, and the hypothesis of the induction, \[\begin{align} \nabla \tilde{\ell}^{\text{SGD}}_1(\tilde{w_{t}},V_{t})&=\nabla\tilde{\ell}^{\text{SGD}}_1(w_{t},V_{t}) =0 =\nabla \ell^{\text{SGD}}_1(w_{t},V_t). \end{align}\] Now, for \(\tilde{\ell}^{\text{SGD}}_2\), for \(t=1\), \(\nabla \ell^{\text{SGD}}_2(w_1,V_1)= 0\) and the maximum is attained uniquely in \(\delta_1=\frac{\eta}{8n^3}\) (the second maximal value is zero). Then, we can apply 29 and by the hypothesis of the induction, it follows that, \[\begin{align} \nabla \tilde{\ell}^{\text{SGD}}_2(\tilde{w_{1}},V_1)&=\nabla\tilde{\ell}^{\text{SGD}}_2(w_{1},V_1) =0 =\nabla \ell^{\text{SGD}}_2(w_{1},V_1). \end{align}\] For every \(t\geq 2\), the maximum is attained uniquely in the linear term of \(k=t-1\),\(u=u_{t-1}\) and \(\psi=\psi^*_{t-1}\) such that the difference between the maximal value the second largest value is larger than \(\frac{\eta\epsilon}{16n^2}\). Then, we can apply 31 and by the hypothesis of the induction, it follows that, \[\begin{align} \nabla \tilde{\ell}^{\text{SGD}}_2(\tilde{w_{t}},V_t)&=\nabla\tilde{\ell}^{\text{SGD}}_2(w_{t},V_t) =\nabla \ell^{\text{SGD}}_t(w_{t},V_t). \end{align}\] In conclusion, we proved that \(\nabla \tilde{f}^{\text{SGD}}(\tilde{w_{t}},V_t)=\nabla f^{\text{SGD}}(w_{t},V_t)\), thus, by the hypothesis of the induction, \[w_{t+1}= w_t- \nabla f^{\text{SGD}}(w_{t},V_t)=\tilde{w}_t - \nabla \tilde{f}^{\text{SGD}}(\tilde{w}_{t},V_t)=\tilde{w}_{t+1}.\] ◻

Proof. We prove by induction on \(t\). For \(t=1\), \(w_t=0\), thus, \[w_1[i]=0\leq \frac{1}{2\sqrt{d}}.\] Moreover, the maximizer is \(j_1=1\). Then, we notice that for both \(d=1\) and \(d=25\eta^2T^2\), \(\eta \leq\frac{1}{5\sqrt{T}}\implies\eta\leq \frac{1}{5\sqrt{d}}\). Then, it holds that, \[\begin{align} \frac{1}{\sqrt{d}}-w_1[j_1]-\frac{\eta j_1}{4d}&\geq \frac{1}{\sqrt{d}}-w_1[j_1]-\frac{\eta}{4}\\&\geq \frac{19}{20\sqrt{d}} \\&>\frac{\eta}{8d}, \end{align}\] and, for every \(k\neq j_1\), \[\begin{align} \frac{1}{\sqrt{d}}-w_1[j_1]-\frac{\eta j_1}{4d}&= \frac{1}{\sqrt{d}}-w_1[k]-\frac{\eta k}{4d}+\frac{\eta (k-j_1)}{4d} \\&\geq \frac{1}{\sqrt{d}}-w_1[k]-\frac{\eta k}{4d}+\frac{\eta}{4d} \\&>\frac{1}{\sqrt{d}}-w_1[k]-\frac{\eta k}{4d}+\frac{\eta}{8d} . \end{align}\]

In the step of the induction we assume that the lemma holds for every \(s\leq t\) and prove it for \(s=t+1\). By the hypothesis of the induction, we know that for every iteration \(s\leq t\), \(\|w_t\|_2\leq \frac{1}{2}\), as a result, we know that the projections does not affect the dynamics of the algorithm until the iteration \(t\). Moreover, we know that for every iteration \(s\leq t\) there exists an index \(j_s\in[d]\) such that the term that achieve the maximum value in \(w_s\) is \(\frac{1}{\sqrt{d}}-w_s[j_s]-\frac{\eta j}{4d}\). This maximum is attained uniquely in \(j_s\) by margin that is strictly larger than \(\frac{\eta}{8d}\). As a result, we derive that, for every \(s\leq t\), \(\nabla f (w_s)=-e_{j_{s}}\). Now, for every index \(m\in[d]\), we define, \[n_t^m=|\{s\leq t : m=\arg\max_{i\in[d]} \{\frac{1}{\sqrt{d}}-w_s[i]-\frac{\eta i}{4d}\}\}|.\] We get that, for every \(i\) it holds that, \[w_{t+1}[i]=\eta n_t^i.\] Then, \[\begin{align} \|w_{t+1}\|_1=\sum_{i} \eta n_t^i\leq \eta t, \end{align}\] and ,thus, there exists a entry \(k\in [d]\) with \(w_{t+1}[k]\leq\frac{\eta t}{d}\). Now, we prove the first part of the lemma using this observation and the step of the induction. For every \(i\neq j_t\), \[w_{t+1}[i]=w_{t}[i]\leq \frac{1}{2\sqrt{d}}.\] Otherwise, we know that, by the definition of \(j_t\) \[\begin{align} \frac{1}{\sqrt{d}}-w_{t}[i]-\frac{\eta i}{4d}>\frac{1}{\sqrt{d}}-w_t[k]-\frac{\eta k}{4d}+\frac{\eta}{8d}, \end{align}\] \[\begin{align} w_{t}[i]&<w_t[k]+\frac{\eta (k-i)}{4d}-\frac{\eta}{8d} \\&\leq\frac{\eta t}{d}+\frac{\eta}{4} \\&\leq\frac{1}{25\sqrt{d}}+\frac{1}{20\sqrt{d}} \end{align}\] and, \[\begin{align} w_{t+1}[i] &\leq w_{t}[i]+\eta \\&\leq \frac{1}{25\sqrt{d}}+\frac{1}{20\sqrt{d}} +\frac{1}{5\sqrt{d}} \\&\leq\frac{1}{2\sqrt{d}}, \end{align}\] where we again used the fact that \(\eta\leq \frac{1}{5\sqrt{T}}\) implies \(\eta\leq\frac{1}{5\sqrt{d}}\) for both \(d=1\) and \(d=25\eta^2T^2\).

For the second part of the lemma, we define \(J_t\subseteq [d]\), \(J_t=\argmin_{j}\{n_t^j\}\) and \(j_{t+1}=\min \{j\in J_t\}\) and show that \(j_{t+1}\) holds the required. We know, for every \(j\neq i\in[d]\), \[\begin{align} w_{t+1}[i]-w_{t+1}[j]=\eta(n_t^i-n_t^j). \end{align}\] For \(k\neq j_{t+1}\) with \(n_t^k > n_t^{j_{t+1}}\), \[\begin{align} \frac{1}{\sqrt{d}}-w_{t+1}[j_{t+1}]-\frac{\eta j_{t+1}}{4d}&\leq \frac{1}{\sqrt{d}}-w_{t+1}[k]-\eta-\frac{\eta j_{t+1}}{4d} \\& = \frac{1}{\sqrt{d}}-w_{t+1}[k]-\eta- \frac{\eta k}{4d}+\frac{\eta(k-j_{t+1})}{4d} \\& \leq \frac{1}{\sqrt{d}}-w_{t+1}[k]-\eta- \frac{\eta k}{4d}+\frac{\eta}{4} \\& < \frac{1}{\sqrt{d}}-w_{t+1}[k]- \frac{\eta k}{4d}-\frac{\eta}{2}. \end{align}\] in contradiction to the fact that \(j_{t+1}\) gets the maximal value. For \(k\neq j_{t+1}\) with \(n_t^k > n_t^{j_{t+1}}\), it holds that \(w_{t+1}[j_{t+1}]\leq w_{t+1}[k]-\eta\), and, \[\begin{align} \frac{1}{\sqrt{d}}-w_{t+1}[j_{t+1}]-\frac{\eta j_{t+1}}{4d}&\geq \frac{1}{\sqrt{d}}-w_{t+1}[k]+\eta-\frac{\eta j_{t+1}}{4d} \\& = \frac{1}{\sqrt{d}}-w_{t+1}[k]+\eta- \frac{\eta k}{4d}+\frac{\eta(k-j_{t+1})}{4d} \\& \geq \frac{1}{\sqrt{d}}-w_{t+1}[k]+\eta- \frac{\eta k}{4d}-\frac{\eta}{4} \\& > \frac{1}{\sqrt{d}}-w_{t+1}[k]- \frac{\eta k}{4d}+\frac{\eta}{8d}, \end{align}\] as required. For the third part of the lemma, we know that for every \(i\in [d]\), \[\begin{align} \frac{1}{\sqrt{d}}-w_{t+1}[i]-\frac{\eta i}{4d} &\geq \frac{1}{2\sqrt{d}}-\frac{\eta }{4} \\&= \frac{9}{20\sqrt{d}} \\&>\frac{\eta}{8d}. \end{align}\] ◻

of 33. The first part of the theorem is an immediate corollary from 34. Moreover, by applying this lemma again, we know that, for every \(i\in[d]\), \[\begin{align} w_{T,m}[i]\leq \frac{1}{2\sqrt{d}}, \end{align}\] thus, \[\begin{align} f^{\text{OPT}}(w_{T,m})-f^{\text{OPT}}(w_*)&\geq \frac{1}{2\sqrt{d}}-\frac{\eta}{4}-0 \\&\geq \frac{1}{2\sqrt{d}}-\frac{\eta}{20\sqrt{d}} \\&> \frac{1}{4\sqrt{d}} \\&=\min\left(\frac{1}{4}, \frac{1}{20\eta T}\right). \end{align}\] ◻

Proof. We proof the lemma by induction on \(t\). For \(t=1\), we know that \(w_1=\tilde{w}_1=0\). Now, we assume that \(w_t=\tilde{w}_t\). By 34, we know that the maximum of the loss function is attained uniquely with the property that the difference between the maximal value and the second maximal value is larger then \(\frac{\eta}{8d}\). As a result, by the facts that \(f\) is \(1\)-Lipschitz and \(\delta=\frac{\eta}{16d}\), we can use 31 for \(\widehat{F}(w_t)\) and get that, \[\nabla \widehat{F}(w_t)=\nabla \widehat{\tilde{F}}(w_t)=\nabla \widehat{\tilde{F}}(\tilde{w}_t).\] It follows by the hypothesis of the induction that, \[w_{t+1} = w_t - \nabla \widehat{F}(w_t)=\tilde{w}_t - \nabla \widehat{\tilde{F}}(\tilde{w}_t)=\tilde{w}_{t+1}.\] ◻

of 35. Let \(\overline{w_{T,m}}\) be the \(m\)-suffix average of \(GD\) when is applied on \(f^{\text{OPT}}\). Let \(\overline{w_*}=\argmin_w f^{\text{OPT}}(w)\). By 36, we know that, \(w_{T,m}=\overline{w_{T,m}}\). Then, by 33 and 32, \[\begin{align} \frac{1}{4\sqrt{d}}&\leq f^{\text{OPT}}(\overline{w_{T,m}})-f^{\text{OPT}}(\overline{w_*}) \\&=f^{\text{OPT}}(w_{T,m})-f^{\text{OPT}}(\overline{w_*}) \\&\leq \tilde{f}^{\text{OPT}}(w_{T,m})+\delta-\tilde{f}^{\text{OPT}}(\overline{w_*})+\delta \\&\leq \tilde{f}^{\text{OPT}}(w_{T,m})+\delta-\tilde{f}^{\text{OPT}}(w_*)+\delta, \end{align}\] and, \[\begin{align} \tilde{f}^{\text{OPT}}(w_{T,m})-\tilde{f}^{\text{OPT}}(w_*)&\geq \frac{1}{4\sqrt{d}}-\frac{\eta}{8d} \\&\geq \frac{1}{4\sqrt{d}}-\frac{1}{8\sqrt{d}} \\&\geq \frac{1}{8\sqrt{d}} \\&\geq \min(\frac{1}{8},\frac{1}{40\eta T}) . \end{align}\] ◻