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

==== ### ====

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).