The $\mathcal{A}^\star$-optimality conjecture for OBL-G$_\flat$

Let $L>0$, let $R>0$, and let $f$ be a convex differentiable function with iterates $x_0,x_1,\ldots,x_N$ generated by optimized backtracking linesearch—gradient norm$_\flat$ (OBL-G$_\flat$). Let $f_\star$ denote the minimum value of $f$, and let $\mathcal{I}_{\operatorname{OBL-G}_\flat}$ be the collection of inequalities

$$\mathcal{I}_{\operatorname{OBL-G}_\flat}=\left\{f(x_k)\geq f(x_{k+1})+\langle\nabla f(x_{k+1}),x_{k+1}-x_k\rangle+\frac{1}{2L}\left\lVert\nabla f(x_k)-\nabla f(x_{k+1})\right\rVert^2\right\}_{k=0}^{N-1}$$ $$\cup\left\{f(x_N)\geq f(x_k)+\langle\nabla f(x_k),x_k-x_N\rangle\right\}_{k=0}^{N}$$ $$\cup\left\{f(x_N)\geq f_\star+\frac{1}{2L}\left\lVert\nabla f(x_N)\right\rVert^2\right\}.$$

OBL-G$_\flat$'s $\mathcal{A}^\star$-optimality conjecture. OBL-G$_\flat$ is $\mathcal{A}^\star$-optimal in the sense that

$$\operatorname{OBL-G}_\flat=\mathcal{A}^\star_N\left(\left\lVert\nabla f(x_N)\right\rVert^2, f(x_0)-f_\star\leq\frac{1}{2}LR^2,\mathcal{I}_{\operatorname{OBL-G}_\flat}\right)$$

and has the minimax optimal rate

$$\mathcal{R}^\star\left(\mathfrak{A}_N,\left\lVert\nabla f(x_N)\right\rVert^2, f(x_0)-f_\star\leq\frac{1}{2}LR^2,\mathcal{I}_{\operatorname{OBL-G}_\flat}\right)=2L^2R^2\frac{N^2+N-\sqrt{2N(N+1)}}{N^2(N+1)^2-2\sqrt{2N(N+1)}}.$$

The PEP for OBL-G$_\flat$ is bi-convex and therefore non-convex, preventing a proof of $\mathcal{A}^\star$-optimality. Numerical experiments nevertheless indicate that the algorithm is likely optimal; the conjecture remains open.