%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Template for homework of Introduction to Machine Learning.
%
% Fill in your name, lecture number, lecture date and body
% of homework as indicated below.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,letter,notitlepage]{article}
%Mise en page
\usepackage[left=2cm, right=2cm, lines=45, top=0.8in, bottom=0.7in]{geometry}
\usepackage{fancyhdr}
\usepackage{fancybox}
\usepackage{graphicx}
\usepackage{pdfpages}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{graphicx}
\usepackage[colorlinks,linkcolor=blue]{hyperref}
\renewcommand{\headrulewidth}{1.5pt}
\renewcommand{\footrulewidth}{1.5pt}
\newcommand\Loadedframemethod{TikZ}
\usepackage[framemethod=\Loadedframemethod]{mdframed}
\usepackage{amssymb,amsmath}
\usepackage{amsthm}
\usepackage{thmtools}
\usepackage {mathrsfs}
\usepackage{afterpage}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{9in}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0.25in}
\setlength{\textwidth}{6in}
\pagestyle{fancy}
\usepackage{sectsty}
\sectionfont{\fontsize{12}{13}\selectfont}
%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% Define math operator %%%%%
%%%%%%%%%%%%%%%%%%%%%%%%
\DeclareMathOperator*{\argmin}{\bf argmin}
\DeclareMathOperator*{\relint}{\bf relint\,}
\DeclareMathOperator*{\dom}{\bf dom\,}
\DeclareMathOperator*{\intp}{\bf int\,}
%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%
%% Define the Problem environment %%
%%%%%%%%%%%%%%%%%%%%%%%%
\mdtheorem[
topline=false,
rightline=false,
leftline=false,
bottomline=false,
leftmargin=-10,
rightmargin=-10
]{problem}{\textbf{Problem}}
%%%%%%%%%%%%%%%%%%%%%%%
%% End of the Exercise environment %%
%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%
%% Define the Solution Environment %%
%%%%%%%%%%%%%%%%%%%%%%%
\declaretheoremstyle
[
spaceabove=0pt,
spacebelow=0pt,
headfont=\normalfont\bfseries,
notefont=\mdseries,
notebraces={(}{)},
headpunct={:\quad},
headindent={},
postheadspace={ },
postheadspace=4pt,
bodyfont=\normalfont,
qed=$\blacksquare$,
preheadhook={\begin{mdframed}[style=myframedstyle]},
postfoothook=\end{mdframed},
]{mystyle}
\declaretheorem[style=mystyle,title=Comment,numbered=no]{comment}
\mdfdefinestyle{myframedstyle}{%
topline=false,
rightline=false,
leftline=false,
bottomline=false,
skipabove=-6ex,
leftmargin=-10,
rightmargin=-10}
\declaretheorem[style=mystyle,title=Solution,numbered=no]{solution}
\mdfdefinestyle{myframedstyle}{%
topline=false,
rightline=false,
leftline=false,
bottomline=false,
skipabove=-6ex,
leftmargin=-10,
rightmargin=-10}
%%%%%%%%%%%%%%%%%%%%%%%
%% End of the Solution environment %%
%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\rank}[1]{ \textbf{rank} (#1) }
\chead{\textbf{
Problem
}}
\begin{document}
\vspace*{-7\baselineskip}
\thispagestyle{empty}
\begin{center}
{\bf\large Problems}\\
\end{center}
\noindent
\rule{\textwidth}{2pt}
\vspace*{1.5\baselineskip}
% \noindent There are two types of problems in two sections.
% \begin{enumerate}
% \item Section \ref{Basic Mathematical Skills} is to test your basic mathematical skills, \textit{please select a problem to answer (required)}. We will evaluate your math skills according to your answer.
% \item Section \ref{Problem Solving Ability} is to test your problem solving ability, \textit{you can select a problem to answer if you like (optional)}. We will evaluate your problem solving ability if you answered.
% \end{enumerate}
% \section{Basic Mathematical Skills}\label{Basic Mathematical Skills}
\noindent Please select {\bf ONE problem} arbitrarily to answer. We will evaluate your problem solving skills according to your answer.
\begin{problem}[Second-order sufficient optimality conditions]
Suppose that $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is twice continuously differentiable at $\mathbf{x}$. Show that $\mathbf{x}$ is a strict local minimum if $\nabla f(\mathbf{x})=0$ and the Hessian matrix $\mathbf{H}(\mathbf{x})$ is positive definite.
\end{problem}
\begin{problem}[Low-rank approximation]
Please solve the problem as follows
\begin{align*}
\min_{X\in\mathbb{R}^{m\times n}}\{\|A-X\|_F:\rank{X}\leq K\}.
\end{align*}
\end{problem}
\begin{problem}[Random walk on $\mathbb{Z}$]
Consider the random walk $ X=\{X_n\}_{n\geq 0} $ on $ \mathbb{Z} $ that starts at $ X_0=0 $. The particle moves with probability $ p $ one unit to the right and with probability $ q=1-p $ one unit to the left at each transition. Prove that the state $ 0 $ is recurrent (i.e., $ \mathbb{P}\{X_n=0 \text{ i.o.}|X_0=0\}=1 $) if and only if $ p=q=1/2 $.
\end{problem}
% \section{Problem Solving Ability}\label{Problem Solving Ability}
\begin{problem}[Computing the Number of Groups in a Knowledge Graph]
Knowledge graphs (KGs) are usually collections of factual triplesâ€”(head entity, relation, tail entity), representing human knowledge in a structured way. In a knowledge graph, we use nodes to denote entities and edges to denote relations, respectively.
\noindent Consider a knowledge graph with $n$ entities and $1$ relation called $DirectlyConnectedWith$. Suppose some of them are connected, while some are not. If entity $e_1$ is connected directly with entity $e_2$ and entity $e_2$ is connected directly with entity $e_3$, then we think that entity $e_1$ is connected indirectly with entity $e_3$. A set of entities in this knowledge graph is called a group, if any two entities in this set are connected directly or indirectly and no other entities outside this set are connected with the entities in this set.
\noindent Given an $n \times n$ adjacency matrix $A$, where $A_{ij}=1$ if there exists a triplet (the $i$-th entity, DirectlyConnectedWith, the $j$-th entity) and $A_{ij}=0$ otherwise. Please compute the total number of groups in this KG. Notice:
\begin{itemize}
\item to simplify the problem, we assume this knowledge graph is undirected, i.e., $A$ is a symmetric matrix;
\item given an input $A = [[1,1,0],[1,1,0],[0,0,1]]$, the correct output is 2;
\item you only need to submit the code as an attachment;
\item the python template is given as follows.
\begin{lstlisting}[language=Python]
def compute_groups(A: List[List[int]]) -> int:
# Fill in your code here.
\end{lstlisting}
\end{itemize}
\end{problem}
\begin{problem}[Recognizing the Handwritten Digit]
% Consider the recognition of handwritten digits.
You are expected to build a binary classifier to predict whether the handwritten digit of a given image is 0 or 1. Notice:
\begin{itemize}
\item you can download the dataset from \href{http://yann.lecun.com/exdb/mnist/}{MNIST};
\item you only need to use the data with label 0 or 1;
\item please unzip the data files and put the code file in the same directory;
\item you can use any model and libraries you want;
\item the accuracy on the test set is supposed to reach at least 90\%;
\item you only need to submit the code as an attachment.
% you are expected to only submit the source code as an attachment.
\end{itemize}
\end{problem}
\begin{problem}[Solve the Pommerman Game by Reinforcement Learning]
Consider an interesting Pommerman game described \href{https://www.pommerman.com/about}{here}. In the default free-for-all (FFA) mode, all agents play against each other. The game ends when only one agent remains, and the last survivor agent will be the winner. Our goal is to control an agent to win the game. We use the reinforcement learning (RL) algorithm to train this agent.
\begin{enumerate}
\item A Markov decision process (MDP) is defined by a tuple $(\mathcal{S}, \mathcal{A}, \mathcal{P}, r)$. How to define the reward function is a core issue in most RL tasks. Please define the reward function according to your understanding of this task and explain the reasons.
\item Now we need to choose an algorithm to solve this task. Please write down which RL algorithm you would like to choose and explain why you choose it.
\item We find that the agent tends to learn policies that do not lay any bombs during the early training process. Intuitively, what may be the potential reason for this phenomenon and what can we do to avoid that?
\item Compared with the 1v1 Go game, what are the additional challenges in the Pommerman Game?
\end{enumerate}
\end{problem}
\appendix
\end{document}