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

=== Assistant: Below is an appendable LaTeX section giving a sufficient cluster certificate theorem and a fully detailed proof that it… ===
Below is an appendable LaTeX section giving a sufficient cluster certificate theorem and a fully detailed proof that it implies (i) the global optimizer is supported on the cluster and (ii) the margin satisfies γ=Ω(ρ)\gamma=\Omega(\sqrt{\rho})γ=Ω(ρ) under a simple outside-degree condition. It is written for the ℓ1\ell_1ℓ1-regularized PageRank objective (3) in your COLT’22 open-problem note. open-problem-fountoulakis22a

<syntaxhighlight lang="latex">% ============================================================
\section{A primal--dual cluster certificate implying a $\sqrt{\rho}$-scale margin}
\label{sec:cluster_certificate_margin}

This section provides a \emph{sufficient} condition ensuring the strict-complementarity margin
\[
\gamma := \min_{i\in I^\star}\left(\lambda_i - |\nabla f(x^\star)_i|\right)
\]
is bounded below by a quantity of order $\sqrt{\rho}$ (in the PageRank specialization).
The result is stated and proved in a general composite form and then specialized to the
$\ell_1$-regularized PageRank objective~(3).

\subsection{General composite model and subgradients}

Consider the composite optimization problem
\begin{equation}\label{eq:comp_model_cert}
\min_{x\in\mathbb{R}^n} F(x) := f(x) + g(x),
\qquad
g(x) := \sum_{i=1}^n \lambda_i |x_i|,
\quad \lambda_i>0.
\end{equation}
Assume $f$ is convex and differentiable. (In our PageRank case, $f$ is quadratic and strongly convex.)

We recall the coordinatewise subdifferential of the weighted $\ell_1$ term.

\begin{lemma}[Subdifferential of weighted $\ell_1$]\label{lem:subdiff_l1_weighted}
Let $g(x)=\sum_{i=1}^n \lambda_i |x_i|$ with $\lambda_i>0$. Then
\[
\partial g(x) = \left\{z\in\mathbb{R}^n:\;
z_i=
\begin{cases}
\lambda_i\,\mathrm{sign}(x_i), & x_i\neq 0,\\[2mm]
\theta_i,\;\; \theta_i\in[-\lambda_i,\lambda_i], & x_i=0,
\end{cases}
\;\; \forall i
\right\}.
\]
\end{lemma}

\begin{proof}
Since $g$ is separable, $g(x)=\sum_i g_i(x_i)$ with $g_i(t)=\lambda_i|t|$.
The subdifferential of $|t|$ is $\partial |t|=\{\mathrm{sign}(t)\}$ for $t\neq 0$ and $\partial |0|=[-1,1]$.
Thus $\partial g_i(t)=\lambda_i\partial|t|$, yielding
$\partial g_i(t)=\{\lambda_i\mathrm{sign}(t)\}$ for $t\neq 0$ and $\partial g_i(0)=[-\lambda_i,\lambda_i]$.
Taking the Cartesian product across coordinates gives the stated formula.
\end{proof}

We also recall the standard first-order optimality characterization for convex minimization.

\begin{lemma}[First-order optimality for convex composite problems]\label{lem:optimality_convex}
Assume $f$ is convex and differentiable and $g$ is convex. Then a point $\bar x$ minimizes $F=f+g$
if and only if
\[
0 \in \partial F(\bar x).
\]
Moreover, since $f$ is differentiable, $\partial f(\bar x)=\{\nabla f(\bar x)\}$ and hence
\[
\partial F(\bar x)=\nabla f(\bar x)+\partial g(\bar x),
\]
so $\bar x$ is a minimizer if and only if there exists $z\in\partial g(\bar x)$ such that
\begin{equation}\label{eq:KKT_general}
\nabla f(\bar x)+z=0.
\end{equation}
\end{lemma}

\begin{proof}
For any proper closed convex function $h$, a point $\bar x$ minimizes $h$ if and only if $0\in\partial h(\bar x)$.
Apply this to $h=F$.

Next, since $f$ is convex and differentiable, $\partial f(\bar x)=\{\nabla f(\bar x)\}$.
A standard subgradient sum rule gives $\partial (f+g)(\bar x)=\partial f(\bar x)+\partial g(\bar x)$,
hence $\partial F(\bar x)=\nabla f(\bar x)+\partial g(\bar x)$.
Therefore $0\in\partial F(\bar x)$ is equivalent to the existence of $z\in\partial g(\bar x)$
satisfying \eqref{eq:KKT_general}.
\end{proof}

