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

=== Assistant: Yes — let’s make this mechanical. ===
Yes — let’s make this mechanical. You don’t need to guess what to change: you will (A) replace the definition of x^\hat xx^, (B) delete one lemma, (C) add two lemmas, (D) replace one lemma’s proof, and (E) replace the theorem+proof (and delete the positivity assumption).

Below I refer to the exact blocks in the code you pasted.

==== ### ====

It starts at:

<syntaxhighlight lang="latex">We will construct a candidate vector supported on $C$ by solving the KKT stationarity equations \emph{restricted to $C$}
under the natural sign choice $x_C>0$ (appropriate for PageRank-type solutions).

Define the restricted candidate $\hat x$ by
\begin{equation}\label{eq:xhat_def_gamma_param}
\hat x_{\bar C}:=0,
\qquad
\hat x_C:=Q_{CC}^{-1}\bigl(b_C-\lambda_C\bigr),
\qquad
b:=\alpha D^{-1/2}s.
\end{equation}

</syntaxhighlight>

===== (copy-paste exactly): =====

<syntaxhighlight lang="latex">We will construct a candidate vector supported on $C$ as the \emph{restricted minimizer}
of the full objective over vectors with $x_{\bar C}=0$.
This avoids imposing (and later proving) a sign pattern such as $\hat x_C>0$.

Let $b:=\alpha D^{-1/2}s$. Define $\hat x$ to be the unique minimizer of
\begin{equation}\label{eq:xhat_def_gamma_param}
\hat x \in \arg\min_{x\in\mathbb{R}^n:\; x_{\bar C}=0}\;
\left\{
\frac12 x^\top Qx-\alpha x^\top D^{-1/2}s
\;+\;
\sum_{i=1}^n \lambda_i |x_i|
\right\}.
\end{equation}
Equivalently, $\hat x_{\bar C}=0$ and $\hat x_C$ uniquely minimizes
\[
\min_{x_C\in\mathbb{R}^{|C|}}
\left\{
\frac12 x_C^\top Q_{CC}x_C - b_C^\top x_C + \sum_{i\in C}\lambda_i|x_i|
\right\}.
\]

</syntaxhighlight>

Keep your equation for ∥bC∥2\|b_C\|_2∥bC∥2 (eq:bC_norm_gamma_param) right after this (no change).

==== ### ====

Remove everything from:

<syntaxhighlight lang="latex">\begin{lemma}[Stationarity on $C$]\label{lem:restricted_stationarity_gamma_param}
...
\end{proof}

</syntaxhighlight>

That lemma relied on the closed-form formula QCC−1(bC−λC)Q_{CC}^{-1}(b_C-\lambda_C)QCC−1(bC−λC), which is not the restricted minimizer once the ℓ1\ell_1ℓ1 term can create zeros/sign changes inside CCC.

==== Paste the following exactly where the stationarity lemma used to be: ====

<syntaxhighlight lang="latex">\begin{lemma}[Absolute-value improvement and nonnegativity]\label{lem:abs_improvement_nonneg}
Assume $v\in C$ so that $b_C\ge 0$ and $b_{\bar C}=0$.
Then for every $x$ with $x_{\bar C}=0$, the componentwise absolute value $|x|$ satisfies
\[
F(|x|)\le F(x).
\]
Consequently, the restricted minimizer $\hat x$ satisfies $\hat x_C\ge 0$ componentwise.
\end{lemma}

\begin{proof}
Fix any $x$ with $x_{\bar C}=0$ and set $y:=|x|$ (so $y_{\bar C}=0$).
Write
\[
F(x)=\frac12 x^\top Qx - b^\top x + \sum_{i=1}^n \lambda_i|x_i|.
\]

