$\underline{w}_{\hat{k}},\overline{w}_{\hat{\ell}}\in[0,1]$ from (S13). For
$1\leq a\leq b\leq n$, let $K^{a,b}$ be as in Step 2b, so that $K^{a,b}$ and
$-K^{a,b}$ are the cones of convex and concave sequences respectively based on
$x_{a},\dotsc,x_{b}$, and let $\xi^{a,b}=(\xi_{a},\xi_{a+1},\dotsc,\xi_{b})$.
Denote by $\check{\theta}^{a,b}:=\operatorname*{argmin}_{v\in
K^{a,b}}\|Y^{a,b}-v\|$ and
$\hat{\theta}^{a,b}:=\operatorname*{argmin}_{v\in-K^{a,b}}\|Y^{a,b}-v\|$ the
projections of $Y^{a,b}:=(Y_{a},Y_{a+1},\dotsc,Y_{b})$ onto $K^{a,b}$ and
$-K^{a,b}$ respectively. Let $\hat{a}:=\lfloor n\tilde{m}_{+}\rfloor+1$ and
$\check{b}:=\lceil nm_{0}\rceil-1$, so that
$x_{\hat{a}-1}\leq{\tilde{m}_{+}}<x_{\hat{a}}$ and $x_{\check{b}}<m_{0}\leq
x_{\check{b}+1}$, and define $\check{a},\hat{b}\in[n]$ by

$\check{a}:=\begin{cases}\,\hat{\ell}&\;\text{if
}\bigl{(}Y_{\hat{\ell}}-\tilde{f}_{n}(x_{\hat{\ell}})\bigr{)}^{2}\leq\xi_{\hat{\ell}}^{2}\\\
\,\hat{\ell}+1&\;\text{otherwise}\end{cases}\qquad\text{and}\qquad\hat{b}:=\begin{cases}\,\hat{k}&\;\text{if
}\bigl{(}Y_{\hat{k}}-\tilde{f}_{n}(x_{\hat{k}})\bigr{)}^{2}\leq\xi_{\hat{k}}^{2}\\\
\,\hat{k}-1&\;\text{otherwise}.\end{cases}$

Then $[x_{\check{a}},x_{\check{b}}]\subseteq\mathcal{I}_{-1}$ and
$[x_{\hat{a}},x_{\hat{b}}]\subseteq\mathcal{I}_{1}$, so
$\hat{\ell}\leq\check{a}\leq\check{b}\leq\hat{\ell}_{+}$ and
$\hat{k}_{-}\leq\hat{a}\leq\hat{b}\leq\hat{k}$. On the event $E_{n}^{+}$, the
function $\tilde{f}_{n}$ is convex on
$[x_{\check{a}},x_{\check{b}}]\subseteq\mathcal{I}_{-1}$ and concave on
$[x_{\hat{a}},x_{\hat{b}}]\subseteq\mathcal{I}_{1}$, so it follows from the
definitions above that

$\tilde{\Delta}_{n,A}=\sum_{i:x_{i}\in\mathcal{I}_{A}}w_{i}^{A}\bigl{\\{}\bigl{(}Y_{i}-\tilde{f}_{n}(x_{i})\bigr{)}^{2}-\xi_{i}^{2}\bigr{\\}}\geq\begin{cases}\,\|Y^{\check{a},\check{b}}-\check{\theta}^{\check{a},\check{b}}\|^{2}-\|\xi^{\check{a},\check{b}}\|^{2}\;&\text{for
}A=-1\\\
\,\|Y^{\hat{a},\hat{b}}-\hat{\theta}^{\hat{a},\hat{b}}\|^{2}-\|\xi^{\hat{a},\hat{b}}\|^{2}\;&\text{for
}A=1\end{cases}$ (S24)

on $E_{n}^{+}$. Next, we develop these bounds further using some orthogonality
properties and the oracle inequality stated as Bellec (2018, Theorem 4.3) once
again, taking into account the randomness of
$\check{a},\check{b},\hat{a},\hat{b}$. For $1\leq a<b\leq n$, let
$\mathbf{1}^{a,b},x^{a,b}\in\mathbb{R}^{b-a+1}$ and
$\theta^{a,b}=\bigl{(}f_{0}(x_{a}),f_{0}(x_{a+1})\dotsc,f_{0}(x_{b})\bigr{)}$
be as in Step 2a, and write
$A^{a,b}:=\operatorname{span}\\{\mathbf{1}^{a,b},x^{a,b}\\}$ for the subspace
of affine sequences of length $b-a+1$ based on $x_{a},x_{a+1},\dotsc,x_{b}$.
Then $\bar{\theta}^{a,b}:=\operatorname*{argmin}_{v\in
A^{a,b}}\|\theta^{a,b}-v\|$ satisfies
$\langle\theta^{a,b}-\bar{\theta}^{a,b},\theta^{a,b}-\theta\rangle=0$ for all
$\theta\in A^{a,b}$. Moreover, for all sufficiently small $\eta>0$, we have
$\check{\theta}^{a,b}\pm\eta(\check{\theta}^{a,b}-\bar{\theta}^{a,b})\in
K^{a,b}$ and
$\hat{\theta}^{a,b}\pm\eta(\hat{\theta}^{a,b}-\bar{\theta}^{a,b})\in-K^{a,b}$,
so it follows from (S3) or Lemma S17(a) that $\langle
Y^{a,b}-\check{\theta}^{a,b},\bar{\theta}^{a,b}-\check{\theta}^{a,b}\rangle=0$
and $\langle
Y^{a,b}-\hat{\theta}^{a,b},\bar{\theta}^{a,b}-\hat{\theta}^{a,b}\rangle=0$.
Therefore, writing $Y^{a,b}=\theta^{a,b}+\xi^{a,b}$, we deduce that

$\displaystyle\|Y^{a,b}-\check{\theta}^{a,b}\|^{2}-\|\xi^{a,b}\|^{2}$
$\displaystyle=\|Y^{a,b}-\bar{\theta}^{a,b}\|^{2}-\|\check{\theta}^{a,b}-\bar{\theta}^{a,b}\|^{2}-\|\xi^{a,b}\|^{2}$
$\displaystyle=\|\xi^{a,b}+(\theta^{a,b}-\bar{\theta}^{a,b})\|^{2}-\|\xi^{a,b}\|^{2}-\|\check{\theta}^{a,b}-\bar{\theta}^{a,b}\|^{2}$
$\displaystyle=2\,\langle\xi^{a,b},\theta^{a,b}-\bar{\theta}^{a,b}\rangle-\|\check{\theta}^{a,b}-\bar{\theta}^{a,b}\|^{2}+\|\theta^{a,b}-\bar{\theta}^{a,b}\|^{2}$
$\displaystyle\geq
2\,\langle\xi^{a,b},\theta^{a,b}-\bar{\theta}^{a,b}\rangle-2\,\|\check{\theta}^{a,b}-\theta^{a,b}\|^{2}-\|\theta^{a,b}-\bar{\theta}^{a,b}\|^{2},$
(S25)

where the final inequality follows since $\|z+z^{\prime}\|^{2}\leq
2(\|z\|^{2}+\|z^{\prime}\|^{2})$ for $z,z^{\prime}\in\mathbb{R}^{b-a+1}$.
Similarly,

$\|Y^{a,b}-\hat{\theta}^{a,b}\|^{2}-\|\xi^{a,b}\|^{2}\geq
2\,\langle\xi^{a,b},\theta^{a,b}-\bar{\theta}^{a,b}\rangle-2\,\|\hat{\theta}^{a,b}-\theta^{a,b}\|^{2}-\|\theta^{a,b}-\bar{\theta}^{a,b}\|^{2},$

and we now address each of the three terms on the right-hand side in turn.
Firstly, letting
$v^{a,b}:=(\theta^{a,b}-\bar{\theta}^{a,b})/\|\theta^{a,b}-\bar{\theta}^{a,b}\|$,
we have $\|v^{a,b}\|=1$, so $\langle\xi^{a,b},v^{a,b}\rangle$ is sub-Gaussian
with parameter 1. Therefore, for any $a,b$ with $1\leq a\leq b\leq n$ and for
every $c>0$, we have

$\mathbb{P}\bigl{(}\lvert\langle\xi^{a,b},\theta^{a,b}-\bar{\theta}^{a,b}\rangle\rvert\geq\sqrt{2c\log
n}\,\|\theta^{a,b}-\bar{\theta}^{a,b}\|\bigr{)}\leq 2n^{-c}.$ (S26)

Secondly, by taking $\mu=\theta^{a,b}$ and $u=\bar{\theta}^{a,b}\in A^{a,b}$
in Bellec (2018, Theorem 4.3) and applying this result to the closed, convex
cones $\pm K^{a,b}$, we find that

$\mathbb{P}\bigl{\\{}\|\check{\theta}^{a,b}-\theta^{a,b}\|^{2}\vee\|\hat{\theta}^{a,b}-\theta^{a,b}\|^{2}\geq\|\theta^{a,b}-\bar{\theta}^{a,b}\|^{2}+16\log\bigl{(}e(b-a+1)\bigr{)}+4c\log
n\bigr{\\}}\leq 2n^{-c}$ (S27)

for any $a,b$ with $1\leq a\leq b\leq n$ and for every $c>0$. Finally, we can
establish the following for each $n$ (without using the local smoothness
condition on $f_{0}$ in Assumption 2):

######  Lemma S7.

For $1\leq a\leq b\leq n$, define
$\breve{\theta}^{a,b}:=\bigl{(}\hat{f}_{n}^{m_{0}}(x_{a}),\hat{f}_{n}^{m_{0}}(x_{a+1}),\dotsc,\hat{f}_{n}^{m_{0}}(x_{b})\bigr{)}$,
and as in Step 2a, let $\Pi_{a,b}\,\xi^{a,b}:=\operatorname*{argmin}_{v\in
L^{a,b}}\|\xi^{a,b}-v\|$ be the projection of $\xi^{a,b}$ onto the subspace
$L^{a,b}=\operatorname{span}\\{\theta^{a,b},\mathbf{1}^{a,b},x^{a,b}\\}$. If
$x_{\tilde{k}}<x_{\tilde{k}^{\prime}}$ are successive knots of
$\hat{f}_{n}^{m_{0}}$, then

$\|\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\|\leq\max_{1\leq
a\leq b\leq n}\,\|\Pi_{a,b}\,\xi^{a,b}\|+2\max_{1\leq i\leq
n}\,\lvert\xi_{i}\rvert+2\max_{1\leq i\leq
n}\,\lvert(\hat{f}_{n}^{m_{0}}-f_{0})(x_{i})\rvert=:\Xi.$

At the start of Step 3, $x_{\hat{\ell}},x_{\hat{\ell}_{+}}$ and
$x_{\hat{k}_{-}},x_{\hat{k}}$ were defined to be pairs of successive knots of
$\hat{f}_{n}^{m_{0}}$. Therefore, since
$\hat{\ell}\leq\check{a}\leq\check{b}\leq\hat{\ell}_{+}$ and
$\bigl{(}\breve{\theta}_{i}^{\hat{\ell},\hat{\ell}_{+}}(x_{\check{a}}),\dotsc,\breve{\theta}_{i}^{\hat{\ell},\hat{\ell}_{+}}(x_{\check{b}})\bigr{)}\in
A_{\check{a},\check{b}}$, it follows that

$\|\theta^{\check{a},\check{b}}-\bar{\theta}^{\check{a},\check{b}}\|^{2}=\min_{\,\theta\in
A_{\check{a},\check{b}}}\|\theta^{\check{a},\check{b}}-\theta\|^{2}\leq\sum_{i=\check{a}}^{\check{b}}\,\bigl{(}\theta_{i}^{\hat{\ell},\hat{\ell}_{+}}-\breve{\theta}_{i}^{\hat{\ell},\hat{\ell}_{+}}\bigr{)}^{2}\leq\|\theta^{\hat{\ell},\hat{\ell}_{+}}-\breve{\theta}^{\hat{\ell},\hat{\ell}_{+}}\|^{2}\leq\Xi^{2}.$

Similarly,
$\|\theta^{\hat{a},\hat{b}}-\bar{\theta}^{\hat{a},\hat{b}}\|\leq\|\theta^{\hat{k}_{-},\hat{k}}-\breve{\theta}^{\hat{k}_{-},\hat{k}}\|\leq\Xi$.
Now recall the tail bound (S19) for $\|\Pi_{a,b}\,\xi^{a,b}\|$, which applies
to all $1\leq a\leq b\leq n$, and our Assumption 2 that
$\xi_{1},\dotsc,\xi_{n}$ are sub-Gaussian random variables with parameter 1.
Applying a union bound, we see that

$\displaystyle\mathbb{P}\,\Bigl{(}\max_{1\leq a\leq b\leq
n}\,\|\Pi_{a,b}\,\xi^{a,b}\|+2\max_{1\leq i\leq n}\,\lvert\xi_{i}\rvert\geq
6\sqrt{c\log n}\Bigr{)}$ $\displaystyle\leq\mathbb{P}\,\Bigl{(}\max_{1\leq
a\leq b\leq n}\,\|\Pi_{a,b}\,\xi^{a,b}\|\geq\sqrt{6c\log n}\Bigr{)}$
$\displaystyle+\mathbb{P}\,\Bigl{(}\max_{1\leq i\leq
n}\,\lvert\xi_{i}\rvert\geq\sqrt{2c\log n}\Bigr{)}\leq 6n^{2-c}+2n^{1-c}$

for every $c>0$. Since
$\max_{x\in[0,1]}\,\lvert(\hat{f}_{n}^{m_{0}}-f_{0})(x)\rvert=o_{p}(1)$ by
Proposition 2(c), it follows from Lemma S7 that

$\mathbb{P}\bigl{(}\|\theta^{\check{a},\check{b}}-\bar{\theta}^{\check{a},\check{b}}\|\vee\|\theta^{\hat{a},\hat{b}}-\bar{\theta}^{\hat{a},\hat{b}}\|\geq
6\sqrt{c\log n}+\eta\bigr{)}\leq\mathbb{P}\bigl{(}\Xi\geq 6\sqrt{c\log
n}+\eta\bigr{)}\rightarrow 0$ (S28)

as $n\rightarrow\infty$, for any $c>2$ and $\eta>0$. We now combine (S28) with
(S26) and (S27), where we take $c=3\;(>2)$ and apply a union bound to handle
all pairs $(a,b)$ with $1\leq a\leq b\leq n$. Together with (S24) and (S25),
these imply that there exist a universal constant $\rho^{\prime}>0$ and events
$(E_{n4})$ with $\mathbb{P}(E_{n4}^{c})\to 0$ such that

$\displaystyle\tilde{\Delta}_{n,-1}\geq\|Y^{\check{a},\check{b}}-\check{\theta}^{\check{a},\check{b}}\|^{2}-\|\xi^{\check{a},\check{b}}\|^{2}$
$\displaystyle\geq
2\,\langle\xi^{\check{a},\check{b}},\theta^{\check{a},\check{b}}-\bar{\theta}^{\check{a},\check{b}}\rangle-2\,\|\check{\theta}^{\check{a},\check{b}}-\theta^{\check{a},\check{b}}\|^{2}-\|\theta^{\check{a},\check{b}}-\bar{\theta}^{\check{a},\check{b}}\|^{2}$
$\displaystyle\geq-2\sqrt{2\log
n}\,\|\theta^{\check{a},\check{b}}-\bar{\theta}^{\check{a},\check{b}}\|-56\log(en)-3\,\|\theta^{\check{a},\check{b}}-\bar{\theta}^{\check{a},\check{b}}\|^{2}$
$\displaystyle\geq-\rho^{\prime}\log(en)$ (S29)

and

$\displaystyle\tilde{\Delta}_{n,1}\geq\|Y^{\hat{a},\hat{b}}-\hat{\theta}^{\hat{a},\hat{b}}\|^{2}-\|\xi^{\hat{a},\hat{b}}\|^{2}$
$\displaystyle\geq
2\,\langle\xi^{\hat{a},\hat{b}},\theta^{\hat{a},\hat{b}}-\bar{\theta}^{\hat{a},\hat{b}}\rangle-2\,\|\hat{\theta}^{\hat{a},\hat{b}}-\theta^{\hat{a},\hat{b}}\|^{2}-\|\theta^{\hat{a},\hat{b}}-\bar{\theta}^{\hat{a},\hat{b}}\|^{2}$
$\displaystyle\geq-2\sqrt{2\log
n}\,\|\theta^{\hat{a},\hat{b}}-\bar{\theta}^{\hat{a},\hat{b}}\|-56\log(en)-3\,\|\theta^{\hat{a},\hat{b}}-\bar{\theta}^{\hat{a},\hat{b}}\|^{2}$
$\displaystyle\geq-\rho^{\prime}\log(en)$ (S30)

on $E_{n}^{+}\cap E_{n1}\cap E_{n4}$, for each $n$.

Having carried out Steps 1–3 above, we finally define the events
$\Omega_{n}:=\bigcap_{\,j=1}^{\,4}E_{nj}$ for $n\in\mathbb{N}$, which satisfy
$\mathbb{P}(\Omega_{n}^{c})\to 0$. We conclude from (S14), (S21), (S23), (S29)
and (S30) that

$\displaystyle\Delta_{n}=S_{n}(\tilde{f}_{n})-S_{n}(\hat{f}_{n}^{m_{0}})$
$\displaystyle\geq\sum_{A=-1}^{1}\tilde{\Delta}_{n,A}=\Lambda_{n2}+\Lambda_{n1}+\Lambda_{n3}+\tilde{\Delta}_{n,-1}+\tilde{\Delta}_{n,1}$
(S31) $\displaystyle\geq 2^{-1}\rho_{\alpha}B^{2}\,(C_{n}/4)^{2\alpha+1}\log
n-2\,(28\log n)-2\rho^{\prime}\log(en)>0$

on $E_{n}^{+}\cap\Omega_{n}$, for all sufficiently large $n$. As mentioned at
the start of the proof, this means that
$\mathbb{P}(E_{n}^{+})\leq\mathbb{P}(E_{n}^{+}\cap\Omega_{n})+\mathbb{P}(\Omega_{n}^{c})\to
0$, as desired. ∎

###### Proof of Proposition 8.

Fix $\tau\in(0,1)$. First, we consider the case where
$f_{0}\in\mathcal{F}^{m_{0}}$ satisfies Assumption 2 for some $\alpha>1$. By
suitably perturbing $f_{0}$, we construct for each (sufficiently large) $n$ a
function $f_{\delta_{n}}\in\mathcal{F}(f_{0},\tau/\sqrt{n})$ that has a unique
inflection point at distance of order
$\delta_{n}\asymp(\tau^{2}/n)^{1/(2\alpha+1)}$ from $m_{0}$. The local
asymptotic minimax lower bound (14) is then obtained by applying (the proof
of) Le Cam’s two-point lemma to $\\{f_{0},f_{\delta_{n}}\\}$. We will write
$d_{\mathrm{TV}}(P,Q)$ for the total variation distance between probability
measures $P,Q$.

To this end, for each $\delta\in(0,1-m_{0})$, let $u(m_{0}+\delta)$ be a
subgradient of the concave function $\left.f_{0}\right|_{[m_{0},1]}$ at
$m_{0}+\delta$, so that $u(m_{0}+\delta)<f_{0}^{\prime}(m_{0})$ and

$f_{0}(x)\leq
f_{0}(m_{0}+\delta)+u(m_{0}+\delta)(x-m_{0}-\delta)=:f_{1,\delta}(x)\quad\text{for
all }x\in[m_{0},1].$

Define

$f_{2,\delta}(x):=f_{0}(m_{0})+f_{0}^{\prime}(m_{0})(x-m_{0})+\delta(x-m_{0})^{\alpha}\quad\text{for
}x\in[m_{0},1],$

so that $f_{2,\delta}$ is strictly convex on $[m_{0},1]$ (thanks to the
inclusion of the final term $\delta(x-m_{0})^{\alpha}$) and
$f_{2,\delta}(x)>f_{0}(m_{0})+f_{0}^{\prime}(m_{0})(x-m_{0})\geq f_{0}(x)$ for
all $x\in(m_{0},1]$. Note in particular that
$f_{1,\delta}(m_{0})>f_{0}(m_{0})=f_{2,\delta}(m_{0})$ and
$f_{1,\delta}(m_{0}+\delta)=f_{0}(m_{0}+\delta)<f_{2,\delta}(m_{0}+\delta)$.
Consequently, defining $f_{\delta}\colon[0,1]\to\mathbb{R}$ by

$f_{\delta}(x):=\begin{cases}f_{0}(x)\quad&x\in[0,m_{0}]\cup[m_{0}+\delta,1]\\\
f_{1,\delta}(x)\wedge f_{2,\delta}(x)&x\in(m_{0},m_{0}+\delta),\end{cases}$
(S32)

we deduce that there exists a unique $c_{\delta}\in(0,1)$ such that
$f_{\delta}=f_{2,\delta}$ on $[m_{0},m_{0}+\delta c_{\delta}]$ and
$f_{\delta}=f_{1,\delta}$ on $[m_{0}+\delta c_{\delta},m_{0}+\delta]$.
Moreover, since $f_{2,\delta}$ is strictly convex and
$f_{1,\delta}(m_{0}+\delta
c_{\delta})>f_{0}^{\prime}(m_{0})>u(m_{0}+\delta)=f_{2,\delta}(m_{0}+\delta
c_{\delta})$, it follows that $f_{\delta}$ lies in $\mathcal{F}$ and has a
unique inflection point at $m_{\delta}:=m_{0}+\delta c_{\delta}$.

Now for any sequence $(\delta_{n})$ with $\delta_{n}\to 0$ and
$n\delta_{n}\to\infty$, it follows from Assumption 2 and some elementary
analytic arguments that the following holds as $n\to\infty$; see Section S5.2.

######  Lemma S8.

For $\alpha>1$, we have
$\|f_{\delta_{n}}-f_{0}\|_{n}^{2}=\bigl{(}1+o(1)\bigr{)}\int_{0}^{1}\,(f_{\delta_{n}}-f_{0})^{2}=\bigl{(}1+o(1)\bigr{)}C_{\alpha}B^{2}\delta_{n}^{2\alpha+1}$
and $c_{\delta_{n}}=\bigl{(}1+o(1)\bigr{)}(1-\alpha^{-1})$ as $n\to\infty$,
where
$C_{\alpha}:=\int_{0}^{1}\,\bigl{\\{}t^{\alpha}-\bigl{(}1-(1-t)\alpha\bigr{)}^{+}\bigr{\\}}^{2}\,dt>0$.

Thus, setting
$\delta_{n}:=\bigl{(}1+o(1)\bigr{)}(2C_{\alpha}B^{2}n\tau^{-2})^{-1/(2\alpha+1)}$,
we deduce that $f_{\delta_{n}}\in\mathcal{F}(f_{0},\tau/\sqrt{n})$ for all
sufficiently large $n$. For all such $n$, write $P_{0,n}^{Y},P_{1,n}^{Y}$ for
the distributions of $(Y_{n1},\dotsc,Y_{nn})$ under the data generating
mechanisms $Y_{ni}=f_{0}(x_{ni})+\xi_{ni}$ and
$Y_{ni}=f_{\delta_{n}}(x_{ni})+\xi_{ni}$ respectively. Since
$\xi_{n1},\dotsc,\xi_{nn}\overset{\mathrm{iid}}{\sim}N(0,1)$ by assumption, we
have by Pinsker’s inequality that
$d_{\mathrm{TV}}^{2}(P_{0,n}^{Y},P_{1,n}^{Y})\leq\operatorname{KL}(P_{0,n}^{Y},P_{1,n}^{Y})/2=n\|f_{\delta_{n}}-f_{0}\|_{n}^{2}/2$,
so for all sufficiently large $n$, the minimax risk can be bounded from below
using Le Cam’s two point lemma:

$\displaystyle\inf_{\breve{m}_{n}}\,\sup_{f\in\mathcal{F}(f_{0},\tau/\sqrt{n})}\mathbb{E}_{f}\bigl{(}d(\breve{m}_{n},\mathcal{I}_{f})\bigr{)}$
$\displaystyle\geq\frac{1}{2}\,\inf_{\breve{m}_{n}}\,\\{\mathbb{E}_{f_{0}}(\lvert\breve{m}_{n}-m_{0}\rvert)+\mathbb{E}_{f_{\delta_{n}}}(\lvert\breve{m}_{n}-m_{\delta_{n}}\rvert)\\}$
$\displaystyle\geq\frac{\lvert
m_{\delta_{n}}-m_{0}\rvert}{2}\,\bigl{(}1-d_{\mathrm{TV}}(P_{0,n}^{Y},P_{1,n}^{Y})\bigr{)}$
$\displaystyle\geq\bigl{(}1+o(1)\bigr{)}\,\frac{\alpha-1}{2\alpha}\biggl{(}\frac{2C_{\alpha}B^{2}n}{\tau^{2}}\biggr{)}^{-1/(2\alpha+1)}\biggl{(}1-\frac{\tau}{2^{1/2}}\biggr{)}.$

This yields (14), as desired.

In the case $\alpha\in(0,1)$, we instead define
$f_{\delta}\colon[0,1]\to\mathbb{R}$ for $\delta\in(0,1-m_{0})$ by

