#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\begin_preamble
% specify here the journal
%\journal{Example: Nuclear Physics B}

% use this if you need line numbers
%\usepackage{lineno}
\usepackage{algorithmic}
\usepackage{hyperref}
\usepackage{tcolorbox}
%\usepackage[inline]{showlabels}
\end_preamble
\use_default_options false
\begin_modules
theorems-ams-bytype
theorems-ams-extended-bytype
fixltx2e
pdfcomment
pdfform
graphicboxes
tcolorbox
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures false
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command bibtex
\index_command default
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder false
\pdf_colorlinks true
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style siam
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 2.5cm
\topmargin 3cm
\rightmargin 2.5cm
\bottommargin 2.5cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 2
\paperpagestyle headings
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
\begin_inset Note Note
status collapsed

\begin_layout Plain Layout
Include: macro.lyx means that you can't use macro syntax in title, but you
 can use latex syntax there.
\end_layout

\end_inset


\begin_inset CommandInset include
LatexCommand include
filename "~/FORK/macros.lyx"

\end_inset


\begin_inset ERT
status open

\begin_layout Plain Layout

%
\backslash
renewcommand{
\backslash
showlabelfont}{
\backslash
tiny
\backslash
color{blue}}
\end_layout

\end_inset


\end_layout

\begin_layout Title
CodeDoc
\end_layout

\begin_layout Standard
In this doc, we focus on personalized Pagerank with 
\begin_inset Formula $\ell_{1}$
\end_inset

-Regularization problem, which can be written as follows:
\begin_inset Formula 
\begin{equation}
\begin{split}\min_{\xbf\in\mbb R^{n}}\ \  & \norm{D^{1/2}\xbf}_{1}\\
\st\ \  & \tfrac{1}{2}\inprod{\xbf}{Q\xbf}-\alpha\inprod{\sbf}{D^{-1/2}\xbf}\leq b,
\end{split}
\label{eq:P}
\end{equation}

\end_inset

where all notations are defined as following Table
\begin_inset ERT
status open

\begin_layout Plain Layout

~
\end_layout

\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "tab:Notations"

\end_inset

.
 Furthermore, the 
\begin_inset Formula $\nabla G(\xbf):=Q\xbf-\alpha D^{-1/2}\sbf$
\end_inset

.
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:Notations"

\end_inset

Notations
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Notations
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Meaning
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\sbf$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
located in probability space, i.e., 
\begin_inset Formula $\inprod{\sbf}{\onebf}=1$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $Q$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $D^{-1/2}\brbra{D-\tfrac{1-\alpha}{2}(D+A)}D^{-1/2}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\alpha$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\in[0,1]$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $A$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
adjacency matrix, that is 
\begin_inset Formula $A_{i,j}=1$
\end_inset

 if 
\begin_inset Formula $i\sim j$
\end_inset

 and 
\begin_inset Formula $0$
\end_inset

 otherwise.
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Section
APDPro
\end_layout

\begin_layout Standard
In this section, we give the pseudocode of APDPro for
\begin_inset ERT
status open

\begin_layout Plain Layout

~
\end_layout

\end_inset


\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:P"
plural "false"
caps "false"
noprefix "false"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
APDPro for Constraint-
\begin_inset Formula $\ell_{1}$
\end_inset

 personlized Pagerank
\end_layout

\end_inset


\end_layout

\begin_layout LyX-Code
Require 
\begin_inset Formula $\tau_{0},\sigma_{0},\xbf_{0},\ybf_{0},K$
\end_inset


\end_layout

\begin_layout LyX-Code
Initialize: 
\begin_inset Formula $(\xbf_{-1},\ybf_{-1})\leftarrow(\xbf_{0},\ybf_{0})$
\end_inset

, 
\begin_inset Formula $\sigma_{-1}\leftarrow\sigma_{0},\gamma_{0}\leftarrow\sigma_{0}/\tau_{0}$
\end_inset

