\documentclass[t,aspectratio=169]{beamer}
\usetheme{metropolis}
\metroset{block=fill}

\input{../../_assets/basicslide1}
\input{../../_assets/macros}

\author{Samuel Vaiter}
\date{}
\institute{
Created: 2023-11-08.\\
Last update: 2023-11-08.\\
Status: inprogress.}
\title{An obvious optimization method: blackbox query}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}


\begin{frame}
  \frametitle{Blackbox query}

  \begin{columns}
    \begin{column}{0.5\linewidth}
      \[
        \min_{x \in [-1,1]^{d}} f(x)
      \]
      \textbf{Goal}: find $\hat x \approx x^{\star}$ up to a precision $\epsilon > 0$.

      \textbf{Discretization}:
      \[
        G_{\epsilon} = \setcond{k \epsilon}{k \in \set{-\lfloor \epsilon^{-1} \rfloor, \dots, \lfloor \epsilon^{-1} \rfloor}}
      \]

      \textbf{Approximate solution}:
      \[
        \hat x = \uargmin{x \in G_{\epsilon}} f(x)
      \]

      \textbf{Error} {\footnotesize (for $L$-Lipschitz function)}:
      \[
        f(\hat x) - f(x^{\star}) \leq L \epsilon
      \]
    \end{column}
    \begin{column}{0.5\linewidth}
      \begin{center}
        \begin{tikzpicture}[domain=-1:1,scale=2.5]
          \draw[->] (-1.1,0) -- (1.1,0) node[above] {$x$};
          \draw[->] (0,-0.1) -- (0,2.5) node[right] {$f(x)$};

          \coordinate (min) at (0.25,0.7);
          \draw[domain=-1:1] plot (\x, {(abs(\x-0.25)+0.7});
          \fill (min) circle [radius=1pt] node[left] {$x^{\star}$};

          \foreach \k in {1, 2, 3} {
            \only<\k>{
              \pgfmathsetmacro\z{-(\k-1)/\k}
              \draw[<->,red] (0,0.15) -- (1/\k,0.15) node[midway,above] {$\epsilon$};
              \foreach \x [parse=true,evaluate=\x as \value using abs(\x-0.25)+0.7] in {-1,\z,...,1,1}
              {
                \draw[blue,thick,dashed] (\x,0) -- (\x,\value);
                \fill[red] (\x,\value) circle [radius=1pt];
              }
            }
          }
        \end{tikzpicture}
      \end{center}
    \end{column}
  \end{columns}
  \note{
    \begin{itemize}
    \item Draw the difference $f(\hat x) - f(x^{\star})$
    \end{itemize}
  }
\end{frame}

\begin{frame}
  \frametitle{Blackbox query: what's the catch? \alert<4->{Curse of dimensionality!}}

  \begin{columns}[T]
    \begin{column}{0.5\linewidth}
      \textbf{Size of $G_{\epsilon}$ to get an $\epsilon$ precision}\\
      \begin{itemize}[<+->]
      \item\emph{1D}: $O(\lfloor \epsilon^{-1} \rfloor)^{\phantom{1}}$ calls to $f$
      \item\emph{2D}: $O(\lfloor \epsilon^{-1} \rfloor)^{2}$ calls to $f$
      \item\emph{3D}: $O(\lfloor \epsilon^{-1} \rfloor)^{3}$ calls to $f$
      \end{itemize}
      \vspace{0.2cm}
      \only<4->{\fbox{\emph{dimension $d$}: $O(\lfloor \epsilon^{-1} \rfloor)^{d}$ calls to $f$}}
      \vspace{0.2cm}
      \begin{center}
        \begin{tikzpicture}[scale=0.25,visible on=<3->]
          \foreach \x in {0,...,10}
          {
            \draw (0,\x ,10) -- (10,\x ,10);
            \draw (\x ,0,10) -- (\x ,10,10);
            \draw (10,\x ,10) -- (10,\x ,0);
            \draw (\x ,10,10) -- (\x ,10,0);
            \draw (10,0,\x ) -- (10,10,\x );
            \draw (0,10,\x ) -- (10,10,\x );
          }
          \foreach \y in {0,...,10}
          \foreach \z in {0,...,10}
          {
            \node [draw, circle, fill=red, minimum size=4pt,inner sep=0pt,] at (10,\y,\z) {};
          }
          \foreach \x in {0,...,10}
          \foreach \z in {0,...,10}
          {
            \node [draw, circle, fill=red, minimum size=4pt,inner sep=0pt,] at (\x,10,\z) {};
          }
          \foreach \x in {0,...,10}
          \foreach \y in {0,...,10}
          {
            \node [draw, circle, fill=red, minimum size=4pt,inner sep=0pt,] at (\x,\y,10) {};
          }
        \end{tikzpicture}
      \end{center}
    \end{column}
    \begin{column}{0.5\linewidth}
      \begin{center}
        \begin{tikzpicture}[domain=-1:1,xscale=2]
          \draw[->] (-1.1,0) -- (1.1,0);
          \draw[->] (0,-0.1) -- (0,2);
          \draw[domain=-1:1] plot (\x, {(abs(\x-0.25)+0.7});

          \foreach \k in {5} {
            \pgfmathsetmacro\z{-(\k-1)/\k}
            \draw[<->,red] (0,0.15) -- (1/\k,0.15) node[midway,above] {$\epsilon$};
            \foreach \x [parse=true,evaluate=\x as \value using abs(\x-0.25)+0.7] in {-1,\z,...,1,1}
            {
              \draw[blue,thick,dashed] (\x,0) -- (\x,\value);
              \node [draw, circle, fill=red, minimum size=4pt,inner sep=0pt,] at (\x,\value) {};
            }
          }
        \end{tikzpicture}

        \begin{tikzpicture}[visible on=<2->]
          \draw[xstep=0.4,ystep=0.4,lightgray,thin] (-2,-2) grid (2,2);
          \foreach \x in {-2,-1.6,...,2}
          \foreach \y in {-2,-1.6,...,2}
          {
            \node [draw, circle, fill=red, minimum size=4pt,inner sep=0pt,] at (\x,\y) {};
          }
          \draw[<->,red] (0,0) -- (0.4,0) node[midway,above] {$\epsilon$};
        \end{tikzpicture}
      \end{center}
    \end{column}
  \end{columns}
\end{frame}

\end{document}