source/experiments.tex

\section{Experiments}
\label{sec:experiments}
This section presents a series of empirical tests over both synthetic and real-world datasets to compare the efficiency and performance of our new method with heuristic and SDP-based methods.

\textbf{Sample-splitting ablations.} In reporting all other experiments than those in the current discussion, whenever we describe an algorithm as $\TPM$, we formally mean a variant of Algorithm~\ref{alg:tpm} that we call $\TPMf$ for disambiguation. This variant reuses the full-sample empirical covariance $\hmsig$ at every iteration, as opposed to Algorithm~\ref{alg:tpm} which splits the sample into independent batches for use in each iteration. We similarly call the variant described in Algorithm~\ref{alg:tpm} $\TPMd$.

We choose to report our experimental results for $\TPMf$ because we believe this better reflects the use of our strategy in practical sparse PCA instances. The sample complexity of $\TPMf$ automatically saves a $T$ factor over the corresponding $\TPMd$ counterpart, which discards samples at every iteration. While our proofs only apply to $\TPMd$ due to our use of independent sub-exponential concentration via Fact~\ref{fact:bilinear_err}, here we conduct an ablation study comparing the effect of sample-splitting on a challenging sparse PCA instance.

We specifically perform our ablation on the $\TC$ counterexample construction (Lemma~\ref{lem:friends_lower_bound} in Section~\ref{sec:counterexamples}). We compare two variants that are identical in all algorithmic choices: they use the same truncation level (set to $r=5s$), the same set of restarts (all standard basis vectors $\{\ve_i\}_{i\in[d]}$, processed in restart batches), the same number of iterations $T$, and the same final selection rule based on maximizing the Rayleigh objective. The only difference is how the empirical covariance is formed across iterations. We report the resulting $\sin^{2}$ error as a function of $T$. As Figure~\ref{fig:spca_ablations} shows, both algorithms achieve similar $\sin^2$ error, which justifies the use of $\TPM$-$\mathsf{full}$ for our experiments. We believe that our theoretical analyses for the batched variant, $\TPM$-$\mathsf{disjoint}$, could potentially be extended to $\TPM$-$\mathsf{full}$, which we leave as an interesting open direction.  

\begin{figure*}[!hbt]
  \centering
  \begin{subfigure}[t]{0.42\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/spca_ablation_1.png}
    % \caption{.}
  \end{subfigure}
  % \hfill
  \begin{subfigure}[t]{0.42\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/spca_ablation_2.png}
    % \caption{.}
  \end{subfigure}

  \begin{subfigure}[t]{0.42\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/spca_ablation_3.png}
    % \caption{.}
  \end{subfigure}
  % \hfill
  \begin{subfigure}[t]{0.42\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/spca_ablation_4.png}
    % \caption{.}
  \end{subfigure}
  \caption{Comparison of performance of full-batch $\TPM$ using all samples together as compared to Algorithm~\ref{alg:tpm}, with varying choices of number of iterations, $T$.}
  \label{fig:spca_ablations}
\end{figure*}

\textbf{Runtime-accuracy tradeoff.}
We empirically compare the runtime efficiency of our proposed algorithm ($\TPM$, Algorithm~\ref{alg:tpm}) with the SDP-based method and other heuristic combinatorial algorithms discussed in Section~\ref{sec:counterexamples}. For the SDP-based approach, we utilize the Fantope Projection and Selection (FPS) method from \cite{VuCLR13}, which implements an alternating direction method of multipliers (ADMM)-based algorithm, although without provable convergence guarantees. State-of-the-art SDP solvers with provable convergence guarantees take time $\Omega(d^{2\omega})$ in theory \cite{SDP_huang2022solving}, and practical SDP solvers with provable guarantees have even larger runtimes, making them infeasible even for moderate dimensionalities, as the sparse PCA SDP has $\Theta(d^2)$ constraints.

The combinatorial algorithms we compare with are $\DT$ (Algorithm~\ref{alg:diagthresh}), $\CT$ (Algorithm~\ref{alg:covthresh}) and $\TC$ (Algorithm~\ref{alg:topcorr}).  Some methods we consider involve tunable parameters, such as the number of iterations, which naturally trades off runtime and performance. Other methods are one-shot and not tunable. For a fair comparison, for tunable algorithms, we report the trajectory of the squared cosine correlation versus cumulative runtime as the number of iterations increases. Non-tunable algorithms appear as single scattered points under the same configuration.

We generate $n$ samples according to Model~\ref{model:spiked_id} and the counterexample in Lemma~\ref{lem:friends_lower_bound}, and
test the runtime for all the methods above. The latter experiment is to illustrate runtime behavior on a non-spiked sparse PCA model as defined in Model~\ref{model:general}. For a meaningful comparison, we choose parameters such that the targeted heuristic methods do not fail.

As seen in Figure~\ref{fig:placeholder}, our $\TPM$ is the only algorithm that consistently achieves high correlation with the target vector across all sample sizes and covariance instances.