, 
\begin_inset Formula $\underline{\mu}=\sigma_{\min}(Q)$
\end_inset

, 
\begin_inset Formula $L_{X}=\sigma_{\max}(Q)$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
\begin_inset Formula $\rho_{0}=0$
\end_inset

, 
\begin_inset Formula $r=\min\{d_{i}\}$
\end_inset

, where 
\begin_inset Formula $d_{i}$
\end_inset

 is the element of matrix 
\begin_inset Formula $D^{1/2}$
\end_inset

.
\end_layout

\end_deeper
\begin_layout LyX-Code
Guess 
\begin_inset Formula $\Delta_{XY}\leftarrow\tfrac{1}{2\tau_{0}}D_{X}^{2}+\tfrac{1}{2\sigma_{0}}D_{Y}^{2}$
\end_inset


\end_layout

\begin_layout LyX-Code
For 
\begin_inset Formula $k=0,\cdots,K-1$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
\begin_inset Formula $\mcal Y_{k}\leftarrow\{\ybf\in\mbb R_{+}\mid y\cdot\underline{\mu}\geq\rho_{k}\}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\theta_{k}=\sigma_{k-1}/\sigma_{k}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $z_{k}\leftarrow(1+\theta_{k})(\tfrac{1}{2}\inprod{\xbf_{k}}{Q\xbf_{k}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k}})-\theta_{k}(\tfrac{1}{2}\inprod{\xbf_{k-1}}{Q\xbf_{k-1}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k-1}})-b$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $y_{k+1}\leftarrow\proj_{\mcal Y_{k}}\{y_{k}+\sigma_{k}z_{k}\}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\xbf_{k+1}\leftarrow\argmin_{\xbf}\norm{D^{1/2}\xbf}_{1}+\inprod{y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)}{\xbf}+\tfrac{1}{2\tau_{k}}\norm{\xbf-\xbf_{k}}^{2}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\beta\leftarrow\tfrac{\sigma_{0}}{\gamma_{k-1}}\Delta_{XY}$
\end_inset


\end_layout

\begin_layout LyX-Code
Updater 
\begin_inset Formula $\rho_{k+1}=\max\{\tfrac{r\cdot\underline{\mu}}{\norm{Q\xbf_{k+1}-\alpha D^{-1/2}\sbf}+L_{X}\sqrt{2\beta}},\rho_{k}\}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\gamma_{k+1}=\gamma_{k}(1+\rho_{k+1}\tau_{k})$
\end_inset

, 
\begin_inset Formula $\tau_{k+1}=\tau_{k}\sqrt{\tfrac{\gamma_{k}}{\gamma_{k+1}}},\sigma_{k+1}=\tau_{k+1}\gamma_{k+1}$
\end_inset


\end_layout

\end_deeper
\begin_layout LyX-Code
End For
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Additional details
\end_layout

\begin_layout Standard
Suppose 
\begin_inset Formula 
\begin{equation}
D^{1/2}=\left[\begin{array}{ccccc}
d_{1}\\
 & d_{2}\\
 &  & d_{3}\\
 &  &  & \ddots\\
 &  &  &  & d_{n}
\end{array}\right]
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Furthermore, in pagerank problem, we have 
\begin_inset Formula $d_{i}>0$
\end_inset

, 
\begin_inset Formula $\forall i\in[m]$
\end_inset

.
\end_layout

\begin_layout Standard
How to calculate 
\begin_inset Formula $\xbf_{k+1}\leftarrow\argmin_{\xbf}\norm{D^{1/2}\xbf}_{1}+\inprod{y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)}{\xbf}+\tfrac{1}{2\tau_{k}}\norm{\xbf-\xbf_{k}}^{2}$
\end_inset

, i.e., 
\begin_inset Formula $\xbf_{k+1}$
\end_inset

 is the solution of 