$f_{\delta}(x)=\begin{cases}f_{0}(x)\wedge\bigl{\\{}f_{0}(m_{0})+(1-\delta)\frac{f_{0}(m_{0}+\delta)-f_{0}(m_{0})}{\delta}(x-m_{0})\bigr{\\}}\quad&\text{for
}x\in[0,m_{0}]\\\
f_{0}(m_{0})+\bigl{(}f_{0}(m_{0}+\delta)-f_{0}(m_{0})\bigr{)}\bigl{\\{}(1-\delta)\frac{x-m_{0}}{\delta}+\delta\bigl{(}\frac{x-m_{0}}{\delta}\bigr{)}^{2}\bigr{\\}}&\text{for
}x\in(m_{0},m_{0}+\delta)\\\ f_{0}(x)\quad&\text{for
}x\in[m_{0}+\delta,1],\end{cases}$

so that $f_{\delta}\in\mathcal{F}$ and $m_{0}+\delta$ is the unique inflection
point of $f_{\delta}$ (since $x\mapsto(x-m_{0})^{2}$ is strictly convex). Then
based on similar (and slightly simpler) calculations to those for Lemma S8, we
can apply Le Cam’s two point lemma as above to obtain the conclusion of
Proposition 8 when $\alpha\in(0,1)$. ∎

##  S3 Projections onto classes of S-shaped functions

The purpose of this section is to introduce the general projection framework
that underpins our estimation methodology, and to study the continuity
properties of this projection. This allows us to deduce not only the
consistency guarantees for our estimator, as stated in Proposition 2, but also
to ensure its robustness to model misspecification; see Proposition S16 below.

For a finite Borel measure $\nu$ on $[0,1]$, we say that
$x\in\operatorname{supp}\nu$ is an _isolated point_ of
$\operatorname{supp}\nu$ if there exists an open neighbourhood $U$ of $x$ such
that $U\cap\operatorname{supp}\nu=\\{x\\}$. Denote by
$\operatorname{csupp}\nu:=\operatorname{conv}(\operatorname{supp}\nu)$ the
_convex support_ of $\nu$, which is the smallest closed, convex set $C$ with
$\nu(C^{c})=0$. For Lebesgue measurable functions
$f,g\colon[0,1]\to\mathbb{R}\cup\\{\pm\infty\\}$, we write $f\sim_{\nu}g$ if
$f=g$ $\nu$-almost everywhere, and noting that $\sim_{\nu}$ defines an
equivalence relation on the set of such measurable functions, we denote by
$[f]_{\nu}$ the $\sim_{\nu}$ equivalence class of $f$.

For $q\in[1,\infty)$, we write $L^{q}(\nu)\equiv L^{q}([0,1],\nu)$ for the
space of Lebesgue measurable functions
$f\colon[0,1]\to\mathbb{R}\cup\\{\pm\infty\\}$ such that
$\|f\|_{L^{q}(\nu)}:=\bigl{(}\int_{[0,1]}\,\lvert
f\rvert^{q}\,d\nu\bigr{)}^{1/q}<\infty$, and define
$\mathcal{L}^{q}(\nu)\equiv\mathcal{L}^{q}([0,1],\nu):=\\{[f]_{\nu}:f\in
L^{q}(\nu)\\}$. When $q=2$, recall that the bilinear form
$\langle\cdot\,,\cdot\rangle_{L^{2}(\nu)}$ on $L^{2}(\nu)$ defined by $\langle
f,g\rangle_{L^{2}(\nu)}:=\int_{[0,1]}fg\,d\nu$ induces a Hilbert space
structure on $\mathcal{L}^{2}(\nu)$.

For a Borel set $A\subseteq[0,1]$ and a Lebesgue measurable function
$f\colon[0,1]\to\mathbb{R}$, let $\|f\|_{L^{\infty}(A,\nu)}:=\inf\\{B\geq
0:\lvert f(x)\rvert\leq B\text{ for }\nu\text{-almost every }x\in A\\}$, where
we adopt the convention that $\inf\emptyset=\infty$. A function
$f\in[0,1]\to\mathbb{R}$ is said to be _locally bounded_ at $x\in[0,1]$ if
there exists $\varepsilon>0$ such that $f$ is bounded on
$(x-\varepsilon,x+\varepsilon)\cap[0,1]$.

The following proposition provides some basic structural properties of the
classes $\mathcal{F}^{m}$. See Section S6 in the supplementary material for
the proofs of all results in this subsection.

######  Proposition S9.

If $m\in[0,1]$ and $\nu$ is a Borel probability measure on $[0,1]$, then
$\mathcal{F}_{\nu}^{m}:=\\{[f]_{\nu}:f\in\mathcal{F}^{m}\\}$ is a convex cone
in $\mathcal{L}^{2}(\nu)$. Moreover, the following hold for all $m\in[0,1]$:

  1. (a)

$\\{[f]_{\nu}:f\in\mathcal{F}^{m}\text{ is Lipschitz}\\}$ is dense in
$\mathcal{F}_{\nu}^{m}$ (with respect to the topology induced by
$\|{\cdot}\|_{L^{2}(\nu)}$).

  2. (b)

Let $\tilde{m}:=\operatorname*{argmin}_{x\in\operatorname{csupp}\nu}\,\lvert
x-m\rvert$. Then $\mathcal{F}_{\nu}^{m}$ is a dense subset of
$\mathcal{F}_{\nu}^{\tilde{m}}$.

  3. (c)

$\mathcal{F}_{\nu}^{m}$ is closed in $\mathcal{L}^{2}(\nu)$ if and only if at
least one of the following conditions is satisfied:

    1. (i)

$\nu([0,m])>0$ and $\nu([m,1])>0$;

    2. (ii)

$\max(\operatorname{supp}\nu)<m$ and $\max(\operatorname{supp}\nu)$ is an
isolated point of $\operatorname{supp}\nu$;

    3. (iii)

$\min(\operatorname{supp}\nu)>m$ and $\min(\operatorname{supp}\nu)$ is an
isolated point of $\operatorname{supp}\nu$.

  4. (d)

Suppose that none of the conditions (i)–(iii) hold, and let $E_{\nu}$ be the
interval containing all
$x\in(\min(\operatorname{supp}\nu),\max(\operatorname{supp}\nu))$ as well as
those $x\in\\{\min(\operatorname{supp}\nu),\max(\operatorname{supp}\nu)\\}$
for which $\nu(\\{x\\})>0$. Denote by $\operatorname{Cl}\mathcal{F}_{\nu}^{m}$
the closure of $\mathcal{F}_{\nu}^{m}$ in $\mathcal{L}^{2}(\nu)$. Then

$\operatorname{Cl}\mathcal{F}_{\nu}^{m}=\begin{cases}\,\\{[f]_{\nu}:f\in
L^{2}(\nu)\text{ and}\left.f\right|_{E_{\nu}}\\!\text{ is convex and
increasing}\\}\;&\text{if }\max(\operatorname{supp}\nu)\leq m\\\
\,\\{[f]_{\nu}:f\in L^{2}(\nu)\text{ and}\left.f\right|_{E_{\nu}}\\!\text{ is
concave and increasing}\\}\;&\text{if }\min(\operatorname{supp}\nu)\geq
m.\end{cases}$

For example, if $\nu$ is Lebesgue measure on $[0,1]$, then
$\mathcal{F}_{\nu}^{m}$ is a closed subset of $\mathcal{L}^{2}(\nu)$ if and
only if $m\in(0,1)$.

Let $\mathcal{P}$ be the class of probability distributions $P$ on
$[0,1]\times\mathbb{R}$ such that
$\int_{[0,1]\times\mathbb{R}}\,y^{2}\,dP(x,y)<\infty$. For $P\in\mathcal{P}$,
denote by $P^{X}$ the marginal distribution on $[0,1]$ induced by the
coordinate projection $(x,y)\mapsto x$, and for $f\in L^{2}(P^{X})$, define

$L(f,P):=\int_{[0,1]\times\mathbb{R}}\,\bigl{(}y-f(x)\bigr{)}^{2}\,dP(x,y).$
(S33)

Introducing $(X,Y)\sim P$, we say that $f_{P}\colon[0,1]\to\mathbb{R}$ is a
_regression function for $P$_ if $f_{P}(X)$ is a version of
$\mathbb{E}(Y|\,X)$. Then $f_{P}\in L^{2}(P^{X})$ and

$\displaystyle L(f,P)=\mathbb{E}\bigl{(}\\{Y-f(X)\\}^{2}\bigr{)}$
$\displaystyle=\mathbb{E}\bigl{(}\\{Y-f_{P}(X)\\}^{2}\bigr{)}+\mathbb{E}\bigl{(}\\{f_{P}(X)-f(X)\\}^{2}\bigr{)}$
$\displaystyle=\mathbb{E}\bigl{(}\\{Y-f_{P}(X)\\}^{2}\bigr{)}+\|f_{P}-f\|_{L^{2}(P^{X})}^{2}$
(S34)

for all $f\in L^{2}(P^{X})$. Note that by (S34), we have $L(f_{n},P)\to
L(f,P)$ whenever $\|f_{n}-f\|_{L^{2}(P^{X})}\to 0$. Thus, for each
$m\in[0,1]$, it follows from Proposition S9(a) that
$L_{m}^{*}(P):=\inf_{f\in\mathcal{F}^{m}}L(f,P)$ is the infimum of $f\mapsto
L(f,P)$ over all Lipschitz $f\in\mathcal{F}^{m}$.

For $\delta\geq 0$, let
$\psi_{m}^{\delta}(P):=\\{f\in\mathcal{F}^{m}:L(f,P)\leq
L_{m}^{*}(P)+\delta\\}$, which is a non-empty set when $\delta>0$. In
Corollary S10(d) below, we give sufficient conditions for $\psi_{m}^{0}(P)$ to
be non-empty, i.e. for $f\mapsto L(f,P)$ to attain its infimum $L_{m}^{*}(P)$
over $\mathcal{F}^{m}$.

Recall that if $E$ is a closed, convex subset of a Hilbert space
$(H,\|{\cdot}\|)$, then for each $x\in H$, there is a unique $y\in E$ such
that $\|x-y\|=\min_{w\in E}\|x-w\|$, namely the _projection_ of $x$ onto $E$
(e.g. Rudin, 1987, Theorem 4.10). In view of this and Proposition S9, we can
now define projection maps
$\psi_{m}^{*}\colon\mathcal{P}\to\mathcal{L}^{2}(P^{X})$ associated with the
convex function classes $\mathcal{F}^{m}$.

######  Corollary S10.

Fix $P\in\mathcal{P}$ and denote by $P^{X}$ the corresponding marginal
distribution on $[0,1]$. For each $m\in[0,1]$, let $\psi_{m}^{*}(P)$ be the
collection of all $f\colon[0,1]\to\mathbb{R}$ such that
$[f]_{P^{X}}\in\operatorname{Cl}\mathcal{F}_{P^{X}}^{m}\subseteq\mathcal{L}^{2}(P^{X})$
and $L(f,P)=L_{m}^{*}(P)$. Then the following hold for all $m\in[0,1]$:

  1. (a)

$\psi_{m}^{*}(P)$ is a non-empty $\sim_{P^{X}}$ equivalence class containing
$\psi_{m}^{0}(P)$.

  2. (b)

$\psi_{m}^{*}(P)\in\mathcal{L}^{2}(P^{X})$, and if
$\psi_{m}^{0}(P)\neq\emptyset$, then
$\psi_{m}^{*}(P)\in\mathcal{L}^{q}(P^{X})$ for all $q\in[1,\infty)$.

  3. (c)

Defining
$\tilde{m}=\operatorname*{argmin}_{x\in\operatorname{csupp}P^{X}}\,\lvert
x-m\rvert$ as in Proposition S9(b), we have
$\psi_{m}^{*}(P)=\psi_{\tilde{m}}^{*}(P)$ and
$L_{m}^{*}(P)=L_{\tilde{m}}^{*}(P)$. If $\psi_{m}^{0}(P)$ is non-empty, then
so is $\psi_{\tilde{m}}^{0}(P)$.

  4. (d)

$\psi_{m}^{0}(P)=\psi_{m}^{*}(P)\cap\mathcal{F}^{m}$ is non-empty if at least
one of the following holds:

    1. (i)

$\mathcal{F}_{P^{X}}^{m}$ is a closed subset of $\mathcal{L}^{2}(P^{X})$, i.e.
if $m,P^{X}$ satisfy at least one of the conditions (i)–(iii) in Proposition
S9(c);

    2. (ii)

$m=\tilde{m}$ and $P$ has a regression function $f_{P}$ that is locally
bounded at $\tilde{m}$.

  5. (e)

All functions in $\psi_{m}^{0}(P)$ agree on
$(\operatorname{supp}P^{X})\setminus\\{m\\}$. If in addition
$P^{X}(\\{m\\})>0$ or all elements of $\psi_{m}^{0}(P)$ are continuous (at
$m$), then they all agree on $\operatorname{supp}P^{X}$.

  6. (f)

When $m\in\operatorname{supp}P^{X}$ and $P^{X}(\\{m\\})=0$, all elements of
$\psi_{m}^{0}(P)$ agree on $\operatorname{supp}P^{X}$ if and only if all
elements of $\psi_{m}^{0}(P)$ are continuous (at $m$).

  7. (g)

Suppose that at least one element of $\psi_{m}^{0}(P)$ is continuous (at $m$),
and moreover that $\operatorname{supp}P^{X}$ has non-empty intersection with
both $(m-\varepsilon,m)$ and $(m,m+\varepsilon)$ for all $\varepsilon>0$. Then
all elements of $\psi_{m}^{0}(P)$ are continuous (at $m$) and agree on
$\operatorname{supp}P^{X}$.

######  Remark S11.

If $m\in\operatorname{Int}(\operatorname{csupp}P^{X})$, then $m,P^{X}$ satisfy
condition (i) in Proposition S9(c), so $\psi_{m}^{0}(P)\neq\emptyset$ in this
case by (d) above. Moreover, in condition (ii) in part (d), we need only
insist that $f_{P}$ is bounded on
$\operatorname{Int}(\operatorname{csupp}P^{X})\cap(\tilde{m}-\varepsilon,\tilde{m}+\varepsilon)$
for some $\varepsilon>0$; indeed, setting
$\tilde{z}:=\operatorname*{argmin}_{x\in\operatorname{csupp}P^{X}}\,\lvert
z-x\rvert$ for $z\in[0,1]$, we can instead work with $\tilde{f}_{P}\colon
z\mapsto f_{P}(\tilde{z})$, which is another regression function for $P$ that
is bounded on $(\tilde{m}-\varepsilon,\tilde{m}+\varepsilon)$. As for (e, f,
g), recall that all elements of $\mathcal{F}^{m}$ are continuous on
$[0,1]\setminus\\{m\\}$, so being continuous on $[0,1]$ is equivalent to being
continuous at $m$ for all such functions.

Next, we investigate the continuity of the maps $(m,P)\mapsto L_{m}^{*}(P)$
and $(m,P)\mapsto\psi_{m}^{*}(P)$ with respect to a suitable topology on
$[0,1]\times\mathcal{P}$. Recall that for $q\in[1,\infty)$ and
$d\in\mathbb{N}$, the _$q$ -Wasserstein distance_ between probability measures
$P_{1},P_{2}$ on $\mathbb{R}^{d}$ is defined by
$W_{q}(P_{1},P_{2}):=\inf_{(X,Y)}\mathbb{E}(\|X-Y\|^{q})^{1/q}$, where the
infimum is taken over all pairs of random variables $X,Y$ defined on a common
probability space with $X\sim P_{1}$ and $Y\sim P_{2}$. It is a standard fact
that $W_{q}(P_{n},P)\to 0$ if and only if $P_{n}\overset{d}{\to}P$ and
$\int_{\mathbb{R}^{d}}\|w\|^{q}\,dP_{n}(w)\to\int_{\mathbb{R}^{d}}\|w\|^{q}\,dP(w)$.

In the result below, we equip $[0,1]\times\mathcal{P}$ with the product
topology induced by the Euclidean metric on $[0,1]$ and the $W_{2}$ metric on
$\mathcal{P}$.

######  Proposition S12.

Let $(m_{n})_{n=1}^{\infty}$ be a sequence in $[0,1]$ that converges to some
$m_{0}\in[0,1]$. Fix $P\in\mathcal{P}$ and the corresponding marginal
distribution $P^{X}$ on $[0,1]$. Let
$\tilde{m}_{0}:=\operatorname*{argmin}_{x\in\operatorname{csupp}P^{X}}\,\lvert
x-m_{0}\rvert$. Let $(P_{n})_{n=1}^{\infty}$ be any sequence of probability
measures in $\mathcal{P}$ such that $W_{2}(P_{n},P)\to 0$. Then

  1. (a)

$\limsup_{n\to\infty}L_{m_{n}}^{*}(P_{n})\leq L_{m_{0}}^{*}(P)$;

  2. (b)

$\liminf_{n\to\infty}L_{m_{n}}^{*}(P_{n})\geq L_{m_{0}}^{*}(P)$ provided that
$P^{X}(\\{\tilde{m}_{0}\\})=0$;

  3. (c)

$\lim_{n\to\infty}L_{m_{n}}^{*}(P)=L_{m_{0}}^{*}(P)$.

Thus, for all $Q\in\mathcal{P}$, the map $m\mapsto L_{m}^{*}(Q)$ is continuous
on $[0,1]$ and $L^{*}(Q):=\min_{m\in[0,1]}L_{m}^{*}(Q)$ is well-defined.
Moreover,

  1. (d)

$\sup_{m\in[0,1]}\,\lvert L_{m}^{*}(P_{n})-L_{m}^{*}(P)\rvert\to 0$ and
$L^{*}(P_{n})\to L^{*}(P)$ as $n\to\infty$ if $P^{X}(\\{m\\})=0$ for all
$m\in[0,1]$.

For $\delta\geq 0$ and $Q\in\mathcal{P}$, define
$\mathcal{I}^{\delta}(Q):=\\{m\in[0,1]:L_{m}^{*}(Q)\leq L^{*}(Q)+\delta\\}$
and
$\mathcal{I}^{*}(Q):=\mathcal{I}^{0}(Q)=\operatorname*{argmin}_{m\in[0,1]}L_{m}^{*}(Q)$.
Let $(\delta_{n})$ be any deterministic, non-negative sequence such that
$\delta_{n}\to 0$. Then

  1. (e)

$\sup_{m_{n}^{\prime}\in\mathcal{I}^{\delta_{n}}(P_{n})}\inf_{m^{*}\in\mathcal{I}^{*}(P)}\,\lvert
m_{n}^{\prime}-m^{*}\rvert\to 0$ as $n\to\infty$ provided that
$P^{X}(\\{m\\})=0$ for all $m\in[0,1]$.

If $P^{X}(\\{\tilde{m}_{0}\\})=0$, then the following hold as $n\to\infty$:

  1. (f)

$\sup_{f_{n}\in\psi_{m_{n}}^{\delta_{n}}(P_{n})}\sup_{f^{*}\in\psi_{m_{0}}^{*}(P)}\|f_{n}-f^{*}\|_{L^{\infty}(A,P^{X})}\to
0$ for all closed sets
$A\subseteq(\operatorname{supp}P^{X})\setminus\\{\tilde{m}_{0}\\}$;

  2. (g)

If $\psi_{\tilde{m}_{0}}^{0}(P)\neq\emptyset$, then
$\sup_{f_{n}\in\psi_{m_{n}}^{\delta_{n}}(P_{n})}\sup_{f^{*}\in\psi_{\tilde{m}_{0}}^{0}(P)}\sup_{x\in
A}\,\lvert f_{n}(x)-f^{*}(x)\rvert\to 0$ for all closed sets
$A\subseteq(\operatorname{supp}P^{X})\setminus\\{\tilde{m}_{0}\\}$.

Suppose further that $m_{0}\in\operatorname{Int}(\operatorname{csupp}P^{X})$
and $P^{X}(\\{m_{0}\\})=0$. Then $\psi_{m_{0}}^{0}(P)\neq\emptyset$ and the
following hold as $n\to\infty$:

  1. (h)

$\sup_{f_{n}\in\psi_{m_{n}}^{\delta_{n}}(P_{n})}\sup_{f^{*}\in\psi_{m_{0}}^{*}(P)}\|f_{n}-f^{*}\|_{L^{q}(P^{X})}\to
0$ for all $q\in[1,\infty)$;

  2. (i)

$\sup_{f_{n}\in\psi_{m_{n}}^{\delta_{n}}(P_{n})}\sup_{f^{*}\in\psi_{m_{0}}^{0}(P)}\sup_{x\in\operatorname{supp}P^{X}}\lvert(f_{n}-f^{*})(x)\rvert\to
0$ provided that all elements of $\psi_{m_{0}}^{0}(P)$ agree on
$\operatorname{supp}P^{X}$.

######  Remark S13.

Since $[0,1]$ is compact, the conclusion of (e) is equivalent to the
following: for any sequence $(m_{n}^{\prime})$ with
$m_{n}^{\prime}\in\mathcal{I}^{\delta_{n}}(P_{n})$ for all $n$, every
subsequence of $(m_{n}^{\prime})$ has a further subsequence that converges to
an element of $\mathcal{I}^{*}(P)$. When
$m_{0}\notin\operatorname{supp}P^{X}$, the conclusion of (i) is implied by
(g). If instead $m_{0}\in\operatorname{supp}P^{X}$, then by Corollary S10(f),
the condition in (i) is satisfied if and only if all elements of
$\psi_{m_{0}}^{0}(P)$ are continuous, and Corollary S10(g) provides a
sufficient criterion for this.

Recall that $\mathcal{F}=\bigcup_{m\in[0,1]}\mathcal{F}^{m}$ denotes the set
of S-shaped functions on $[0,1]$. For $P\in\mathcal{P}$ and $\delta\geq 0$,
define $\psi^{\delta}(P):=\\{f\in\mathcal{F}:L(f,P)\leq L^{*}(P)+\delta\\}$,
which is non-empty when $\delta>0$, and note that
$\psi^{\delta}(P)\subseteq\bigcup_{m\in\mathcal{I}^{\delta}(P)}\psi_{m}^{\delta}(P)$.
Also, let
$\psi^{*}(P):=\bigcup_{m\in\mathcal{I}^{*}(P)}\psi_{m}^{*}(P)\supseteq\bigcup_{m\in\mathcal{I}^{*}(P)}\psi_{m}^{0}(P)=\psi^{0}(P)$.

######  Corollary S14.

Fix $P\in\mathcal{P}$ and the corresponding marginal distribution $P^{X}$ on
$[0,1]$. Then

  1. (a)

$\psi^{0}(P)\neq\emptyset$ if and only if $\psi_{m}^{0}(P)\neq\emptyset$ for
some $m\in\mathcal{I}^{*}(P)\cap\operatorname{csupp}P^{X}$, which is
guaranteed if at least one of the following holds:

    1. (i)

$\mathcal{I}^{*}(P)\cap\operatorname{Int}(\operatorname{csupp}P^{X})\neq\emptyset$;

    2. (ii)

$P$ has a regression function $f_{P}\colon[0,1]\to\mathbb{R}$ that is locally
bounded at each
$m\in\mathcal{I}^{*}(P)\cap\\{\min(\operatorname{csupp}P^{X}),\max(\operatorname{csupp}P^{X})\\}$
for which $P^{X}(\\{m\\})=0$.

If (ii) holds, then $\psi_{m}^{0}(P)\neq\emptyset$ for all
$m\in\mathcal{I}^{*}(P)\cap\operatorname{csupp}P^{X}$.

Suppose that $P^{X}(\\{m\\})=0$ for all $m\in[0,1]$. Let
$(P_{n})_{n=1}^{\infty}$ be a sequence in $\mathcal{P}$ with
$W_{2}(P_{n},P)\to 0$ and let $(\delta_{n})$ be any deterministic, non-
negative sequence such that $\delta_{n}\to 0$. Then the following hold as
$n\to\infty$:

  1. (b)

$\sup_{f_{n}\in\psi^{\delta_{n}}(P_{n})}\inf_{f^{*}\in\psi^{*}(P)}\|f_{n}-f^{*}\|_{L^{\infty}(A,P^{X})}\to
0$ for all closed sets
$A\subseteq(\operatorname{supp}P^{X})\setminus\mathcal{I}^{*}(P)$.

  2. (c)

Assume that $\psi_{m}^{0}(P)\neq\emptyset$ for all
$m\in\mathcal{I}^{*}(P)\cap\operatorname{csupp}P^{X}$ and let
$\tilde{\mathcal{I}}^{*}(P)$ be the set of $m^{*}\in\mathcal{I}^{*}(P)$ such
that either $m^{*}\notin\operatorname{Int}(\operatorname{csupp}P^{X})$ or not
all elements of $\psi_{m^{*}}^{0}(P)$ are continuous. Then
$\sup_{f_{n}\in\psi^{\delta_{n}}(P_{n})}\inf_{f^{*}\in\psi^{0}(P)}\sup_{x\in
A}\,\lvert(f_{n}-f^{*})(x)\rvert\to 0$ for all closed sets
$A\subseteq(\operatorname{supp}P^{X})\setminus\tilde{\mathcal{I}}^{*}(P)$.

  3. (d)

If $\mathcal{I}^{*}(P)\subseteq\operatorname{Int}(\operatorname{csupp}P^{X})$,
then
$\sup_{f_{n}\in\psi^{\delta_{n}}(P_{n})}\inf_{f^{*}\in\psi^{0}(P)}\|f_{n}-f^{*}\|_{L^{q}(P^{X})}\to
0$ for all $q\in[1,\infty)$.

######  Remark S15.

