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

==== Paste the following into your document, and then replace the definition \eqref{eq:xhat_def_gamma_param} and Theorem~\ref{thm:gamma_parameterized_by_cluster} (and its proof) with the revised versions below. ====

<syntaxhighlight lang="latex">% ------------------------------------------------------------
% Fix: define \hat x as the restricted minimizer (no sign guess),
% prove \hat x_C \ge 0, and use its KKT multiplier z_C.
% ------------------------------------------------------------

\subsubsection*{Restricted minimizer on a candidate cluster}

Define the restricted optimization problem on $C$ by fixing $x_{\bar C}=0$:
\begin{equation}\label{eq:restricted_problem_C}
\min_{x\in\mathbb{R}^n:\; x_{\bar C}=0}\;
F(x)
=
\frac12 x^\top Qx-\alpha x^\top D^{-1/2}s
\;+\;
\sum_{i\in C}\lambda_i |x_i|,
\qquad \lambda_i=\rho\alpha\sqrt{d_i}.
\end{equation}

\begin{definition}[Restricted minimizer]\label{def:xhat_restricted}
Let $\hat x$ denote the unique minimizer of \eqref{eq:restricted_problem_C}.
Equivalently, $\hat x_{\bar C}=0$ and $\hat x_C$ is the unique minimizer of
\[
\min_{x_C\in\mathbb{R}^{|C|}}\;
\frac12 x_C^\top Q_{CC}x_C - b_C^\top x_C + \sum_{i\in C}\lambda_i|x_i|,
\qquad b:=\alpha D^{-1/2}s.
\]
\end{definition}

\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:
\begin{enumerate}
\item For every $x$ with $x_{\bar C}=0$, the vector $|x|$ (componentwise absolute value) satisfies
\[
F(|x|)\le F(x).
\]
\item Consequently, the restricted minimizer satisfies $\hat x_C\ge 0$ componentwise.
\end{enumerate}
\end{lemma}

\begin{proof}
Fix any $x$ with $x_{\bar C}=0$ and set $y:=|x|$ (so $y_{\bar C}=0$).
We compare each term in $F$.

\medskip\noindent\textbf{(i) 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$.
Write
\[
x^\top Qx = \sum_i Q_{ii}x_i^2 + 2\sum_{i<j}Q_{ij}x_i x_j.
\]
For each $i<j$, we have $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$.
Therefore $x^\top Qx \ge y^\top Qy$.

\medskip\noindent\textbf{(ii) Linear term.}
Since $b\ge 0$ and $y_i=|x_i|\ge x_i$ for all $i$, we have
$-b^\top y \le -b^\top x$.

\medskip\noindent\textbf{(iii) $\ell_1$ term.}
By definition, $\sum_i \lambda_i |y_i|=\sum_i\lambda_i|x_i|$.

\medskip\noindent
Combining (i)--(iii) yields $F(y)\le F(x)$, proving the first claim.
For the second claim, 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}
Q_{CC}\hat x_C - b_C + z_C = 0,
\end{equation}
and for every $i\in C$,
\begin{equation}\label{eq:zC_bound}
z_{C,i}\in \lambda_i\,\partial |\,\hat x_i\,| \subseteq [-\lambda_i,\lambda_i].
\end{equation}
In particular, $|z_{C,i}|\le \lambda_i$ for all $i\in C$, and thus
$\|z_C\|_2 \le \|\lambda_C\|_2 = \rho\alpha\sqrt{\mathrm{vol}(C)}$.
\end{lemma}

\begin{proof}
The restricted objective in \eqref{eq:restricted_problem_C} is strongly convex in $x_C$
because $Q_{CC}\succ 0$ and the $\ell_1$ term is convex, hence it has a unique minimizer $\hat x_C$.
First-order optimality for convex composite problems gives
\[
0 \in Q_{CC}\hat x_C - b_C + \partial\!\left(\sum_{i\in C}\lambda_i|\hat x_i|\right),
\]
which is exactly the existence of $z_C$ satisfying \eqref{eq:restricted_KKT}--\eqref{eq:zC_bound}.
The norm bound follows from $|z_{C,i}|\le\lambda_i$ and the definition of $\|\lambda_C\|_2$.
\end{proof}