\begin_inset Formula $\partial\norm{D^{1/2}\xbf}_{1}+y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)+\tfrac{1}{\tau_{k}}(\xbf-\xbf_{k})$
\end_inset

.
 Then we have
\begin_inset Formula 
\begin{equation}
\xbf_{k+1}=\xbf_{k}-\tau_{k}(\partial\norm{D^{1/2}\xbf}_{1}+y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)).
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
which implies that
\begin_inset Formula 
\begin{equation}
(\xbf_{k+1})_{i}=\begin{cases}
(\xbf_{k})_{i}-\tau_{k}(d_{i}+y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)_{i})) & (\xbf_{k})_{i}-\tau_{k}(d_{i}+y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)_{i}))>0\\
0 & o.w.\\
(\xbf_{k})_{i}-\tau_{k}(-d_{i}+y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)_{i}) & (\xbf_{k})_{i}-\tau_{k}(-d_{i}+y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)_{i})<0
\end{cases}
\end{equation}

\end_inset


\end_layout

\begin_layout Section
msAPD
\end_layout

\begin_layout Standard
In this section, we give the pseudocode of msAPD for
\begin_inset ERT
status open

\begin_layout Plain Layout

~
\end_layout

\end_inset


\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:P"
plural "false"
caps "false"
noprefix "false"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
msAPD for Constraint-
\begin_inset Formula $\ell_{1}$
\end_inset

 personlized Pagerank
\end_layout

\end_inset


\end_layout

\begin_layout LyX-Code
Require 
\begin_inset Formula $\tau_{0},\sigma_{0},\xbf_{0},\ybf_{0},K$
\end_inset


\end_layout

\begin_layout LyX-Code
Initialize: 
\begin_inset Formula $(\xbf_{-1},\ybf_{-1})\leftarrow(\xbf_{0},\ybf_{0})$
\end_inset

, 
\begin_inset Formula $\sigma_{-1}\leftarrow\sigma_{0},\gamma_{0}\leftarrow\sigma_{0}/\tau_{0}$
\end_inset

, 
\begin_inset Formula $\underline{\mu}=\sigma_{\min}(Q)$
\end_inset

, 
\begin_inset Formula $L_{X}=\sigma_{\max}(Q)$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
\begin_inset Formula $\rho_{0}=0$
\end_inset

, 
\begin_inset Formula $r=\min\{d_{i}\}$
\end_inset

, where 
\begin_inset Formula $d_{i}$
\end_inset

 is the element of matrix 
\begin_inset Formula $D^{1/2}$
\end_inset

.
\end_layout

\end_deeper
\begin_layout LyX-Code
Guess 
\begin_inset Formula $\Delta_{XY}\leftarrow\tfrac{1}{2\tau_{0}}D_{X}^{2}+\tfrac{1}{2\sigma_{0}}D_{Y}^{2}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\sum_{i=0}^{5}\sqrt{2}^{i}T=K$
\end_inset


\end_layout

\begin_layout LyX-Code
For 
\begin_inset Formula $k=0,\cdots,K-1$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
if 
\begin_inset Formula $k$
\end_inset

 = 
\begin_inset Formula $\sqrt{2}^{i}T$
\end_inset

 for 
\begin_inset Formula $\forall i$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
\begin_inset Formula $\tau_{k}=\tau_{k-1}/\sqrt{2},\sigma_{k}=\sigma_{k-1}\cdot\sqrt{2}$
\end_inset


\end_layout

\end_deeper
\begin_layout LyX-Code
\begin_inset Formula $z_{k}\leftarrow(1+\theta_{k})(\tfrac{1}{2}\inprod{\xbf_{k}}{Q\xbf_{k}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k}})-\theta_{k}(\tfrac{1}{2}\inprod{\xbf_{k-1}}{Q\xbf_{k-1}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k-1}})-b$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $y_{k+1}\leftarrow\proj_{\mcal Y_{k}}\{y_{k}+\sigma_{k}z_{k}\}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\xbf_{k+1}\leftarrow\argmin_{\xbf}\norm{D^{1/2}\xbf}_{1}+\inprod{y_{k+1}(Q\xbf_{k}-\alpha D^{-1/2}\sbf)}{\xbf}+\tfrac{1}{2\tau_{k}}\norm{\xbf-\xbf_{k}}^{2}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\tau_{k+1}=\tau_{k},\sigma_{k+1}=\sigma_{k}$
\end_inset