In assertions (b)–(d), we see that $\psi^{*}(P)$ or $\psi^{0}(P)$ can be
regarded as a ‘limiting set’ $\mathcal{M}$ to which the sets
$\mathcal{M}_{n}=\psi^{\delta_{n}}(P_{n})$ converge, in the sense that
$\sup_{f_{n}\in\mathcal{M}_{n}}\inf_{f\in\mathcal{M}}\,\rho(f_{n},f)\to 0$ for
each of three different pseudometrics $\rho$. In the proof, we establish a
slightly stronger conclusion for each $\rho$: for any sequence $(f_{n})$ with
$f_{n}\in\mathcal{M}_{n}$ for all $n$, every subsequence of $(f_{n})$ has a
further subsequence that converges to an element of $\mathcal{M}$ with respect
to $\rho$. Note that unlike in Proposition S12(f)–(i), we take an infimum
rather than a supremum over $\mathcal{M}$ in the convergence statements above.
This is because we do not in general have $\rho(f,g)=0$ for all
$f,g\in\mathcal{M}$ (in contrast to the sets $\psi_{m}^{*}(P)$ for each fixed
$m\in[0,1]$). In Section S7, we also demonstrate through Examples S32 and S33
that if certain technical conditions in Proposition S12 and Corollary S14 are
dropped, then some of the conclusions fail to hold in general.

For a regression function $f_{0}\colon[0,1]\to\mathbb{R}$ (that need not be
S-shaped) and a sequence of models (2) indexed by $n\in\mathbb{N}$, we can now
establish asymptotic convergence results for S-shaped LSEs and their
inflection points, including under model misspecification. To this end, we
apply the continuity results from the general projection theory above
(specifically Proposition S12 and Corollary S14) to the empirical
distributions $\mathbb{P}_{n}:=n^{-1}\sum_{i=1}^{n}\delta_{(x_{ni},Y_{ni})}$.
Recall that we write
$\mathbb{P}_{n}^{X}:=n^{-1}\sum_{i=1}^{n}\delta_{x_{ni}}$.

######  Proposition S16.

Suppose that the following conditions hold:

  1. (i)

$(\mathbb{P}_{n}^{X})$ converges weakly to a distribution $P_{0}^{X}$ on
$[0,1]$ satisfying $P_{0}^{X}(\\{m\\})=0$ for all $m\in[0,1]$;

  2. (ii)

For some distribution $P_{\xi}$ with mean 0 and finite variance, we have
$\xi_{n1},\dotsc,\xi_{nn}\overset{\mathrm{iid}}{\sim}P_{\xi}$ for each $n$;

  3. (iii)

$f_{0}$ is bounded on $[0,1]$ and continuous $P_{0}^{X}$-almost everywhere
(i.e. the set of discontinuities of $f_{0}$ has $P_{0}^{X}$ measure 0).

Let $P_{0}\in\mathcal{P}$ be the distribution of $(X,f_{0}(X)+\xi)$, where
$X\sim P_{0}^{X}$ and $\xi\sim P_{\xi}$ are independent, and define
$L_{m}^{*}(P_{0})$ for $m\in[0,1]$ and $L^{*}(P_{0}),\psi^{0}(P_{0})$,
$\mathcal{I}^{*}(P_{0})$, $\tilde{\mathcal{I}}^{*}(P_{0})$ as in Proposition
S12 and Corollary S14. Then $\psi^{0}(P_{0})\neq\emptyset$, and

  1. (a)

$\sup_{m\in[0,1]}\,\lvert
L_{m}^{*}(\mathbb{P}_{n})-L_{m}^{*}(P_{0})\rvert\overset{p}{\to}0$ and
$L^{*}(\mathbb{P}_{n})-L^{*}(P_{0})\overset{p}{\to}0$ as $n\to\infty$, where
$L_{m}^{*}(\mathbb{P}_{n})=S_{n}(\hat{f}_{n}^{m})/n$ and
$L^{*}(\mathbb{P}_{n})=\min_{1\leq j\leq n}S_{n}(\hat{f}_{n}^{x_{nj}})/n$ for
$m\in[0,1]$ and $n\in\mathbb{N}$.

For each $n$, fix an LSE $\tilde{f}_{n}$ over $\mathcal{F}$, so that
$\tilde{f}_{n}\in\psi^{0}(\mathbb{P}_{n})$, and let $\tilde{m}_{n}$ be any
inflection point of $\tilde{f}_{n}$. Then the following hold as $n\to\infty$:

  1. (b)

$\inf_{m^{*}\in\mathcal{I}^{*}(P_{0})}\,\lvert\tilde{m}_{n}-m^{*}\rvert\overset{p}{\to}0$;

  2. (c)

$\inf_{f^{*}\in\psi^{0}(P_{0})}\sup_{x\in
A}\,\lvert(\tilde{f}_{n}-f^{*})(x)\rvert\overset{p\ast}{\to}0$ for any closed
set
$A\subseteq\operatorname{supp}P_{0}^{X}\setminus\tilde{\mathcal{I}}^{*}(P_{0})$;

  3. (d)

$\inf_{f^{*}\in\psi^{0}(P_{0})}\,\|\tilde{f}_{n}-f^{*}\|_{L^{q}(P_{0}^{X})}\overset{p\ast}{\to}0$
for all $q\in[1,\infty)$, provided that
$\mathcal{I}^{*}(P_{0})\subseteq\operatorname{Int}(\operatorname{csupp}P_{0}^{X})$.

Using the full strength of Proposition S12 and Corollary S14, we see that for
a sequence of non-negative tolerances $\delta_{n}\to 0$, the conclusions above
extend to sequences $(\tilde{f}_{n})$ where each $\tilde{f}_{n}$ takes values
in $\psi^{\delta_{n}}(\mathbb{P}_{n})$, the set of approximate
$\delta_{n}$-minimisers of $f\mapsto S_{n}(f)$ over $\mathcal{F}$.

In the correctly specified setting where $f_{0}\in\mathcal{F}^{m_{0}}$ for
some unique $m_{0}\in[0,1]$, Proposition S16 specialises to the consistency
result stated as Proposition 2 in the main text.

##  S4 Proofs for Section 7

For reference, we state a result from convex analysis that generalises Lemmas
9 and 10.

######  Lemma S17.

Let $\Lambda\subseteq\mathbb{R}^{n}$ be a non-empty closed, convex set. For
each $y\in\mathbb{R}^{n}$, there exists a unique projection of $y$ onto
$\Lambda$, given by
$\Pi_{\Lambda}(y)=\operatorname*{argmin}_{u\in\Lambda}\|u-y\|$, and we have
the following:

  1. (a)

$\Pi_{\Lambda}(y)$ is the unique $\hat{y}\in\Lambda$ for which $\langle
u-\hat{y},y-\hat{y}\rangle\leq 0$ for all $u\in\Lambda$.

  2. (b)

For each $u\in\Lambda$, we have
$\Pi_{\Lambda}^{-1}(\\{u\\})=u+N_{\Lambda}(u)$, where
$N_{\Lambda}(u):=\\{v\in\mathbb{R}^{n}\setminus\\{0\\}:\langle
v,\tilde{u}\rangle\leq\langle v,u\rangle\text{ for all
}\tilde{u}\in\Lambda\\}\cup\\{0\\}$ is the _normal cone_ of $\Lambda$ at $u$.

Furthermore, each element of $\Lambda$ is contained in the relative interior
of a unique face of $\Lambda$. For each face $F\subseteq\Lambda$, we have the
following:

  1. (c)

There is a closed convex cone $N_{\Lambda}(F)$ such that
$N_{\Lambda}(u)=N_{\Lambda}(F)$ for all $u\in\operatorname{relint}F$, and
$\Pi_{\Lambda}^{-1}(\operatorname{relint}F)=(\operatorname{relint}F)+N_{\Lambda}(F)$.
If $u\in\operatorname{relint}F$ and $v\in N_{\Lambda}(F)$, then
$\Pi_{\Lambda}(u+v)=u$.

  2. (d)

For all $y\in\Pi_{\Lambda}^{-1}(\operatorname{relint}F)$, we have
$\Pi_{\Lambda}(y)=\Pi_{\operatorname{aff}(F)}(y)$, where
$\operatorname{aff}(F)$ denotes the affine hull of $F$, i.e. the smallest
affine subspace containing $F$.

  3. (e)

If in addition $\Lambda$ is a finitely generated cone, then $F$ and
$N_{\Lambda}(F)$ are also finitely generated cones, and
$\operatorname{span}(F)$ and
$\operatorname{span}\bigl{(}N_{\Lambda}(F)\bigr{)}$ are complementary
orthogonal subspaces. Thus,
$\Pi_{\Lambda}^{-1}(\operatorname{relint}F)=(\operatorname{relint}F)+N_{\Lambda}(F)$
is an $n$-dimensional convex cone (with non-empty interior).

###### Proof.

For (a, b) and the first assertion in (c), see Schneider (2014, Section 1.2),
and (2.3) and Lemma 2.2.2 in Schneider (2014, Section 2.2). Using these, we
now complete the proofs of (c, d, e).

(c) By the definition of $N_{\Lambda}(F)$, we have $\langle
v,\tilde{u}-u\rangle\leq 0$ for all $v\in N_{\Lambda}(F)$,
$\tilde{u}\in\operatorname{relint}F$ and $u\in\Lambda$, with equality when
$u\in\operatorname{relint}F$. It now follows from (a) that
$\Pi_{\Lambda}(u+v)=u$ for all $u\in\operatorname{relint}F$ and $v\in
N_{\Lambda}(F)$.

(d) Take any $u\in\operatorname{aff}(F)$. Since
$\Pi_{\Lambda}(y)\in\operatorname{relint}F$, we have $\Pi_{\Lambda}(y)+\lambda
u$ for some sufficiently small $\lambda>0$, so $\langle\lambda
u,y-\Pi_{\Lambda}(y)\rangle=0$. Thus,
$\Pi_{\Lambda}(y)\in\operatorname{aff}(F)$ and $\langle
u,y-\Pi_{\Lambda}(y)\rangle=0$ for all $u\in\operatorname{aff}(F)$, so indeed
$\Pi_{\Lambda}(y)=\Pi_{\operatorname{aff}(F)}(y)$.

(e) For a finitely generated cone $\Lambda$, this follows from Theorem 2.4.9
and (2.25) in Schneider (2014, Section 2.2). ∎

By applying Lemma 9, we can give an alternative self-contained proof of Lemma
10 for the cone $\Lambda^{j}\subseteq\mathbb{R}^{j}$ of increasing convex
sequences based on $x_{1},\dotsc,x_{j}$, whose generators $\pm
u^{0},u^{1},\dotsc,u^{j-1}$ are specified in the paragraph below (6). For
$A\subseteq[j-1]$, recall from Remark 11 that we write
$P_{A}\in\mathbb{R}^{j\times j}$ for the matrix that represents the orthogonal
projection $\Pi_{\mathcal{L}_{A}}$ onto
$\mathcal{L}_{A}=\operatorname{span}\\{u^{\ell^{\prime}}:\ell^{\prime}\in
A\cup\\{0\\}\\}$, the subspace consisting of all $v\in\mathbb{R}^{j}$ whose
knots lie in $A$.

###### Proof of Lemma 10.

For each $\tilde{v}\in\\{v^{\prime},v^{\prime\prime}\\}$, we have
$\Pi_{\Lambda}(\tilde{v})\in F_{A}\subseteq\operatorname{Im}(U_{A})$, and
Lemma 9 implies that $\langle
u^{\ell},\tilde{v}-\Pi_{\Lambda}(\tilde{v})\rangle=0$ for all $\ell\in
A\cup\\{0\\}$. This shows that
$P_{A}(\tilde{v})=\Pi_{\Lambda}(\tilde{v})\in\operatorname{relint}F_{A}$ for
$\tilde{v}\in\\{v^{\prime},v^{\prime\prime}\\}$. Now fix $t\in[0,1]$ and
$v:=(1-t)v^{\prime}+tv^{\prime\prime}$. Then
$P_{A}(v)=(1-t)P_{A}(v^{\prime})+tP_{A}(v^{\prime\prime})=(1-t)\Pi_{\Lambda}(v^{\prime})+t\Pi_{\Lambda}(v^{\prime\prime})\in\operatorname{relint}F_{A}$
by the convexity of $\operatorname{relint}F_{A}$. In addition, by applying
Lemma 9 to $\Pi_{\Lambda}(v^{\prime}),\Pi_{\Lambda}(v^{\prime\prime})$, we
deduce that

$\langle u^{\ell},v-P_{A}(v)\rangle=(1-t)\langle
u^{\ell},v^{\prime}-\Pi_{\Lambda}(v^{\prime})\rangle+t\langle
u^{\ell},v^{\prime\prime}-\Pi_{\Lambda}(v^{\prime\prime})\rangle\leq 0$

for all $0\leq\ell\leq j-1$, with equality if $\ell\in A\cup\\{0\\}$ (in view
of the definition of $P_{A}$). It follows from Lemma 9 that
$\Pi_{\Lambda}(v)=P_{A}(v)\in\operatorname{relint}F_{A}$, as required. ∎

###### Proof of Lemma 12.

For (iv), we know from (iii) that
$\Pi_{\Lambda^{j}}\bigl{(}v(t)\bigr{)}=P_{A_{r}}v(t)$ for all
$t\in[t_{r},t_{r+1}]$ after an iteration of (II). By applying Lemma 10, we
deduce that there exist $\eta>0$ and $A^{\prime}\subseteq[j-1]$ with
$A^{\prime}\neq A_{r}$ such that
$\hat{v}(t):=\Pi_{\Lambda^{j}}\bigl{(}v(t)\bigr{)}=P_{A^{\prime}}v(t)\in\Lambda^{j}\cap\mathcal{L}_{A^{\prime}}=\\{u\in\Lambda^{j}:A(u)\subseteq
A^{\prime}\\}$ for all $t\in[t_{r+1},t_{r+1}+\eta]$. Now in (IV), note that

  * •

If $\ell\in A_{r}\setminus A_{r}^{-}$, then
$\lambda_{\ell}\bigl{(}\hat{v}(t_{r+1})\bigr{)}=\beta_{\ell}(t_{r+1})>0$, so
$\ell\in A\bigl{(}\hat{v}(t_{r+1})\bigr{)}\subseteq A^{\prime}$;

  * •

If $\ell\in A^{\prime}$, then $\gamma_{\ell}(t_{r+1})=\langle
u^{\ell},v(t_{r+1})-\hat{v}(t_{r+1})\rangle=\langle
u^{\ell},(I-P_{A^{\prime}})v(t_{r+1})\rangle=0$, so
$\ell\in\\{1\leq\ell^{\prime}\leq
j-1:\gamma_{\ell^{\prime}}(t_{r+1})=0\\}=A_{r}\cup A_{r}^{+}$.

Thus, $A_{r}\setminus A_{r}^{-}\subseteq A^{\prime}\subseteq A_{r}\cup
A_{r}^{+}$, so in all cases, (IV) is guaranteed to find subsets
$A^{\pm}\subseteq A_{r}^{\pm}$ such that when we take $A_{r+1}=(A_{r}\setminus
A^{-})\cup A^{+}$, the next iteration of (II) strictly increases $t$. In
particular, this always happens in scenario (a) where $\lvert A_{r}^{-}\cup
A_{r}^{+}\rvert=1$, since we necessarily have $A^{\prime}=(A_{r}\setminus
A_{r}^{-})\cup A_{r}^{+}=A_{r+1}$ in this case.

For (v), recall again that for each $r\in\mathbb{N}_{0}$, we have
$\Pi_{\Lambda^{j}}\bigl{(}v(t)\bigr{)}=P_{A_{r}}v(t)\equiv\hat{v}_{r}(t)$ for
all $t\in[t_{r},t_{r+1}]$. As noted in (II),
$\lambda_{\ell}\bigl{(}\hat{v}_{r}(t)\bigr{)}$ and $\langle
u^{\ell},v(t)-\hat{v}_{r}(t)\rangle$ vary linearly with $t$ for all
$\ell\in[j-1]$, so it follows from this and (18) that

$t_{r+1}=\sup\,\bigl{\\{}t\geq
t_{r}:\lambda_{\ell}\bigl{(}\hat{v}_{r}(t)\bigr{)}\geq 0,\,\langle
u^{\ell},v(t)-\hat{v}_{r}(t)\rangle\leq 0\text{ for all }1\leq\ell\leq
j-1\bigr{\\}}.$

Thus, by Lemma 9, we cannot have
$\hat{v}_{r}(t)=\Pi_{\Lambda^{j}}\bigl{(}v(t)\bigr{)}$ for any $t>t_{r+1}$, so
$A_{r}\neq A_{r^{\prime}}$ for all $r^{\prime}>r$, as claimed. ∎

Degeneracies in Algorithm 7: It can be verified that there is a set
$A\subseteq\mathbb{R}^{j}\times\mathbb{R}^{j}$ of Lebesgue measure 0 such that
if $(v(0),v(1))\notin A$, then no degeneracies occur on the trajectory of the
algorithm. Thus, degeneracies are rarely an issue when $v(0),v(1)$ are
obtained from simulated or real data rather than artificially constructed (see
Example S19). To avoid them in practice, Fraser and Massam (1989, page 73) and
Meyer (1999, page 28) suggest slightly perturbing $v(0),v(1)$ or some
intermediate $v(t_{r})$. The approach we outline in Stage (IV) covers all
eventualities in the degenerate scenario (b), but this can be time-consuming
when $\lvert A_{r}^{-}\cup A_{r}^{+}\rvert$ is large.

In the special case where $u=v(0)-v(1)$ is a positive multiple of
$u^{j-1}=e_{j}=(0,\dotsc,0,1)\in\mathbb{R}^{j}$ (which is of particular
relevance in the SeqConReg procedure in Section 3), a more efficient
alternative to (IV) is as follows:

  1. (IV’)

Instead define $A_{r}^{-}:=\\{\ell\in
A_{r}:\beta_{\ell}(t_{r+1})=0,\,\hat{\lambda}_{\ell}^{A_{r}}(u)>0\\}$ and
$A_{r}^{+}:=\\{\ell\in
A_{r}^{c}:\gamma_{\ell}(t_{r+1})=0,\,\hat{\zeta}_{\ell}^{A_{r}}(u)<0\\}$, and
let $\ell_{\max}:=\max(A_{r}^{-}\cup A_{r}^{+})$. Let
$A_{r+1}:=A_{r}\setminus\\{\ell_{\max}\\}$ if $\ell_{\max}\in A_{r}^{-}$ and
otherwise let $A_{r+1}:=A_{r}\cup\\{\ell_{\max}\\}$ if $\ell_{\max}\in
A_{r}^{+}$. Then execute (II) and (III) with this $A_{r+1}$ (and $r+1$ in
place of $r$ throughout).

If there is a degeneracy at $t_{r+1}$, then when we run this modified
algorithm, there may be several subsequent iterations of (II) in which $t$
does not increase (i.e. we remain at $t_{r+1}$). Nevertheless, the choice of
$\ell_{\max}=\max(A_{r}^{-}\cup A_{r}^{+})$ in (IV’) ensures that property
(iv) still holds, and hence that the algorithm terminates with the exact
solution (usually after fewer iterations than in the original).

######  Proposition S18.

Suppose that $u=v(0)-v(1)$ is a positive multiple of
$u^{j-1}=e_{j}\in\mathbb{R}^{j}$. Then with modification (IV’), Algorithm 7
terminates with the correct solution after finitely many steps, and the
following hold for any $r\in\mathbb{N}_{0}$:

  1. (a)

$\max A_{r}\geq\max A_{r+1}$; in other words, if $\max A_{r}<\ell\leq j-1$,
then $\ell\notin A_{r^{\prime}}$ for any $r^{\prime}>r$.

  2. (b)

Let $\ell_{r}:=\max(\\{\ell\in A_{r}:\ell+1\in A_{r}\\}\cup\\{0\\})$. Then in
(19), we have
$\hat{\lambda}_{\ell}^{A_{r}}(u)\equiv\lambda_{\ell}(P_{A_{r}}u)=0$ for all
$0\leq\ell\leq\ell_{r}-1$ and $\hat{\zeta}_{\ell}^{A_{r}}(u)\equiv\langle
u^{\ell},(I-P_{A_{r}})u\rangle=0$ for all $0\leq\ell\leq\ell_{r}+1$.

This follows from Lemma S20 below, which captures some specific structural
features of the generators $\pm u^{0},u^{1},\dotsc,u^{j-1}$ of $\Lambda^{j}$.
The facts in (a) and (b) lead to some additional computational shortcuts in
Algorithm 7 when $u$ is a positive multiple of $e_{j}$. Specifically, when
computing $t_{r+1}$ in Stage (II) of the procedure, it follows from
Proposition S18 that we need only compute the ratios in (19) for
$\ell_{r}<\ell\leq\max A_{r}$. Thus, when $t\geq t_{r}$, we can drop all
$\beta_{\ell}(t)$ and $\gamma_{\ell}(t)$ with $\ell>\max A_{r}$, and when
updating the primal and dual variables for use in subsequent iterations, no
calculations are needed to see that
$\beta_{\ell}(t_{r+1})=\beta_{\ell}(t_{r})$ and
$\gamma_{\ell}(t_{r+1})=\gamma_{\ell}(t_{r})$ for all $1\leq\ell\leq\ell_{r}$.

######  Example S19.

We can actually write down explicitly the sequence of ‘active sets’
$A_{0},A_{1},\dotsc$ obtained by Algorithm 7 in the special case where
$v(0)\in\Lambda^{j}$ and $u=v(0)-v(1)$ is a positive multiple of $e_{j}$. This
can happen if for example in (7), the observations $Y_{1},\dotsc,Y_{j}$ are
drawn according to a _noiseless_ regression model (2) in which $f_{0}$ is
increasing and convex on $[x_{1},x_{j-1}]$. With
$A_{0}=A\bigl{(}v(0)\bigr{)}$, it turns out that for $r\in\mathbb{N}_{0}$, we
have

$A_{r+1}=\begin{cases}A_{r}\setminus\\{\max A_{r}\\}&\quad\text{if }\max
A_{r}-1\in A_{r}\text{ or }\max A_{r}=j-1\\\ A_{r}\cup\\{\max
A_{r}-1\\}&\quad\text{if }\max A_{r}-1\notin A_{r}\text{ and }\max
A_{r}<j-1.\end{cases}$ (S35)

Indeed, given that $v(0)\in\Lambda^{j}$ and hence that $\gamma_{\ell}(0)=0$
for all $0\leq\ell\leq j-1$, we can apply Proposition S18 to establish
inductively that $\gamma_{\ell}(t_{r+1})=0$ for all $0\leq\ell\leq\max A_{r}$
and $r\in\mathbb{N}_{0}$. In particular, we always have
$A_{r}^{+}=\\{1,\dotsc,\max A_{r}-1\\}\cap A_{r}^{c}$, and

  * •

If $\max A_{r}-1\in A_{r}$ or $\max A_{r}=j-1$, then $t_{r}<t_{r+1}$ and
$A_{r}^{-}=\\{\max A_{r}\\}$;

  * •

If $\max A_{r}-1\notin A_{r}$ and $\max A_{r}<j-1$, then $t_{r}=t_{r+1}$ and
$A_{r}^{-}=\emptyset$.

Note that unless $\\{1,\dotsc,\max A_{r}-2\\}\subseteq A_{r}$, there is a
degeneracy at $t_{r+1}$, so we use (IV’) above to form the next ‘active set’
$A_{r+1}$. In addition, we have $\max A_{r}>\max A_{r+2}$ for all
$r\in\mathbb{N}_{0}$ in view of (S35), so the number of distinct ‘active sets’
on the trajectory of Algorithm 7 is at most $2(j-1)$. This is much less than
$2^{j-1}$, the total number of subsets of $[j-1]$, and an open question is
whether for general $v(0)\in\mathbb{R}^{j}$ (and $u=v(0)-v(1)$ as above), the
number of ‘active sets’ is necessarily bounded above by a polynomial in $j$.
If this is always true (or true in ‘most’ cases), then our sequential
procedure for increasing convex regression is guaranteed to have a worst-case
(or average-case) complexity that is at most polynomial in the number of
observations $n$.

For fixed $j\in[n]$, $\ell\in[j-1]$ and $A\subseteq[j-1]$, Lemma S20
determines the signs of the entries of $(I-P_{A})u^{\ell}\in\mathbb{R}^{j}$
indexed by $A\cup\\{\ell\\}$. This yields useful information on how the primal
and dual variables change in Algorithm 7 when the vector $u=v(0)-v(1)$ therein
is a positive multiple of $e_{j}$. This enables us to justify the more
efficient implementation (IV’) of Stage (IV) of this procedure, as well as
assertions (a) and (b) in Proposition S18 on the composition of the resulting
active sets.

We write $e_{1},\dotsc,e_{j}$ for the standard basis vectors in
$\mathbb{R}^{j}$ and $\langle\cdot\,,\cdot\rangle$ for the standard Euclidean
inner product. For $t\in\mathbb{R}$, let $\operatorname{sgn}(t):=(\lvert
t\rvert/t)\mathbbm{1}_{\\{t\neq 0\\}}$.

######  Lemma S20.

For $A\subseteq[j-1]$, enumerate the elements of $A$ as
$a_{1}>a_{2}>\cdots>a_{m}$, and let $a_{0}=j$ and $a_{m+1}=0$. Fix
$\ell\in[j-1]$. Then $(I-P_{A})u^{\ell}\in\mathcal{L}_{A\cup\\{\ell\\}}$, and
$(I-P_{A})u^{\ell}=0$ if and only if $\ell\in A$.

