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

=== Assistant: Here is appendable LaTeX that turns the last two prompts + my two answers star + path constructions, and the “γ<ρ\gamma… ===
Here is appendable LaTeX that turns the last two prompts + my two answers (star + path constructions, and the “γ<ρ\gamma<\sqrt{\rho}γ<ρ” point) into a clean section you can paste into your current note (it refers to the ℓ1\ell_1ℓ1-regularized PageRank objective (3) in the COLT’22 open-problem note open-problem-fountoulakis22a

).

<syntaxhighlight lang="latex">% ============================================================
\section{Bad instances where the margin $\gamma$ can be much smaller than $\sqrt{\rho}$}

We now record two explicit graph families showing that the strict-complementarity margin
\[
\gamma := \min_{i\in I^\star}\bigl(\lambda_i-|\nabla f(x^\star)_i|\bigr),
\qquad \lambda_i=\rho\alpha\sqrt{d_i},
\]
can be made \emph{arbitrarily small} (even $\gamma=0$) by choosing $\rho$ near a breakpoint of the
regularization path where an inactive KKT inequality becomes tight.
In particular, these instances satisfy $\gamma<\sqrt{\rho}$ for suitable choices of $\rho$.

\begin{remark}[Algorithmic parameters vs.\ $\gamma$]
The margin $\gamma$ is a property of the \emph{instance} (graph, seed $s$, and PageRank parameters $\alpha,\rho$),
since it is defined from the KKT slack at the \emph{true minimizer} $x^\star$.
Step size and momentum parameters of an accelerated method do \emph{not} change $\gamma$; they only affect
the transient behavior before the iterates enter a $\gamma$-neighborhood of $x^\star$.
\end{remark}

\subsection{Star graph (seed at the center)}

Let $G$ be a star on $m+1$ nodes with center node $c$ of degree $d_c=m$ and leaves $\ell$ of degree $1$.
Let the seed be $s=e_c$. Consider candidates of the form $x=x_c e_c$.

\begin{lemma}[Star graph breakpoint: $\gamma$ can be $0$]\label{lem:star_gamma_small}
Fix $\alpha\in(0,1]$ and $m\ge 1$ and define
\[
\rho_0 := \frac{1-\alpha}{2m}.
\]
For any $\rho\in[\rho_0,\,1/m)$, the unique minimizer has support $S^\star=\{c\}$, with
\[
x_c^\star = \frac{2\alpha(1-\rho m)}{(1+\alpha)\sqrt{m}}.
\]
Moreover, the KKT slack on any leaf $\ell$ equals
\[
\lambda_\ell - |\nabla f(x^\star)_\ell|
= \frac{2\alpha}{1+\alpha}\,(\rho-\rho_0),
\]
and thus at the breakpoint $\rho=\rho_0$ one has $\gamma=0<\sqrt{\rho_0}$.
\end{lemma}

\begin{proof}
For undirected graphs,
\[
Q=\frac{1+\alpha}{2}I-\frac{1-\alpha}{2}D^{-1/2}AD^{-1/2},
\qquad
\nabla f(x)=Qx-\alpha D^{-1/2}s.
\]
On the star, $Q_{cc}=\frac{1+\alpha}{2}$ and for each leaf $\ell$,
$Q_{\ell c}=Q_{c\ell}=-\frac{1-\alpha}{2}\frac{1}{\sqrt{m}}$.

Assume $x^\star=x_c^\star e_c$ with $x_c^\star>0$.
The active KKT condition at $c$ is
\[
0 = \nabla f(x^\star)_c + \lambda_c
= \frac{1+\alpha}{2}x_c^\star - \frac{\alpha}{\sqrt{m}} + \rho\alpha\sqrt{m},
\]
which yields the stated formula for $x_c^\star$ (and requires $\rho<1/m$ for positivity).
For a leaf $\ell$, the inactive KKT inequality is
\[
|\nabla f(x^\star)_\ell|
= |(Qx^\star)_\ell|
= \frac{1-\alpha}{2}\frac{x_c^\star}{\sqrt{m}}
\le \lambda_\ell=\rho\alpha,
\]
which reduces to $\rho\ge\rho_0$ after substituting $x_c^\star$.
Strong convexity of $F$ implies the KKT conditions certify the unique minimizer and its support.