\begin{lemma}[Bounding $\|\hat x_C\|_2$ by internal connectivity]\label{lem:xhatC_norm_gamma_param_fixed}
Let $\mu_C=\lambda_{\min}(Q_{CC})$. Then
\[
\|\hat x_C\|_2
\le
\frac{1}{\mu_C}\left(\|b_C\|_2+\|z_C\|_2\right)
\le
\frac{1}{\mu_C}\left(\frac{\alpha}{\sqrt{d_v}}+\rho\alpha\sqrt{\mathrm{vol}(C)}\right).
\]
\end{lemma}

\begin{proof}
From \eqref{eq:restricted_KKT}, $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 \frac{1}{\mu_C}\left(\|b_C\|_2+\|z_C\|_2\right).
\]
Since $s=e_v$ and $v\in C$, we have $\|b_C\|_2=\alpha/\sqrt{d_v}$, and
Lemma~\ref{lem:restricted_KKT_on_C} gives $\|z_C\|_2\le \rho\alpha\sqrt{\mathrm{vol}(C)}$.
\end{proof}

</syntaxhighlight>

Now here is the revised theorem that replaces the positivity-dependent one. Note how it (correctly) lower bounds an outside margin γCˉ\gamma_{\bar C}γCˉ. If you still want the global γ\gammaγ, you’ll need an extra interior assumption (I add that as an “optional add-on” at the end).

<syntaxhighlight lang="latex">\begin{theorem}[Parameterized outside-margin bound without assuming $\hat x_C>0$]
\label{thm:gamma_parameterized_by_cluster_fixed}
Assume $v\in C$ and let $\hat x$ be the restricted minimizer from Definition~\ref{def:xhat_restricted}.
Define
\[
\gamma_{\bar C}:=\min_{i\in\bar C}\Bigl(\lambda_i-|\nabla f(x^\star)_i|\Bigr),
\qquad \lambda_i=\rho\alpha\sqrt{d_i}.
\]
Let $\Delta(C)$ be defined exactly as in \eqref{eq:DeltaC_def_gamma_param}, but with
$\|\hat x_C\|_2$ bounded using Lemma~\ref{lem:xhatC_norm_gamma_param_fixed}; i.e.
\[
\Delta(C)
:=
\frac{1-\alpha}{2\mu_C}\,
\sqrt{\frac{\phi(C)\mathrm{vol}(C)}{d_{\mathrm{out}}\,d_{\mathrm{in}}}}\,
\left(\frac{\alpha}{\sqrt{d_v}}+\rho\alpha\sqrt{\mathrm{vol}(C)}\right).
\]
Then:
\begin{enumerate}
\item[(i)] If $\Delta(C)\le (1-\eta)\rho\alpha\sqrt{d_{\mathrm{out}}}$ for some $\eta\in(0,1)$, then
$x^\star_{\bar C}=0$ (the global minimizer is supported inside $C$).
\item[(ii)] Under the same condition, the \emph{outside margin} satisfies
\[
\gamma_{\bar C}\ge \eta\,\rho\alpha\sqrt{d_{\mathrm{out}}}.
\]
\end{enumerate}
\end{theorem}

\begin{proof}
\medskip\noindent\textbf{Step 1 (Outside-gradient bound).}
Since $v\in C$, we have $b_{\bar C}=0$.
Because $\hat x_{\bar C}=0$,
\[
\nabla f(\hat x)_{\bar C} = (Q\hat x-b)_{\bar C} = (Q_{\bar C C}\hat x_C)_{\bar C}.
\]
Lemma~\ref{lem:outside_grad_bound_gamma_param} (unchanged) bounds
$\max_{i\in\bar C}|\nabla f(\hat x)_i|\le \Delta(C)$, using
Lemma~\ref{lem:xhatC_norm_gamma_param_fixed} to control $\|\hat x_C\|_2$.

