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

=== Assistant: Append the following replacement section it gives an explicit parameterized lower bound on the margin γ\gammaγ in terms… ===
Append the following replacement section (it gives an explicit parameterized lower bound on the margin γ\gammaγ in terms of conductance, internal connectivity, and outside degree, and then a corollary showing when this becomes Ω(ρ)\Omega(\sqrt{\rho})Ω(ρ)). open-problem-fountoulakis22a

<syntaxhighlight lang="latex">% ============================================================
\section{A conductance--connectivity--degree lower bound on the margin}
\label{sec:gamma_conductance_connectivity_degree}

We specialize to the $\ell_1$-regularized PageRank objective~(3):
\begin{equation}\label{eq:ppr_obj_gamma_param}
\min_{x\in\mathbb{R}^n}
F(x)
:=
\underbrace{\frac12 x^\top Qx-\alpha x^\top D^{-1/2}s}_{=:f(x)}
\;+\;
\underbrace{\rho\alpha\|D^{1/2}x\|_1}_{=:g(x)}.
\end{equation}
Here $G=(V,E)$ is undirected and unweighted, $A$ is the adjacency matrix, $D$ is the diagonal degree matrix,
$s=e_v$ is a seed at node $v$, and
\begin{equation}\label{eq:Q_def_gamma_param}
Q=\alpha I+\frac{1-\alpha}{2}L
=
\frac{1+\alpha}{2}I-\frac{1-\alpha}{2}\,D^{-1/2}AD^{-1/2}.
\end{equation}
The weighted $\ell_1$ penalty has coordinate weights
\begin{equation}\label{eq:lambda_def_gamma_param}
g(x)=\sum_{i=1}^n \lambda_i |x_i|,
\qquad
\lambda_i:=\rho\alpha\sqrt{d_i}.
\end{equation}

\paragraph{Cluster notation.}
Fix a set (candidate cluster) $C\subseteq V$ with $v\in C$, and let $\bar C:=V\setminus C$.
Define the volume and cut:
\[
\mathrm{vol}(C):=\sum_{i\in C} d_i,
\qquad
\mathrm{cut}(C,\bar C):=|\{(i,j)\in E:\; i\in C,\ j\in\bar C\}|.
\]
We use the (one-sided) conductance
\[
\phi(C):=\frac{\mathrm{cut}(C,\bar C)}{\mathrm{vol}(C)}.
\]
Let
\[
d_{\mathrm{in}}:=\min_{j\in C} d_j,
\qquad
d_{\mathrm{out}}:=\min_{i\in\bar C} d_i,
\qquad
d_v:=d_{v}.
\]

\paragraph{Internal connectivity parameter.}
Let
\begin{equation}\label{eq:muC_def_gamma_param}
\mu_C:=\lambda_{\min}(Q_{CC}),
\end{equation}
the smallest eigenvalue of the principal submatrix $Q_{CC}$.
Since $Q\succeq \alpha I$, we always have $\mu_C\ge \alpha$, and larger $\mu_C$ corresponds to
stronger internal connectivity/conditioning on the cluster.

\subsection{A pointwise bound on the outside gradient in terms of $\phi(C)$ and $\mu_C$}

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}
Since $s=e_v$ and $v\in C$, the vector $b_C$ has exactly one nonzero entry:
\begin{equation}\label{eq:bC_norm_gamma_param}
\|b_C\|_2=\frac{\alpha}{\sqrt{d_v}}.
\end{equation}

\begin{lemma}[Stationarity on $C$]\label{lem:restricted_stationarity_gamma_param}
The vector $\hat x$ satisfies the exact stationarity equation on $C$:
\begin{equation}\label{eq:restricted_stationarity_gamma_param}
\nabla f(\hat x)_C+\lambda_C = 0.
\end{equation}
\end{lemma}

\begin{proof}
Since $\nabla f(x)=Qx-b$, and $\hat x_{\bar C}=0$, we have
\[
\nabla f(\hat x)_C
=
(Q_{CC}\hat x_C - b_C).
\]
By the definition \eqref{eq:xhat_def_gamma_param}, $Q_{CC}\hat x_C=b_C-\lambda_C$, hence
$\nabla f(\hat x)_C = -\lambda_C$, which is \eqref{eq:restricted_stationarity_gamma_param}.
\end{proof}

Next we bound the gradient on $\bar C$ in terms of conductance, internal connectivity, and outside degree.

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

\begin{proof}
Since $Q_{CC}$ is symmetric positive definite and $\lambda_{\min}(Q_{CC})=\mu_C$,
\[
\|Q_{CC}^{-1}\|_2 = \frac{1}{\mu_C}.
\]
Using \eqref{eq:xhat_def_gamma_param} and the triangle inequality,
\[
\|\hat x_C\|_2
=
\left\|Q_{CC}^{-1}(b_C-\lambda_C)\right\|_2
\le
\|Q_{CC}^{-1}\|_2\bigl(\|b_C\|_2+\|\lambda_C\|_2\bigr).
\]
By \eqref{eq:bC_norm_gamma_param}, $\|b_C\|_2=\alpha/\sqrt{d_v}$.
Also, by \eqref{eq:lambda_def_gamma_param},
\[
\|\lambda_C\|_2^2=\sum_{i\in C} (\rho\alpha\sqrt{d_i})^2
=(\rho\alpha)^2\sum_{i\in C} d_i
=(\rho\alpha)^2\,\mathrm{vol}(C),
\]
so $\|\lambda_C\|_2=\rho\alpha\sqrt{\mathrm{vol}(C)}$.
Substitute these bounds to obtain \eqref{eq:xC_norm_gamma_param}.
\end{proof}