\emph{Quadratic term.}
Since $Q=\frac{1+\alpha}{2}I-\frac{1-\alpha}{2}D^{-1/2}AD^{-1/2}$, we have $Q_{ij}\le 0$ for $i\neq j$.
Expand
\[
x^\top Qx = \sum_i Q_{ii}x_i^2 + 2\sum_{i<j}Q_{ij}x_i x_j.
\]
For each $i<j$, $x_i x_j\le |x_i||x_j|=y_i y_j$, and since $Q_{ij}\le 0$ this implies
$Q_{ij}x_i x_j \ge Q_{ij}y_i y_j$.
Hence $x^\top Qx \ge y^\top Qy$.

\emph{Linear term.}
Since $b\ge 0$ (here $b=\alpha D^{-1/2}s$ with $s=e_v$) and $y_i=|x_i|\ge x_i$ for all $i$,
we have $-b^\top y \le -b^\top x$.

\emph{$\ell_1$ term.}
$\sum_i \lambda_i|y_i|=\sum_i\lambda_i|x_i|$ by definition.

Combining the three comparisons gives $F(y)\le F(x)$.
Now let $\hat x$ be the unique restricted minimizer. Then $F(|\hat x|)\le F(\hat x)$, so $|\hat x|$ is also a minimizer.
By uniqueness, $|\hat x|=\hat x$, hence $\hat x_C\ge 0$.
\end{proof}

\begin{lemma}[Restricted KKT on $C$]\label{lem:restricted_KKT_on_C}
There exists a vector $z_C\in\mathbb{R}^{|C|}$ such that
\begin{equation}\label{eq:restricted_KKT_on_C}
Q_{CC}\hat x_C - b_C + z_C = 0,
\end{equation}
and for every $i\in C$,
\begin{equation}\label{eq:zC_in_subdiff}
z_{C,i}\in \lambda_i\,\partial|\hat x_i| \subseteq [-\lambda_i,\lambda_i].
\end{equation}
In particular, $\|z_C\|_2 \le \|\lambda_C\|_2 = \rho\alpha\sqrt{\mathrm{vol}(C)}$.
\end{lemma}

\begin{proof}
The restricted objective over $x_C$ is strongly convex because $Q_{CC}\succ 0$ and the $\ell_1$ term is convex,
so $\hat x_C$ is unique. First-order optimality yields
\[
0\in Q_{CC}\hat x_C - b_C + \partial\!\Big(\sum_{i\in C}\lambda_i|\hat x_i|\Big),
\]
which is exactly the existence of $z_C$ satisfying \eqref{eq:restricted_KKT_on_C}--\eqref{eq:zC_in_subdiff}.
The norm bound follows from $|z_{C,i}|\le \lambda_i$ and
$\|\lambda_C\|_2^2=\sum_{i\in C}(\rho\alpha\sqrt{d_i})^2=(\rho\alpha)^2\mathrm{vol}(C)$.
\end{proof}

</syntaxhighlight>

==== You can keep the statement and label exactly the same; only change the proof so it no longer uses ====
x^C=QCC−1(bC−λC)\hat x_C=Q_{CC}^{-1}(b_C-\lambda_C)x^C=QCC−1(bC−λC).

===== <syntaxhighlight lang="latex">\begin{proof} =====
From Lemma~\ref{lem:restricted_KKT_on_C}, $Q_{CC}\hat x_C=b_C-z_C$, so
\[
\|\hat x_C\|_2 \le \|Q_{CC}^{-1}\|_2\,\|b_C-z_C\|_2
\le \|Q_{CC}^{-1}\|_2\bigl(\|b_C\|_2+\|z_C\|_2\bigr).
\]
Since $\lambda_{\min}(Q_{CC})=\mu_C$, we have $\|Q_{CC}^{-1}\|_2=1/\mu_C$.
Also, by \eqref{eq:bC_norm_gamma_param}, $\|b_C\|_2=\alpha/\sqrt{d_v}$.
Finally, Lemma~\ref{lem:restricted_KKT_on_C} gives $\|z_C\|_2\le \rho\alpha\sqrt{\mathrm{vol}(C)}$.
Substituting yields \eqref{eq:xC_norm_gamma_param}.
\end{proof}