Suppose now that $\ell\notin A$ and let $q\in[m+1]$ be such that
$a_{q}<\ell<a_{q-1}$. Define $q_{-}:=\max(\\{1\leq\tilde{q}\leq
q-1:a_{\tilde{q}-1}=a_{\tilde{q}}+1\\}\cup\\{0\\})$ and
$q_{+}:=\min(\\{q+1\leq\tilde{q}\leq
m:a_{\tilde{q}-1}=a_{\tilde{q}}+1\\}\cup\\{m+1\\})$. Then
$\langle(I-P_{A})u^{\ell},e_{\ell}\rangle<0$, $\langle
P_{A}u^{\ell},e_{1}\rangle=\langle P_{A}u^{\ell},e_{a_{m}}\rangle$, and for
$0\leq s\leq m$, we have

$\operatorname{sgn}\bigl{(}\langle(I-P_{A})u^{\ell},e_{a_{s}}\rangle\bigr{)}=\begin{cases}(-1)^{s-q}&\quad\text{if
}q\leq s<q_{+}\\\ (-1)^{q-1-s}&\quad\text{if }q_{-}\leq s\leq q-1\\\
0&\quad\text{if }s<q_{+}\text{ or }s\geq q_{+}.\end{cases}$ (S36)

###### Proof of Lemma S20.

The generators $u^{0},u^{1},\dotsc,u^{j-1}$ of the cone $\Lambda^{j}$ are
linearly independent, so
$u^{\ell}\equiv(u_{1}^{\ell},\dotsc,u_{j}^{\ell})=\bigl{(}(x_{i}-x_{\ell})^{+}:1\leq
i\leq j\bigr{)}\in\mathcal{L}_{A}$ (i.e. $(I-P_{A})u^{\ell}=0$) if and only if
$\ell\in A$. Suppose henceforth that $\ell\notin A$ and let
$\tilde{z}\equiv(\tilde{z}_{1},\dotsc,\tilde{z}_{j}):=P_{A}u^{\ell}=\operatorname*{argmin}_{z\in\mathcal{L}_{A}}\|u^{\ell}-z\|$.
Then
$u^{\ell}-\tilde{z}=(I-P_{A})u^{\ell}\in\operatorname{span}(\\{u^{\ell}\\}\cup\mathcal{L}_{A})=\mathcal{L}_{A\cup\\{\ell\\}}$,
so $u^{\ell}-\tilde{z}$ is determined by
$\\{u_{i}^{\ell}-\tilde{z}_{i}=\langle(I-P_{A})u^{\ell},e_{i}\rangle:i\in
A\cup\\{\ell\\}\\}$.

To establish (S36), we make the following additional definitions. For
$z\in\mathbb{R}^{j}$ and $J=\\{b,b+1,\dotsc,b^{\prime}\\}$ with $1\leq b\leq
b^{\prime}\leq j$, we write $z_{J}=(z_{b},z_{b+1},\dotsc,z_{b^{\prime}})$ for
the subvector of $z$ indexed by $J$. For $s\in[m]$, partition $[j]$ into the
subsets

$J_{s}^{+}:=\\{1,\dotsc,a_{s}\\},\quad
J_{s}:=\\{a_{s}+1,\dotsc,a_{s-1}-1\\},\quad
J_{s}^{-}:=\\{a_{s-1},\dotsc,j\\},$

and for $i\in J_{s}$, let
$t_{i}^{J_{s}}:=(x_{i}-x_{a_{s}})/(x_{a_{s-1}}-x_{a_{s}})\in(0,1)$, so that
any affine sequence based on $(x_{i}:i\in J_{s})$ can be written in the form
$v^{J_{s}}(\lambda,\vartheta):=\bigl{(}(1-t_{i}^{J_{s}})(u_{a_{s}}^{\ell}-\lambda)+t_{i}^{J_{s}}(u_{a_{s-1}}^{\ell}-\vartheta):a_{s}+1\leq
i\leq a_{s-1}-1\bigr{)}$ for some $\lambda,\vartheta\in\mathbb{R}$. Moreover,

$\mathcal{L}_{A,s}^{+}(\lambda):=\\{z_{J_{s}^{+}}:z\in\mathcal{L}_{A},\,z_{a_{s}}=\lambda\\}\subseteq\mathbb{R}^{\lvert
J_{s}^{+}\rvert}\;\text{ and
}\;\mathcal{L}_{A,s}^{-}(\lambda):=\\{z_{J_{s}^{-}}:z\in\mathcal{L}_{A},\,z_{a_{s-1}}=\lambda\\}\subseteq\mathbb{R}^{\lvert
J_{s}^{-}\rvert}$

are affine subspaces for each $\lambda\in\mathbb{R}$, and
$\mathcal{L}_{A,s}^{\pm}(\lambda)=\lambda\mathcal{L}_{A,s}^{\pm}(1)$ if
$\lambda\neq 0$, so the vectors
$\tilde{v}^{J_{s}^{\pm}}:=\operatorname*{argmin}_{v\in\mathcal{L}_{A,s}^{\pm}(1)}\|v\|$
and
$\lambda\tilde{v}^{J_{s}^{\pm}}=\operatorname*{argmin}_{v\in\mathcal{L}_{A,s}^{\pm}(\lambda)}\|v\|$
are well-defined for all $\lambda\in\mathbb{R}$.

######  Claim 1.

Let $\star\in\\{+,-\\}$ and $s\in[m-1]$ be such that $a_{s},a_{s\star 1}\in
J_{q}^{\star}$. If $\lvert a_{s}-a_{s\star 1}\rvert=1$, then
$\tilde{v}_{a_{s\star 1}}^{J_{q}^{\star}}=0$. Otherwise, if $\lvert
a_{s}-a_{s\star 1}\rvert>1$, then
$\operatorname{sgn}\bigl{(}\tilde{v}_{a_{s\star
1}}^{J_{q}^{\star}}\bigr{)}=-\operatorname{sgn}\bigl{(}\tilde{v}_{a_{s}}^{J_{q}^{\star}}\bigr{)}$.
Thus,

$\operatorname{sgn}\bigl{(}\tilde{v}_{a_{s}}^{J_{q}^{+}}\bigr{)}=\begin{cases}(-1)^{s-q}&\quad\text{if
}q\leq s<q_{+}\\\ 0&\quad\text{if }q_{+}\leq s\leq
m;\end{cases}\quad\operatorname{sgn}\bigl{(}\tilde{v}_{a_{s}}^{J_{q}^{-}}\bigr{)}=\begin{cases}(-1)^{q-1-s}&\quad\text{if
}q_{-}\leq s\leq q-1\\\ 0&\quad\text{if }0\leq s<q_{-}.\end{cases}$

###### Proof of Claim 1.

We focus on the case $\star=+$; the arguments for $\star=-$ are similar. Note
that $a_{s},a_{s+1}\in J_{s}^{+}$ precisely when $q\leq s\leq m-1$. For any
such $s$ and $\mu\in\mathbb{R}$, define
$\tilde{v}^{J_{q}^{+}}(s;\mu)\equiv\bigl{(}\tilde{v}_{i}^{J_{q}^{+}}(s,\mu):1\leq
i\leq a_{q}\bigr{)}$ by

$\tilde{v}_{i}^{J_{q}^{+}}(s;\mu):=\begin{cases}\mu\tilde{v}_{i}^{J_{s+1}^{+}}=\operatorname*{argmin}_{v\in\mathcal{L}_{A,s+1}^{+}(\mu)}\|v\|\;\>&\text{for
}i\in J_{s+1}^{+}=\\{1,\dotsc,a_{s+1}\\}\\\
(1-t_{i}^{J_{s+1}})\mu+t_{i}^{J_{s+1}}\tilde{v}_{a_{s}}^{J_{q}^{+}}=v_{i}^{J_{s+1}}\bigl{(}-\mu,-\tilde{v}_{a_{s}}^{J_{q}^{+}}\bigr{)}\;\>&\text{for
}i\in J_{s+1}\\\ \tilde{v}_{i}^{J_{q}^{+}}\;\>&\text{for }i\in J_{s+1}^{-}\cap
J_{q}^{+}=\\{a_{s},\dotsc,a_{q}\\}.\end{cases}$

Then $\tilde{v}_{a_{s}}^{J_{q}^{+}}(s;\mu)=\tilde{v}_{a_{s}}^{J_{q}^{+}}$, and
since $\mu\tilde{v}^{J_{s+1}^{+}}\in\mathcal{L}_{A,s+1}^{+}(\mu)$, we have
$\tilde{v}_{a_{s+1}}^{J_{q}^{+}}(s;\mu)=\mu$, so
$\tilde{v}^{J_{q}^{+}}(s;\mu)\in\mathcal{L}_{A,q}^{+}(1)$. Observe in addition
that
$\tilde{v}^{J_{q}^{+}}\bigl{(}s;\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\bigr{)}=\tilde{v}^{J_{q}^{+}}$;
indeed,
$\tilde{v}_{i}^{J_{q}^{+}}\bigl{(}s;\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\bigr{)}=\tilde{v}_{i}^{J_{q}^{+}}$
for $a_{s+1}+1\leq i\leq a_{q}$ and

$\displaystyle\tilde{\mathcal{L}}_{A,q,s+1}^{+}$
$\displaystyle:=\bigl{\\{}v\equiv(v_{1},\dotsc,v_{a_{q}})\in\mathcal{L}_{A,q}^{+}:v_{i}=\tilde{v}_{i}^{J_{q}^{+}}\text{
for }a_{s+1}+1\leq i\leq a_{q}\bigr{\\}}$
$\displaystyle\phantom{:}=\bigl{\\{}(v_{1},\dotsc,v_{a_{q}})\in\mathbb{R}^{a_{q}}:v_{J_{s+1}^{+}}\in\mathcal{L}_{A,s+1}^{+}\bigl{(}\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\bigr{)},\,v_{i}=\tilde{v}_{i}^{J_{q}^{+}}\text{
for }a_{s+1}+1\leq i\leq a_{q}\bigr{\\}},$

so
$\tilde{v}^{J_{q}^{+}}=\operatorname*{argmin}_{v\in\mathcal{L}_{A,q}^{+}(1)}\|v\|=\operatorname*{argmin}_{v\in\tilde{\mathcal{L}}_{A,q,s+1}^{+}}\\!\|v\|$
satisfies

$(\tilde{v}^{J_{q}^{+}})_{J_{s+1}^{+}}=\operatorname*{argmin}_{v^{\prime}\in\mathcal{L}_{A,s+1}^{+}\bigl{(}\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\bigr{)}}\\!\|v^{\prime}\|=\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\tilde{v}^{J_{s+1}^{+}}=\bigl{(}\tilde{v}^{J_{q}^{+}}(s;\tilde{v}_{a_{s+1}}^{J_{q}^{+}})\bigr{)}_{J_{s+1}^{+}}.$

Thus,

$\mu\mapsto
r_{s}(\mu):=\|\tilde{v}^{J_{q}^{+}}(s;\mu)\|^{2}=\mu^{2}\,\|\tilde{v}^{J_{s+1}^{+}}\|^{2}+\sum_{i\in
J_{s+1}}\bigl{(}(1-t_{i}^{J_{s+1}})\mu+t_{i}^{J_{s+1}}\tilde{v}_{a_{s}}^{J_{q}^{+}}\bigr{)}^{2}+\sum_{i=a_{s}}^{a_{q}}\bigl{(}\tilde{v}_{i}^{J_{q}^{+}}\bigr{)}^{2}$

is a quadratic function with
$r_{s}\bigl{(}\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\bigr{)}=\|\tilde{v}^{J_{q}^{+}}\|^{2}=\min_{v\in\mathcal{L}_{A,q}^{+}(1)}\|v\|^{2}=\min_{\mu\in\mathbb{R}}r_{s}(\mu)$,
so

$0=r_{s}^{\prime}\bigl{(}\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\bigr{)}=2\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\,\|\tilde{v}^{J_{s+1}^{+}}\|^{2}+2\sum_{i\in
J_{s+1}}\bigl{(}(1-t_{i}^{J_{s+1}})\tilde{v}_{a_{s+1}}^{J_{q}^{+}}+t_{i}^{J_{s+1}}\tilde{v}_{a_{s}}^{J_{q}^{+}}\bigr{)}\bigl{(}1-t_{i}^{J_{s+1}}\bigr{)}.$
(S37)

Now $\|\tilde{v}^{J_{s+1}^{+}}\|^{2}>0$ by the definition of
$\tilde{v}^{J_{s+1}^{+}}\in\mathcal{L}_{A,s+1}^{+}(1)$, so if
$a_{s}=a_{s+1}+1$, i.e. $J_{s+1}=\emptyset$, then
$\tilde{v}_{a_{s+1}}^{J_{q}^{+}}=0$ by (S37). On the other hand, suppose
instead that $a_{s}>a_{s+1}+1$, in which case $J_{s+1}\neq\emptyset$. If
$\tilde{v}_{a_{s}}^{J_{q}^{+}}=0$, then $\tilde{v}_{a_{s+1}}^{J_{q}^{+}}=0$ by
(S37). When $\tilde{v}_{a_{s}}^{J_{q}^{+}}>0$, we must have
$\tilde{v}_{a_{s+1}}^{J_{q}^{+}}<0$, since otherwise the first term on the
right-hand side of (S37) would be non-negative and each summand in the second
term would be strictly positive, contradicting the fact that
$r_{s}^{\prime}\bigl{(}\tilde{v}_{a_{s+1}}^{J_{q}^{+}}\bigr{)}=0$. Similarly,
if $\tilde{v}_{a_{s}}^{J_{q}^{+}}<0$, then
$\tilde{v}_{a_{s+1}}^{J_{q}^{+}}>0$. This completes the proof of the claim. ∎

Next, note that
$u_{J_{q}^{+}}^{\ell}=0\in\mathcal{L}_{A,q}^{+}(0)=\mathcal{L}_{A,q}^{+}(u_{a_{q}}^{\ell})$
and $u_{J_{q}^{-}}^{\ell}=(x_{i}-x_{\ell}:a_{q-1}\leq i\leq
j)\in\mathcal{L}_{A,q}^{-}(u_{a_{q-1}}^{\ell})$. Thus, for each
$(\lambda,\vartheta)\in\mathbb{R}^{2}$, we have

$\displaystyle\mathcal{L}_{A}^{q}(\lambda,\vartheta)$
$\displaystyle:=\\{z\in\mathcal{L}_{A}:(u^{\ell}-z)_{a_{q}}=\lambda,\,(u^{\ell}-z)_{a_{q-1}}=\vartheta\\}$
$\displaystyle\phantom{:}=\bigl{\\{}z\in\mathcal{L}_{A}:(u^{\ell}-z)_{J_{q}^{+}}\in\mathcal{L}_{A,q}^{+}(\lambda),\,(u^{\ell}-z)_{J_{q}^{-}}\in\mathcal{L}_{A,q}^{-}(\vartheta),\,z_{J_{q}}=v^{J_{q}}(\lambda,\vartheta)\bigr{\\}},$
(S38)

and the unique minimiser $\tilde{z}(\lambda,\vartheta)$ of
$z\mapsto\|u^{\ell}-z\|^{2}=\|(u^{\ell}-z)_{J_{q}^{+}}\|^{2}+\|(u^{\ell}-z)_{J_{q}}\|^{2}+\|(u^{\ell}-z)_{J_{q}^{-}}\|^{2}$
over $\mathcal{L}_{A}^{q}(\lambda,\vartheta)$ satisfies
$\tilde{z}(\lambda,\vartheta)_{J_{q}}=v^{J_{q}}(\lambda,\vartheta)$,
$\bigl{(}u^{\ell}-\tilde{z}(\lambda,\vartheta)\bigr{)}_{J_{q}^{+}}=\operatorname*{argmin}_{v\in\mathcal{L}_{A,q}^{+}(\lambda)}\|v\|=\lambda\tilde{v}^{J_{q}^{+}}$
and
$\bigl{(}u^{\ell}-\tilde{z}(\lambda,\vartheta)\bigr{)}_{J_{q}^{-}}=\operatorname*{argmin}_{v\in\mathcal{L}_{A,q}^{-}(\vartheta)}\|v\|=\vartheta\tilde{v}^{J_{q}^{-}}$.
Let

$\displaystyle r(\lambda,\vartheta)$
$\displaystyle:=\min_{z\in\mathcal{L}_{A}^{q}(\lambda,\vartheta)}\|u^{\ell}-z\|^{2}=\|u^{\ell}-\tilde{z}(\lambda,\vartheta)\|^{2}=\|\lambda\tilde{v}^{J_{q}^{+}}\|^{2}+\|u_{J_{q}}^{\ell}-v^{J_{q}}(\lambda,\vartheta)\|^{2}+\|\vartheta\tilde{v}^{J_{q}^{-}}\|^{2}$
$\displaystyle\phantom{:}=\lambda^{2}\,\|\tilde{v}^{J_{q}^{+}}\|^{2}+\sum_{i\in
J_{q}}\bigl{(}u_{i}^{\ell}-(1-t_{i}^{J_{q}})(u_{a_{q}}^{\ell}-\lambda)-t_{i}^{J_{q}}(u_{a_{q-1}}^{\ell}-\vartheta)\bigr{)}^{2}+\vartheta^{2}\,\|\tilde{v}^{J_{q}^{-}}\|^{2},$

so that $(\lambda,\vartheta)\mapsto r(\lambda,\vartheta)$ is a quadratic form
with

$\nabla
r(\lambda,\vartheta)=2\lambda\,\|\tilde{v}^{J_{q}^{+}}\|^{2}\begin{pmatrix}1\\\
0\end{pmatrix}+2\sum_{i\in
J_{q}}\bigl{(}u_{i}^{\ell}-v_{i}^{J_{q}}(\lambda,\vartheta)\bigr{)}\begin{pmatrix}1-t_{i}^{J_{q}}\\\
t_{i}^{J_{q}}\end{pmatrix}+2\vartheta\,\|\tilde{v}^{J_{q}^{-}}\|^{2}\begin{pmatrix}0\\\
1\end{pmatrix}$ (S39)

for each $(\lambda,\vartheta)\in\mathbb{R}^{2}$, and $\tilde{z}=P_{A}u^{\ell}$
satisfies
$\|u^{\ell}-\tilde{z}\|^{2}=\min_{z\in\mathcal{L}_{A}}\|u^{\ell}-z\|^{2}=\min_{(\lambda,\vartheta)\in\mathbb{R}^{2}}r(\lambda,\vartheta)$.
Thus, writing
$\tilde{\lambda}:=(u^{\ell}-\tilde{z})_{a_{q}}=\langle(I-P_{A})u^{\ell},e_{a_{q}}\rangle$
and
$\tilde{\vartheta}:=(u^{\ell}-\tilde{z})_{a_{q-1}}=\langle(I-P_{A})u^{\ell},e_{a_{q-1}}\rangle$,
we have $\tilde{z}=\tilde{z}(\tilde{\lambda},\tilde{\vartheta})$ and
$(\tilde{\lambda},\tilde{\vartheta})=\operatorname*{argmin}_{(\lambda,\vartheta)\in\mathbb{R}^{2}}r(\lambda,\vartheta)$,
whence $\nabla r(\tilde{\lambda},\tilde{\vartheta})=0$.

######  Claim 2.

$\tilde{\lambda},\tilde{\vartheta}>0$ and
$\langle(I-P_{A})u^{\ell},e_{\ell}\rangle=(u^{\ell}-\tilde{z})_{\ell}=u_{\ell}^{\ell}-v^{J_{q}}(\tilde{\lambda},\tilde{\vartheta})_{\ell}<0$.

###### Proof of Claim 2.

It suffices to show that if $(\lambda,\vartheta)\in\mathbb{R}^{2}$ is such
that either $\lambda\leq 0$, $\vartheta\leq 0$ or
$u_{\ell}^{\ell}-v^{J_{q}}(\lambda,\vartheta)_{\ell}\geq 0$, then $\nabla
r(\lambda,\vartheta)\neq 0$. For any such $(\lambda,\vartheta)$, it is enough
to prove that there exist $\lambda^{\prime},\vartheta^{\prime}\in\mathbb{R}$
such that $\lambda\lambda^{\prime}\geq 0$, $\vartheta\vartheta^{\prime}\geq 0$
and
$\bigl{(}u_{i}^{\ell}-v_{i}^{J_{q}}(\lambda,\vartheta)\bigr{)}\bigl{(}(1-t_{i}^{J_{q}})\lambda^{\prime}+t_{i}^{J_{q}}\vartheta^{\prime}\bigr{)}\geq
0$ for all $i\in J_{q}$, with at least one of these inequalities being strict,
since then

$\nabla r(\lambda,\vartheta)^{\top}\begin{pmatrix}\lambda^{\prime}\\\
\vartheta^{\prime}\end{pmatrix}=2\lambda\lambda^{\prime}\,\|\tilde{v}^{J_{q}^{+}}\|^{2}+2\sum_{i\in
J_{q}}\bigl{(}u_{i}^{\ell}-v_{i}^{J_{q}}(\lambda,\vartheta)\bigr{)}\bigl{(}(1-t_{i}^{J_{q}})\lambda^{\prime}+t_{i}^{J_{q}}\vartheta^{\prime}\bigr{)}+2\vartheta\vartheta^{\prime}\,\|\tilde{v}^{J_{q}^{-}}\|^{2}>0$

by (S39). To this end, define the convex function $g\colon
x\mapsto(x-x_{\ell})^{+}$ on $[x_{a_{q}},x_{a_{q-1}}]$, and let $h$ be the
unique affine function with $h(x_{a_{q-1}})=g(x_{a_{q-1}})-\lambda$ and
$h(x_{a_{q}})=g(x_{a_{q}})-\vartheta$, so that $g(x_{i})=u_{i}^{\ell}$ and
$h(x_{i})=v_{i}^{J_{q}}(\lambda,\vartheta)$ for $a_{q}\leq i\leq a_{q-1}$.
Since $(\lambda,\vartheta)$ satisfies at least one of the three conditions
above, the possibilities for $I:=\\{x\in(x_{a_{q}},x_{a_{q-1}}):h(x)>g(x)\\}$
are as follows. In each case, we verify that there is an affine function
$\tilde{h}$ such that
$\bigl{(}g(x)-h(x)\bigr{)}\bigl{(}h(x)-\tilde{h}(x)\bigr{)}\geq 0$ for all
$x\in[x_{a_{q}},x_{a_{q-1}}]$, with strict inequality for some
$x\in\\{x_{a_{q}},x_{a_{q}+1},\dotsc,x_{a_{q-1}}\\}$:

  * •

$I=\emptyset$: then $g(x)\geq h(x)$ for all $x\in[x_{a_{q}},x_{a_{q-1}}]$, and
strict inequality holds for some
$x\in\\{x_{a_{q}},x_{a_{q}+1},\dotsc,x_{a_{q-1}}\\}$, so we can take
$\tilde{h}$ to be any affine function such that $\tilde{h}<h$ on
$[x_{a_{q}},x_{a_{q-1}}]$.

  * •

$I=(x_{a_{q}},x_{a_{q-1}})$: by the continuity of $g,h$, we have $g(x)\leq
h(x)$ for all $x\in[x_{a_{q}},x_{a_{q-1}}]$, with strict inequality for some
$x\in\\{x_{a_{q}},x_{a_{q}+1},\dotsc,x_{a_{q-1}}\\}$, and we can take
$\tilde{h}$ to be any affine function such that $\tilde{h}>h$ on
$[x_{a_{q}},x_{a_{q-1}}]$.

  * •

$I=(x_{a_{q}},\tilde{x})$ for some $\tilde{x}\in(x_{a_{q}},x_{a_{q-1}})$: by
continuity, $g(\tilde{x})=h(\tilde{x})$, and we must have
$g(x_{a_{q-1}})>h(x_{a_{q-1}})$ since $I\neq(x_{a_{q}},x_{a_{q-1}})$. Thus, we
can take $\tilde{h}$ to be any affine function satisfying
$\tilde{h}(\tilde{x})=h(\tilde{x})$ and $\tilde{h}(x_{a_{q}})>h(x_{a_{q}})$,
so that $g\leq h\leq\tilde{h}$ on $[x_{a_{q}},\tilde{x}]$, $g\geq
h\geq\tilde{h}$ on $[\tilde{x},x_{a_{q-1}}]$ and
$g(x_{a_{q-1}})>h(x_{a_{q-1}})>\tilde{h}(x_{a_{q-1}})$.

  * •

$I=(\tilde{x},x_{a_{q-1}})$ for some $\tilde{x}\in(x_{a_{q}},x_{a_{q-1}})$:
similarly, we can take $\tilde{h}$ to be any affine function satisfying
$\tilde{h}(\tilde{x})=h(\tilde{x})$ and
$\tilde{h}(x_{a_{q-1}})>h(x_{a_{q-1}})$.

Now let $\lambda^{\prime}:=(h-\tilde{h})(x_{a_{q}})$ and
$\vartheta^{\prime}:=(h-\tilde{h})(x_{a_{q-1}})$. Then for each $i\in J_{q}$,
we have
$(h-\tilde{h})(x_{i})=(1-t_{i}^{J_{q}})\lambda^{\prime}+t_{i}^{J_{q}}\vartheta^{\prime}$
since $h-\tilde{h}$ is an affine function, and recall that
$(g-h)(x_{i})=u_{i}^{\ell}-v_{i}^{J_{q}}(\lambda,\vartheta)$. Thus,
$\lambda^{\prime},\vartheta^{\prime}$ have the required properties. ∎

In conclusion, by the observation after (S38) and Claim 2, we have

