\arxiv{\vspace{-6pt}}
\section{Numerical experiments}\label{sec:exp}
\arxiv{\vspace{-3pt}}
To see whether our analysis applies to non-worst case problem instances, 
we generate 5,000 random cubic-regularization problems with 
$d=10^{6}$ and controlled condition number 
$\kappa=(\lmax+\rs)/(\lmin+\rs)$ (see Section~\ref{sec:exp-details} in 
the supplement for more details). We repeat the experiment three 
times with different values of $\kappa$ and summarize the results in 
Figure~\ref{fig:exp}a.  

As seen in the figure, about 20 Lanczos iterations suffice to solve even the 
worst-conditioned instances to about $10\%$ accuracy, and 100 
iterations give accuracy better than $1\%$. Moreover, for $t \gtrapprox 
\sqrt{\kappa}$, the approximation error decays exponentially with precisely 
the rate $4/\sqrt{\kappa}$ predicted by our analysis, for almost all the 
generated problems. For $t \ll \sqrt{\kappa}$, the error decays 
approximately as $t^{-2}$. We conclude that the rates characterized by  
Theorem~\ref{thm:tr} are relevant beyond the worst case.

We conduct an additional experiment to test the effect of randomization for 
``hard case'' instances, where $\kappa = \infty$.

We generate such problem instances 

(see details in Section~\ref{sec:exp-details}), and 
compare the joint subspace randomization scheme 
(Corollary~\ref{cor:tr-rand-joint}) to the perturbation scheme 
(Corollary~\ref{cor:tr-rand}) with different perturbation magnitudes 
$\sigma$; the results are shown in Figure~\ref{fig:exp}b. For any fixed 
target accuracy, some choices of $\sigma$ 
yield faster convergence than the joint subspace scheme. However, for any 
fixed $\sigma$ optimization eventually hits a noise floor due to the 
perturbation, while the joint subspace scheme continues to improve. 
Choosing $\sigma$ requires striking a balance: if too large  
the noise floor is high and might even be worse 
than no perturbation at all; if too small, escaping the unperturbed error 
level will take too long, and the method might falsely declare convergence. 
A 
practical heuristic for safely choosing 
$\sigma$ 
is 
an interesting topic for future research.

\begin{figure}
	    \centering
	\hspace{-0.75cm}
	\begin{minipage}[t]{0.72\textwidth}
		\centering
		\includegraphics[height=5.025cm]{code/figures/experiment.png}
		\\
		\footnotesize\textbf{(a)}
	\end{minipage}
	\begin{minipage}[t]{0.27\textwidth}
		\centering
		\includegraphics[height=5.1cm]{code/figures/pert_experiment.png}
		\\
		\nips{~~~~~~~~~~~~~~~~}
		\arxiv{~~~~~}
		\footnotesize\textbf{(b)}
	\end{minipage}
	\caption{\label{fig:exp}Optimality gap of 
	Krylov subspace solutions on random 
	cubic-regularization problems, versus subspace dimension 
	$t$. \textbf{(a)} Columns show ensembles with different 
	condition numbers 
	$\kappa$, and rows differ by scaling of $t$. Thin lines indicate 
	results for individual instances, and bold lines indicate ensemble median 
	and maximum suboptimality. 


	\textbf{(b)} Each line represents median suboptimality, and shaded 
	regions represent inter-quartile range.


	Different lines 
	correspond to different randomization settings.
}
\end{figure}
{"config": "arxiv", "file": "1806.09222/experiment.tex"}