\subsection{A cluster (support) certificate and a margin lower bound}

Let $C\subseteq\{1,\dots,n\}$ be a candidate ``cluster'' and let $\bar C:=\{1,\dots,n\}\setminus C$.
For vectors we use the block notation $x=(x_C,x_{\bar C})$.

\begin{theorem}[Primal--dual cluster certificate $\Rightarrow$ support containment and margin]\label{thm:cluster_certificate}
Consider \eqref{eq:comp_model_cert} with convex differentiable $f$ and weights $\lambda_i>0$.
Assume in addition that $F=f+g$ is $\mu$-strongly convex for some $\mu>0$, so the minimizer $x^\star$ is unique.

Fix a set $C\subseteq\{1,\dots,n\}$ and suppose there exist:
\begin{itemize}
\item a vector $\hat x\in\mathbb{R}^n$ with \emph{exact} support $\,\supp(\hat x)=C$
(i.e.\ $\hat x_C$ has no zero entries and $\hat x_{\bar C}=0$), and
\item a parameter $\eta\in(0,1)$,
\end{itemize}
such that the following two conditions hold:
\begin{enumerate}
\item[\textbf{(i)}] \textbf{Stationarity on $C$.}
For all $i\in C$,
\begin{equation}\label{eq:stationarity_C}
\nabla f(\hat x)_i + \lambda_i\,\mathrm{sign}(\hat x_i)=0.
\end{equation}
\item[\textbf{(ii)}] \textbf{Strict dual feasibility on $\bar C$.}
For all $i\in \bar C$,
\begin{equation}\label{eq:strict_dual_feas}
|\nabla f(\hat x)_i| \le (1-\eta)\lambda_i.
\end{equation}
\end{enumerate}
Then:
\begin{enumerate}
\item[(a)] $\hat x$ is the unique global minimizer: $\hat x=x^\star$. Hence $\supp(x^\star)=C$.
\item[(b)] The strict-complementarity margin satisfies
\begin{equation}\label{eq:gamma_lower_bound_cert}
\gamma := \min_{i\in I^\star}\bigl(\lambda_i-|\nabla f(x^\star)_i|\bigr)
\;\ge\; \eta\,\min_{i\in \bar C}\lambda_i.
\end{equation}
\end{enumerate}
\end{theorem}

\begin{proof}
\paragraph{Step 1: Construct an explicit subgradient $z\in\partial g(\hat x)$.}
Define $z\in\mathbb{R}^n$ coordinatewise by
\[
z_i :=
\begin{cases}
\lambda_i\,\mathrm{sign}(\hat x_i), & i\in C,\\[1mm]
-\nabla f(\hat x)_i, & i\in\bar C.
\end{cases}
\]
We claim $z\in\partial g(\hat x)$.

Indeed, since $\supp(\hat x)=C$, we have $\hat x_i\neq 0$ for all $i\in C$ and $\hat x_i=0$ for all $i\in\bar C$.
By Lemma~\ref{lem:subdiff_l1_weighted}:
\begin{itemize}
\item For $i\in C$ (nonzero coordinates), the subdifferential requires $z_i=\lambda_i\mathrm{sign}(\hat x_i)$,
which holds by definition.
\item For $i\in\bar C$ (zero coordinates), the subdifferential requires $z_i\in[-\lambda_i,\lambda_i]$.
But by \eqref{eq:strict_dual_feas} and our definition, $|z_i|=|\nabla f(\hat x)_i|\le (1-\eta)\lambda_i<\lambda_i$,
so indeed $z_i\in[-\lambda_i,\lambda_i]$.
\end{itemize}
Thus $z\in\partial g(\hat x)$.

\paragraph{Step 2: Verify the KKT condition $\nabla f(\hat x)+z=0$.}
We check this coordinatewise.

\begin{itemize}
\item For $i\in C$, $z_i=\lambda_i\mathrm{sign}(\hat x_i)$ and \eqref{eq:stationarity_C} gives
$\nabla f(\hat x)_i+z_i=0$.
\item For $i\in\bar C$, we defined $z_i=-\nabla f(\hat x)_i$, hence $\nabla f(\hat x)_i+z_i=0$ holds trivially.
\end{itemize}
Therefore $\nabla f(\hat x)+z=0$ with $z\in\partial g(\hat x)$.

\paragraph{Step 3: Conclude $\hat x$ is a global minimizer.}
By Lemma~\ref{lem:optimality_convex}, the existence of $z\in\partial g(\hat x)$ such that
$\nabla f(\hat x)+z=0$ implies $0\in\partial F(\hat x)$ and hence $\hat x$ minimizes $F$.