\begin{figure}[ht]
    \centering
    \includegraphics[width=\linewidth]{pics/runtime.pdf}
    \caption{\small Runtime versus accuracy for $\TPM$, heuristic and SDP-based methods. First row: spiked identity in Model~\ref{model:spiked_id} with $d = 1000$ and $s = 8$. Second row: counterexample against Greedy Correlation presented in Lemma~\ref{lem:friends_lower_bound} with $d = 1000$, $s = 8$, and $\lambda_1(\msig) = 1.2$, $\lambda_2(\msig) = 0.8$. RTPM runs with $r = s$ and the relaxation coefficient for the SDP-based method is set as suggested in \cite{VuCLR13}. }
    \label{fig:placeholder}
\end{figure}


\textbf{Counterexamples.} For each counterexample discussed in Section~\ref{sec:counterexamples}, we will compare the performance of the targeted heuristic method, $\TPM$, and the SDP-based method. Some parameters in data generation and algorithmic implementations are not set exactly as in their theoretical analysis, as they often rely on some universal constants that are impractical to compute. Instead, we adopt a pragmatic strategy to combine heuristic choices with a coarse grid search. 

The experiments in Figure~\ref{fig:counterexample} confirm the theoretical guaranties that our counterexamples successfully fool the simple heuristic methods. Moreover, these tests also indicate that our method is able to overcome these counterexamples and performs well on many instances under the general Model~\ref{model:general}.

\begin{figure}[ht]
    \centering
    \includegraphics[width=\linewidth]{pics/counterexample.pdf}
    \caption{\small Performance on counterexamples. In each subplot, we vary the sample size $n$ under fixed $d, k$, and compare the output correlation achieved $\TPM$, the targeted heuristics and the SDP-based method. The dataset parameter except $(n, d, s)$ are set as following: the left plot uses $\lambda_1 = 1.0$, $\lambda_2 = 0.5$, $\lambda_2/\lambda_3 = 2.1$ and $\lambda_2/\lambda_4 = 2.2$; the middle plot uses $u = 25$, $r = 6$, $\theta = 1$ and $c = 0.25$; the right plot uses parameters as in Lemma~\ref{lem:friends_lower_bound}. The RTPM method is run for 40 iterations and the relaxation coefficient for SDP-based method is set as suggested in \cite{VuCLR13}. %The results show that the counterexamples successfully cause the heuristics to fail, while RTPM consistently overcomes these challenges. 
    }
    \label{fig:counterexample}
\end{figure}

%According to Lemma~\ref{lem:friends_lower_bound}, the greedy correlation method fails to recover the correct sparse vector on the counterexample with probability at most $\half$. This aligns with our empirical observations. Therefore, we repeat the experiment for multiple times and report in Figure~\ref{fig:counterexample} a trial in which the counterexample successfully cheats the heuristic method. %Additional runs are provided in the Appendix.

\begin{figure}[!hbt]
\centering

% ---------------- Row 1: vs s ----------------
\begin{subfigure}[t]{0.4\textwidth}
  \centering
  \includegraphics[width=\linewidth]{pics/scaling_s_spiked.png}
  \caption{\label{fig:scaling_s_spiked}Spiked: $n_{\mathrm{scale}}$ vs $s$}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.42\textwidth}
  \centering
  \includegraphics[width=\linewidth]{pics/scaling_s_lemma4.png}
  \caption{\label{fig:scaling_s_lemma4}Lemma~\ref{lem:friends_lower_bound} counterexample: $n_{\mathrm{scale}}$ vs $s$}
\end{subfigure}

% ---------------- Row 2: vs gamma ----------------
\begin{subfigure}[t]{0.4\textwidth}
  \centering
  \includegraphics[width=\linewidth]{pics/scaling_gamma_spiked.png}
  \caption{\label{fig:scaling_gamma_spiked}Spiked: $n_{\mathrm{scale}}$ vs $\gamma$}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.42\textwidth}
  \centering
  \includegraphics[width=\linewidth]{pics/scaling_gamma_lemma4.png}
  \caption{\label{fig:scaling_gamma_lemma4}Lemma~\ref{lem:friends_lower_bound} counterexample: $n_{\mathrm{scale}}$ vs $\gamma$}
\end{subfigure}

% ---------------- Row 3: vs Delta ----------------
\begin{subfigure}[t]{0.4\textwidth}
  \centering
  \includegraphics[width=\linewidth]{pics/scaling_delta_spiked.png}
  \caption{\label{fig:scaling_delta_spiked}Spiked: $n_{\mathrm{scale}}$ vs $\Delta$}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.42\textwidth}
  \centering
  \includegraphics[width=\linewidth]{pics/scaling_delta_lemma4.png}
  \caption{\label{fig:scaling_delta_lemma4}Lemma~\ref{lem:friends_lower_bound} counterexample: $n_{\mathrm{scale}}$ vs $\Delta$}