$\operatorname{sgn}\bigl{(}\langle(I-P_{A})u^{\ell},e_{a_{s}}\rangle\bigr{)}=\operatorname{sgn}\bigl{(}(u^{\ell}-\tilde{z}(\tilde{\lambda},\tilde{\vartheta}))_{a_{s}}\bigr{)}=\begin{cases}\operatorname{sgn}\bigl{(}\tilde{\lambda}\tilde{v}_{a_{s}}^{J_{q}^{+}}\bigr{)}=\operatorname{sgn}\bigl{(}\tilde{v}_{a_{s}}^{J_{q}^{+}}\bigr{)}&\quad\text{if
}q\leq s\leq m\\\
\operatorname{sgn}\bigl{(}\tilde{\vartheta}\tilde{v}_{a_{s}}^{J_{q}^{-}}\bigr{)}=\operatorname{sgn}\bigl{(}\tilde{v}_{a_{s}}^{J_{q}^{-}}\bigr{)}&\quad\text{if
}0\leq s\leq q-1,\end{cases}$

which together with Claim 1 implies (S36), as desired. ∎

###### Proof of Proposition S18.

For fixed $A\subseteq[j-1]$ and $\ell\in[j-1]$, let
$\hat{\lambda}_{\ell}^{A}(u)=\lambda_{\ell}(P_{A}u)$ and
$\hat{\zeta}_{\ell}^{A}(u)=\langle u^{\ell},(I-P_{A})u\rangle$ be as in (19),
where $u$ is some positive multiple of $e_{j}$. Enumerate the elements of $A$
as $j=a_{0}>a_{1}>\cdots>a_{m}>a_{m+1}=0$ and let
$q^{\prime}:=\min(\\{2\leq\tilde{q}\leq
m:a_{\tilde{q}-1}=a_{\tilde{q}}+1\\}\cup\\{m+1\\})$. Now
$P_{A}u\in\mathcal{L}_{A}$, and if $j-1\notin A$, then for all
$s\in\\{0,\dotsc,m\\}$, it follows by taking $\ell=j-1$ and $q=1$ in (S36)
that

$\langle P_{A}u,e_{a_{s}}\rangle\>\begin{cases}>0&\;\text{if
}s<q^{\prime}\text{ and }s\text{ is odd}\\\ <0&\;\text{if }s<q^{\prime}\text{
and }s\text{ is even}\\\ =0&\;\text{if }s\geq q^{\prime}.\end{cases}$

For $\ell\in[j-1]$, we deduce from this and (16) that

$\hat{\lambda}_{\ell}^{A}(u)=\lambda_{\ell}(P_{A}u)\>\begin{cases}>0&\;\text{if
}\ell=a_{s}\text{ for some odd }1\leq s\leq q^{\prime}\\\ <0&\;\text{if
}\ell=a_{s}\text{ for some even }1\leq s\leq q^{\prime}\\\
=0&\;\text{otherwise}.\end{cases}$ (S40)

Moreover, if $j-1\notin A$, then for $\ell\in[j-1]$, it follows by taking
$s=0$ in (S36) that

$\hat{\zeta}_{\ell}^{A}(u)=\langle(I-P_{A})u^{\ell},u\rangle\>\begin{cases}>0&\;\text{if
}a_{q}<\ell<a_{q-1}\text{ for some odd }q\in[q^{\prime}]\\\ <0&\;\text{if
}a_{q}<\ell<a_{q-1}\text{ for some even }q\in[q^{\prime}]\\\ =0&\;\text{if
}\ell\leq a_{q^{\prime}}=\ell_{r}\text{ or }\ell\in A.\end{cases}$ (S41)

We are now in a position to show that under modification (IV’), Algorithm 7
cannot remain indefinitely at any of the thresholds $t_{r}$. To this end, it
suffices to verify that if $r\in\mathbb{N}$ is such that
$t_{r}=t_{r+1}=t_{r+2}$, then $\ell_{\max}:=\max(A_{r}^{-}\cup
A_{r}^{+})>\max(A_{r+1}^{-}\cup A_{r+1}^{+})$. First, we prove that
$\ell_{\max}\notin A_{r+1}^{-}\cup A_{r+1}^{+}$. Enumerating the elements of
$A\equiv A_{r}$ as $a_{1}>\cdots>a_{m}$ and defining $a_{0},q^{\prime}$ as
above, we consider separately the cases $\ell_{\max}\in A_{r}^{-}$ and
$\ell_{\max}\in A_{r}^{+}$.

  * •

If $\ell_{\max}\in A_{r}^{-}$, then $\beta_{\ell_{\max}}(t_{r+1})=0$ and
$\hat{\lambda}_{\ell_{\max}}^{A_{r}}(u)>0$. This means that
$\ell_{\max}=a_{s}$ for some odd $s\in[q^{\prime}]$. Indeed, when $j-1\notin
A_{r}$, this follows from (S40), and otherwise if $j-1\in A_{r}$, then
$A_{r}^{-}=\\{j-1\\}$ and $\ell_{\max}=j-1=a_{1}$. Now
$A_{r+1}=A_{r}\setminus\\{\ell_{\max}\\}\subseteq[j-2]$ under (IV’), so
$\ell_{\max}\notin A_{r+1}^{-}\subseteq A_{r+1}$, and enumerating the elements
of $A_{r+1}$ as
$a_{1}>\cdots>a_{s-1}>a_{s}^{\prime}>a_{s+1}^{\prime}>\cdots>a_{m-1}^{\prime}$,
we have $a_{s}^{\prime}<\ell_{\max}<a_{s-1}$. Since $s\;(\leq q^{\prime})$ is
odd, we deduce from (S41) that $\hat{\zeta}_{\ell_{\max}}^{A_{r+1}}(u)>0$, and
hence that $\ell_{\max}\notin A_{r+1}^{+}$.

  * •

Otherwise, if $\ell_{\max}\in A_{r}^{+}$, then
$\gamma_{\ell_{\max}}(t_{r+1})=0$ and
$\hat{\zeta}_{\ell_{\max}}^{A_{r}}(u)<0$. In this case, we necessarily have
$j-1\notin A_{r}$, since otherwise $A_{r}^{+}=\emptyset$, so it follows from
(S41) that $a_{s}<\ell_{\max}<a_{s-1}$ for some even $s\in[q^{\prime}-1]$. Now
$A_{r+1}=A_{r}\cup\\{\ell_{\max}\\}\subseteq[j-2]$ under (IV’), so
$\ell_{\max}\notin A_{r+1}^{+}\subseteq A_{r+1}^{c}$, and $A_{r+1}$ can be
enumerated as
$a_{1}>\cdots>a_{s-1}>a_{s}^{\prime}>a_{s+1}^{\prime}>\cdots>a_{m+1}^{\prime}$,
where $a_{s}^{\prime}=\ell_{\max}$. Since $s$ is even, we deduce from (S40)
that $\hat{\lambda}_{\ell_{\max}}^{A_{r+1}}(u)\leq 0$, and hence that
$\ell_{\max}\notin A_{r+1}^{-}$.

It remains to show that $A_{r+1}^{-}\cup A_{r+1}^{+}$ does not contain any
$\ell\in\\{\ell_{\max}+1,\dotsc,j-1\\}$. If $\ell_{\max}=j-1$, then there is
nothing to prove, so we assume that $\ell_{\max}<j-1$, in which case
$j-1\notin A_{r}$ by the arguments above. Writing $a_{q}^{\prime}$ for the
$q^{th}$ largest element of $A_{r+1}$, we see that in both cases above,
$a_{1}^{\prime}=a_{1}>\cdots>a_{s-1}^{\prime}=a_{s-1}$ are precisely the
indices in $A_{r+1}$ that are strictly greater than $\ell_{\max}$, where
$s\leq q^{\prime}$. Now fix $j-1\geq\ell>\ell_{\max}$ and note that since
$t_{r+1}=t_{r+2}$ by assumption, we have the following:

  * •

Suppose that $\ell\in A_{r+1}$ and $\beta_{\ell}(t_{r+2})=0$, in which case
$\beta_{\ell}(t_{r+1})=0$, $\ell\in A_{r}$ and $\ell\notin A_{r}^{-}$ by the
definition of $\ell_{\max}$. Thus, $\hat{\lambda}_{\ell}^{A_{r}}(u)\leq 0$, so
by applying (S40) to $A_{r}$, we deduce that $\ell\neq a_{q}$ for any odd
$q\in[q^{\prime}]$. Since $a_{q}=a_{q}^{\prime}$ for $q\leq s-1$ and
$\ell>a_{q}^{\prime}$ for $q\geq s$, this means that $\ell\neq a_{q}^{\prime}$
for any odd $q$. Applying (S40) once again to $A_{r+1}$, we conclude that
$\hat{\lambda}_{\ell}^{A_{r+1}}(u)\leq 0$, whence $\ell\notin A_{r+1}^{-}$.

  * •

Suppose that $\ell\notin A_{r+1}$ and $\gamma_{\ell}(t_{r+2})=0$, in which
case $\gamma_{\ell}(t_{r+1})=0$, $\ell\notin A_{r}$ and $\ell\notin A_{r}^{+}$
by the definition of $\ell_{\max}$. Thus, $\hat{\zeta}_{\ell}^{A_{r}}(u)\geq
0$, so in view of (S41), we cannot have $a_{q}<\ell<a_{q-1}$ for any even
$q\in[q^{\prime}-1]$. As above, it follows that we cannot have
$a_{q}^{\prime}<\ell<a_{q-1}^{\prime}$ for any even $q$. Applying (S41) once
again to $A_{r+1}$, we conclude that $\hat{\zeta}_{\ell}^{A_{r+1}}(u)\geq 0$,
whence $\ell\notin A_{r+1}^{+}$.

This completes the justification of (IV’). Finally, we obtain both assertions
of Proposition S18 as straightforward consequences of (S40) and (S41).

(a) By taking $q=1$ in the first line of (S41), we see that
$\hat{\lambda}_{\ell}^{A_{r}}(u)>0$ for all $\max A_{r}=a_{1}<\ell\leq j-1$.
Thus, in Algorithm 7 with modification (IV’), $A_{r+1}\subseteq A_{r}\cup
A_{r}^{+}\subseteq\\{1,\dotsc,\max A_{r}\\}$.

(b) Since $\ell_{r}=a_{q^{\prime}}$ here, this follows immediately from the
final lines of (S40) and (S41). ∎

##  S5 Auxiliary results for Section S2

###  S5.1 Auxiliary results for Section S2.1

The proof of Theorem 5 relies on the following bound on the localised Gaussian
widths of the cone
$\Gamma[\mathcal{D}]=\bigl{\\{}\bigl{(}f(x_{1}),\dotsc,f(x_{n})\bigr{)}:f\in\mathcal{F}\bigr{\\}}\subseteq\mathbb{R}^{n}$,
where $\mathcal{D}$ is a set of design points $x_{1}<\cdots<x_{n}$ in $[0,1]$
and $\mathcal{F}$ is the class of all S-shaped functions on $[0,1]$. For
$\theta\equiv(\theta_{1},\dotsc,\theta_{n})\in\mathbb{R}^{n}$ and $r>0$,
recall from Section S2 that we defined $V(\theta)=\theta_{n}-\theta_{1}$ and
$\Gamma(\theta,r)\equiv\Gamma(\theta,r)[\mathcal{D}]=\\{v\in\Gamma[\mathcal{D}]:\|v-\theta\|\leq
r\\}$.

######  Lemma S21.

For a set $\mathcal{D}\subseteq[0,1]$ of design points $x_{1}<\cdots<x_{n}$
with $n\geq 2$, define $\tilde{R}(\mathcal{D})$ as in (S10). Fix
$\theta\in\Gamma[\mathcal{D}]$ and $r>0$. If $Z\sim N_{n}(0,I_{n})$, then for
all $\tilde{C}\geq 1$, we have

$\displaystyle\mathbb{E}\,\biggl{(}\sup_{v\in\Gamma(\theta,r)}\>\lvert
Z^{\top}(v-\theta)\rvert\biggr{)}$
$\displaystyle\lesssim\frac{r^{2}}{\tilde{C}}+r\sqrt{\log
n}+\bigl{(}V(\theta)+\tilde{C}\bigr{)}^{1/4}\tilde{R}(\mathcal{D})^{1/8}\,r^{3/4}$
$\displaystyle\lesssim\frac{r^{2}}{\tilde{C}}+r\sqrt{\log
n}+\bigl{(}V(\theta)+\tilde{C}\bigr{)}^{1/4}\biggl{(}\frac{x_{n}-x_{1}}{\min_{2\leq
i\leq n}(x_{i}-x_{i-1})}\biggr{)}^{1/8}\,r^{3/4}.$ (S42)

We will derive this result from the bounds in Lemma S22 and S23 on the
covering numbers of

$\displaystyle\Gamma_{A,B}[\mathcal{D}]$
$\displaystyle:=\\{(v_{1},\dotsc,v_{n})\in\Gamma[\mathcal{D}]:A\leq v_{i}\leq
B\text{ for all }i\\}$ $\displaystyle K_{A,B}[\mathcal{D}]$
$\displaystyle:=\bigl{\\{}\bigl{(}f(x_{1}),\dotsc,f(x_{n})\bigr{)},\,f\text{
is convex },\,A\leq f\leq B\bigr{\\}},$

where $-\infty<A<B<\infty$. For $\varepsilon>0$ and
$U\subseteq\mathbb{R}^{n}$, recall that $\mathcal{N}\subseteq\mathbb{R}^{n}$
is said to be an _$\varepsilon$ -cover_ of $U$ (with respect to the Euclidean
norm $\|{\cdot}\|$) if
$U\subseteq\bigcup_{u\in\mathcal{N}}\bar{B}(u,\varepsilon)$, where
$\bar{B}(u,\varepsilon):=\\{v\in\mathbb{R}^{n}:\|v-u\|\leq\varepsilon\\}$. We
denote by $N(\varepsilon,U):=\inf\\{\lvert\mathcal{N}\rvert:\mathcal{N}\text{
is an }\varepsilon\text{-cover of }U\\}\in\mathbb{N}\cup\\{\infty\\}$ the
_$\varepsilon$ -covering number_ of $U$.

######  Lemma S22.

In the setting of Lemma S21, the following holds for all $-\infty<A<B<\infty$
and $\varepsilon>0$:

$\log N(\varepsilon,\Gamma_{A,B}[\mathcal{D}])\lesssim\log
n+(B-A)^{1/2}\,\frac{\tilde{R}(\mathcal{D})^{1/4}}{\varepsilon^{1/2}}.$ (S43)

######  Lemma S23.

For any finite set $\mathcal{D}\subseteq[0,1]$ and every $\varepsilon>0$, we
have

$\log
N(\varepsilon,K_{0,1}[\mathcal{D}])\lesssim\frac{\tilde{R}(\mathcal{D})^{1/4}}{\varepsilon^{1/2}}.$
(S44)

We first give the proof of (S44), which gives rise to the definition of
$\tilde{R}(\mathcal{D})$ in (S10), and then deduce Lemmas S22 and S21 in that
order.

###### Proof of Lemma S23.

We proceed by induction on $n=\lvert\mathcal{D}\rvert$: for $n=1$, the bound
clearly holds since $\tilde{R}(\mathcal{D})=1$ by definition, so suppose now
that $\mathcal{D}=\\{x_{1}<\cdots<x_{n}\\}$ for some $n\geq 2$. First, by
taking $c_{1}=n\min_{2\leq i\leq n}(x_{i}-x_{i-1})$ in the second bound in
Guntuboyina and Sen (2013, Lemma A.4) and then arguing as in the proof of
Chatterjee (2016, Lemma 3.3) Chatterjee (2016, Lemma 3.3), we see that

$\log
N(\varepsilon,K_{0,1}[\mathcal{D}])\lesssim\frac{1}{\varepsilon^{1/2}}\biggl{(}\frac{(x_{n}-x_{1})}{\min_{2\leq
i\leq n}(x_{i}-x_{i-1})}\biggr{)}^{1/4}.$ (S45)

In addition, for a fixed partition of $\mathcal{D}$ into $k\geq 2$ non-empty
sets $\mathcal{D}_{1},\dotsc,\mathcal{D}_{k}$, we now define
$\tilde{a}_{\ell}:=\tilde{R}(\mathcal{D}_{\ell})^{1/10}/\bigl{(}\sum_{\ell^{\prime}=1}^{k}\tilde{R}(\mathcal{D}_{\ell^{\prime}})^{1/5}\bigr{)}^{1/2}$
for $\ell\in[k]$. Given $\varepsilon>0$, let
$\varepsilon_{\ell}:=\varepsilon\tilde{a}_{\ell}$ for each $\ell$, so that
$\varepsilon^{2}=\sum_{\ell=1}^{k}\varepsilon_{\ell}^{2}$. Then since
$\lvert\mathcal{D}_{1}\rvert,\dotsc,\lvert\mathcal{D}_{k}\rvert<\lvert\mathcal{D}\rvert$,
it follows by induction that

$\log N(\varepsilon,K_{0,1}[\mathcal{D}])\leq\sum_{\ell=1}^{k}\log
N(\varepsilon_{\ell},K_{0,1}[\mathcal{D}_{\ell}])\lesssim\sum_{\ell=1}^{k}\,\frac{\tilde{R}(\mathcal{D}_{\ell})^{1/4}}{\varepsilon_{\ell}^{1/2}}=\frac{\bigl{(}\sum_{\ell=1}^{k}\tilde{R}(\mathcal{D}_{\ell})^{1/5}\bigr{)}^{5/4}}{\varepsilon^{1/2}},$
(S46)

where by Lemma S24 below (with $b_{\ell}=\tilde{R}(\mathcal{D}_{\ell})^{1/2}$
for all $\ell$), our choice of $\varepsilon_{1},\dotsc,\varepsilon_{k}$
minimises the penultimate expression above subject to the constraint
$\varepsilon^{2}=\sum_{\ell=1}^{k}\varepsilon_{\ell}^{2}$. Minimising the
right hand side of (S46) over all partitions of $\mathcal{D}$ into $k\geq 2$
non-empty subsets, we can combine (S45) and (S46) to complete the inductive
step for (S44), in view of the definition of $\tilde{R}(\mathcal{D})$ in
(S10). ∎

######  Lemma S24.

For fixed $b_{1},\dotsc,b_{k}>0$, the unique solution to the optimisation
problem

$\min\;\sum_{\ell=1}^{k}\left(\frac{b_{\ell}}{a_{\ell}}\right)^{1/2}\quad\text{subject
to }\;\;\sum_{\ell=1}^{k}a_{\ell}^{2}=1,\,a_{\ell}>0\text{ for }\ell\in[k]$

is given by
$\sum_{\ell=1}^{k}(b_{\ell}/a_{\ell}^{*})^{1/2}=\bigl{(}\sum_{\ell=1}^{k}b_{\ell}^{2/5}\bigr{)}^{5/4}$,
where
$a_{\ell}^{*}:=b_{\ell}^{1/5}/\bigl{(}\sum_{\ell=1}^{k}b_{\ell}^{2/5}\bigr{)}^{1/2}$
for each $\ell$.

###### Proof of Lemma S24.

Let $\tau=2/5$, $p=2/(2-\tau)$ and $q=2/\tau$, so that $1/p+1/q=1$, $\tau
p=1/2$ and $\tau q=2$. Then by Hölder’s inequality,

$\sum_{\ell=1}^{k}b_{\ell}^{2/5}=\sum_{\ell=1}^{k}b_{\ell}^{\tau}\leq\left\\{\sum_{\ell=1}^{k}\left(\frac{b_{\ell}^{\tau}}{a_{\ell}^{\tau}}\right)^{p}\right\\}^{1/p}\left(\sum_{\ell=1}^{k}a_{\ell}^{\tau
q}\right)^{1/q}=\left(\sum_{\ell=1}^{k}b_{\ell}^{2/5}\right)^{5/4},$

with equality if and only if
$a_{\ell}=b_{\ell}^{p/(p+q)}/\lambda=b_{\ell}^{1/5}/\lambda$ for all $\ell$,
where taking $\lambda=\bigl{(}\sum_{\ell=1}^{k}b_{\ell}^{2/5}\bigr{)}^{1/2}$
ensures that $\sum_{\ell=1}^{k}a_{\ell}^{2}=1$. ∎

###### Proof of Lemma S22.

By a scaling argument, it suffices to show that

$\log N(\varepsilon,\Gamma_{0,1}[\mathcal{D}])\lesssim\log
n+\frac{\tilde{R}(\mathcal{D})^{1/4}}{\varepsilon^{1/2}}$ (S47)

for all $\varepsilon>0$, i.e. that (S43) holds when $A=0$ and $B=1$. Indeed,
for general $-\infty<A<B<\infty$, define the invertible affine map
$L_{A,B}\colon\mathbb{R}^{n}\to\mathbb{R}^{n}$ by
$L_{A,B}(v)_{i}:=A+(B-A)v_{i}$ for
$v\equiv(v_{1},\dotsc,v_{n})\in\mathbb{R}^{n}$ and $i\in[n]$, so that
$\Gamma_{A,B}[\mathcal{D}]=\\{L_{A,B}(v):v\in\Gamma_{0,1}[\mathcal{D}]\\}$. If
(S47) holds, then for any $\varepsilon>0$, we can find an
$\varepsilon/(B-A)$-cover $\mathcal{N}$ of $\Gamma_{0,1}[\mathcal{D}]$ with
$\log\,\lvert\mathcal{N}\rvert\lesssim\log
n+(B-A)^{1/2}\,(\sqrt{Rn}/\varepsilon)^{1/2}$. For any
$\theta\in\Gamma_{A,B}[\mathcal{D}]$, there exists $\theta^{*}\in\mathcal{N}$
satisfying $\|\theta-
L_{A,B}(\theta^{*})\|=(B-A)\|L_{A,B}^{-1}(\theta)-\theta^{*}\|\leq\varepsilon$,
so $\mathcal{N}_{A,B}:=\\{L_{A,B}(v):v\in\mathcal{N}\\}$ is an
$\varepsilon$-cover of $\Gamma_{A,B}[\mathcal{D}]$ with
$\log\,\lvert\mathcal{N}_{A,B}\rvert=\log\,\lvert\mathcal{N}\rvert\lesssim\log
n+(B-A)^{1/2}\,(\sqrt{Rn}/\varepsilon)^{1/2}$, as desired.

To establish (S47), fix $\varepsilon>0$ and let
$\Gamma_{0,1}^{m}[\mathcal{D}]:=\bigl{\\{}\bigl{(}f(x_{1}),\dotsc,f(x_{n})\bigr{)}:f\in\mathcal{F}^{m},\,0\leq
f\leq 1\bigr{\\}}$ for $m\in[0,1]$, so that
$\Gamma_{0,1}[\mathcal{D}]=\bigcup_{j=1}^{\,n}\Gamma_{0,1}^{x_{j}}[\mathcal{D}]$
and

$N(\varepsilon,\Gamma_{0,1}[\mathcal{D}])\leq\sum_{i=1}^{n}N(\varepsilon,\Gamma_{0,1}^{x_{j}}[\mathcal{D}])\leq
n\max_{1\leq j\leq n}N(\varepsilon,\Gamma_{0,1}^{x_{j}}[\mathcal{D}]).$

Now for $j\in[n]$, let $\mathcal{D}_{j}^{-}:=\\{x_{i}:1\leq i\leq j\\}$ and
$\mathcal{D}_{j}^{+}:=\\{x_{i}:j+1\leq i\leq n\\}$. Then
$\Gamma_{0,1}[\mathcal{D}]\subseteq
K_{0,1}[\mathcal{D}_{j}^{-}]\times\bigl{(}-K_{0,1}[\mathcal{D}_{j}^{+}]\bigr{)}$
and $\tilde{R}(\mathcal{D}_{j}^{\pm})\leq\tilde{R}(\mathcal{D})$ by (S10), so
it follows from Lemma S23 that

$\log N(\varepsilon,\Gamma_{0,1}^{x_{j}}[\mathcal{D}])\leq\log
N\bigl{(}\varepsilon/\sqrt{2},K_{0,1}[\mathcal{D}_{j}^{-}]\bigr{)}+\log
N\bigl{(}\varepsilon/\sqrt{2},K_{0,1}[\mathcal{D}_{j}^{+}]\bigr{)}\lesssim\frac{\tilde{R}(\mathcal{D})^{1/4}}{\varepsilon^{1/2}}.$

We conclude that

$\log N(\varepsilon,\Gamma_{0,1}[\mathcal{D}])\leq\log n+\max_{1\leq j\leq
n}\log N(\varepsilon_{\ell},\Gamma_{0,1}^{x_{j}}[\mathcal{D}])\lesssim\log
n+\frac{\tilde{R}(\mathcal{D})^{1/4}}{\varepsilon^{1/2}},$

as required. ∎

When $\varepsilon\gg B-A$, it turns out that in the proof above, we do not
have to construct separate $\varepsilon$-covers for each of the sets
$\Gamma_{A,B}^{x_{1}}[\mathcal{D}],\dotsc,\Gamma_{A,B}^{x_{n}}[\mathcal{D}]$
individually. This is because elements of $\Gamma_{A,B}^{x_{j}}[\mathcal{D}]$
can be approximated to accuracy $\varepsilon$ by those in a covering set for
$\Gamma_{A,B}^{x_{j^{\prime}}}[\mathcal{D}]$ with $j^{\prime}$ close to $j$.
In general, we can improve the first $\log n$ term in (S43) to
$\log\bigl{(}1\vee\\{n(B-A)^{2}/\varepsilon^{2}\\}\wedge n\bigr{)}$, and hence
obtain an overall bound in Lemma S22 that tends to 0 as
$\varepsilon\rightarrow\infty$. We omit further details of these additional
arguments, since this improved result leads to the same worst-case oracle
inequality (9) as in Theorem 5 (possibly with a slightly smaller universal
constant $C$).

