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

=== Assistant: Here’s a path graph version of the same “bad margin” phenomenon. ===
Here’s a path graph version of the same “bad margin” phenomenon. It’s actually even cleaner than you might expect: you can make γ\gammaγ arbitrarily small by tuning ρ\rhoρ to sit extremely close to the point where the next node on the path is about to enter the support.

I’ll stick to the ℓ1\ell_1ℓ1-regularized PPR objective (your eq. (3)) and the usual Q=αI+1−α2LQ=\alpha I+\frac{1-\alpha}{2}LQ=αI+21−αL setup. open-problem-fountoulakis22a

==== Let Pm+1P_{m+1}Pm+1 be the path graph on nodes 1,2,…,m+11,2,\dots,m+11,2,…,m+1 with edges (i,i+1)(i,i+1)(i,i+1). ====
Take the seed s=e1s=e_1s=e1 at endpoint node 111.

Degrees:
* d1=1d_1=1d1=1,
* di=2d_i=2di=2 for 2≤i≤m2\le i\le m2≤i≤m,
* dm+1=1d_{m+1}=1dm+1=1.

Regularizer weights in (3) are λi=ραdi\lambda_i=\rho\alpha\sqrt{d_i}λi=ραdi, so
* λ1=ρα\lambda_1=\rho\alphaλ1=ρα,
* λ2=ρα2\lambda_2=\rho\alpha\sqrt{2}λ2=ρα2,
* and for interior nodes similarly ρα2\rho\alpha\sqrt{2}ρα2.

Also, for an undirected graph you can write

Q  =  1+α2I  −  1−α2D−1/2AD−1/2,Q \;=\; \frac{1+\alpha}{2}I \;-\; \frac{1-\alpha}{2}D^{-1/2}AD^{-1/2},Q=21+αI−21−αD−1/2AD−1/2,
so the only off-diagonals are on edges:

Qij=−1−α2⋅1didjif (i,j)∈E.Q_{ij} = -\frac{1-\alpha}{2}\cdot \frac{1}{\sqrt{d_i d_j}}
\quad \text{if } (i,j)\in E.Qij=−21−α⋅didj1if (i,j)∈E.
In particular, between nodes 111 and 222,

Q21=−1−α2⋅11⋅2=−1−α22.Q_{21} = -\frac{1-\alpha}{2}\cdot \frac{1}{\sqrt{1\cdot 2}} = -\frac{1-\alpha}{2\sqrt{2}}.Q21=−21−α⋅1⋅21=−221−α.

==== Consider the candidate solution ====

x⋆=(x1⋆,0,0,…,0),x1⋆>0.x^\star = (x_1^\star, 0,0,\dots,0),
\quad x_1^\star>0.x⋆=(x1⋆,0,0,…,0),x1⋆>0.
===== The smooth gradient is ∇f(x)=Qx−αD−1/2s\nabla f(x)=Qx-\alpha D^{-1/2}s∇f(x)=Qx−αD−1/2s, and since d1=1d_1=1d1=1 we have D−1/2s=e1D^{-1/2}s=e_1D−1/2s=e1. =====
So the KKT condition at coordinate 1 (active, positive) is:

(Qx⋆)1−α+λ1=0.(Qx^\star)_1 - \alpha + \lambda_1 = 0.(Qx⋆)1−α+λ1=0.
But (Qx⋆)1=Q11x1⋆=1+α2x1⋆(Qx^\star)_1 = Q_{11}x_1^\star = \frac{1+\alpha}{2}x_1^\star(Qx⋆)1=Q11x1⋆=21+αx1⋆. Hence

1+α2x1⋆−α+ρα=0⟹x1⋆=2α(1−ρ)1+α.\frac{1+\alpha}{2}x_1^\star - \alpha + \rho\alpha = 0
\quad\Longrightarrow\quad
x_1^\star = \frac{2\alpha(1-\rho)}{1+\alpha}.21+αx1⋆−α+ρα=0⟹x1⋆=1+α2α(1−ρ).
So this is positive as long as ρ<1\rho<1ρ<1.

===== Node 2 is inactive (x2⋆=0x_2^\star=0x2⋆=0) iff its KKT inequality holds: =====

∣∇f(x⋆)2∣≤λ2.|\nabla f(x^\star)_2| \le \lambda_2.∣∇f(x⋆)2∣≤λ2.
Now ∇f(x⋆)2=(Qx⋆)2\nabla f(x^\star)_2 = (Qx^\star)_2∇f(x⋆)2=(Qx⋆)2 (no seed term at node 2), and since only x1⋆x_1^\starx1⋆ is nonzero,

(Qx⋆)2=Q21x1⋆=−1−α22x1⋆.(Qx^\star)_2 = Q_{21}x_1^\star
= -\frac{1-\alpha}{2\sqrt{2}}x_1^\star.(Qx⋆)2=Q21x1⋆=−221−αx1⋆.
So

∣∇f(x⋆)2∣=1−α22x1⋆=1−α22⋅2α(1−ρ)1+α=α(1−α)(1−ρ)(1+α)2.|\nabla f(x^\star)_2|
= \frac{1-\alpha}{2\sqrt{2}}x_1^\star
= \frac{1-\alpha}{2\sqrt{2}}\cdot \frac{2\alpha(1-\rho)}{1+\alpha}
= \frac{\alpha(1-\alpha)(1-\rho)}{(1+\alpha)\sqrt{2}}.∣∇f(x⋆)2∣=221−αx1⋆=221−α⋅1+α2α(1−ρ)=(1+α)2α(1−α)(1−ρ).
The threshold is λ2=ρα2\lambda_2=\rho\alpha\sqrt{2}λ2=ρα2. The inequality becomes:

