\documentclass{article}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}
\usepackage[top=2cm, bottom=4.5cm, left=2.5cm, right=2.5cm]{geometry}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage{xcolor}


% Edit these as appropriate
\newcommand\course{CS 1420}
\newcommand\semester{Spring 2026}            % <-- current semester
\newcommand\hwnumber{3}                      % <-- homework number
\newcommand\duedate{Thursday, February 19, 2026 at 12:00pm \textbf{(Noon)}}

\begin{document}
   \begin{center}
\huge\textbf{Homework \hwnumber}
   \end{center}

   \begin{center}
        \large{Due: \duedate}
   \end{center}

\section*{Written Assignment}
\subsection*{Problem 1: Bias-Complexity Tradeoff}
(10 points)
\begin{enumerate}[a.]
    \item Explain why the No Free Lunch Theorem requires us to introduce bias into our machine learning models.
% TODO: add your solution here!
%
%
%
%
%
%
    \item While training a machine learning model, Steve notices that the model's error remains large even after many training iterations. Steve determines that this error results from overfitting, and he proposes changing the complexity of the hypothesis class to reduce the error. Will changing the complexity of the hypothesis class successfully reduce the error? 
    If so, how should the complexity be changed? If not, why not?
    Explain your reasoning.
% TODO: add your solution here!
%
%
%
%
%
%
    \item After tinkering with his model, Steve eventually manages to prevent his model from overfitting. However, Steve notices that his model's error remains large because his model is now underfitting the data. To decrease underfitting, Steve decides to collect more training data. Will collecting more training data successfully reduce the error? Explain your reasoning. 
    \textit{Hint: Consider if collecting more training data affects approximation and/or estimation error, and if so, explain how.}
% TODO: add your solution here!
%
%
%
%
%
%
    \item Tuning hyperparameters to strike a balance between underfitting and overfitting is a critical part of the machine learning process. Going too far in either direction can often lead to unintended consequences. What are some ways that overfitting or underfitting could produce unfairness in a learned model?
% TODO: add your solution here!
%
%
%
%
%
%
\end{enumerate}

\newpage

\subsection*{Problem 2: Assumptions \& Guarantees}
(10 points)
\begin{enumerate}[a.]
    \item In lecture, we made several assumptions before proving that an ERM solution is PAC learnable. What are these assumptions?
% TODO: add your solution here!
%
%
%
%
%
%
    \item The HTAs want to produce a model to predict the rating of a restaurant in Providence. During the data collection process, the HTAs just select restaurants by going down Thayer Street. Why does the ERM solution not perform well at test time? Explain in terms of the assumptions above.
% TODO: add your solution here!
%
%
%
%
%
%
    \item Steve wants to produce a model to predict the bill at Al Forno based on certain characteristics (party size, number of items ordered, and total time spent at the table). He trains his model on a dataset from \textbf{East Side Pockets} and then uses it to make predictions about bills at \textbf{Al Forno}. Why does the ERM solution not perform well at test time?
% TODO: add your solution here!
%
%
%
%
%
%
\end{enumerate}

\newpage

\subsection*{Problem 3: PAC Learning of Partial Orderings}
\textbf{(20 points)} 
\newcommand{\po}{\preceq}
\subsubsection*{Background Information}
A \textit{partial ordering} (denoted $\po$) is a binary relation over a set $X$ that satisfies the following properties: 
\begin{itemize}
    \item \textit{Reflexivity}: $\forall s \in X$, \; $s \po s$
    \item \textit{Antisymmetry}: $\forall s,t \in X$, \;if $s \po t, t\po s,$ then $s = t$
    \item \textit{Transitivity}: $\forall r,s,t \in X$, \;if $r \po s, s \po t,$ then $r \po t$
\end{itemize}
A \textit{total ordering} is a partial ordering with the additional guarantee that any two elements of the set $A$ are comparable, that is, for any two $a,b \in A$, either $a \preceq b$ or $b \preceq a$ is true. In the case that $\preceq$ is a partial ordering and neither $a \preceq b$ nor $b \preceq a$ are true, we say that $a$ and $b$ are \textit{incomparable} under the partial ordering $\preceq$. 
\\\\
\textbf{Example:} The ``$\leq$" relation is a total ordering on the real numbers. Any two numbers $a, b$ may be compared such that either $a \leq b$ or $b \leq a$. Additionally, the ``$\leq$" relation satisfies the conditions of reflexivity, antisymmetry and transitivity stated above.\\\\
\textbf{Example:} The ``$\subseteq$" relation is a partial ordering but not total ordering. ``$\subseteq$" satisfies reflexivity, transitivity and antisymmetry. However, given two sets $A$ and $B$, there is no guarantee that either $A \subseteq B$ or $B \subseteq$ A.

\subsubsection*{Problem}
Now consider the following:

\begin{itemize}
    \item Let $X$ be a set of $n$ unique elements: $\{1,2,3,...,n\}$.
    \item \textbf{Input Space:} The set $S$ of all possible permutations of length $n$, composed the elements of $X$.\\
    For example, if $X$ is a set of length $n=5$, a permutation could look like $(3,4,2,5,1)$, and $S$ would be the set of all different possible 5-element permutations.
    \item \textbf{Hypothesis Space (H):} The set of all hypotheses, where each hypothesis maps all $n$-element permutations to either 0 or 1. Each hypothesis represents a partial ordering. So, according to the hypothesis, a $n$-element permutation would be mapped to $1$ if it abides by the partial ordering and to $0$ otherwise.
    For example, if a hypothesis $h$ is $1 \preceq 3$, and we have the permutation $(3,1)$, the permutation does not abide by the hypothesis since $3$ is before $1$, reading left to right. Therefore, $h$ would map $(3,1)$ to $0$.

