File size: 7,502 Bytes
d3206a6 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | \section{Experiments}\label{sec:experiments}
We validate Theorems~\ref{thm:formal} and~\ref{thm:lower_bound} empirically by simulating Algorithm~\ref{alg:oja_comp}. Unless otherwise stated, experiments use $\lambda_1=2$, $\lambda_2=1$ (eigengap $\Delta=1$) and the decaying step-size schedule of Theorem~\ref{thm:formal}.
\subsection{Adaptive vs.\ Non-Adaptive Measurements}
A natural question is whether the adaptive measurement strategy --- measuring along the current estimate $\vu_t$ and its orthogonal complement --- is necessary, or whether non-adaptive random measurements suffice. Table~\ref{tab:adaptive} shows that adaptivity provides a substantial, dimension-dependent advantage.
\begin{table}[t]
\centering
\caption{Iterations to reach target error $10^{-2}$ for adaptive vs.\ non-adaptive measurements ($\lambda_1=2$, $\lambda_2=1$, learning rate $\eta = 0.01/d$, median of 20 trials). Both methods use exactly two scalar measurements per iteration. The Slowdown column is computed from the unrounded medians; dividing the displayed (rounded) values differs slightly in the last digit.}
\label{tab:adaptive}
\vspace{2mm}
\begin{tabular}{cccc}
\toprule
Dimension $d$ & Adaptive & Non-Adaptive & Slowdown \\
\midrule
16 & $3.8 \times 10^{4}$ & $1.6 \times 10^{5}$ & $4.2\times$ \\
32 & $1.9 \times 10^{5}$ & $1.3 \times 10^{6}$ & $7.1\times$ \\
64 & $8.4 \times 10^{5}$ & $1.2 \times 10^{7}$ & $14\times$ \\
\bottomrule
\end{tabular}
\end{table}
The slowdown grows with dimension: from $4.2\times$ at $d=16$ to $14\times$ at $d=64$. This has an intuitive explanation: a random 2-dimensional subspace has expected squared overlap of only $O(1/d)$ with any fixed direction, so non-adaptive sensing extracts little useful gradient information per iteration. In contrast, our adaptive strategy measures along the current estimate $\vu_t$, creating a positive feedback loop where any existing alignment with the signal is amplified.
\subsection{Upper Bound, Lower Bound, and Empirical Error}\label{sec:exp_ub_lb}
\begin{figure}
\centering
\includegraphics[width=\linewidth]{plots/ub_lb_empirical.png}
\caption{Upper bound (Theorem~\ref{thm:formal}), minimax lower bound (Theorem~\ref{thm:lower_bound}), and empirical error of Algorithm~\ref{alg:oja_comp} on shared axes. Empirical curve shows median (solid) and 25--75 percentile band (shaded) over 50 trials. The constant-factor gap between the two bounds is $12\cdot 864 = 10{,}368$ asymptotically (Section~\ref{sec:results}); the empirical curve sits neatly between the two bounds. Parameters: $d=64$, $\lambda_1=2$, $\lambda_2=1$, step sizes from Theorem~\ref{thm:formal}.}
\label{fig:ub_lb_empirical}
\vspace{-1mm}
\end{figure}
Figure~\ref{fig:ub_lb_empirical} jointly shows our upper and lower bounds together with averaged empirical error trajectories. The empirical median tracks the upper and lower bounds to within constant factors across the local-convergence phase. The upper bound is tighter than the lower bound, which is typical of Assouad-based proofs, where the lower-bound construction is intrinsically conservative.
\subsection{Dimension Scaling}
\begin{figure}
\centering
\includegraphics[width=\linewidth]{plots/dimension_scaling.png}
\caption{Empirical validation of the $d^2$ dimension scaling. (a)~Convergence trajectories at $d \in \{16, 32, 64, 128, 256\}$, each median crossing the target error $10^{-2}$ (dashed gray) at progressively later iterations. (b)~Log-log iterations to reach target error vs.\ dimension on the extended grid $d \in \{16, 32, 64, 128, 256, 512, 1024\}$ with $10$ trials per dimension; the empirical least-squares fit $t \propto d^{2.16}$ (orange dashed) closely tracks the theoretical leading-order $t \propto d^2$ (gray dotted). Simulations use $\lambda_1=2$, $\lambda_2=1$, learning rate $\eta = 0.01/d$.}
\label{fig:scaling}
\vspace{-1mm}
\end{figure}
To validate our theoretical prediction that convergence time scales as $\Theta(d^2)$, we run Algorithm~\ref{alg:oja_comp} across dimensions $d \in \{16, 32, 64, 128, 256, 512, 1024\}$ and measure iterations to reach target error $10^{-2}$. Figure~\ref{fig:scaling}(a) shows convergence trajectories at five dimensions reaching the $10^{-2}$ target; Figure~\ref{fig:scaling}(b) shows the log-log scaling analysis on the extended seven-dimension grid, and Table~\ref{tab:scaling} reports the corresponding numerical values.
The empirical scaling exponent is $2.16$ on $d\in\{16,32,64,128,256,512,1024\}$ with $10$ trials per dimension, closely matching the theoretical $d^2$ prediction. Two finite-sample effects account for the small excess over $2$: (i) the second term $15\lambda_1 d/\Delta$ in $S = 3\lambda_1\lambda_2 d^2/\Delta^2 + 15\lambda_1 d/\Delta$ is non-negligible at moderate $d$, contributing an $O(d)$ component to the leading-order rate; and (ii) the warmup phase $t_0 = (4S+1)\log(d/2)$ adds a $\log d$ correction. The leading $d^2$ term dominates as $d\to\infty$, so the fitted exponent approaches $2$ asymptotically.
\begin{table}[t]
\centering
\caption{Numerical results for the dimension scaling experiment. Iterations to reach target error $10^{-2}$ (median of $10$ trials per dimension) with $\lambda_1=2$, $\lambda_2=1$, learning rate $\eta = 0.01/d$. The ratio column shows $t_d / t_{d/2}$, which equals $4$ for exact $d^2$ scaling.}
\label{tab:scaling}
\vspace{2mm}
\begin{tabular}{ccc}
\toprule
Dimension $d$ & Iterations & Ratio \\
\midrule
16 & 35{,}500 & --- \\
32 & 172{,}750 & 4.87 \\
64 & 879{,}190 & 5.09 \\
128 & 4{,}091{,}830 & 4.65 \\
256 & 17{,}950{,}000 & 4.39 \\
512 & 68{,}500{,}000 & 3.82 \\
1024 & 284{,}650{,}000 & 4.15 \\
\bottomrule
\end{tabular}
\end{table}
The ratio between successive dimensions in Table~\ref{tab:scaling} hovers around $4$--$5$, consistent with $d^2$ scaling; Appendix~\ref{app:additional_experiments} provides further validation, including eigengap dependence.
\subsection{Tracking Validation}
\begin{figure}
\centering
\includegraphics[width=\linewidth]{plots/tracking.png}
\caption{Validation of tracking analysis. (a) Convergence trajectories for drift velocities $V \in \{10^{-7}, 10^{-6}, 10^{-5}, 10^{-4}, 10^{-3}\}$, each converging to a different steady-state error. Solid lines show medians over 20 trials with 20--80 percentile shading; dashed lines show theoretical fixed points from Equation~\ref{eq:fixed}. (b) Theoretical fixed point $x^* = V + \sqrt{VS}$ (dashed) versus empirical steady-state error (solid with 20--80 percentile shading). Parameters: $d=10$, $\lambda_1=2$, $\lambda_2=1$, step size from Equation~\ref{eq:fixed_lr}, initial alignment $(\bar\vu^T\vu_0)^2 = 0.1$.}
\label{fig:tracking}
\vspace{-1mm}
\end{figure}
Figure~\ref{fig:tracking} validates the tracking analysis from Section~\ref{sec:tracking_main}, simulating Algorithm~\ref{alg:oja_comp} with a time-varying principal eigenvector that rotates by a random angle $\theta$ per iteration with $\sin^2(\theta) = V$ at the constant step size of Equation~\ref{eq:fixed_lr}. Panel~(a) shows the error converging to a steady-state value that increases with drift velocity, and Panel~(b) confirms that the theoretical fixed point $x^* = V + \sqrt{VS}$ provides a valid upper bound across four orders of magnitude in $V$.
|