α(1−α)(1−ρ)(1+α)2≤ρα2⟺(1−α)(1−ρ)1+α≤2ρ.\frac{\alpha(1-\alpha)(1-\rho)}{(1+\alpha)\sqrt{2}}
\le \rho\alpha\sqrt{2}
\quad\Longleftrightarrow\quad
\frac{(1-\alpha)(1-\rho)}{1+\alpha}\le 2\rho.(1+α)2α(1−α)(1−ρ)≤ρα2⟺1+α(1−α)(1−ρ)≤2ρ.
Solving yields the breakpoint:

  ρ0=1−α3+α  \boxed{\;\rho_0 = \frac{1-\alpha}{3+\alpha}\;}ρ0=3+α1−α
and for any ρ∈[ρ0,1)\rho\in[\rho_0,1)ρ∈[ρ0,1), the solution with support {1}\{1\}{1} satisfies all KKT conditions.
(Every node i≥3i\ge 3i≥3 has (Qx⋆)i=0(Qx^\star)_i=0(Qx⋆)i=0 when only x1⋆≠0x_1^\star\neq 0x1⋆=0, so their inequalities are trivially satisfied.)

So for all path lengths mmm, you get:

S⋆={1},∣S⋆∣=1≤1/ρ,whenever ρ∈[ρ0,1).S^\star = \{1\},\quad |S^\star|=1\le 1/\rho,
\quad \text{whenever }\rho\in[\rho_0,1).S⋆={1},∣S⋆∣=1≤1/ρ,whenever ρ∈[ρ0,1).

==== The margin is ====

γ=min⁡i∈I⋆(λi−∣∇f(x⋆)i∣).\gamma = \min_{i\in I^\star}(\lambda_i - |\nabla f(x^\star)_i|).γ=i∈I⋆min(λi−∣∇f(x⋆)i∣).
Here the tightest inactive coordinate is node 2 (the only one with nonzero gradient), so

γ=λ2−∣∇f(x⋆)2∣=ρα2−α(1−α)(1−ρ)(1+α)2.\gamma = \lambda_2 - |\nabla f(x^\star)_2|
= \rho\alpha\sqrt{2} - \frac{\alpha(1-\alpha)(1-\rho)}{(1+\alpha)\sqrt{2}}.γ=λ2−∣∇f(x⋆)2∣=ρα2−(1+α)2α(1−α)(1−ρ).
This simplifies neatly to a linear function of ρ−ρ0\rho-\rho_0ρ−ρ0:

  γ=α(3+α)(1+α)2  (ρ−ρ0).  \boxed{\;
\gamma
= \frac{\alpha(3+\alpha)}{(1+\alpha)\sqrt{2}}\;(\rho-\rho_0).
\;}γ=(1+α)2α(3+α)(ρ−ρ0).
So:
* At ρ=ρ0\rho=\rho_0ρ=ρ0, γ=0\gamma=0γ=0.
* For ρ=ρ0+δ\rho=\rho_0+\deltaρ=ρ0+δ with tiny δ>0\delta>0δ>0, you get γ=Cδ\gamma = C\deltaγ=Cδ with C=α(3+α)(1+α)2C=\frac{\alpha(3+\alpha)}{(1+\alpha)\sqrt{2}}C=(1+α)2α(3+α).

Since ρ\sqrt{\rho}ρ is Θ(1)\Theta(1)Θ(1) here (because ρ0\rho_0ρ0 is a constant depending on α\alphaα), taking δ\deltaδ extremely small makes γ\gammaγ much smaller than ρ\sqrt{\rho}ρ.

===== Take α=0.15\alpha=0.15α=0.15. Then =====

ρ0=0.853.15≈0.26984,ρ0≈0.519.\rho_0 = \frac{0.85}{3.15}\approx 0.26984,
\qquad
\sqrt{\rho_0}\approx 0.519.ρ0=3.150.85≈0.26984,ρ0≈0.519.
Now choose ρ=ρ0+10−6\rho=\rho_0+10^{-6}ρ=ρ0+10−6. Then

γ≈0.15⋅3.151.15⋅1.414⋅10−6≈2.9×10−7≪0.519≈ρ.\gamma
\approx \frac{0.15\cdot 3.15}{1.15\cdot 1.414}\cdot 10^{-6}
\approx 2.9\times 10^{-7}
\ll 0.519 \approx \sqrt{\rho}.γ≈1.15⋅1.4140.15⋅3.15⋅10−6≈2.9×10−7≪0.519≈ρ.
So this path graph gives you a very explicit, closed-form “bad” case where

γ<ρ\gamma < \sqrt{\rho}γ<ρ
by an arbitrarily large margin, while the true support is tiny (∣S⋆∣=1≤1/ρ|S^\star|=1\le 1/\rho∣S⋆∣=1≤1/ρ).

===== Algorithm parameters (t,βt,\betat,β, restart, etc.) don’t change γ\gammaγ: γ\gammaγ is a property of the instance (graph + α,ρ,s\alpha,\rho,sα,ρ,s) at the true optimizer. What algorithm parameters affect is how much transient “support thrashing” you might see before you enter the γ\gammaγ-neighborhood. =====

If you want, I can also give a path-prefix support construction (where S⋆={1,2,…,k}S^\star=\{1,2,\dots,k\}S⋆={1,2,…,k}) and show the breakpoint for node k+1k+1k+1, so you can make γ\gammaγ tiny while ∣S⋆∣≈k≈1/ρ|S^\star|\approx k\approx 1/\rho∣S⋆∣≈k≈1/ρ.