Editing Openai/693e3ce6-229c-8008-97dc-ab720cb1f95a (section)

=== Assistant: Append the following material it converts the support-sum bound into a total running-time / total coordinate-work bound… ===
Append the following material (it converts the support-sum bound into a total running-time / total coordinate-work bound, using ∣S⋆∣≤1/ρ|S^\star|\le 1/\rho∣S⋆∣≤1/ρ as in the local-PPR setting). open-problem-fountoulakis22a

<syntaxhighlight lang="latex">% ============================================================
\section{Total running time via the sum of supports}

We now convert the support-sum bounds into a total work bound for an $\varepsilon$-accurate solution.
Throughout, we measure work in a standard \emph{support-sensitive} model: the cost of iteration $k$
is proportional to the number of (stored/updated) nonzeros in the vectors that appear in the update.
This is the same model implicitly used when one argues that a method is ``local'' because it only
touches $O(1/\rho)$ coordinates per iteration.

\subsection{A simple support-sensitive work model}

\begin{assumption}[Support-sensitive iteration cost]\label{ass:work_model}
There exist absolute constants $c_1,c_2>0$ such that iteration $k$ of \eqref{eq:apg}
can be implemented with work
\[
\mathrm{work}(k) \;\le\; c_1\,|\supp(y_k)| \;+\; c_2\,|\supp(x_{k+1})|.
\]
(Any $O(1)$ overhead per iteration can be absorbed into the constants.)
\end{assumption}

\begin{lemma}[Support of the extrapolated point]\label{lem:supp_y}
For all $k\ge 1$,
\[
\supp(y_k)\subseteq \supp(x_k)\cup \supp(x_{k-1}),
\qquad\text{hence}\qquad
|\supp(y_k)| \le |\supp(x_k)|+|\supp(x_{k-1})|.
\]
\end{lemma}

\begin{proof}
Coordinatewise, $y_{k,i}=(1+\beta)x_{k,i}-\beta x_{k-1,i}$.
Thus if $x_{k,i}=x_{k-1,i}=0$ then $y_{k,i}=0$.
\end{proof}

\subsection{Total work up to a fixed iteration budget}

Define the cumulative work up to $N$ iterations as
\[
\mathrm{Work}(N) := \sum_{k=0}^{N-1}\mathrm{work}(k).
\]

Let
\begin{equation}\label{eq:Cspur_def}
C_{\rm spur}:=\left(\frac{1+tL}{t\gamma}\right)^2
\left(
\frac{2\Delta_0}{\mu}
+\frac{4\Delta_0}{\mu}\cdot \frac{(1+\beta)^2 q + \beta^2}{1-q}
\right),
\end{equation}
which is exactly the constant appearing in Theorem~\ref{thm:sum_support_transient}.

\begin{corollary}[Work bound up to $N$ iterations]\label{cor:workN}
Assume Assumptions~\ref{ass:margin},~\ref{ass:linear_rate}, and~\ref{ass:work_model}.
Then for every integer $N\ge 1$,
\begin{align}
\sum_{k=0}^{N-1} |\supp(x_{k+1})|
&\le N|S^\star| + C_{\rm spur},\label{eq:supp_sum_xN}\\
\sum_{k=0}^{N-1} |\supp(y_k)|
&\le 2N|S^\star| + 2C_{\rm spur},\label{eq:supp_sum_yN}
\end{align}
and therefore
\begin{equation}\label{eq:workN_bound}
\mathrm{Work}(N) \;\le\; O\!\left(N|S^\star| + C_{\rm spur}\right),
\end{equation}
where the hidden constant depends only on $(c_1,c_2)$.

If, moreover, $|S^\star|\le 1/\rho$, then
\begin{equation}\label{eq:workN_rho}
\mathrm{Work}(N) \;\le\; O\!\left(\frac{N}{\rho} + C_{\rm spur}\right).
\end{equation}
\end{corollary}

\begin{proof}
For each $k$ we have $\supp(x_{k+1})\subseteq S^\star \cup A_k$, hence
$|\supp(x_{k+1})|\le |S^\star|+|A_k|$.
Summing over $k=0,\dots,N-1$ yields
$\sum_{k=0}^{N-1} |\supp(x_{k+1})|\le N|S^\star| + \sum_{k=0}^{N-1}|A_k|$.
The proof of Theorem~\ref{thm:sum_support_transient} bounds the entire geometric series
$\sum_{k=0}^{\infty}|A_k|\le C_{\rm spur}$, which implies \eqref{eq:supp_sum_xN}.
Next, Lemma~\ref{lem:supp_y} gives for $k\ge 1$:
$|\supp(y_k)|\le |\supp(x_k)|+|\supp(x_{k-1})|$.
Summing this for $k=1,\dots,N-1$ and using $y_0=x_0$ yields \eqref{eq:supp_sum_yN}.
Finally, combine \eqref{eq:supp_sum_xN}--\eqref{eq:supp_sum_yN} with Assumption~\ref{ass:work_model}.
\end{proof}

\subsection{Total work to reach $\varepsilon$ accuracy}

Assumption~\ref{ass:linear_rate} implies that $F(x_N)-F(x^\star)\le \varepsilon$ once
\begin{equation}\label{eq:Neps_def}
N \;\ge\; N_\varepsilon
:= \left\lceil \frac{\log(\Delta_0/\varepsilon)}{\log(1/q)} \right\rceil.
\end{equation}

\begin{corollary}[Total running time to $\varepsilon$ accuracy]\label{cor:workeps}
Assume $|S^\star|\le 1/\rho$ and the hypotheses of Corollary~\ref{cor:workN}.
Then the total support-sensitive work to compute an iterate $x_N$ with
$F(x_N)-F(x^\star)\le \varepsilon$ is
\begin{equation}\label{eq:workeps_general}
\mathrm{Work}(N_\varepsilon)
\;\le\;
O\!\left(
\frac{1}{\rho}\cdot\frac{\log(\Delta_0/\varepsilon)}{\log(1/q)}
\;+\;
C_{\rm spur}
\right).
\end{equation}

With the standard accelerated choice $q\approx 1-\sqrt{\mu/L}$ and step $t=1/L$, this becomes
\begin{equation}\label{eq:workeps_simplified}
\mathrm{Work}(N_\varepsilon)
=
O\!\left(
\frac{1}{\rho}\sqrt{\frac{L}{\mu}}\,\log\frac{\Delta_0}{\varepsilon}
\;+\;
\frac{\Delta_0\,L^{5/2}}{\gamma^2\,\mu^{3/2}}
\right).
\end{equation}

In the $\ell_1$-regularized PageRank setting (undirected graph), $L\le 1$ and $\mu=\alpha$.
If additionally $\Delta_0\le \alpha/2$ (single-seed case) and we take $t=1$, then
\begin{equation}\label{eq:workeps_ppr}
\mathrm{Work}(N_\varepsilon)
=
O\!\left(
\frac{1}{\rho\sqrt{\alpha}}\log\frac{1}{\varepsilon}
\;+\;
\frac{1}{\gamma^2\sqrt{\alpha}}
\right),
\end{equation}
up to the standard constant-factor variants in the accelerated rate.
\end{corollary}
% ============================================================

</syntaxhighlight>