\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, amsfonts}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage{xcolor}

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

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

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


\subsection*{Problem 1: VC Dimension} 
(40 points)\\

\noindent For any hypothesis class $\mathcal{H}$ on domain $\mathcal{X}$, to show that the VC Dimension of $\mathcal{H}$ is $d$, you should prove each of the following:

\begin{itemize}
    \item There exists a set $C \subset \mathcal{X}$ of size $d$ such that $\mathcal{H}$ shatters $C$. (Recall that a set is a collection of unique elements.)
    \item There does not exist a set $C' \subset \mathcal{X}$ of size $d + 1$ such that $\mathcal{H}$ shatters $C'$. 
\end{itemize}

\begin{enumerate}
    \item Compute and prove the VC dimension for the following hypothesis classes:

\begin{enumerate}[a.]
    \item The class of signed intervals in $\mathbb{R}$, $\mathcal{H} = \{h_{a,b,s} : a \leq b, s \in \{-1, 1\}\}$ where:
    
\[
    h_{a,b,s} = 
    \begin{cases}
        s & \text{if} \; x \in [a, b] \\
        -s & \text{if} \; x \not \in [a,b]
    \end{cases}
\]

    \item The class of origin-centered spheres in $\mathbb{R}^d$, $\mathcal{H}
    = \{h_{a,s} : s \in \{-1, 1\}, a \in \mathbb{R}\}$ where:
    % change from R^d to R^k
    % change to a \geq 0
\[
    h_{a,s} = 
        \begin{cases}
            s & \text{if} \; x \; \text{is within or on the origin centered sphere of radius} \; a \\
            -s & \text{if} \; x \; \text{is outside the origin centered sphere of radius} \; a
        \end{cases}
\]

\end{enumerate}

\item Consider two hypothesis classes $\mathcal{H}_1$, $\mathcal{H}_2$ such that $\mathcal{H}_1 \subset \mathcal{H}_2$. Prove that the VC Dimension of $\mathcal{H}_2$ is at least as large as the VC Dimension of $\mathcal{H}_1$.

\end{enumerate}

% TODO: add your solution here!
%
%
%
%
%
%

\subsection*{Problem 2: VC Dimension and PAC Learning} 
(40 points) \\

\noindent Decision trees can split on data with binary features ($\mathcal{X} = \{0,1\}^d$) or continuous features ($\mathcal{X}=\mathbb{R}^d$). Assume that the nodes of a continuous decision tree have splitting rules that threshold the value of a single feature. \textit{Note that for continuous decision trees, multiple splits can be made on the same feature. For binary decision trees, only a single split can be made on a feature.} \\ \\
Consider the following hypothesis classes:
\begin{align*}
    \mathcal{H}_1 &= \{h : h \text{ is a decision tree for data with only binary features}\} \\
    \mathcal{H}_2 &= \{h : h \text{ is a decision tree for data with only continuous features}\}
\end{align*}

\begin{enumerate}
    \item Compute and prove the VC dimension of $\mathcal{H}_1$.
    \item Show that the VC dimension is infinite for $\mathcal{H}_2$.
    \item Is $\mathcal{H}_1$ PAC learnable? How about $\mathcal{H}_2$? Explain.
\end{enumerate}

% TODO: add your solution here!
%
%
%
%
%
%

\subsection*{Problem 3: Uniform Convergence} 
(15 points) \\

\noindent In class and in Corollary 4.6 in the textbook, we proved that finite hypothesis classes enjoy uniform convergence, and therefore are agnostically PAC learnable. In those proofs, we assumed that the loss function has a range of $[0, 1]$. Prove that if the range of the loss function is instead $[a, b]$, then the sample complexity satisfies: \\

\[
m_{\mathcal{H}}(\epsilon, \delta)
\leq m_\mathcal{H}^{\text{UC}}(\epsilon / 2, \delta)
\leq \left \lceil{\frac{2 \log(2 |\mathcal{H}| / \delta) (b-a)^2}{\epsilon^2}} \right\rceil \; .
\] \\
You may not use the result from in class or Corollary 4.6 as an argument for your proof, but you may (and it is recommended!) use the same proof steps in guiding your approach. \\\\
% TODO: add your solution here!
%
%
%
%
%
%

\subsection*{Problem 4: Socially Responsible Computing: Data Privacy}
(5 points)\\

\noindent 
In 2012, Minerva High School, a public school in Pittsburgh, PA with nearly 3,000 students, hit a record student dropout rate of nine percent.\footnote[1]{\href{https://aiethics.princeton.edu/wp-content/uploads/sites/587/2018/10/Princeton-AI-Ethics-Case-Study-3.pdf}{Case study} by Princeton Dialogues on AI and Ethics licensed under \href{https://creativecommons.org/licenses/by/4.0/legalcode}{CC Attribution 4.0 International}}
The school principal and board decided to put the extensive data the school had already collected about its students’ behavior to use. These datasets included demographic information, academic performance, disciplinary and attendance records, and teacher statistics (i.e. percent of students failing per class, years of teaching). The school also tracked students’ internet use and monitored their movements throughout the campus. 

The board members suggested that developments in machine learning could be applied to this information to understand what causes students to drop out so that new incentive structures for teachers and students could be created. They contracted a local data science company, Hephaestats, to provide them with their existing databases and gave them access to new data as it was collected. Given the urgency of the situation, the principal proceeded quickly, without time to notify students and parents of this agreement, nor giving them the opportunity to opt out. They justified that this decision was supported by the school board and fell within the general mandate to promote positive educational outcomes for all. 

\begin{enumerate}
    \item In this case, the decision to adopt AI technologies came from above---a suggestion from the school board, implemented by the principal. Who are the other relevant stakeholders, and how could they have been involved? Should they have been involved in the decision to use Hephaestats?
\item Review \href{https://bidenwhitehouse.archives.gov/ostp/ai-bill-of-rights/data-privacy/}{the introduction} of this section on Data Privacy in the Blueprint for an AI Bill of Rights. According to the blueprint, did the school violate the privacy of its students by sharing their data with Hephaestats? If you were the principal, what would you have done? 
\end{enumerate}


\subsection*{Grading Breakdown}

The grading breakdown for the assignment is as follows:
\begin{center}
\begin{tabular}{| l | r |}
	\hline
	Problem 1 & 40 points \\
	Problem 2 & 40 points \\
	Problem 3 & 15 points \\
	Problem 4 & 5 points \\
	\hline
	Total & 100 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, 3, and 4. 

\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}