###### Proof of Lemma S21.

Fix $\theta\in\Gamma$ and let $Z\sim N_{n}(0,I_{n})$. For every
$k\in\mathbb{N}$, let $A_{k}:=\theta_{1}-2^{k}=\min_{1\leq i\leq
n}\theta_{i}-2^{k}$ and $B_{k}:=\theta_{n}+2^{k}=\max_{1\leq i\leq
n}\theta_{i}+2^{k}$, and define $\pi_{k}(s):=s\vee A_{k}\wedge B_{k}$ for
$s\in\mathbb{R}$. Note that if $v\in\Gamma$, then
$\pi_{k}(v):=(\pi_{k}(v_{1}),\dotsc,\pi_{k}(v_{n}))\in\Gamma_{A_{k},B_{k}}=:\tilde{\Gamma}_{k}$.
Moreover, $\theta\in\tilde{\Gamma}_{k}$ in view of our choice of
$A_{k},B_{k}$, and if $v\in\Gamma(\theta,r)$ for some $r>0$, then
$\pi_{k}(v)\in\tilde{\Gamma}_{k}(\theta,r)$. Consequently, for any $r>0$ and
$k\in\mathbb{N}$, we have

$\displaystyle\mathbb{E}\,\biggl{(}\sup_{v\in\Gamma(\theta,r)}\>\lvert
Z^{\top}(v-\theta)\rvert\biggr{)}$
$\displaystyle\leq\mathbb{E}\,\biggl{(}\sup_{v\in\Gamma(\theta,r)}\>\bigl{|}Z^{\top}\bigl{(}\pi_{k}(v)-\theta\bigr{)}\bigr{|}\biggr{)}+\mathbb{E}\,\biggl{(}\sup_{v\in\Gamma(\theta,r)}\>\bigl{|}Z^{\top}\bigl{(}v-\pi_{k}(v)\bigr{)}\bigr{|}\biggr{)}$
$\displaystyle\leq\mathbb{E}\,\biggl{(}\sup_{u\in\tilde{\Gamma}_{k}(\theta,r)}\>\lvert
Z^{\top}(u-\theta)\rvert\biggr{)}+\mathbb{E}\,\biggl{(}\sup_{v\in\Gamma(\theta,r)}\>\bigl{|}Z^{\top}\bigl{(}v-\pi_{k}(v)\bigr{)}\bigr{|}\biggr{)}.$
(S48)

To bound the first term in (S48), observe first that by the triangle
inequality, $\tilde{\Gamma}_{k}(\theta,r)$ has diameter
$d:=\sup\\{\|v-v^{\prime}\|:v,v^{\prime}\in\tilde{\Gamma}_{k}(\theta,r)\\}\leq
2r$. We can now apply Lemma S22 in conjunction with Dudley’s metric entropy
bound for Gaussian processes (e.g. Giné and Nickl, 2016, Theorem 2.3.7) to see
that

$\displaystyle\mathbb{E}\,\biggl{(}\sup_{u\in\tilde{\Gamma}_{k}(\theta,r)}\>\lvert
Z^{\top}(u-\theta)\rvert\biggr{)}$ $\displaystyle\leq
4\sqrt{2}\int_{0}^{d/2}\sqrt{\log
2N\bigl{(}\varepsilon,\tilde{\Gamma}_{k}(\theta,r)\bigr{)}}\,d\varepsilon\leq
4\sqrt{2}\int_{0}^{r}\sqrt{\log
2N(\varepsilon,\Gamma_{A_{k},B_{k}})}\,d\varepsilon$
$\displaystyle\lesssim\int_{0}^{r}\,\bigl{\\{}\sqrt{\log
n}+(B_{k}-A_{k})^{1/4}\tilde{R}(\mathcal{D})^{1/8}\,\varepsilon^{-1/4}\bigr{\\}}\,d\varepsilon$
$\displaystyle\lesssim r\sqrt{\log
n}+\bigl{(}V(\theta)+2^{k}\bigr{)}^{1/4}\tilde{R}(\mathcal{D})^{1/8}\,r^{3/4}.$
(S49)

As for the second term in (S48), we define $I_{1,\ell}(v):=\\{1\leq i\leq
n:A_{\ell+1}<v_{i}\leq A_{\ell}\\}$ and $I_{2,\ell}(v):=\\{1\leq i\leq
n:B_{\ell}\leq v_{i}<B_{\ell+1}\\}$ for
$v\equiv(v_{1},\dotsc,v_{n})\in\mathbb{R}^{n}$ and $\ell\in\mathbb{N}$. Note
that if $j\in I_{1,\ell}(v)$ for some $\ell\geq k$, then
$\theta_{j}-v_{j}\geq\theta_{1}-A_{\ell}=2^{\ell}$ and
$0\leq\pi_{k}(v_{j})-v_{j}<\theta_{1}-A_{\ell+1}=2^{\ell+1}$. Similarly,
$v_{j}-\theta_{j}\geq 2^{\ell}$ and $0\leq v_{j}-\pi_{k}(v_{j})<2^{\ell+1}$
for all $j\in I_{2,\ell}(v)$. Thus, if $v\in\Gamma(\theta,r)$, then
$\sum_{i=1}^{n}(\theta_{i}-v_{i})^{2}\leq r^{2}$, so $\lvert
I_{1,\ell}(v)\rvert\vee\lvert I_{2,\ell}(v)\rvert\leq r^{2}/2^{2\ell}$; in
fact, since $v_{1}\leq\cdots\leq v_{n}$, this means that
$I_{1,\ell}(v)\subseteq\\{1,\dotsc,\lfloor r^{2}/2^{2\ell}\rfloor\\}$ and
$I_{2,\ell}(v)\subseteq\\{n+1-i:1\leq i\leq\lfloor r^{2}/2^{2\ell}\rfloor\\}$.
Consequently, for every $v\in\Gamma(\theta,r)$, we have

$\displaystyle\bigl{|}Z^{\top}\bigl{(}v-\pi_{k}(v)\bigr{)}\bigr{|}\leq\sum_{\ell=k}^{\infty}\,\sum_{i\in
I_{1,\ell}(v)\,\cup\,I_{2,\ell}(v)}\lvert Z_{i}\rvert\,\lvert
v_{i}-\pi_{k}(v_{i})\rvert$
$\displaystyle\leq\sum_{\ell=k}^{\infty}\,2^{\ell+1}\sum_{i\in
I_{1,\ell}(v)\,\cup\,I_{2,\ell}(v)}\lvert Z_{i}\rvert$
$\displaystyle\leq\sum_{\ell=k}^{\infty}\,2^{\ell+1}\sum_{i=1}^{\lfloor
r^{2}/2^{2\ell}\rfloor}(\lvert Z_{i}\rvert+\lvert Z_{n+1-i}\rvert),$

so

$\mathbb{E}\,\biggl{(}\sup_{v\in\Gamma(\theta,r)}\>\bigl{|}Z^{\top}\bigl{(}v-\pi_{k}(v)\bigr{)}\bigr{|}\biggr{)}\leq\sum_{\ell=k}^{\infty}\,2^{\ell+2}\sum_{i=1}^{\lfloor
r^{2}/2^{2\ell}\rfloor}\mathbb{E}(\lvert
Z_{i}\rvert)\lesssim\sum_{\ell=k}^{\infty}\frac{r^{2}}{2^{\ell}}\lesssim\frac{r^{2}}{2^{k}}.$
(S50)

Finally, for any $\tilde{C}\geq 1$, let $k\in\mathbb{N}$ be such that
$2^{k-1}\leq\tilde{C}<2^{k}$. The desired bound (S21) then follows from (S48),
(S49) and (S50). ∎

###  S5.2 Auxiliary results for Section S2.2

Here, we establish the key technical Lemmas S5–S7 that form part of the proof
of Theorem 7, as well as Lemma S8 from the proof of Proposition 8. Lemma S25
below is the starting point for the proof of Lemma S5, and applies to general
configurations of design points $x_{1}<\cdots<x_{n}$ (which need not be
equispaced).

######  Lemma S25.

Let $x_{k}$ be a kink of the convex LSE $\hat{g}_{n}$ based on
$(x_{1},Y_{1}),\dotsc,(x_{n},Y_{n})$. Let
$\bar{x}_{L}:=k^{-1}\sum_{i=1}^{k}x_{i}$ and
$\bar{x}:=n^{-1}\sum_{i=1}^{n}x_{i}$. Then

$\frac{\sum_{i=1}^{k}(x_{i}-\bar{x}_{L})Y_{i}}{\sum_{i=1}^{k}(x_{i}-\bar{x}_{L})^{2}}\leq\frac{\sum_{i=1}^{n}(x_{i}-\bar{x})Y_{i}}{\sum_{i=1}^{n}(x_{i}-\bar{x})^{2}}.$

In other words, the slope of the regression line fitted using
$\\{(x_{i},Y_{i}):1\leq i\leq k\\}$ is at most that of the regression line
fitted using $\\{(x_{i},Y_{i}):1\leq i\leq n\\}$.

###### Proof.

Let $S_{L}^{2}:=\sum_{i=1}^{k}(x_{i}-\bar{x}_{L})^{2}$ and
$S^{2}:=\sum_{i=1}^{n}(x_{i}-\bar{x})^{2}$. Then

$S^{2}\geq\sum_{i=1}^{k}(x_{i}-\bar{x})^{2}=\sum_{i=1}^{k}(x_{i}-\bar{x}_{L})^{2}+k(\bar{x}_{L}-\bar{x})^{2}\geq
S_{L}^{2}>0,$

since $k\geq 2$. The linear functions
$h_{L},h_{R}\colon\mathbb{R}\to\mathbb{R}$ defined by
$h_{L}(x):=S_{L}^{-2}(x-\bar{x}_{L})-S^{-2}(x-\bar{x})$ and
$h_{R}(x):=-S^{-2}(x-\bar{x})$ have slopes $S_{L}^{-2}-S^{-2}\geq 0$ and
$-S^{-2}<0$ respectively. Now let $h\in\mathcal{G}$ be such that
$h(x_{i})=h_{L}(x_{i})$ for $i\in[k]$ and $h(x_{i})=h_{R}(x_{i})$ for $k+1\leq
i\leq n$. Since
$h_{L}(x_{k})=S_{L}^{-2}(x_{k}-\bar{x}_{L})-S^{-2}(x_{k}-\bar{x})\geq-S^{-2}(x_{k}-\bar{x})=h_{R}(x_{k})$,
this means that $h$ is convex on both $[x_{1},x_{k}]$ and $[x_{k},x_{n}]$ (and
locally concave at $x_{k}$, a kink of $\hat{g}_{n}$). Therefore,
$\hat{g}_{n}+\eta h\in\mathcal{G}$ is convex for sufficiently small $\eta>0$,
whence $\sum_{i=1}^{n}h(x_{i})\bigl{(}Y_{i}-\hat{g}_{n}(x_{i})\bigr{)}\leq 0$
by (S3) or Lemma S17.

To establish that
$\sum_{i=1}^{n}h(x_{i})\,Y_{i}=\sum_{i=1}^{k}(h_{L}-h_{R})(x_{i})\,Y_{i}+\sum_{i=1}^{n}h_{R}(x_{i})\,Y_{i}\leq
0$, as claimed in the lemma, it therefore suffices to show that

$\sum_{i=1}^{n}h(x_{i})\,\hat{g}_{n}(x_{i})=\sum_{i=1}^{k}(h_{L}-h_{R})(x_{i})\,\hat{g}_{n}(x_{i})+\sum_{i=1}^{n}h_{R}(x_{i})\,\hat{g}_{n}(x_{i})\leq
0,$

i.e. that the slope of the regression line fitted using
$\\{(x_{i},\hat{g}_{n}(x_{i})):1\leq i\leq k\\}$ is at most that of the
regression line fitted using $\\{(x_{i},\hat{g}_{n}(x_{i})):1\leq i\leq n\\}$.
To this end, for $j\in[n]$, let $K^{1,j}\subseteq\mathbb{R}^{j}$ be the
closed, convex cone of convex sequences based on $x_{1},\dotsc,x_{j}$, as
defined at the start of Section S2, and define
$\hat{v}^{j}:=\bigl{(}\hat{g}_{n}(x_{1}),\dotsc,\hat{g}_{n}(x_{j})\bigr{)}\in
K^{1,j}$. Let $\pm u^{j,0},\pm u^{j,1},u^{j,2},\dotsc,u^{j,j-1}\in K^{1,j}$ be
its generators, where $u_{i}^{j,0}=1$ and
$u_{i}^{j,\ell}=(x_{i}-x_{\ell})^{+}$ for all $i\in[j]$ and $\ell\in[j-1]$ as
in the paragraph containing (6). Since $\hat{v}^{n}\in K^{1,n}$, we can write
$\hat{v}^{n}=\sum_{\ell=0}^{n-1}\hat{\lambda}_{\ell}u^{\ell}$ for some
$\hat{\lambda}_{0},\dotsc,\hat{\lambda}_{n-1}\in\mathbb{R}$ with
$\hat{\lambda}_{2},\dotsc,\hat{\lambda}_{n-1}\geq 0$. Let
$A_{L}:=\\{0,1\\}\cup\\{2\leq\ell\leq k-1:\hat{\lambda}_{\ell}>0\\}$ and
$A_{R}:=\\{k\leq\ell\leq n-1:\hat{\lambda}_{\ell}>0\\}$, so that

$\hat{v}^{k}=\sum_{\ell\in
A_{L}}\hat{\lambda}_{\ell}u^{k,\ell}\quad\text{and}\quad\hat{v}^{n}=\sum_{\ell\in
A_{L}}\hat{\lambda}_{\ell}u^{n,\ell}+\sum_{\ell\in
A_{R}}\hat{\lambda}_{\ell}u^{n,\ell}.$

For $j\in[n]$, let $\tilde{P}_{j}\in\mathbb{R}^{j\times j}$ represent the
orthogonal projection onto $L_{j}:=\operatorname{span}\\{u^{j,0},u^{j,1}\\}$,
so that if $z\in\mathbb{R}^{j}$, then $\tilde{P}_{j}z$ is the vector of fitted
values from ordinary least squares regression based on $\\{(x_{i},z_{i}):1\leq
i\leq j\\}$. We say that $v\in L_{j}$ has _slope_ $b$ if
$v_{i}-v_{i-1}=b(x_{i}-x_{i-1})$ for $2\leq i\leq j$, and denote by
$b_{j\ell}$ the slope of $\tilde{P}_{j}u^{j,\ell}$ for $0\leq\ell\leq j-1$.
Since $k\leq n$, observe that $0\leq b_{k\ell}\leq b_{n\ell}\leq 1$ for all
$0\leq\ell\leq k-1$ and $b_{k\ell}=b_{n\ell}$ for $r\in\\{0,1\\}$. Writing
$b_{k}$ and $b_{n}$ for the slopes of $\tilde{P}_{k}\hat{v}^{k}=\sum_{\ell\in
A_{L}}\hat{\lambda}_{\ell}\tilde{P}_{k}u^{k,\ell}$ and
$\tilde{P}_{n}\hat{v}^{n}=\sum_{\ell\in
A_{L}}\hat{\lambda}_{\ell}\tilde{P}_{n}u^{n,\ell}+\sum_{\ell\in
A_{R}}\hat{\lambda}_{\ell}\tilde{P}_{n}u^{n,\ell}$ respectively, we conclude
that

$b_{k}=\sum_{\ell\in A_{L}}\hat{\lambda}_{\ell}\,b_{k\ell}\leq\sum_{\ell\in
A_{L}}\hat{\lambda}_{\ell}\,b_{n\ell}+\sum_{\ell\in
A_{R}}\hat{\lambda}_{\ell}\,b_{n\ell}=b_{n}.$

This completes the proof. ∎

###### Proof of Lemma S5.

If $\hat{\tau}_{0L}\neq m_{0}$ (i.e. $\\{i:x_{i}\in\mathcal{I}_{01}\\}$ is
non-empty), then $\hat{\tau}_{0L}$ is a kink of $\hat{g}_{n,0}$ in
$(m_{0},(m_{0}+\tilde{m}_{+})/2]$. Define
$N_{01}:=\lvert\\{i:x_{i}\in\mathcal{I}_{01}\\}\rvert\vee 1$,
$N_{0}:=\lvert\\{i:x_{i}\in\mathcal{I}_{0}\\}\rvert$,
$\bar{x}_{01}:=N_{01}^{-1}\sum_{i:x_{i}\in\mathcal{I}_{01}}x_{i}$ and
$\bar{x}_{0}:=N_{0}^{-1}\sum_{i:x_{i}\in\mathcal{I}_{0}}x_{i}$, where we
suppress the dependence on $n$ for convenience. We deduce from Lemma S25 that
if $N_{01}\geq 2$, then

$\frac{\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})Y_{i}}{\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})^{2}}\leq\frac{\sum_{i:x_{i}\in\mathcal{I}_{0}}(x_{i}-\bar{x}_{0})Y_{i}}{\sum_{i:x_{i}\in\mathcal{I}_{0}}(x_{i}-\bar{x}_{0})^{2}},$

and hence that

$\displaystyle\frac{\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})f_{0}(x_{i})}{\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})^{2}}-\frac{\sum_{i:x_{i}\in\mathcal{I}_{0}}(x_{i}-\bar{x}_{0})f_{0}(x_{i})}{\sum_{i:x_{i}\in\mathcal{I}_{0}}(x_{i}-\bar{x}_{0})^{2}}$
$\displaystyle\hskip
85.35826pt\leq\frac{\sum_{i:x_{i}\in\mathcal{I}_{0}}(x_{i}-\bar{x}_{0})\,\xi_{i}}{\sum_{i:x_{i}\in\mathcal{I}_{0}}(x_{i}-\bar{x}_{0})^{2}}-\frac{\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})\,\xi_{i}}{\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})^{2}}.$
(S51)

Let $\beta_{L1},\beta_{L2}$ be equal to the first and second terms
respectively on the right-hand side of (S51) when $N_{01}\geq 2$ (and set
$\beta_{L1}=\beta_{L2}=0$ otherwise). Taking into account the randomness of
the intervals $\mathcal{I}_{01},\mathcal{I}_{0}$, we claim that
$(\beta_{L1}-\beta_{L2})\sqrt{n(\hat{\tau}_{0L}-m_{0})^{3}}=O_{p}(\sqrt{\log
n})$. Indeed, for fixed $1\leq a<b\leq n$, define
$\bar{x}_{a:b}:=(b-a+1)^{-1}\sum_{i=a}^{b}x_{i}$,
$S_{ab}^{2}:=\sum_{i=a}^{b}(x_{i}-\bar{x}_{a:b})^{2}$ and
$\tilde{\beta}_{ab}:=S_{ab}^{-2}\,\sum_{i=a}^{b}(x_{i}-\bar{x}_{a:b})\,\xi_{i}$.
Under Assumption 2, the design points $x_{i}\equiv x_{ni}=i/n$ are equispaced
and the errors $\xi_{i}$ are sub-Gaussian with parameter 1, so
$S_{ab}^{2}\asymp(b-a)^{3}/n^{2}$ and $\tilde{\beta}_{ab}$ has sub-Gaussian
parameter $S_{ab}^{-2}\asymp n^{2}/(b-a)^{3}=n^{-1}(x_{b}-x_{a})^{-3}$.
Therefore, $\tilde{\beta}_{\mathrm{max}}:=\max_{1\leq a<b\leq
n}\,\lvert\tilde{\beta}_{ab}\rvert\sqrt{n(x_{b}-x_{a})^{3}}=O_{p}(\sqrt{\log
n})$ (e.g. Giné and Nickl, 2016, Lemma 2.3.4), so

$\displaystyle\sqrt{n(\hat{\tau}_{0L}-m_{0})^{3}}\,\lvert\beta_{L1}\rvert\leq
2^{3/2}\,\tilde{\beta}_{\mathrm{max}}$ $\displaystyle=O_{p}(\sqrt{\log n})$
$\displaystyle\sqrt{n(\hat{\tau}_{0L}-m_{0})^{3}}\,\lvert\beta_{L2}\rvert\leq\sqrt{n(\tilde{m}_{+}-m_{0})^{3}}\,\lvert\beta_{L2}\rvert\leq
2^{3/2}\,\tilde{\beta}_{\mathrm{max}}$ $\displaystyle=O_{p}(\sqrt{\log n}),$
(S52)

which justifies the claim above. Now let $b_{L1},b_{L2}$ be equal to the first
and second terms respectively on the left-hand side of (S51) when $N_{01}\geq
2$ (and set $b_{L1}=b_{L2}=0$ otherwise). For $\gamma>1$ and
$x_{a}\in(m_{0},1]$, let
$s_{\gamma}(x_{a}):=n^{-1}\sum_{i:x_{i}\in(m_{0},x_{a}]}(x_{i}-m_{0})^{\gamma}$,
and observe that if $x_{j-1}\leq m_{0}<x_{j}<x_{a}$, then

$\displaystyle\frac{(x_{a}-m_{0})^{\gamma+1}}{\gamma+1}\leq\int_{x_{j-1}}^{x_{a}}(x-m_{0})^{\gamma}\,dx\leq
s_{\gamma}(x_{a})$ $\displaystyle\leq\int_{x_{j}}^{x_{a+1}}(x_{a}\wedge
x-m_{0})^{\gamma}\,dx$
$\displaystyle\leq\frac{(x_{a}-m_{0})^{\gamma+1}}{\gamma+1}\left(1+\frac{\gamma+1}{n(x_{a}-m_{0})}\right).$
(S53)

We claim that if $\hat{\tau}_{0L}-m_{0}\geq 2n^{-1/(2\alpha+1)}$, then

$\displaystyle b_{L1}$
$\displaystyle=f_{0}^{\prime}(m_{0})-B\bigl{(}1+o_{p}(1)\bigr{)}\,\frac{s_{\alpha+1}(\hat{\tau}_{0L})-2^{-1}s_{\alpha}(\hat{\tau}_{0L})(\hat{\tau}_{0L}-m_{0})}{s_{2}(\hat{\tau}_{0L})-2^{-1}s_{1}(\hat{\tau}_{0L})(\hat{\tau}_{0L}-m_{0})}$
$\displaystyle\geq f_{0}^{\prime}(m_{0})-\frac{6\alpha
B}{(\alpha+1)(\alpha+2)}\bigl{(}1+o_{p}(1)\bigr{)}(\hat{\tau}_{0L}-m_{0})^{\alpha-1}$
(S54)

and

$\displaystyle b_{L2}$
$\displaystyle=f_{0}^{\prime}(m_{0})-B\bigl{(}1+o_{p}(1)\bigr{)}\,\frac{s_{\alpha+1}(\tilde{m}_{+})-2^{-1}s_{\alpha}(\tilde{m}_{+})(\tilde{m}_{+}-m_{0})}{s_{2}(\tilde{m}_{+})-2^{-1}s_{1}(\tilde{m}_{+})(\tilde{m}_{+}-m_{0})}$
$\displaystyle\leq f_{0}^{\prime}(m_{0})-\frac{6\alpha
B}{(\alpha+1)(\alpha+2)}\bigl{(}1+o_{p}(1)\bigr{)}(\tilde{m}_{+}-m_{0})^{\alpha-1}$
$\displaystyle\leq f_{0}^{\prime}(m_{0})-2^{\alpha-1}\frac{6\alpha
B}{(\alpha+1)(\alpha+2)}\bigl{(}1+o_{p}(1)\bigr{)}(\hat{\tau}_{0L}-m_{0})^{\alpha-1}.$
(S55)

To see this, recall that under (13) in Assumption 2, we can write
$f_{0}(x)=f_{0}(m_{0})+f_{0}^{\prime}(m_{0})(x-m_{0})-B\bigl{(}1+\eta(x-m_{0})\bigr{)}\operatorname{sgn}(x-m_{0})\lvert
x-m_{0}\rvert^{\alpha}$ for $x\in[0,1]$ when $\alpha>1$, where
$\eta(x-m_{0})\to 0$ as $x\to m_{0}$. Writing
$x_{i}-\bar{x}_{01}=(x_{i}-m_{0})-2^{-1}(\hat{\tau}_{0L}-m_{0})$, we see that

$\displaystyle\textstyle\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})\bigl{(}f_{0}(m_{0})+f_{0}^{\prime}(m_{0})(x_{i}-m_{0})\bigr{)}$
$\displaystyle\textstyle=f_{0}^{\prime}(m_{0})\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})(x_{i}-m_{0})$
$\displaystyle\textstyle=f_{0}^{\prime}(m_{0})\bigl{(}s_{2}(\hat{\tau}_{0L})-2^{-1}s_{1}(\hat{\tau}_{0L})(\hat{\tau}_{0L}-m_{0})\bigr{)}$
(S56)
$\displaystyle\textstyle=f_{0}^{\prime}(m_{0})\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})^{2}$
$\displaystyle\text{and}\qquad\textstyle\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})(x_{i}-m_{0})^{\alpha}$
$\displaystyle=s_{\alpha+1}(\hat{\tau}_{0L})-2^{-1}s_{\alpha}(\hat{\tau}_{0L}).$
(S57)

