\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\title{CSCI 145 Problem 8: The Slowest Direction Sets the Pace}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}

\maketitle

\subsection*{Submission Instructions}

Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive --- so bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 8: The Slowest Direction Sets the Pace \hfill \textnormal{2 points}}

Consider the quadratic loss
$$
\mathcal{L}(\mathbf{w})=\frac12(\mathbf{w}-\mathbf{w}^\star)^\top
\mathbf{A}(\mathbf{w}-\mathbf{w}^\star),
$$
where $\mathbf{A}\in\mathbb{R}^{d\times d}$ is symmetric positive definite with eigenvalues in $[\lambda_{\min},\lambda_{\max}]$. You must choose one fixed learning rate $\alpha$ before seeing the initial error or which eigendirections it contains.

Choose the learning rate that minimizes the worst possible fraction of the error norm surviving one gradient-descent step. Prove that your choice is optimal, derive its contraction factor in terms of $\kappa=\lambda_{\max}/\lambda_{\min}$, and determine the number of steps needed to reduce every initial error by a factor of $10$.

Use the result to explain the conditioning experiment from lecture: before feature scaling, the least-squares bowl had $\kappa\approx9.5\times10^5$. Estimate the worst-case error remaining after $20{,}000$ optimally tuned steps and the number of steps needed for a tenfold reduction. Compare this with a perfectly scaled bowl, and assess the claim that a model is slow to optimize primarily because it has many parameters.

\paragraph{Results you may use.}
Along an eigenvector of curvature $\lambda$, one gradient-descent step multiplies the error component by $1-\alpha\lambda$. Thus the worst one-step contraction is $\max_{\lambda\in[\lambda_{\min},\lambda_{\max}]}|1-\alpha\lambda|$, whose maximum occurs at an endpoint. For small $u$, you may use $\log(1-u)\approx-u$.

%\input{solutions/solution08}

\end{document}