\paragraph{Step 4: Conclude uniqueness and identify the support.}
By assumption, $F$ is $\mu$-strongly convex with $\mu>0$, hence the minimizer is unique.
Since $\hat x$ is a minimizer, it must equal the unique minimizer: $\hat x=x^\star$.
In particular, $\supp(x^\star)=\supp(\hat x)=C$ and thus $I^\star=\bar C$.

\paragraph{Step 5: Lower bound the margin.}
Since $I^\star=\bar C$, we can write
\[
\gamma = \min_{i\in\bar C}\left(\lambda_i-|\nabla f(x^\star)_i|\right)
= \min_{i\in\bar C}\left(\lambda_i-|\nabla f(\hat x)_i|\right),
\]
where the equality uses $x^\star=\hat x$.
Using \eqref{eq:strict_dual_feas}, for each $i\in\bar C$ we have
\[
\lambda_i-|\nabla f(\hat x)_i|
\ge \lambda_i-(1-\eta)\lambda_i = \eta\lambda_i.
\]
Taking the minimum over $i\in\bar C$ yields \eqref{eq:gamma_lower_bound_cert}.
\end{proof}

\subsection{Specialization to $\ell_1$-regularized PageRank and a $\sqrt{\rho}$ condition}

We now specialize Theorem~\ref{thm:cluster_certificate} to the $\ell_1$-regularized PageRank objective~(3):
\[
F(x)= f(x)+g(x),\qquad
f(x)=\frac12 x^\top Qx-\alpha x^\top D^{-1/2}s,\qquad
g(x)=\rho\alpha\|D^{1/2}x\|_1.
\]
In this case $g(x)=\sum_{i=1}^n \lambda_i|x_i|$ with weights
\begin{equation}\label{eq:lambda_ppr}
\lambda_i=\rho\alpha\sqrt{d_i}.
\end{equation}

\begin{corollary}[$\gamma=\Omega(\sqrt{\rho})$ under a degree condition]\label{cor:gamma_sqrt_rho}
Assume the PageRank objective~(3) and suppose the hypotheses of Theorem~\ref{thm:cluster_certificate}
hold for some set $C$ and slack $\eta\in(0,1)$.
Then
\[
\gamma \ge \eta\,\min_{i\in\bar C}\lambda_i = \eta\,\rho\alpha\,\min_{i\in\bar C}\sqrt{d_i}.
\]
In particular, if the complement degrees satisfy
\begin{equation}\label{eq:degree_condition_out}
\min_{i\in\bar C} d_i \;\ge\; \frac{c_0}{\alpha^2\rho}
\qquad\text{for some constant }c_0>0,
\end{equation}
then
\begin{equation}\label{eq:gamma_Omega_sqrt_rho}
\gamma \;\ge\; \eta\,\sqrt{c_0}\,\sqrt{\rho}.
\end{equation}
\end{corollary}

\begin{proof}
The first inequality follows immediately by substituting \eqref{eq:lambda_ppr} into
\eqref{eq:gamma_lower_bound_cert}.

If additionally \eqref{eq:degree_condition_out} holds, then for all $i\in\bar C$,
\[
\lambda_i=\rho\alpha\sqrt{d_i}\ge \rho\alpha\sqrt{\frac{c_0}{\alpha^2\rho}}=\sqrt{c_0}\,\sqrt{\rho}.
\]
Taking the minimum over $i\in\bar C$ and multiplying by $\eta$ yields \eqref{eq:gamma_Omega_sqrt_rho}.
\end{proof}

\begin{remark}[Relation to conductance and internal connectivity]
Theorem~\ref{thm:cluster_certificate} isolates the core requirement:
a \emph{strict dual feasibility} inequality \eqref{eq:strict_dual_feas} on $\bar C$.
In the PageRank setting, $\nabla f(\hat x)=Q\hat x-\alpha D^{-1/2}s$ and the block $Q_{\bar C C}$
only involves edges crossing the cut $(C,\bar C)$.
Thus, when $C$ has small boundary (low conductance) and is internally well-conditioned (so the restricted solution
on $C$ does not become too large), one expects \eqref{eq:strict_dual_feas} to hold with a nontrivial slack $\eta$.
The degree condition \eqref{eq:degree_condition_out} is a simple sufficient way to ensure
$\min_{i\in\bar C}\lambda_i=\Theta(\sqrt{\rho})$, which is necessary for $\gamma$ to be of order $\sqrt{\rho}$.
\end{remark}
% ============================================================

</syntaxhighlight>