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!

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') 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$$

• Thanks for the answer @Bey! Quick question: how do we know that $x_n'$ defined above is the argmin of the function $g$ among the mesh points Commented Jan 20, 2022 at 23:35
• @WaitedLeastSquare great question, it's not. I need to make this case more clearly in my answer because I was implicitly assuming that eventually $x'_n$ becomes your $\text{argmax}_{x_i} g(x_i)$ for all $n>N$ Commented Jan 21, 2022 at 3:10
• @WaitedLeastSquare ok, fleshed out the key gap here that addresses the case when the unimodal region around the unique maximizer is not symmetric about the maximizer. Commented Jan 21, 2022 at 6:06
• I see now. Thanks so much for the answer @Bey! Commented Jan 21, 2022 at 7:15