Moreover, since
$\omega(\delta):=\sup\,\\{\lvert\eta(x-m_{0})\rvert:x\in[0,1],\,\lvert
x-m_{0}\rvert\leq\delta\\}\to 0$ as $\delta\to 0$ and
$\tilde{m}_{+}-m_{0}=o_{p}(1)$ by Proposition 2(a), we have

$\displaystyle\textstyle\lvert\sum_{i:x_{i}\in\mathcal{I}_{01}}(x_{i}-\bar{x}_{01})\,\eta(x_{i}-m_{0})(x_{i}-m_{0})^{\alpha}\rvert$
$\displaystyle\textstyle\leq\omega(\lvert\tilde{m}_{+}-m_{0}\rvert)\sum_{i:x_{i}\in\mathcal{I}_{01}}\lvert
x_{i}-\bar{x}_{01}\rvert(x_{i}-m_{0})^{\alpha}$
$\displaystyle\textstyle=o_{p}(1)\,\bigl{(}s_{\alpha+1}(\hat{\tau}_{0L})+2^{-1}s_{\alpha}(\hat{\tau}_{0L})(\hat{\tau}_{0L}-m_{0})\bigr{)}.$
(S58)

Combining (S56), (S57) and (S58), we obtain the first equality in (S54). On
the event $\\{\hat{\tau}_{0L}-m_{0}\geq 2n^{-1/(2\alpha+1)}\\}$, we find using
(S53) that

$\displaystyle\frac{s_{\alpha+1}(\hat{\tau}_{0L})-2^{-1}s_{\alpha}(\hat{\tau}_{0L})(\hat{\tau}_{0L}-m_{0})}{s_{2}(\hat{\tau}_{0L})-2^{-1}s_{1}(\hat{\tau}_{0L})(\hat{\tau}_{0L}-m_{0})}$
$\displaystyle\leq\frac{\frac{\alpha}{2(\alpha+1)(\alpha+2)}+\frac{1}{n(\hat{\tau}_{0L}-m_{0})}}{\frac{1}{12}-\frac{1}{2n(\hat{\tau}_{0L}-m_{0})}}(\hat{\tau}_{0L}-m_{0})^{\alpha-1}$
$\displaystyle\leq\bigl{(}1+o(1)\bigr{)}\frac{6\alpha}{(\alpha+1)(\alpha+2)}(\hat{\tau}_{0L}-m_{0})^{\alpha-1},$

which justifies the lower bound on $b_{L1}$ in (S54). We can derive (S55)
similarly by first establishing analogues of (S56), (S57) and (S58), and then
applying (S53) to see that

$\displaystyle\frac{s_{\alpha+1}(\tilde{m}_{+})-2^{-1}s_{\alpha}(\tilde{m}_{+})(\tilde{m}_{+}-m_{0})}{s_{2}(\tilde{m}_{+})-2^{-1}s_{1}(\tilde{m}_{+})(\tilde{m}_{+}-m_{0})}$
$\displaystyle\geq\frac{\frac{\alpha}{2(\alpha+1)(\alpha+2)}-\frac{1}{2n(\tilde{m}_{+}-m_{0})}}{\frac{1}{12}+\frac{1}{n(\tilde{m}_{+}-m_{0})}}(\tilde{m}_{+}-m_{0})^{\alpha-1}$
$\displaystyle\geq\bigl{(}1+o(1)\bigr{)}\frac{6\alpha}{(\alpha+1)(\alpha+2)}(\tilde{m}_{+}-m_{0})^{\alpha-1}$

on the event $E_{n}^{+}\supseteq\\{\hat{\tau}_{0L}-m_{0}\geq
2n^{-1/(2\alpha+1)}\\}$. Since $\tilde{m}_{+}-m_{0}\geq
2(\hat{\tau}_{0L}-m_{0})$ and $\alpha>1$, this yields the upper bound on
$b_{L2}$ in (S55).

Thus, on the event $\\{\hat{\tau}_{0L}-m_{0}\geq 2n^{-1/(2\alpha+1)}\\}$, we
can apply (S54), (S55), (S51) and (S52) in that order to deduce that

$\displaystyle(2^{\alpha-1}-1)\frac{6\alpha
B}{(\alpha+1)(\alpha+2)}\bigl{(}1+o_{p}(1)\bigr{)}\sqrt{n}(\hat{\tau}_{0L}-m_{0})^{\alpha+\frac{1}{2}}$
$\displaystyle\leq(b_{L1}-b_{L2})\sqrt{n(\hat{\tau}_{0L}-m_{0})^{3}}$ (S59)
$\displaystyle\leq(\beta_{L1}-\beta_{L2})\sqrt{n(\hat{\tau}_{0L}-m_{0})^{3}}$
$\displaystyle=O_{p}(\sqrt{\log n}).$

We conclude that $\hat{\tau}_{0L}-m_{0}=O_{p}\bigl{(}(n/\log
n)^{-1/(2\alpha+1)}\bigr{)}$, as required. ∎

###### Proof of Lemma S6.

Since $C_{n}\to\infty$, we have

$t_{n}=\sqrt{C_{n}}\,(n/\log n)^{-1/(2\alpha+1)}<4^{-1}C_{n}(n/\log
n)^{-1/(2\alpha+1)}=u_{n}/2$

for all sufficiently large $n$. For each $n$, let $a_{n}:=\lceil
n(m_{0}+u_{n}/2)\rceil$ and $b_{n}:=\lfloor n(m_{0}+u_{n})\rfloor$, so that
$x_{a_{n}}<m_{0}+u_{n}/2\leq x_{a_{n}+1}$ and $x_{b_{n}-1}\leq
m_{0}+u_{n}<x_{b_{n}}$. Then for all sufficiently large $n$, we have
$\inf_{(a,b)\in\mathcal{T}_{n}}\inf_{c_{0},c_{1}}\|\theta^{a,b}-c_{0}\mathbf{1}^{a,b}-c_{1}x^{a,b}\|^{2}\geq\inf_{c_{0},c_{1}}\|\theta^{a_{n},b_{n}}-c_{0}\mathbf{1}^{a_{n},b_{n}}-c_{1}x^{a_{n},b_{n}}\|^{2}=:R_{n}$.

For $x\in[m_{0},1]$, recall from (13) in Assumption 2 that

$f_{0}(x)=\begin{cases}f_{0}(m_{0})+f_{0}^{\prime}(m_{0})(x-m_{0})-B\bigl{(}1+\eta(x-m_{0})\bigr{)}(x-m_{0})^{\alpha}\quad&\text{when
}\alpha>1\\\
f_{0}(m_{0})+B\bigl{(}1+\eta(x-m_{0})\bigr{)}(x-m_{0})^{\alpha}\quad&\text{when
}\alpha\in(0,1),\end{cases}$

where $\eta(x-m_{0})\to 0$ as $x\to m_{0}$. For each $n$, let
$\widetilde{\theta}_{i}^{a_{n},b_{n}}:=B\bigl{(}1+\eta(x_{i}-m_{0})\bigr{)}(x_{i}-m_{0})^{\alpha}$
for $m_{0}\leq a_{n}\leq i\leq b_{n}$ and
$\widetilde{\theta}^{a_{n},b_{n}}:=\bigl{(}\widetilde{\theta}_{a_{n}}^{a_{n},b_{n}},\dotsc,\widetilde{\theta}_{b_{n}}^{a_{n},b_{n}}\bigr{)}$,
so that
$\widetilde{\theta}^{a_{n},b_{n}}+\theta^{a_{n},b_{n}}\in\operatorname{span}\\{\mathbf{1}^{a_{n},b_{n}},x^{a_{n},b_{n}}\\}=:A^{a_{n},b_{n}}$
when $\alpha>1$ and $\widetilde{\theta}^{a_{n},b_{n}}-\theta^{a_{n},b_{n}}\in
A^{a_{n},b_{n}}$ when $\alpha\in(0,1)$. In addition, let
$\bar{x}_{a_{n},b_{n}}:=(b_{n}-a_{n}+1)^{-1}\sum_{i=a_{n}}^{b_{n}}x_{i}$, so
that
$\widetilde{x}^{a_{n},b_{n}}:=x^{a_{n},b_{n}}-\bar{x}_{a_{n},b_{n}}\mathbf{1}^{a_{n},b_{n}}$
satisfies
$\langle\mathbf{1}^{a_{n},b_{n}},\widetilde{x}^{a_{n},b_{n}}\rangle=0$ and
$A^{a_{n},b_{n}}=\operatorname{span}\\{\mathbf{1}^{a_{n},b_{n}},\widetilde{x}^{a_{n},b_{n}}\\}$.
Then

$R_{n}=\inf_{v\in A^{a_{n},b_{n}}}\|\theta^{a_{n},b_{n}}-v\|^{2}=\inf_{v\in
A^{a_{n},b_{n}}}\|\widetilde{\theta}^{a_{n},b_{n}}-v\|^{2}=\|\widetilde{\theta}^{a_{n},b_{n}}\|^{2}-c_{n0}^{2}\,\|\mathbf{1}^{a_{n},b_{n}}\|^{2}-c_{n1}^{2}\,\|\widetilde{x}^{a_{n},b_{n}}\|^{2},$
(S60)

where
$c_{n0}:=\langle\widetilde{\theta}^{a_{n},b_{n}},\mathbf{1}^{a_{n},b_{n}}\rangle/\|\mathbf{1}^{a_{n},b_{n}}\|^{2}$
and
$c_{n1}:=\langle\widetilde{\theta}^{a_{n},b_{n}},\widetilde{x}^{a_{n},b_{n}}\rangle/\|\widetilde{x}^{a_{n},b_{n}}\|^{2}$.
We will consider in turn the three terms on the right-hand side of (S60). For
each $n$, let $M_{n}:=nu_{n}$ and $z_{n,i}:=(x_{i}-m_{0})/u_{n}$ for
$a_{n}\leq i\leq b_{n}$, where $x_{i}\equiv x_{ni}=i/n$ by Assumption 2. Then
$z_{n,i+1}-z_{n,i}=1/M_{n}$ for all $a_{n}\leq i<b_{n}$, and
$z_{n,a_{n}}=1/2+o(1/M_{n})$ and $z_{n,b_{n}}=1+o(1/M_{n})$ by the definitions
of $a_{n},b_{n}$. Moreover, let
$\tilde{\eta}_{n}(z):=\bigl{(}1+\eta(u_{n}z)\bigr{)}^{2}-1$ for $z\in[1/2,1]$
and note that $\sup_{z\in[1/2,1]}\,\lvert\tilde{\eta}_{n}(z)\rvert=o(1)$ as
$n\to\infty$. The first term in (S60) can now be written as

$\displaystyle\|\widetilde{\theta}^{a_{n},b_{n}}\|^{2}$
$\displaystyle=\sum_{i=a_{n}}^{b_{n}}B^{2}\bigl{(}1+\eta(x_{i}-m_{0})\bigr{)}^{2}(x_{i}-m_{0})^{2\alpha}$
$\displaystyle=nu_{n}^{2\alpha+1}\sum_{i=a_{n}}^{b_{n}}\frac{B^{2}}{nu_{n}}\bigl{(}1+\eta(x_{i}-m_{0})\bigr{)}^{2}\left(\frac{x_{i}-m_{0}}{u_{n}}\right)^{2\alpha}$
$\displaystyle=B^{2}nu_{n}^{2\alpha+1}\sum_{i=a_{n}}^{b_{n}}M_{n}^{-1}\bigl{(}1+\tilde{\eta}_{n}(z_{n,i})\bigr{)}\,z_{n,i}^{2\alpha}.$
(S61)

Defining $F(z):=z^{\alpha}$ for $z\in[1/2,1]$ and noting that
$M_{n}=nu_{n}=2^{-1}C_{n}(n^{2\alpha}\log n)^{1/(2\alpha+1)}\to\infty$, we
have

$\textstyle\sum_{i=a_{n}}^{b_{n}}M_{n}^{-1}z_{n,i}^{2\alpha}=\sum_{j=0}^{b_{n}-a_{n}}M_{n}^{-1}\,F(z_{n,a_{n}}+j/M_{n})^{2}=\int_{1/2}^{1}F(z)^{2}\,dz+o(1)=\bigl{(}1+o(1)\bigr{)}\int_{1/2}^{1}z^{2\alpha}\,dz$
(S62)

as $n\to\infty$, by a Riemann sum approximation to the (uniformly) continuous
function $F$ on $[1/2,1]$. Since
$\bigl{|}\sum_{i=a_{n}}^{b_{n}}M_{n}^{-1}\,\tilde{\eta}_{n}(z_{n,i})\,z_{n,i}^{2\alpha}\bigr{|}\leq\sup_{z\in[1/2,1]}\,\lvert\tilde{\eta}_{n}(z)\rvert\,\sum_{i=a_{n}}^{b_{n}}M_{n}^{-1}z_{n,i}^{2\alpha}=o(1)$,
we deduce that

$\textstyle\|\widetilde{\theta}^{a_{n},b_{n}}\|^{2}=B^{2}nu_{n}^{2\alpha+1}\bigl{(}1+o(1)\bigr{)}\int_{1/2}^{1}z^{2\alpha}\,dz.$
(S63)

For $\gamma\geq 0$, we can use the rescaled design points $z_{n,i}$ and argue
as in (S61) and (S62) to see that

$\textstyle
s_{n,\gamma}:=\sum_{i=a_{n}}^{b_{n}}(x_{i}-m_{0})^{\gamma}=nu_{n}^{\gamma+1}\textstyle\sum_{i=a_{n}}^{b_{n}}M_{n}^{-1}z_{n,i}^{\gamma}=nu_{n}^{\gamma+1}\bigl{(}1+o(1)\bigr{)}\textstyle\int_{1/2}^{1}z^{\gamma}\,dz$

and

$\displaystyle\textstyle\tilde{s}_{n,\gamma}:=\sum_{i=a_{n}}^{b_{n}}\bigl{(}1+\eta(x_{i}-m_{0})\bigr{)}(x_{i}-m_{0})^{\gamma}$
$\displaystyle=nu_{n}^{\gamma+1}\textstyle\sum_{i=a_{n}}^{b_{n}}M_{n}^{-1}\bigl{(}1+\eta(u_{n}z_{n,i})\bigr{)}z_{n,i}^{\gamma}$
$\displaystyle=nu_{n}^{\gamma+1}\bigl{(}1+o(1)\bigr{)}\textstyle\int_{1/2}^{1}z^{\gamma}\,dz;$

see also (S53), (S57) and (S58) in the proof of Lemma S5. Now writing
$x_{i}-\bar{x}_{a_{n},b_{n}}=(x_{i}-m_{0})-(\bar{x}_{a_{n},b_{n}}-m_{0})$ for
$a_{n}\leq i\leq b_{n}$ and $\bar{x}_{a_{n},b_{n}}-m_{0}=s_{n,1}/s_{n,0}$, we
have

$\displaystyle\langle\widetilde{\theta}^{a_{n},b_{n}},\mathbf{1}^{a_{n},b_{n}}\rangle$
$\displaystyle=\textstyle\sum_{i=a_{n}}^{b_{n}}B\bigl{(}1+\eta(x_{i}-m_{0})\bigr{)}(x_{i}-m_{0})^{\alpha}=B\tilde{s}_{n\alpha}$
$\displaystyle\langle\widetilde{\theta}^{a_{n},b_{n}},\widetilde{x}^{a_{n},b_{n}}\rangle$
$\displaystyle=\textstyle\sum_{i=a_{n}}^{b_{n}}B\bigl{(}1+\eta(x_{i}-m_{0})\bigr{)}(x_{i}-\bar{x}_{a_{n},b_{n}})(x_{i}-m_{0})^{\alpha}=B(\tilde{s}_{n,\alpha+1}-\tilde{s}_{n,\alpha}s_{n,1}/s_{n,0})$
$\displaystyle\|\mathbf{1}^{a_{n},b_{n}}\|^{2}$
$\displaystyle=\textstyle\sum_{i=a_{n}}^{b_{n}}1=s_{n,0}$
$\displaystyle\|\widetilde{x}^{a_{n},b_{n}}\|^{2}$
$\displaystyle=\textstyle\sum_{i=a_{n}}^{b_{n}}(x_{i}-\bar{x}_{a_{n},b_{n}})^{2}=\sum_{i=a_{n}}^{b_{n}}\\{(x_{i}-m_{0})^{2}-(\bar{x}_{a_{n},b_{n}}-m_{0})^{2}\\}=s_{n,2}-s_{n,1}^{2}/s_{n,0}.$

Setting $\bar{z}:=3/4$, we note that
$s_{n,1}/s_{n,0}=u_{n}\bigl{(}1+o(1)\bigr{)}\bar{z}$. Therefore, the second
and third terms in (S60) can be written as

$\displaystyle c_{n0}^{2}\,\|\mathbf{1}^{a_{n},b_{n}}\|^{2}$
$\displaystyle=\frac{\langle\widetilde{\theta}^{a_{n},b_{n}},\mathbf{1}^{a_{n},b_{n}}\rangle^{2}}{\|\mathbf{1}^{a_{n},b_{n}}\|^{2}}$
$\displaystyle=\frac{B^{2}\tilde{s}_{n,\alpha}^{2}}{s_{n,0}}=B^{2}nu_{n}^{2\alpha+1}\bigl{(}1+o(1)\bigr{)}\\!\left(\frac{\int_{1/2}^{1}z^{\alpha}\,dz}{\int_{1/2}^{1}\,dz}\right)^{2}$
$\displaystyle c_{n1}^{2}\,\|\widetilde{x}^{a_{n},b_{n}}\|^{2}$
$\displaystyle=\frac{\langle\widetilde{\theta}^{a_{n},b_{n}},\widetilde{x}^{a_{n},b_{n}}\rangle^{2}}{\|\widetilde{x}^{a_{n},b_{n}}\|^{2}}$
$\displaystyle=\frac{B^{2}(\tilde{s}_{n,\alpha+1}-\tilde{s}_{n,\alpha}s_{n,1}/s_{n,0})^{2}}{s_{n,2}-s_{n,1}^{2}/s_{n,0}}$
$\displaystyle=B^{2}nu_{n}^{2\alpha+1}\bigl{(}1+o(1)\bigr{)}\\!\left(\frac{\int_{1/2}^{1}\,(z-\bar{z})z^{\alpha}\,dz}{\int_{1/2}^{1}\,(z-\bar{z})^{2}\,dz}\right)^{2}.$
(S64)

Now for $G,\tilde{G}\in L^{2}[1/2,1]$, let $\langle
G,\tilde{G}\rangle_{\ast}:=\int_{1/2}^{1}G(z)\,\tilde{G}(z)\,dz$ and
$\|G\|_{\ast}^{2}:=\langle G,G\rangle_{\ast}$. Moreover, define
$G_{0},G_{1}\colon[1/2,1]\to\mathbb{R}$ by $G_{0}(z):=1$ and
$G_{1}(z):=z-\bar{z}$. These span the (closed) subspace $\mathcal{L}$ of
affine functions $G\colon[1/2,1]\to\mathbb{R}$ and satisfy $\langle
G_{0},G_{1}\rangle_{\ast}=0$. Let $c_{j}^{*}:=\langle
F,G_{j}\rangle_{\ast}/\|G_{j}\|_{\ast}^{2}$ for $j=0,1$, so that
$F^{*}:=c_{0}^{*}G_{0}+c_{1}^{*}G_{1}$ is the projection of $F\colon z\mapsto
z^{\alpha}$ onto $\mathcal{L}$ with respect to
$\langle\cdot\,,\cdot\rangle_{\ast}$. Since $\alpha\neq 1$ in Assumption 2, we
have $F\notin\mathcal{L}$, so

$\rho_{\alpha}:=\|F\|_{\ast}^{2}-c_{0}^{*}\|G_{0}\|_{\ast}^{2}-c_{1}^{*}\|G_{1}\|_{\ast}^{2}=\|F-c_{0}^{*}G_{0}-c_{1}^{*}G_{1}\|_{\ast}^{2}=\|F-F^{*}\|_{\ast}^{2}=\textstyle\int_{1/2}^{1}\,(F-F^{*})^{2}>0.$
(S65)

Thus, for all sufficiently large $n$, we can combine (S60), (S63), (S64) and
(S65) to conclude that

$\displaystyle\inf_{(a,b)\in\mathcal{T}_{n}}\inf_{c_{0},c_{1}}\|\theta^{a,b}-c_{0}\mathbf{1}^{a,b}-c_{1}x^{a,b}\|^{2}\geq
R_{n}$
$\displaystyle=B^{2}nu_{n}^{2\alpha+1}\bigl{(}1+o(1)\bigr{)}\bigl{(}\|F\|_{\ast}^{2}-c_{0}^{*}\|G_{0}\|_{\ast}^{2}-c_{1}^{*}\|G_{1}\|_{\ast}^{2}\bigr{)}$
$\displaystyle=\rho_{\alpha}B^{2}nu_{n}^{2\alpha+1}\bigl{(}1+o(1)\bigr{)}.$

Since $u_{n}=2^{-1}C_{n}(n/\log
n)^{-1/(2\alpha+1)}=2^{-1}C_{n}\bigl{(}1+o(1)\bigr{)}(n/\log
n)^{-1/(2\alpha+1)}$ for all $n$, this completes the proof. ∎

###### Proof of Lemma S7.

Let $h\in\mathcal{G}$ be such that
$h(x_{i}):=\bigl{(}\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\bigr{)}_{\tilde{k}\vee
i\wedge\tilde{k}^{\prime}}$ for $i\in[n]$. Since
$x_{\tilde{k}},x_{\tilde{k}^{\prime}}$ are successive knots of
$\hat{f}_{n}^{m_{0}}\in\mathcal{F}^{m_{0}}$ by assumption,
$\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}=\bigl{(}\hat{f}_{n}^{m_{0}}(x_{\tilde{k}}),\dotsc,\hat{f}_{n}^{m_{0}}(x_{\tilde{k}^{\prime}})\bigr{)}$
is an affine sequence. Recalling that $f_{0}\in\mathcal{F}^{m_{0}}$ and
$\theta^{\tilde{k},\tilde{k}^{\prime}}=\bigl{(}f_{0}(x_{\tilde{k}}),\dotsc,f_{0}(x_{\tilde{k}^{\prime}})\bigr{)}$,
we can verify that $\hat{f}_{n}^{m_{0}}+\eta h\in\mathcal{H}^{m_{0}}$ for all
sufficiently small $\eta>0$. Defining
$\breve{\theta}:=\bigl{(}\hat{f}_{n}^{m_{0}}(x_{1}),\dotsc,\hat{f}_{n}^{m_{0}}(x_{n})\bigr{)}$,
$\theta:=\bigl{(}f_{0}(x_{1}),\dotsc,f_{0}(x_{n})\bigr{)}$ and
$Y^{\tilde{k},\tilde{k}^{\prime}}:=(Y_{\tilde{k}},\dotsc,Y_{\tilde{k}^{\prime}})$,
we deduce from (S3) or Lemma S17 that

$\displaystyle 0$
$\displaystyle\geq\sum_{i=1}^{n}h(x_{i})(Y_{i}-\breve{\theta}_{i})$
$\displaystyle=\bigl{(}\theta_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\bigr{)}\sum_{i=1}^{\tilde{k}-1}\,(Y_{i}-\breve{\theta}_{i})+\langle\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}},Y^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\rangle+\bigl{(}\theta_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\bigr{)}\sum_{i=\tilde{k}^{\prime}}^{n}\,(Y_{i}-\breve{\theta}_{i}).$

Now since $x_{\tilde{k}},x_{\tilde{k}^{\prime}}$ are knots of
$\hat{f}_{n}^{m_{0}}$, it follows from (S4) in the proof of Lemma S1
(specialised to the setting of Proposition S4) that

$\textstyle\lvert\sum_{i=1}^{\tilde{k}-1}\,(Y_{i}-\breve{\theta}_{i})\rvert\leq\lvert
Y_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\rvert\leq\lvert\theta_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\rvert+\lvert\xi_{\tilde{k}}\rvert\;\;\;\text{and}\;\;\;\textstyle\lvert\sum_{i=\tilde{k}^{\prime}}^{n}\,(Y_{i}-\breve{\theta}_{i})\rvert\leq\lvert
Y_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\rvert\leq\lvert\theta_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\rvert+\lvert\xi_{\tilde{k}^{\prime}}\rvert.$

Therefore, writing
$Y^{\tilde{k},\tilde{k}^{\prime}}=\theta^{\tilde{k},\tilde{k}^{\prime}}+\xi^{\tilde{k},\tilde{k}^{\prime}}$,
we have

$\|\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\|^{2}\leq\langle\xi^{\tilde{k},\tilde{k}^{\prime}},\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}-\theta^{\tilde{k},\tilde{k}^{\prime}}\rangle+\lvert\theta_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\rvert\,\bigl{(}\lvert\theta_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\rvert+\lvert\xi_{\tilde{k}}\rvert\bigr{)}+\lvert\theta_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\rvert\,\bigl{(}\lvert\theta_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\rvert+\lvert\xi_{\tilde{k}^{\prime}}\rvert\bigr{)}.$

Since
$\lvert\theta_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\rvert\vee\lvert\theta_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\rvert\leq\|\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\|$,
this implies that

$\|\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\|\leq\frac{\langle\xi^{\tilde{k},\tilde{k}^{\prime}},\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}-\theta^{\tilde{k},\tilde{k}^{\prime}}\rangle}{\|\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\|}+\lvert\xi_{\tilde{k}}\rvert+\lvert\xi_{\tilde{k}^{\prime}}\rvert+\lvert\theta_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\rvert+\lvert\theta_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\rvert.$

