\section{Proof of Theorem \ref{thm:main}\label{sec:theory}}
{\color{red} Ahmet: I'll modify with $Ax-b$, and also remove the assumption on $k_0$, also add the small proof for second order stationarity we discussed with Armin}\textbf{AE: IMHO, the first two are not worth the effort right now.}
For every $k\ge2$, recall from (\ref{eq:Lagrangian}) and Step~2 of Algorithm~\ref{Algo:2} that $x_{k}$ satisfies
We next translate \eqref{eq:before_restriction} into a bound on the feasibility gap $\|A(x_k)\|$. Using the regularity condition \eqref{eq:regularity}, the left-hand side of \eqref{eq:before_restriction} can be bounded below as
In words, the feasibility gap is directly controlled by the dual sequence $\{y_k\}_k$. We next establish that the dual sequence is bounded. Indeed, for every $k\in K$, note that
\begin{align}
\|y_k\|& = \| y_0 + \sum_{i=1}^{k}\s_i A(x_i) \|
\quad\text{(Step 5 of Algorithm \ref{Algo:2})}
\nonumber\\
&\le\|y_0\|+ \sum_{i=1}^k \s_i \|A(x_i)\|
\qquad\text{(triangle inequality)}\nonumber\\
&\le\|y_0\|+ \sum_{i=1}^k \frac{\|A(x_1)\|\log^2 2 }{ k \log^2(k+1)}
\quad\text{(Step 4)}
\nonumber\\
&\le\|y_0\|+ c \|A(x_1) \|\log^2 2 =: y_{\max},
\label{eq:dual growth}
\end{align}
where
\begin{align}
c \ge\sum_{i=1}^{\infty}\frac{1}{k \log^2 (k+1)}.
\end{align}
Substituting \eqref{eq:dual growth} back into \eqref{eq:before_dual_controlled}, we reach
where the second line above holds if $k_0$ is large enough, which would in turn guarantees that $\epsilon_k=1/\b_{k-1}$ is sufficiently small since $\{\b_k\}_k$ is increasing and unbounded.
Let us now revisit and simplify \eqref{eq:to_be_checked_later}. Note that $\rho'$ automatically satisfies the second inequality there, owing to Step~3 of Algorithm~\ref{Algo:2}. Also, $\rho$ satisfies the first inequality in \eqref{eq:to_be_checked_later} if
%where the last line above holds when $k_0$ is large enough, because $\b_k \ge \b_1$ and $\lim_{k\rightarrow\infty} \epsilon_k=0$.
It remains to control the first term in \eqref{eq:cvg metric}. To that end, after recalling Step 2 of Algorithm~\ref{Algo:2} and applying the triangle inequality, we can write that
The first term on the right hand side is lower bounded by $-\epsilon_{k-1}$ by Step 2 of Algorithm~\ref{Algo:2}, we next have to bound the second term on the right hand side.