\medskip\noindent\textbf{Step 2 (Build a global KKT certificate).}
From Lemma~\ref{lem:restricted_KKT_on_C} there exists $z_C\in\partial g_C(\hat x_C)$ such that
$Q_{CC}\hat x_C-b_C+z_C=0$.
Define a full vector $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 On $C$, $z_C\in\partial g_C(\hat x_C)$ by construction.
\item On $\bar C$, $\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}
Under the hypothesis $\Delta(C)\le (1-\eta)\rho\alpha\sqrt{d_{\mathrm{out}}}$ we have
$|\nabla f(\hat x)_i|\le \Delta(C)\le (1-\eta)\rho\alpha\sqrt{d_{\mathrm{out}}}\le \lambda_i$
for all $i\in\bar C$ (since $\lambda_i\ge \rho\alpha\sqrt{d_{\mathrm{out}}}$).
Thus $z\in\partial g(\hat x)$.

Finally, note that for $i\in C$,
\[
(\nabla f(\hat x)+z)_i = (Q_{CC}\hat x_C-b_C+z_C)_i = 0,
\]
and for $i\in\bar C$ we have $(\nabla f(\hat x)+z)_i= \nabla f(\hat x)_i-\nabla f(\hat x)_i=0$.
Hence $\nabla f(\hat x)+z=0$ with $z\in\partial g(\hat x)$, i.e. $0\in\partial F(\hat x)$.
Therefore $\hat x$ is a global minimizer. By strong convexity, it is the unique global minimizer:
$\hat x=x^\star$. In particular $x^\star_{\bar C}=0$, proving (i).

\medskip\noindent\textbf{Step 3 (Outside margin).}
Since $x^\star=\hat x$ and $\bar C\subseteq I^\star$, 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)
\ge \eta\rho\alpha\sqrt{d_{\mathrm{out}}}.
\]
Taking the minimum over $i\in\bar C$ yields $\gamma_{\bar C}\ge \eta\rho\alpha\sqrt{d_{\mathrm{out}}}$, proving (ii).
\end{proof}

\begin{remark}[Why this does not automatically give the \emph{global} margin $\gamma$]
The global margin is $\gamma=\min_{i\in I^\star}(\lambda_i-|\nabla f(x^\star)_i|)$, where $I^\star$ includes
\emph{all} zero coordinates of $x^\star$, including any zeros inside $C$.
The theorem above lower bounds the margin only on $\bar C$.
To conclude the same lower bound for the global $\gamma$, one needs an additional assumption that
$x^\star_i>0$ for all $i\in C$ (equivalently, $I^\star=\bar C$), or else a separate lower bound on the slack
for the (possibly) inactive indices inside $C$.
Such an ``interior beta-min / interior slack'' condition cannot be forced solely from $\phi(C)$, $\mu_C$, and $d_{\mathrm{out}}$:
even an internally expanding cluster with $\phi(C)=0$ can have many coordinates truncated to $0$ if $\rho$ is chosen large.
\end{remark}

</syntaxhighlight>

===== - No, ρ\rhoρ vs. ϕ(C)\phi(C)ϕ(C) does not guarantee x^C>0\hat x_C>0x^C>0. =====
* The right fix is to: - define x^\hat xx^ as the restricted minimizer, - prove x^C≥0\hat x_C\ge 0x^C≥0 (done above), - and then your conductance/connectivity/degree bound gives a clean Ω(ρ)\Omega(\sqrt{\rho})Ω(ρ) outside margin.

If you tell me whether you truly need the global γ\gammaγ (including possible zeros inside CCC) or whether an outside margin γCˉ\gamma_{\bar C}γCˉ is sufficient for your downstream argument (runtime/locality), I can tighten the statement accordingly.