Finally, $\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}$ is an affine sequence
belonging to
$A_{\tilde{k},\tilde{k}^{\prime}}=\operatorname{span}\\{\mathbf{1}^{\tilde{k},\tilde{k}^{\prime}},x^{\tilde{k},\tilde{k}^{\prime}}\\}$,
so
$\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\in
L_{\tilde{k},\tilde{k}^{\prime}}=\operatorname{span}\\{\theta^{\tilde{k},\tilde{k}^{\prime}},\mathbf{1}^{\tilde{k},\tilde{k}^{\prime}},x^{\tilde{k},\tilde{k}^{\prime}}\\}$
and it follows as in (S18) that

$\frac{\langle\xi^{\tilde{k},\tilde{k}^{\prime}},\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}-\theta^{\tilde{k},\tilde{k}^{\prime}}\rangle}{\|\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\|}\leq\|\Pi_{\tilde{k},\tilde{k}^{\prime}}\,\xi^{\tilde{k},\tilde{k}^{\prime}}\|\leq\max_{1\leq
a\leq b\leq n}\,\|\Pi_{a,b}\,\xi^{a,b}\|.$

Since
$\lvert\theta_{\tilde{k}}-\breve{\theta}_{\tilde{k}}\rvert+\lvert\theta_{\tilde{k}^{\prime}}-\breve{\theta}_{\tilde{k}^{\prime}}\rvert\leq
2\max_{1\leq i\leq n}\,\lvert\theta_{i}-\breve{\theta}_{i}\rvert=2\max_{1\leq
i\leq n}\,\lvert(\hat{f}_{n}^{m_{0}}-f_{0})(x_{i})\rvert$, we conclude that

$\|\theta^{\tilde{k},\tilde{k}^{\prime}}-\breve{\theta}^{\tilde{k},\tilde{k}^{\prime}}\|\leq\max_{1\leq
a\leq b\leq n}\,\|\Pi_{a,b}\,\xi^{a,b}\|+2\max_{1\leq i\leq
n}\,\lvert(\hat{f}_{n}^{m_{0}}-f_{0})(x_{i})\rvert+2\max_{1\leq i\leq
n}\,\lvert\xi_{i}\rvert=\Xi,$

as required. ∎

###### Proof of Lemma S8.

For $\delta\in(0,(1-m_{0})/2]$ and $t\in[0,(1-m_{0})/\delta]$, let

$g_{0,\delta}(t):=\delta^{-\alpha}\bigl{(}f_{0}(m_{0})+f_{0}^{\prime}(m_{0})\delta
t-f_{0}(m_{0}+\delta t)\bigr{)}\quad\text{and}\quad
u_{\delta}:=\delta^{-(\alpha-1)}\bigl{(}f_{0}^{\prime}(m_{0})-u(m_{0}+\delta)\bigr{)},$

where $\alpha>1$. Then $g_{0,\delta}$ is convex and non-negative on $[0,2]$
for each such $\delta$, and since $u(m_{0}+\delta)$ was taken to be a
subgradient of $\left.f_{0}\right|_{[m_{0},1]}$ at $m_{0}+\delta$, we see that
$u_{\delta}$ is a subgradient of $g_{0,\delta}$ at $t=1$. Assumption 2 ensures
that $g_{0,\delta}$ converges uniformly on $[0,2]$ to the function
$g_{0}\colon t\mapsto Bt^{\alpha}$ as $\delta\to 0$, and so by taking
$C=(0,2)$ in Seijo and Sen (2011, Lemma 3.10), we deduce further that
$u_{\delta}\to g_{0}^{\prime}(1)=B\alpha$ as $\delta\to 0$.

Moreover, for $\delta\in(0,(1-m_{0})/2]$ and $t\in[0,1]$, let

$\displaystyle g_{1,\delta}(t)$
$\displaystyle:=\delta^{-\alpha}\bigl{(}f_{0}(m_{0})+f_{0}^{\prime}(m_{0})\delta
t-f_{1,\delta}(m_{0}+\delta t)\bigr{)}$
$\displaystyle\phantom{:}=\delta^{-\alpha}\bigl{\\{}\bigl{(}f_{0}(m_{0})+f_{0}^{\prime}(m_{0})\delta-
f_{0}(m_{0}+\delta)\bigr{)}-\delta(1-t)\bigl{(}f_{0}^{\prime}(m_{0})-u(m_{0}+\delta)\bigr{)}\bigr{\\}}$
$\displaystyle\phantom{:}=g_{0,\delta}(1)-(1-t)u_{\delta}\leq g_{0,\delta}(t)$
$\displaystyle\text{and}\qquad g_{2,\delta}(t)$
$\displaystyle:=\delta^{-\alpha}\bigl{(}f_{0}(m_{0})+f_{0}^{\prime}(m_{0})\delta
t-f_{2,\delta}(m_{0}+\delta t)\bigr{)}=-\delta t^{\alpha},$

where $f_{1,\delta},f_{2,\delta}$ are as defined in the proof of Proposition
8. Recalling from (S32) that $f_{\delta}=f_{1,\delta}\wedge f_{2,\delta}$ on
$[m_{0},m_{0}+\delta]$ by definition, we have

$g_{\delta}(t):=\delta^{-\alpha}\bigl{(}f_{0}(m_{0})+f_{0}^{\prime}(m_{0})\delta
t-f_{\delta}(m_{0}+\delta t)\bigr{)}=g_{1,\delta}(t)\vee g_{2,\delta}(t)$
(S66)

for all $t\in[0,1]$. Note that $g_{1,\delta}(0)<g_{0,\delta}(0)=0\leq
g_{2,\delta}(0)$ and $g_{1,\delta}(1)=g_{0,\delta}(1)\geq 0>g_{2,\delta}(1)$.
Thus, since $g_{1,\delta},g_{2,\delta}$ are continuous functions that are
strictly increasing and strictly decreasing respectively, there is a unique
$c_{\delta}\in(0,1)$ satisfying $g_{1,\delta}\leq g_{2,\delta}$ on
$[0,c_{\delta}]$ and $g_{1,\delta}\geq g_{2,\delta}$ on $[c_{\delta},1]$; in
other words, $f_{1,\delta}\geq f_{2,\delta}$ on $[m_{0},m_{0}+\delta
c_{\delta}]$ and $f_{1,\delta}\leq f_{2,\delta}$ on $[m_{0}+\delta
c_{\delta},m_{0}+\delta]$, so this is consistent with the definition of
$c_{\delta}$ in the proof of Proposition 8. Since
$g_{0,\delta}(1)-(1-c_{\delta})u_{\delta}=g_{1,\delta}(c_{\delta})=g_{2,\delta}(c_{\delta})\in[-\delta,0]$,
we have

$1-u_{\delta}^{-1}g_{0,\delta}(1)\geq c_{\delta}\geq
1-u_{\delta}^{-1}\bigl{(}g_{0,\delta}(1)+\delta\bigr{)}.$

In the limit as $\delta\to 0$, it was shown above that $g_{0,\delta}(1)\to
g_{0}(1)=B$ and $u_{\delta}\to g_{0}^{\prime}(1)=B\alpha$, so $c_{\delta}\to
1-\alpha^{-1}$ and $g_{1,\delta}$ converges uniformly on $[0,1]$ to the affine
function $g_{1}\colon t\mapsto
g_{0}(1)-(1-t)g_{0}^{\prime}(1)=B\bigl{(}1-(1-t)\alpha\bigr{)}$. Consequently,
$g_{\delta}=g_{1,\delta}\vee g_{2,\delta}\to g_{1}\vee 0\equiv g_{1}^{+}$
uniformly on $[0,1]$ as $\delta\to 0$.

Now let $(\delta_{n})$ be any sequence such that $\delta_{n}\to 0$ and
$n\delta_{n}\to 0$ as $n\to\infty$. Having already shown that
$\lim_{n\to\infty}c_{\delta_{n}}=1-\alpha^{-1}$, we proceed to establish the
claimed limiting expression for $\|f_{\delta_{n}}-f_{0}\|_{n}^{2}$. For each
$n$, let $z_{n,i}:=(x_{i}-m_{0})/\delta_{n}$ for $i\in[n]$, where $x_{i}\equiv
x_{ni}=i/n$ by Assumption 2, so that $z_{n,i+1}-z_{n,i}=1/(n\delta_{n})$ for
all $i\in[n-1]$. Then recalling from (S32) that $f_{\delta_{n}}=f_{0}$ on
$[0,1]\setminus(m_{0},m_{0}+\delta_{n})$, we can use (S66) to write

$\|f_{\delta_{n}}-f_{0}\|_{n}^{2}=\frac{1}{n}\sum_{i\,:\,m_{0}<x_{i}<m_{0}+\delta_{n}}(f_{\delta_{n}}-f_{0})^{2}(x_{i})=\delta_{n}^{2\alpha+1}\,\frac{1}{n\delta_{n}}\sum_{i\,:\,0<z_{n,i}<1}(g_{\delta_{n}}-g_{0,\delta_{n}})^{2}(z_{n,i})$
(S67)

for each $n$. Since $\lvert\\{i:0<z_{n,i}<1\\}\rvert=O(n\delta_{n})$ and
$(g_{\delta_{n}}-g_{0,\delta_{n}})^{2}\to(g_{1}^{+}-g_{0})^{2}$ uniformly on
$[0,1]$ as $n\to\infty$, we have

$\displaystyle\frac{1}{n\delta_{n}}\sum_{i\,:\,0<z_{n,i}<1}\lvert(g_{\delta_{n}}-g_{0,\delta_{n}})^{2}(z_{n,i})-(g_{1}^{+}-g_{0})^{2}(z_{n,i})\rvert$
$\displaystyle\hskip
56.9055pt\leq\frac{\lvert\\{i:0<z_{n,i}<1\\}\rvert}{n\delta_{n}}\sup_{x\in[0,1]}\bigl{|}(g_{\delta_{n}}-g_{0,\delta_{n}})^{2}-(g_{1}^{+}-g_{0})^{2}\bigr{|}=o(1).$

Thus, by a Riemann sum approximation to the (uniformly) continuous function
$(g_{1}^{+}-g_{0})^{2}$ on $[0,1]$ and the fact that $n\delta_{n}\to\infty$,
we see that

$\displaystyle\frac{1}{n\delta_{n}}\sum_{i\,:\,0<z_{n,i}<1}(g_{\delta_{n}}-g_{0,\delta_{n}})^{2}(z_{n,i})$
$\displaystyle=\frac{1}{n\delta_{n}}\sum_{i\,:\,0<z_{n,i}<1}(g_{1}^{+}-g_{0})^{2}(z_{n,i})+o(1)$
$\displaystyle=\int_{0}^{1}\,(g_{1}^{+}-g_{0})^{2}+o(1)$
$\displaystyle=B^{2}\int_{0}^{1}\,\bigl{\\{}t^{\alpha}-\bigl{(}1-(1-t)\alpha\bigr{)}^{+}\bigr{\\}}^{2}\,dt+o(1)$
$\displaystyle=\bigl{(}1+o(1)\bigr{)}C_{\alpha}B^{2}$

as $n\to\infty$, where
$C_{\alpha}:=\int_{0}^{1}\,\bigl{\\{}t^{\alpha}-\bigl{(}1-(1-t)\alpha\bigr{)}^{+}\bigr{\\}}^{2}\,dt$.
Combining this with (S67) yields the desired conclusion. ∎

##  S6 Proofs for Section S3

###### Proof of Proposition S9.

(a) Since every $g\in\mathcal{F}^{m}$ is bounded on $[0,1]$, it follows that
$\mathcal{F}^{m}\subseteq L^{2}(\nu)$. If $g,h\in\mathcal{F}^{m}$, then
certainly $\lambda g\in\mathcal{F}^{m}$ for all $\lambda>0$ and $\lambda
g+(1-\lambda)h\in\mathcal{F}^{m}$ for all $\lambda\in[0,1]$. Now fix
$g\in\mathcal{F}^{m}$, and for each $n\in\mathbb{N}$, let
$g_{n}\colon[0,1]\to\mathbb{R}$ be the Lipschitz function that agrees with $g$
on $[0,m(1-1/n)]\cup\\{m\\}\cup[m(1-1/n)+1/n,1]$, and is also linear on both
$[m(1-1/n),m]$ and $[m,m(1-1/n)+1/n]$. Then $g_{n}\in\mathcal{F}^{m}$ and
$g(0)\leq g_{n}\leq g(1)$ for all $n$, and since $g_{n}\to g$ pointwise, we
have $\|g_{n}-g\|_{L^{2}(\nu)}\to 0$ by the dominated convergence theorem.

(b) Let $M_{\nu}^{L}:=\min(\operatorname{supp}\nu)$ and
$M_{\nu}^{R}:=\max(\operatorname{supp}\nu)$, so that
$\operatorname{csupp}\nu=[M_{\nu}^{L},M_{\nu}^{R}]$. There is nothing to prove
when $m\in\operatorname{csupp}\nu$, so suppose now that $m>M_{\nu}^{R}$. Then
$\tilde{m}=M_{\nu}^{R}$, and note that $g\colon[0,\tilde{m}]\to\mathbb{R}$ is
increasing, convex and Lipschitz if and only if there exists a Lipschitz
$f\in\mathcal{F}^{m}$ such that $g=\left.f\right|_{[0,\tilde{m}]}$. Thus,
$\mathcal{F}_{\nu}^{m}=\\{[f]_{\nu}:f\in\mathcal{F}^{\tilde{m}}\text{ is
Lipschitz}\\}$ is dense in $\mathcal{F}_{\nu}^{\tilde{m}}$ by (a). The case
$m<M_{\nu}^{L}$ is similar.

(c, $\Leftarrow$) We first show that if $(f_{n})_{n=1}^{\infty}$ is a sequence
of functions in $\mathcal{F}^{m}$ such that $\|f_{n}-f\|_{L^{2}(\nu)}\to 0$
for some $f\in L^{2}(\nu)$, then under any one of the conditions (i)–(iii)
above, there exists $g\in\mathcal{F}^{m}$ such that $f\sim_{\nu}g$. To begin
with, note that $f_{n}\to f$ in $\nu$-measure, so there exists a subsequence
$(g_{k})_{k=1}^{\infty}\equiv(f_{n_{k}})_{k=1}^{\infty}$ such that $g_{k}\to
f$ $\nu$-almost everywhere. In each of the cases below, we will in fact show
that there is some $g\in\mathcal{F}^{m}$ that agrees with $f$ on
$A:=\\{x\in\operatorname{supp}\nu:g_{k}(x)\to f(x)\\}$, which is a dense
subset of $\operatorname{supp}\nu$. Indeed, if
$S\subseteq\operatorname{supp}\nu$ satisfies
$\nu(S^{c}\cap\operatorname{supp}\nu)=0$, then by the definition of
$\operatorname{supp}\nu$, the set $S^{c}\cap\operatorname{supp}\nu$ has empty
interior; in other words, $S$ is dense in $\operatorname{supp}\nu$.

Case 1 – $\nu([0,m))\wedge\nu((m,1])>0$: Since $A$ is dense in
$\operatorname{supp}\nu$, there exist $a_{L},a_{R}\in
A\subseteq\operatorname{supp}\nu$ such that $a_{L}<m<a_{R}$ and $g_{k}\to f$
on $\\{a_{L},a_{R}\\}$. Since the functions $g_{k}$ are convex on $[0,m]$,
concave on $[m,1]$ and increasing on $[0,1]$, we have

$\displaystyle\liminf_{k\to\infty}g_{k}(0)$
$\displaystyle\geq\liminf_{k\to\infty}\,\frac{m\,g_{k}(a_{L})-a_{L}\,g_{k}(m)}{m-a_{L}}\geq\frac{m\,f(a_{L})-a_{L}\,f(a_{R})}{m-a_{L}}$
$\displaystyle\limsup_{k\to\infty}g_{k}(1)$
$\displaystyle\leq\limsup_{k\to\infty}\,\frac{(1-m)\,g_{k}(a_{R})-(1-a_{R})\,g_{k}(m)}{a_{R}-m}\leq\frac{(1-m)\,f(a_{R})-(1-a_{R})\,f(a_{L})}{a_{R}-m},$
(S68)

so $\\{g_{k}(x)\\}_{k=1}^{\infty}$ is bounded for each $x\in[0,1]$. Therefore,
by considering separately the intervals $(0,m),(m,1)$, we can apply
Rockafellar (1997, Theorem 10.9) and extract a subsequence $(g_{k_{\ell}})$ of
$(g_{k})$ that converges pointwise on $(0,m)\cup(m,1)$. In fact,
$(g_{k_{\ell}})$ converges pointwise on $[0,1]\setminus\\{m\\}$ by Lemma S29,
and the limit function $g$ is convex on $[0,m)$, concave on $(m,1]$ and
increasing on $[0,1]\setminus\\{m\\}$. If in addition $m\in A$, then

$g(z)=\lim_{\ell\to\infty}g_{k_{\ell}}(z)\leq\lim_{\ell\to\infty}g_{k_{\ell}}(m)=f(m)\leq\lim_{\ell\to\infty}g_{k_{\ell}}(w)=g(w)$

for all $z\in(0,m)$ and $w\in(m,1)$, so $\lim_{x\nearrow\,m}g(x)\leq
f(m)\leq\lim_{x\searrow\,m}g(x)$. Thus, we can extend $g$ to a function on
$[0,1]$ that belongs to $\mathcal{F}^{m}$ by setting $g(m)=f(m)$. Otherwise,
if $m\notin A$, then we can set $g(m)=\lim_{x\searrow\,m}g(x)$ for
concreteness. In both cases, we have $g\in\mathcal{F}^{m}$ and $f=g$ on $A$,
as required.

Case 2 – $\nu((m,1])=0$: Here, we have $\operatorname{supp}\nu\subseteq[0,m]$.
We also assume that $\operatorname{supp}\nu$ contains at least two points,
since otherwise the result holds trivially. Note that
$\operatorname{conv}(\operatorname{Cl}A)\supseteq\operatorname{Int}\operatorname{csupp}\nu=(M_{\nu}^{L},M_{\nu}^{R})$.
By convexity arguments similar to those given in Case 1, it follows that
$\\{g_{k}(x)\\}_{k=1}^{\infty}$ is bounded for all
$x\in(M_{\nu}^{L},M_{\nu}^{R})$. Thus, again by Rockafellar (1997, Theorem
10.9) and Lemma S29, there exists a subsequence $(g_{k_{\ell}})$ of $(g_{k})$
that converges pointwise on $[0,M_{\nu}^{R})$ to some increasing convex
function $g\colon[0,M_{\nu}^{R})\to\mathbb{R}$. By the definition of $A$, we
must have $f=g$ on $[0,M_{\nu}^{R})\cap A$.

  * •

If condition (i) holds, then $M_{\nu}^{R}=m$ and $\nu(\\{m\\})>0$, so $m\in
A$, i.e. $g_{k}(m)\to f(m)$. We now extend $g$ to $[0,1]$ by setting
$g(x)=f(m)$ for all $x\in[m,1]$. Then $f=g$ on $A$, and for all $x\in[0,m)$,
we have
$g(x)=\lim_{\ell\to\infty}g_{k_{\ell}}(x)\leq\lim_{\ell\to\infty}g_{k_{\ell}}(m)=f(m)$,
so $g\in\mathcal{F}^{m}$.

  * •

If condition (ii) holds, then $M_{\nu}^{R}\in(0,m)$ is an isolated point of
$\operatorname{supp}\nu$, so $\nu(\\{M_{\nu}^{R}\\})>0$, $M_{\nu}^{R}\in A$
and
$M_{\nu}^{\prime}:=\max(\operatorname{supp}\nu\setminus\\{M_{\nu}^{R}\\})<M_{\nu}^{R}<m$.
Let $h\colon[0,1]\to\mathbb{R}$ be the function that agrees with $f$ on
$[0,M_{\nu}^{\prime}]\cup\\{M_{\nu}^{R}\\}$ and is linear on
$[M_{\nu}^{\prime},1]$. Then $h$ is linear on $[m,1]$ and convex and
increasing on $[0,1]$, so $h\in\mathcal{F}^{m}$. Since
$(M_{\nu}^{\prime},1]\cap A=\\{M_{\nu}^{R}\\}$, the functions $f,g,h$ agree on
$A$, as required.

The analogous case where $\operatorname{supp}\nu\subseteq[m,1]$ can be handled
in much the same way, and so we have now demonstrated the sufficiency of each
of the conditions (i), (ii) and (iii).

(c, $\Rightarrow$) Supposing that none of the conditions (i)–(iii) hold, we
now verify that
$\operatorname{Cl}\mathcal{F}_{\nu}^{m}\supsetneqq\mathcal{F}_{\nu}^{m}$. We
consider only the cases where $\operatorname{supp}\nu\subseteq[0,m]$; the
arguments are similar if $\operatorname{supp}\nu\subseteq[m,1]$.

Case 1 – $\nu(\\{M_{\nu}^{R}\\})=0$: Note that there exists $f\in L^{2}(\nu)$
such that $\left.f\right|_{E_{\nu}}$ is convex and increasing, and
$f(x)\to\infty$ as $x\nearrow M_{\nu}^{R}$. Indeed, a concrete example of such
a function can be obtained via the following construction: since $M_{\nu}^{R}$
is not an isolated point of $\operatorname{supp}\nu$ by assumption, there
exists a sequence
$(a_{n}\in\operatorname{supp}\nu\setminus\\{M_{\nu}^{R}\\}:n\in\mathbb{N})$
such that $a_{n}\nearrow M_{\nu}^{R}$ and $\nu((a_{n},M_{\nu}^{R}))\leq
2^{-3n}$ for all $n$. For each $n$, let $h_{n}\colon[0,1]\to\mathbb{R}$ be
such that $h_{n}=0$ on $[0,a_{n}]$, $h_{n}(M_{\nu}^{R})=2^{n/2}$ and $h_{n}$
is linear on $[a_{n},1]$. Then $h_{n}$ is convex and increasing, and
$\|h_{n}\|_{L^{2}(\nu)}\leq(2^{n}\cdot 2^{-3n})^{1/2}=2^{-n}$. Thus, the
function $h\colon[0,1]\to\mathbb{R}$ defined by
$h(x):=\sum_{n=1}^{\infty}h_{n}(x)\mathbbm{1}_{\\{x<M_{\nu}^{R}\\}}$ is also
convex and increasing. Moreover,
$\|h\|_{L^{2}(\nu)}\leq\sum_{n=1}^{\infty}\|h_{n}\|_{L^{2}(\nu)}<\infty$ and
$h(x)\to\infty$ as $x\nearrow M_{\nu}^{R}$.

For any $f$ with the above properties, we now argue that
$[f]_{\nu}\notin\mathcal{F}_{\nu}^{m}$, i.e. that there does not exist
$g\in\mathcal{F}^{m}$ such that $f\sim_{\nu}g$. Indeed, if $g$ is a function
that agrees with $f$ on a set $S\subseteq\operatorname{supp}\nu$ with the
property that $\nu(S^{c}\cap\operatorname{supp}\nu)=0$, then recall from the
second paragraph of the proof that $S$ is dense in $\operatorname{supp}\nu$.
Thus, since $M_{\nu}^{R}$ is not an isolated point of
$\operatorname{supp}\nu$, there exists a sequence $(s_{n}\in
S\setminus\\{M_{\nu}^{R}\\}:n\in\mathbb{N})$ such that $s_{n}\to M_{\nu}^{R}$,
and we must have $g(s_{n})=f(s_{n})$ for all $n$. But this implies that
$g(x)\to\infty$ as $x\nearrow M_{\nu}^{R}$, so $g$ cannot be extended to a
finite convex function on $[0,m]$.

Case 2 – $\nu(\\{M_{\nu}^{R}\\})>0$: Consider any $f\in L^{2}(\nu)$ such that
$\left.f\right|_{E_{\nu}}$ is convex and increasing, and $f$ is discontinuous
at $M_{\nu}^{R}$. Since $M_{\nu}^{R}\in(0,m)$ is not an isolated point of
$\operatorname{supp}\nu$, we deduce as before that if $f\sim_{\nu}g$ for some
$g\colon[0,1]\to\mathbb{R}$, then there exists a sequence
$(s_{n}\in\operatorname{supp}\nu\setminus\\{M_{\nu}^{R}\\}:n\in\mathbb{N})$
such that $s_{n}\to M_{\nu}^{R}$ and $g(s_{n})=f(s_{n})$ for all $n$. But
since $\nu(\\{M_{\nu}^{R}\\})>0$, we have
$g(M_{\nu}^{R})=f(M_{\nu}^{R})\neq\lim_{n\to\infty}f(s_{n})=\lim_{n\to\infty}g(s_{n})$,
so $g$ is not continuous at $M_{\nu}^{R}\in(0,m)$ and hence does not belong to
$\mathcal{F}^{m}$. This shows that $[f]_{\nu}\notin\mathcal{F}_{\nu}^{m}$ and
hence that
$\operatorname{Cl}\mathcal{F}_{\nu}^{m}\supsetneqq\mathcal{F}_{\nu}^{m}$, as
required.

(d) Suppose again that none of the conditions (i)–(iii) hold, assuming for the
time being that $\operatorname{supp}\nu\subseteq[0,m]$. Then $m>0$ and
$M_{\nu}^{R}\in[0,m]$ is not an isolated point of $\operatorname{supp}\nu$.
Let $(f_{n})_{n=1}^{\infty}$ be any sequence in $\mathcal{F}^{m}$ such that
$\|f_{n}-f\|_{L^{2}(\nu)}\to 0$ for some $f\in L^{2}(\nu)$. By a very similar