Discretization of the Optimization Problem Say that $g:[0,1] \rightarrow \mathbb{R}$ is a smooth function that has a unique maximizer.
Let $x_1,\cdots,x_n$ be a set of equally spaced points on $[0,1]$.
Question: How close does the discretized maximizer approximate the true maximizer? Under what conditions do we have
$$ \left| \underset{x \in [0,1]}{\text{argmax}} g(x) - \underset{x_i}{\text{argmax}} g(x_i) \right| = O(1/n), \text{ as } n \to \infty. $$
Thanks in advance for any help! References are greatly appreciated!
 A: Let $m_i$ be the $(i)$-th maximum (i.e., $g(m_i)=0$) of $g$ on $I:=[0,1]$, where $m_1$ is the (unique) global maximum . Also, let $S_i := \{x \in I: g(x) = m_i\}$ be the set of points in $I$ that map to $m_i$
Since $g$ has a unique maximizer, we know that $S_i=\{x^*\}$ is a singleton set, so there is one unique value we will call $x^*$ that maximizes $g$. In addition, due to continuity of $g$, there is a "unimodal interval" $U:=(x_L,x_R)$ where $g(x) > m_2 : x\in U$. If we restrict the function to $U$, we will only have the unique maximum $m_1$ and so $g$ is "locally unimodal" if restricted to the interval $U$ with mode $g(x^*)=m_1$.
Define the $n$-th equal-spaced mesh of $I$ as $I_n := \left(\frac{i}{n}\right)_{i \in \{0,...,n\}}$
For a given $n$, we know
$$\min_{x \in I_n}|x^*-x| \leq \frac{1}{2n}=O\left(\frac{1}{n}\right)$$
Let $x'_n:=\arg \min_{x \in I_n}|x^*-x|$ be the closest mesh point to $x^*$ then we can define the absolute secant slope as:
$$\delta_n:=\left|\frac{g(x^*) - g(x_n')}{x^*-x_n'}\right|$$
Since $g'(x^*) = 0$ we have:
$$g'(x^*) = 0 \implies \lim_{n\to \infty} \delta_n = 0 \implies \left|g(x^*) - g(x_n')\right|=o\left(|x^*-x_n'|\right)=o\left(\frac{1}{2n}\right)$$
$$\implies \left|g(x^*) - g(x_n')\right|=O\left(\frac{1}{n}\right)$$
However, we will not generally know $x'_n$. Instead, we will know the "discrete maximum" $\widehat{x_n}:=\arg \max_{x \in I_n}g(x)$.
Since $g$ on $U$ is unimodal, we know that there exists and integer $N>0$ such that:
$$\frac{1}{n} <\frac{|U|}{2}\;\forall n> N$$
Without loss of generality, assume $n>N$ in all that follows so $g$ is unimodal about $x^*$. At this point, we know that  $\;\widehat{x_n} \in U \;\;\forall n>N$.
If $g(x)$ were symmetric about $x^*$ on $U$, then $x_n'=\widehat{x_n}$ and we've shown that it converges $O\left(\frac{1}{n}\right)$; however, if $g(x_n')<g(\widehat{x_n})$ then $\widehat{x_n}$ must be on the opposite side of $x^*$ than $x_n'$, since if it were not, it would be be closer to $x^*$ than $x_n'$, which is a contradiction.
How far away from $x'_n$ can $\widehat{x_n}$ be?
Assume without loss of generality that $\widehat{x_n} > x^*$, and also assume there is a mesh point $z_n \in (x^*,\widehat{x_n})$. By unimodality, $g(z_n)>g(\widehat{x_n})$ which is also a contradiction. Therefore, there can be no mesh points between $x'_n$ and $\widehat{x_n}$ which implies that they are, at most, adjacent mesh points:
$$\Delta_n := |x'_n - \widehat{x_n}| \in \left\{0,\frac{1}{n}\right\} \implies \Delta_n \leq \frac{1}{n}$$
Since $x^* \in (x'_n, \widehat{x_n})$ we know
$$|x^* - \widehat{x_n}| < \Delta_n < \frac{1}{n} = O\left(\frac{1}{n}\right) \square$$