\end_layout

\end_deeper
\begin_layout LyX-Code
End For
\end_layout

\end_inset


\end_layout

\begin_layout Section
Mirror-prox
\end_layout

\begin_layout Standard
In this section, we give the pseudocode of Mirror-prox for
\begin_inset ERT
status open

\begin_layout Plain Layout

~
\end_layout

\end_inset


\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:P"
plural "false"
caps "false"
noprefix "false"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Mirror-prox for Constraint-
\begin_inset Formula $\ell_{1}$
\end_inset

 personlized Pagerank
\end_layout

\end_inset


\end_layout

\begin_layout LyX-Code
Require 
\begin_inset Formula $\gamma_{k},\xbf_{0},\ybf_{0},K$
\end_inset


\end_layout

\begin_layout LyX-Code
Initialize: 
\begin_inset Formula $(\xbf_{0},\ybf_{0})$
\end_inset

,
\end_layout

\begin_layout LyX-Code
For 
\begin_inset Formula $k=0,\cdots,K-1$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
\begin_inset Formula $\xbf_{k}^{1/2}\leftarrow\argmin_{\xbf}\inprod{\xbf}{Q\xbf_{k}-\alpha D^{-1/2}\sbf}+\gamma_{k}\norm{D^{1/2}\xbf}_{1}+\tfrac{1}{2}\norm{\xbf-\xbf_{k}}^{2}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\ybf_{k}^{1/2}\leftarrow\argmin_{\ybf}-\gamma_{k}y\cdot(\tfrac{1}{2}\inprod{\xbf_{k}}{Q\xbf_{k}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k}}-b)+\tfrac{1}{2}\norm{y-y_{k}}^{2}$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
\begin_inset Formula $y_{k}^{1/2}\leftarrow\proj_{\mcal Y}\{y_{k}+\gamma_{k}(\tfrac{1}{2}\inprod{\xbf_{k}}{Q\xbf_{k}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k}}-b)\}$
\end_inset


\end_layout

\end_deeper
\begin_layout LyX-Code
\begin_inset Formula $\xbf_{k+1}\leftarrow\argmin_{\xbf}\inprod{\xbf}{Q\xbf_{k}^{1/2}-\alpha D^{-1/2}\sbf}+\gamma_{k}\norm{D^{1/2}\xbf}_{1}+\tfrac{1}{2}\norm{\xbf-\xbf_{k}}^{2}$
\end_inset


\end_layout

\begin_layout LyX-Code
\begin_inset Formula $\ybf_{k+1}\leftarrow\argmin_{\ybf}-\gamma_{k}y\cdot(\tfrac{1}{2}\inprod{\xbf_{k}^{1/2}}{Q\xbf_{k}^{1/2}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k}^{1/2}}-b)+\tfrac{1}{2}\norm{y-y_{k}}^{2}$
\end_inset


\end_layout

\begin_deeper
\begin_layout LyX-Code
\begin_inset Formula $y_{k+1}\leftarrow\proj_{\mcal Y}\{y_{k}+\gamma_{k}(\tfrac{1}{2}\inprod{\xbf_{k}^{1/2}}{Q\xbf_{k}^{1/2}}-\alpha\inprod{\sbf}{D^{-1/2}\xbf_{k}^{1/2}}-b)\}$
\end_inset


\end_layout

\end_deeper
\end_deeper
\begin_layout LyX-Code
End For
\end_layout

\end_inset


\end_layout

\end_body
\end_document