Finally, the slack at a leaf is
\[
\lambda_\ell-|\nabla f(x^\star)_\ell|
= \rho\alpha - \frac{1-\alpha}{2}\frac{x_c^\star}{\sqrt{m}}
= \frac{2\alpha}{1+\alpha}(\rho-\rho_0),
\]
and since all inactive coordinates are leaves, this gives $\gamma$.
\end{proof}

\begin{remark}[Getting $\gamma<\sqrt{\rho}$ with $\gamma>0$ on the star]
Take $\rho=\rho_0+\delta$ with $\delta>0$.
Then $\gamma=\frac{2\alpha}{1+\alpha}\delta$ while $\rho=\rho_0+\delta>0$.
Choosing $\delta$ sufficiently small gives $\gamma<\sqrt{\rho}$ (and $\gamma$ can be made arbitrarily small).
\end{remark}

\subsection{Path graph (seed at an endpoint)}

Let $G=P_{m+1}$ be the path on nodes $1,2,\dots,m+1$ with edges $(i,i+1)$.
Let $s=e_1$ (seed at endpoint $1$). Here $d_1=d_{m+1}=1$ and $d_i=2$ for $2\le i\le m$.
Consider candidates of the form $x=x_1 e_1$.

\begin{lemma}[Path graph breakpoint: $\gamma$ can be $0$]\label{lem:path_gamma_small}
Fix $\alpha\in(0,1]$ and $m\ge 1$ and define
\[
\rho_0 := \frac{1-\alpha}{3+\alpha}.
\]
For any $\rho\in[\rho_0,\,1)$, the unique minimizer has support $S^\star=\{1\}$, with
\[
x_1^\star = \frac{2\alpha(1-\rho)}{1+\alpha}.
\]
Moreover, the KKT slack at node $2$ equals
\[
\lambda_2-|\nabla f(x^\star)_2|
= \frac{\alpha(3+\alpha)}{(1+\alpha)\sqrt{2}}\,(\rho-\rho_0).
\]
In particular, at the breakpoint $\rho=\rho_0$ one has $\gamma=0<\sqrt{\rho_0}$.
\end{lemma}

\begin{proof}
As above, $Q=\frac{1+\alpha}{2}I-\frac{1-\alpha}{2}D^{-1/2}AD^{-1/2}$.
Since $(1,2)\in E$ and $(D^{-1/2}AD^{-1/2})_{21}=1/\sqrt{1\cdot 2}=1/\sqrt{2}$, we have
$Q_{11}=\frac{1+\alpha}{2}$ and $Q_{21}=-\frac{1-\alpha}{2\sqrt{2}}$.

Assume $x^\star=x_1^\star e_1$ with $x_1^\star>0$.
The active KKT condition at node $1$ is
\[
0=\nabla f(x^\star)_1+\lambda_1
= \frac{1+\alpha}{2}x_1^\star - \alpha + \rho\alpha,
\]
which yields $x_1^\star=\frac{2\alpha(1-\rho)}{1+\alpha}$ (positive for $\rho<1$).
The inactive KKT inequality at node $2$ is
\[
|\nabla f(x^\star)_2|
= |(Qx^\star)_2|
= \frac{1-\alpha}{2\sqrt{2}}\,x_1^\star
\le \lambda_2=\rho\alpha\sqrt{2},
\]
which reduces to $\rho\ge\rho_0$ after substituting $x_1^\star$.
For nodes $i\ge 3$, $(Qx^\star)_i=0$ because $x^\star$ is supported only on node $1$ and $Q$ is sparse along edges,
hence their KKT inequalities hold trivially. Strong convexity implies uniqueness.

Finally,
\[
\lambda_2-|\nabla f(x^\star)_2|
= \rho\alpha\sqrt{2} - \frac{1-\alpha}{2\sqrt{2}}x_1^\star
= \frac{\alpha(3+\alpha)}{(1+\alpha)\sqrt{2}}(\rho-\rho_0),
\]
and at $\rho=\rho_0$ this slack is $0$, so $\gamma=0$.
\end{proof}

\begin{remark}[Getting $\gamma<\sqrt{\rho}$ with $\gamma>0$ on the path]
Take $\rho=\rho_0+\delta$ with $\delta>0$.
Then the slack at node $2$ is $O(\delta)$, hence $\gamma\le O(\delta)$, while $\sqrt{\rho}\approx \sqrt{\rho_0}>0$.
Choosing $\delta$ sufficiently small yields $\gamma<\sqrt{\rho}$ (and $\gamma$ can be made arbitrarily small).
\end{remark}
% ============================================================

</syntaxhighlight>