\begin{lemma}[Outside gradient bound from conductance and degrees]\label{lem:outside_grad_bound_gamma_param}
Assume $v\in C$ so that $b_{\bar C}=0$. Then for each $i\in\bar C$,
\begin{equation}\label{eq:outside_grad_pointwise_gamma_param}
|\nabla f(\hat x)_i|
\le
\frac{1-\alpha}{2}\,\|\hat x_C\|_2\,
\sqrt{\frac{\mathrm{cut}(C,\bar C)}{d_i\,d_{\mathrm{in}}}}.
\end{equation}
Consequently, using $d_i\ge d_{\mathrm{out}}$ and $\mathrm{cut}(C,\bar C)=\phi(C)\mathrm{vol}(C)$,
\begin{equation}\label{eq:outside_grad_uniform_gamma_param}
\max_{i\in\bar C}|\nabla f(\hat x)_i|
\le
\frac{1-\alpha}{2}\,\|\hat x_C\|_2\,
\sqrt{\frac{\phi(C)\mathrm{vol}(C)}{d_{\mathrm{out}}\,d_{\mathrm{in}}}}.
\end{equation}
\end{lemma}

\begin{proof}
Fix $i\in\bar C$. Since $\hat x_{\bar C}=0$ and $b_{\bar C}=0$,
\[
\nabla f(\hat x)_i = (Q\hat x - b)_i = (Q_{\bar C C}\hat x_C)_i = \sum_{j\in C}Q_{ij}\hat x_j.
\]
From \eqref{eq:Q_def_gamma_param}, for $i\neq j$ we have
\[
Q_{ij} = -\frac{1-\alpha}{2}(D^{-1/2}AD^{-1/2})_{ij}
=
\begin{cases}
-\dfrac{1-\alpha}{2}\dfrac{1}{\sqrt{d_i d_j}}, & (i,j)\in E,\\[2mm]
0, & (i,j)\notin E.
\end{cases}
\]
Thus
\[
|\nabla f(\hat x)_i|
=
\left|\sum_{j\in C\cap N(i)} -\frac{1-\alpha}{2}\frac{\hat x_j}{\sqrt{d_i d_j}}\right|
\le
\frac{1-\alpha}{2}\cdot \frac{1}{\sqrt{d_i}}
\sum_{j\in C\cap N(i)}\frac{|\hat x_j|}{\sqrt{d_j}}.
\]
Apply Cauchy--Schwarz to the sum:
\[
\sum_{j\in C\cap N(i)}\frac{|\hat x_j|}{\sqrt{d_j}}
\le
\left(\sum_{j\in C\cap N(i)} \hat x_j^2\right)^{1/2}
\left(\sum_{j\in C\cap N(i)} \frac{1}{d_j}\right)^{1/2}
\le
\|\hat x_C\|_2\left(\sum_{j\in C\cap N(i)} \frac{1}{d_j}\right)^{1/2}.
\]
Since $d_j\ge d_{\mathrm{in}}$ for all $j\in C$, we have
\[
\sum_{j\in C\cap N(i)} \frac{1}{d_j}
\le
\frac{|C\cap N(i)|}{d_{\mathrm{in}}}.
\]
Finally, $|C\cap N(i)|$ is the number of cut edges incident to $i$, hence $|C\cap N(i)|\le \mathrm{cut}(C,\bar C)$,
which gives \eqref{eq:outside_grad_pointwise_gamma_param}. The uniform bound
\eqref{eq:outside_grad_uniform_gamma_param} follows by using $d_i\ge d_{\mathrm{out}}$
and $\mathrm{cut}(C,\bar C)=\phi(C)\mathrm{vol}(C)$.
\end{proof}

\subsection{A parameterized margin lower bound and a $\sqrt{\rho}$ corollary}

Define the cluster-dependent quantity
\begin{equation}\label{eq:DeltaC_def_gamma_param}
\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).
\end{equation}