</syntaxhighlight>

Everything else in that lemma (statement and equation eq:xC_norm_gamma_param) stays unchanged.

==== ### ====

Remove these lines entirely:

<syntaxhighlight lang="latex">Assume $v\in C$ and that the restricted candidate \eqref{eq:xhat_def_gamma_param} satisfies
\begin{equation}\label{eq:xhat_positive_gamma_param}
\hat x_C>0\quad\text{(componentwise)}.
\end{equation}

</syntaxhighlight>

===== Replace everything from: =====

<syntaxhighlight lang="latex">\begin{theorem}[Margin bound parameterized by conductance, internal connectivity, and outside degree]
\label{thm:gamma_parameterized_by_cluster}
...
\end{proof}

</syntaxhighlight>

with the following (copy-paste):

<syntaxhighlight lang="latex">\begin{theorem}[Margin bound parameterized by conductance, internal connectivity, and outside degree]
\label{thm:gamma_parameterized_by_cluster}
Assume $v\in C$ and let $\hat x$ be defined by \eqref{eq:xhat_def_gamma_param} (restricted minimizer with $\hat x_{\bar C}=0$).
Then:
\begin{enumerate}
\item[(i)] If $\Delta(C)<\min_{i\in\bar C}\lambda_i=\rho\alpha\sqrt{d_{\mathrm{out}}}$, then $\hat x$ is the \emph{unique}
global minimizer of \eqref{eq:ppr_obj_gamma_param}. In particular, $x^\star=\hat x$ and $x^\star_{\bar C}=0$.
\item[(ii)] Whenever $x^\star=\hat x$, the \emph{outside} slack (margin on $\bar C$) satisfies the explicit lower bound
\begin{equation}\label{eq:gamma_param_bound_gamma_param}
\min_{i\in \bar C}\Bigl(\lambda_i-|\nabla f(x^\star)_i|\Bigr)
\;\ge\;
\rho\alpha\sqrt{d_{\mathrm{out}}}-\Delta(C).
\end{equation}
Equivalently, if $\Delta(C)\le (1-\eta)\rho\alpha\sqrt{d_{\mathrm{out}}}$ for some $\eta\in(0,1)$, then
\begin{equation}\label{eq:gamma_eta_bound_gamma_param}
\min_{i\in \bar C}\Bigl(\lambda_i-|\nabla f(x^\star)_i|\Bigr)
\ge \eta\,\rho\alpha\sqrt{d_{\mathrm{out}}}.
\end{equation}
\end{enumerate}
\end{theorem}

\begin{proof}
We prove (i) and (ii) in order.

\medskip\noindent\textbf{Step 1: KKT conditions for \eqref{eq:ppr_obj_gamma_param}.}
Since $f$ is differentiable and $g(x)=\sum_i \lambda_i|x_i|$, a point $x$ is optimal if and only if there exists
$z\in\partial g(x)$ such that
\begin{equation}\label{eq:KKT_gamma_param}
\nabla f(x)+z=0.
\end{equation}
Moreover, $F$ is strongly convex because $f$ is $\alpha$-strongly convex and $g$ is convex,
so the minimizer is unique.

\medskip\noindent\textbf{Step 2: Build a valid $z\in\partial g(\hat x)$ and verify \eqref{eq:KKT_gamma_param}.}
From Lemma~\ref{lem:restricted_KKT_on_C}, there exists $z_C$ such that
$Q_{CC}\hat x_C-b_C+z_C=0$ and $z_{C,i}\in[-\lambda_i,\lambda_i]$ for all $i\in C$.

