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

\title{CSCI 145 Problem 11: Expressivity versus Optimization}
\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; bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 11: Expressivity versus Optimization \hfill \textnormal{2 points}}

Consider the XOR data set $\mathbf{x}\in\{0,1\}^2$, with label $y=1$ when exactly one coordinate of $\mathbf{x}$ is one and $y=-1$ otherwise. Fit it with
$$
f_{\boldsymbol{\theta}}(\mathbf{x})=c+\sum_{j=1}^2 a_j\operatorname{ReLU}(\mathbf{w}_j^\top \mathbf{x}+b_j)
$$
by minimizing the average squared error over the four examples.

A researcher claims: ``Once a neural-network architecture can fit the training data, every parameter setting with nonzero loss has a descent direction.'' Determine whether this architecture can fit the data, then decide whether the claim is true for its squared-error landscape. Give a proof or counterexample that accounts for the full gradient with respect to $c$, $a_j$, $\mathbf{w}_j$, and $b_j$. Any stationary point used in your argument must keep every hidden preactivation strictly away from the ReLU kink on all four inputs, so nondifferentiability cannot explain it.

Your answer should make clear which fact is about the functions the architecture can represent and which is about the loss landscape seen by backpropagation.

\paragraph{Results you may use.}
On a strictly negative input, the ReLU and its derivative are both zero. You may also quote the scalar backpropagation equations from the reading.

%\input{solutions/solution11}
\end{document}