\begin{theorem}[Margin bound parameterized by conductance, internal connectivity, and outside degree]
\label{thm:gamma_parameterized_by_cluster}
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}
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 strict-complementarity margin satisfies the explicit lower bound
\begin{equation}\label{eq:gamma_param_bound_gamma_param}
\gamma
=
\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}
\gamma \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}.}
Because of \eqref{eq:xhat_positive_gamma_param}, $\mathrm{sign}(\hat x_i)=+1$ for all $i\in C$.
Define $z\in\mathbb{R}^n$ by
\[
z_i :=
\begin{cases}
\lambda_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 $\hat x_i>0$ and the weighted-$\ell_1$ subgradient requires $z_i=\lambda_i$, which holds.
\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, Lemma~\ref{lem:restricted_stationarity_gamma_param} gives $\nabla f(\hat x)_C=-\lambda_C$, so
$\nabla f(\hat x)_C+z_C=0$.
By definition, $\nabla f(\hat x)_{\bar C}+z_{\bar C}=0$.
Thus \eqref{eq:KKT_gamma_param} holds.

\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 $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 margin.}
Assume $x^\star=\hat x$. Since $x^\star_{\bar C}=0$, the inactive set contains $\bar C$ and
\[
\gamma
=
\min_{i\in \bar C}\bigl(\lambda_i-|\nabla f(x^\star)_i|\bigr)
\ge
\min_{i\in\bar C}\lambda_i - \max_{i\in\bar C}|\nabla f(\hat x)_i|
=
\rho\alpha\sqrt{d_{\mathrm{out}}} - \max_{i\in\bar C}|\nabla f(\hat x)_i|.
\]
Using $\max_{i\in\bar C}|\nabla f(\hat x)_i|\le \Delta(C)$ gives \eqref{eq:gamma_param_bound_gamma_param}.
The $\eta$-form \eqref{eq:gamma_eta_bound_gamma_param} is immediate.
\end{proof}

\begin{corollary}[A concrete $\gamma=\Omega(\sqrt{\rho})$ regime]\label{cor:gamma_Omega_sqrt_rho_regime}
Assume the hypotheses of Theorem~\ref{thm:gamma_parameterized_by_cluster}.
Suppose, in addition, that there are constants $V_0,d_0,\mu_0,c_0>0$ such that
\[
\mathrm{vol}(C)\le \frac{V_0}{\rho},\qquad
d_{\mathrm{in}}\ge d_0,\qquad
d_v\ge d_0,\qquad
\mu_C\ge \mu_0,\qquad
d_{\mathrm{out}}\ge \frac{c_0}{\alpha^2\rho}.
\]
If furthermore the conductance satisfies
\begin{equation}\label{eq:phi_rho_condition_gamma_param}
\phi(C)\le c_1\rho
\quad\text{for a sufficiently small constant $c_1$ (depending only on $V_0,d_0,\mu_0,c_0,\alpha$),}
\end{equation}
then there exists a constant $\eta\in(0,1)$ (depending only on the same parameters) such that
\[
\gamma \ge \eta\,\sqrt{\rho}.
\]
\end{corollary}

\begin{proof}
From $d_{\mathrm{out}}\ge c_0/(\alpha^2\rho)$ we get
\[
\rho\alpha\sqrt{d_{\mathrm{out}}}\ge \rho\alpha\sqrt{\frac{c_0}{\alpha^2\rho}}=\sqrt{c_0}\,\sqrt{\rho}.
\]
Next, using the assumed bounds in \eqref{eq:DeltaC_def_gamma_param},
\[
\Delta(C)
\le
\frac{1-\alpha}{2\mu_0}\,
\sqrt{\frac{\phi(C)\cdot (V_0/\rho)}{(c_0/(\alpha^2\rho))\cdot d_0}}\,
\left(\frac{\alpha}{\sqrt{d_0}}+\rho\alpha\sqrt{V_0/\rho}\right)
=
\frac{1-\alpha}{2\mu_0}\,
\alpha\,\sqrt{\frac{V_0}{c_0 d_0}}\,
\sqrt{\phi(C)}\,
\left(\frac{\alpha}{\sqrt{d_0}}+\alpha\sqrt{V_0}\sqrt{\rho}\right).
\]
Under \eqref{eq:phi_rho_condition_gamma_param}, $\sqrt{\phi(C)}\le \sqrt{c_1}\sqrt{\rho}$, hence $\Delta(C)\le K\sqrt{\rho}$
for a constant $K$ depending only on $(V_0,d_0,\mu_0,c_0,\alpha)$ and $c_1$.
Choosing $c_1$ sufficiently small ensures $\Delta(C)\le (1-\eta)\sqrt{c_0}\sqrt{\rho}$ for some $\eta\in(0,1)$.
Applying \eqref{eq:gamma_param_bound_gamma_param} then yields $\gamma\ge \eta\sqrt{c_0}\sqrt{\rho}$.
Absorbing $\sqrt{c_0}$ into $\eta$ gives the stated $\gamma\ge \eta\sqrt{\rho}$.
\end{proof}

\begin{remark}[Interpretation]
The quantity $\Delta(C)$ in \eqref{eq:DeltaC_def_gamma_param} is explicit and shows how the margin depends on:
(i) the \emph{outside degree} $d_{\mathrm{out}}$ through the threshold $\lambda_i=\rho\alpha\sqrt{d_i}$,
(ii) the \emph{boundary size} through $\phi(C)$, and
(iii) the \emph{internal conditioning} $\mu_C=\lambda_{\min}(Q_{CC})$.
When $\phi(C)=O(\rho)$, $d_{\mathrm{out}}=\Theta(1/(\alpha^2\rho))$, and $\mu_C$ is bounded below,
the bound forces $\gamma=\Omega(\sqrt{\rho})$.
\end{remark}
% ============================================================

</syntaxhighlight>