\end{itemize}

\noindent Suppose that there is a hidden partial ordering that we do not have access to. We have a sample of permutations, and a label for each sample indicating whether the permutation is consistent with the true hidden partial ordering.
Assume that the sample has both positively and negatively labelled permutations.
We are trying to learn the rule from this sample.
\\\\
\noindent \textbf{Example:} Let $\preceq$ be a partial ordering on the set $X=\{1, 2, 3\}$, defined such that $1 \preceq 2$ and $3$ is incomparable to both $1,2$. Let $h$ be the hypothesis associated with $\preceq$; that is, $h$ is the hypothesis which maps all permutations of $X$ abiding by $\preceq$ to $1$ and all permutations not abiding by $\preceq$ to $0$. 

Then, the permutations
    \begin{equation*}
        (1,2,3),\qquad (1,3,2),\qquad (3,1,2)
    \end{equation*}
    abide by $\preceq$ (notice that $1$ precedes $2$ in all three and it does not matter where $3$ is) and are labelled 1 by $h$. However,
    \begin{equation*}
        (2,1,3), \qquad (2,3,1), \qquad (3,2,1)
    \end{equation*}
    do not abide by $\preceq$ since $2$ precedes $1$ in all three of these. Hence, they are labelled 0 by $h$.

% \textbf{Example}:
    
% \(\)\\
% Suppose $n=3$, the set $X=\{1,2,3\}$, and we have a hidden partial ordering $1 \po 3$. \\
% Then our input space is the set of all possible $3$-element permutations consisting of elements from $\{1,2,3\}$, and our hypothesis space is the set of all hypotheses mapping each permutation to $0$ or $1$.\\
% We have access to a sample of permutations that are labeled. For example, let $(2,3,1)$ be a permutation that is available to us. It has a label of $0$ since it violates the hidden partial ordering - $3$ precedes $1$ in this permutation, which does not match the hidden ordering. However, since we don't have access to the ordering, we have to use this permutation and the rest of sample to learn this true ordering.

\begin{enumerate}[a.]
    
    \item Show that $|H|$ is between $n!$ and $3^{(n^2)}$. 
    That is, show that the number of possible valid partial orders generated from $n$ elements is bounded by $n!$ and $3^{(n^2)}$. \\
    \textit{Hint: For the upper bound, it may be helpful to consider that $h \in H$ may be represented as a Directed Acyclic Graph (DAG). The nodes of the DAG can be thought of as the elements that make up the $n$-element permutations of the input space. Think about how the relations between nodes in a DAG are similar to the relations between elements within a partial ordering.
    This question may also therefore be approached by thinking about the number of valid DAGs with n nodes. }
% TODO: add your solution here!
%
%
%
%
%
%
    \item Show that the amount of data needed is polynomial in $n$ (provide the asymptotic bound using the Big-O notation), in order to ensure the ERM solution is PAC. \textit{Hint: Consider the bounds for $|H|$ we proved in part (a).}
% TODO: add your solution here!
%
%
%
%
%
%
    \item Describe an algorithm you could use to efficiently find an ERM solution (the true partial ordering, or DAG) for a given sample of observations. Be sure to explain the steps of your algorithm, prove the correctness of the algorithm and analyze its runtime. Note, we do not have a           
    strict runtime requirement, but the algorithm should be in polynomial time. The algorithm itself can be written in pseudocode or in words. \textit{Hint: The true hypothesis is within our hypothesis space. Consider the direction of the ordering between any two elements in every permutation with label 1.}
% TODO: add your solution here!
%
%
%
%
%
%
\end{enumerate}

\newpage

\subsection*{Grading Breakdown}

The grading breakdown for the assignment is as follows:
\begin{center}
\begin{tabular}{| l | r |}
	\hline
	Problem 1 & 10 points \\
	Problem 2 & 10 points \\
	Problem 3 & 20 points \\
	\hline
	Total & 40 points \\
	\hline
\end{tabular}
\end{center}

\subsection*{Handing in}
Your written assignment should be uploaded to Gradescope under ``Homework 3.''
If you have questions on how to set up or use Gradescope, ask on Edstem! For this assignment, you should have written answers for Problems 1, 2, and 3. 

\subsubsection*{Anonymous Grading}

You need to be graded anonymously, so do not write your name anywhere on your handin. 


\subsection*{Academic Integrity}
The \href{https://cs.brown.edu/courses/csci1420/assets/docs/collaboration.pdf}{CSCI 1420 Collaboration Policy} applies to this assignment.
As outlined in the \href{https://college.brown.edu/design-your-education/academic-policies/academic-code}{Brown Academic Code} and the \href{https://graduateschool.brown.edu/academics-research/rules-regulations/academic-code}{Brown Academic Code, Graduate Student Edition}, attempting to pass off another's work or AI-generated work as your own can result in failing the assignment, failing this course, or even dismissal or expulsion from Brown.  More than that, you will be missing out on the goal of your education, which is the cultivation of your own mind, thoughts, and abilities.  Please review this course's collaboration policy and if you have any questions, please contact the instructor.

\end{document}