\end{subfigure}
\caption{\label{rtpm_scaling_all}Scaling-law experiments for $\TPM$. Left column: spiked covariance model. Right column: Lemma~\ref{lem:friends_lower_bound} counterexample. Rows correspond to varying $s$, $\gamma$, and $\Delta$, respectively.}
\end{figure}

\textbf{Scaling ablations.} We study how many samples are needed for the $\TPM$ to recover the top sparse component on both a standard spiked model and the structured non-spiked construction in Lemma~\ref{lem:friends_lower_bound}. In both cases we work in ambient dimension $d=2500$, run $\TPM$, set truncation level $r=10s$, and $T=100$ iterations, and define $n_{\mathrm{scale}}=\min\{n \text{ in the grid}:\ \sin^2\angle(\hat \vv,\vv)\le \Delta\}$. For the spiked model we draw $\vx_i\sim \mathcal{N}(\0,\msig)$ with $\msig := (1-\gamma)\id_d+\gamma \vv\vv^\top$ where $\vv$ has uniform entries $s^{-\half}$ on its support; for our other experiment we use the worst-case block construction in Lemma~\ref{lem:friends_lower_bound} (with the second eigenvalue $\lambda_2=1-\gamma$) embedded into $d=2500$ by padding the remaining coordinates with isotropic variance $1-\gamma$. Across all sweeps, the empirical behavior is consistent and monotone: $n_{\mathrm{scale}}$ increases with $s$, decreases as $\gamma$ grows, and decreases as the target error $\Delta$ is relaxed. 

We also fit degree-$2$ and $3$ polynomials to the curves in Figures \ref{fig:scaling_s_spiked} and \ref{fig:scaling_s_lemma4}, and power functions with negative exponents $1$ and $2$ for Figures~\ref{fig:scaling_gamma_spiked}, \ref{fig:scaling_gamma_lemma4}, \ref{fig:scaling_delta_spiked}, \ref{fig:scaling_delta_lemma4} to understand the variation of the sample size with these parameters. For dependence on $s$, both 2 and 3 degree polynomial-fit curves capture most of the variation. The plots also suggest that the dependence of the error of our algorithm on $\gamma$ and $\Delta$ is possibly more moderate than that suggested by the theoretical results.


\textbf{Real data.}  We experiment on a standard text sparse PCA setup in  \cite{zhang2011large} using the publicly available NYTimes bag-of-words dataset from the UCI ``Bag of Words'' collection \cite{bag_of_words_164}.
Each document is represented as a sparse word count vector. We restrict to the first $n=10000$ documents, and we select a vocabulary of size $d=20000$. We apply a stabilizing transform $\log(1+c)$ to word-document counts and center the data by subtracting the empirical feature mean. We compute $k=4$ sparse principal components via a deflation-style routine (Algorithm~\ref{alg:deflation}) coupled with the
$\TPM$ algorithm (Algorithm~\ref{alg:deflation}) with $r = 50$ and $T=50$. The output is a sparse vector whose largest-magnitude entries correspond
to an interpretable set of words (see Figure~\ref{fig:nytimes_top_words}). 

The resulting sparse components cleanly separate semantic themes in the corpus.
From the top-10 words by absolute value of entries, the leading components align with
(i) sports and game coverage (PC $1$), (ii) US politics and elections (PC $2$), (iii) markets, business, and finance (PC $3$),
and (iv) web, publishing, and metadata terms (PC $4$). The ``union-support'' in Figure~\ref{fig:nytimes_cov_and_union}  shows that most energy of each component is concentrated in its top ranks, consistent with sparsity. 
Our findings in this application are very \emph{interpretable}: each component is supported
on a small set of words, making the latent topic structure easy to understand compared to dense PCA. This aligns with the results in~\cite{zhang2011large}.

\begin{figure*}[!hbt]
  \centering
    \centering
    \includegraphics[width=0.8\linewidth]{pics/all_pcs_support.png}
    \caption{Top 4 components restricted to the union support, with each row sorted by rank of entries.}
  \label{fig:nytimes_cov_and_union}
\end{figure*}

\begin{figure*}[!hbt]
  \centering
  \begin{subfigure}[t]{0.4\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/pc1_nytimes_words.png}
    \caption{PC 1 (top 10 words by $|\text{entry}|$).}
  \end{subfigure}
  \hfill
  \begin{subfigure}[t]{0.4\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/pc2_nytimes_words.png}
    \caption{PC 2 (top 10 words by $|\text{entry}|$).}
  \end{subfigure}

  \begin{subfigure}[t]{0.4\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/pc3_nytimes_words.png}
    \caption{PC 3 (top 10 words by $|\text{entry}|$).}
  \end{subfigure}
  \hfill
  \begin{subfigure}[t]{0.4\textwidth}
    \centering
    \includegraphics[width=\linewidth]{pics/pc4_nytimes_words.png}
    \caption{PC 4 (top 10 words by $|\text{entry}|$).}
  \end{subfigure}
  \caption{Top 10 words associated with each sparse principal component.}
  \label{fig:nytimes_top_words}
\end{figure*}