Define $z\in\mathbb{R}^n$ by
\[
z_i :=
\begin{cases}
(z_C)_i, & i\in C,\\[1mm]
-\nabla f(\hat x)_i, & i\in\bar C.
\end{cases}
\]
We claim $z\in\partial g(\hat x)$ provided $|\nabla f(\hat x)_i|\le \lambda_i$ for all $i\in\bar C$.
Indeed:
\begin{itemize}
\item If $i\in C$, then $z_{C,i}\in \lambda_i\,\partial|\hat x_i|$ by Lemma~\ref{lem:restricted_KKT_on_C},
so it is a valid weighted-$\ell_1$ subgradient component on $C$.
\item If $i\in\bar C$, then $\hat x_i=0$ and the subgradient condition is $z_i\in[-\lambda_i,\lambda_i]$.
This holds if $|z_i|=|\nabla f(\hat x)_i|\le \lambda_i$.
\end{itemize}

Next we check \eqref{eq:KKT_gamma_param}.
On $C$, since $\hat x_{\bar C}=0$,
\[
\nabla f(\hat x)_C = (Q\hat x-b)_C = Q_{CC}\hat x_C - b_C,
\]
hence $\nabla f(\hat x)_C+z_C=0$ by $Q_{CC}\hat x_C-b_C+z_C=0$.
On $\bar C$, by construction $\nabla f(\hat x)_{\bar C}+z_{\bar C}=0$.
Therefore $\nabla f(\hat x)+z=0$.

\medskip\noindent\textbf{Step 3: Enforce the outside inequalities via $\Delta(C)$.}
By Lemma~\ref{lem:outside_grad_bound_gamma_param} and Lemma~\ref{lem:xC_norm_gamma_param},
\[
\max_{i\in\bar C}|\nabla f(\hat x)_i|
\le
\Delta(C).
\]
Therefore, if $\Delta(C)<\rho\alpha\sqrt{d_{\mathrm{out}}}\le \lambda_i$ for all $i\in\bar C$,
then $|\nabla f(\hat x)_i|<\lambda_i$ on $\bar C$, so indeed $z\in\partial g(\hat x)$ and the KKT condition holds.
Hence $\hat x$ is a minimizer, and by strong convexity it is the unique minimizer:
$\hat x=x^\star$. This proves (i).

\medskip\noindent\textbf{Step 4: Lower bound the outside margin on $\bar C$.}
Assume $x^\star=\hat x$. Then for every $i\in\bar C$,
\[
\lambda_i-|\nabla f(x^\star)_i|
=\lambda_i-|\nabla f(\hat x)_i|
\ge \lambda_i-\Delta(C)
\ge \rho\alpha\sqrt{d_{\mathrm{out}}}-\Delta(C),
\]
where we used $\lambda_i\ge \rho\alpha\sqrt{d_{\mathrm{out}}}$.
Taking the minimum over $i\in\bar C$ yields \eqref{eq:gamma_param_bound_gamma_param},
and the $\eta$-form \eqref{eq:gamma_eta_bound_gamma_param} follows immediately.
\end{proof}

</syntaxhighlight>

✅ After this change, you no longer need to prove x^C>0\hat x_C>0x^C>0; the theorem is correct with only x^C≥0\hat x_C\ge 0x^C≥0 (which we proved in Lemma lem:abs_improvement_nonneg), and it yields the parameterized slack bound on Cˉ\bar CCˉ (which is what your conductance/outside-degree analysis controls).

==== This updated theorem lower bounds the slack for nodes in Cˉ\bar CCˉ. It does not claim that every node in CCC is nonzero; that cannot be guaranteed just from ϕ(C)\phi(C)ϕ(C), μC\mu_CμC, doutd_{\mathrm{out}}dout (the ℓ1\ell_1ℓ1 term can still zero out interior nodes). ====

If you want, I can show you the minimal additional “interior beta-min” condition that makes the global margin coincide with this outside margin.

(And yes: this whole section is for objective (3) in your note. open-problem-fountoulakis22a

)