Do Good Algorithms Necessarily Query Bad Points?

Let $\mathcal{W}\subseteq\mathbb{R}^d$ be a closed convex set. Consider stochastic convex optimization of

where $F$ is convex on $\mathcal{W}$ and attains its minimum at some $w^*\in\arg\min_{w\in\mathcal{W}}F(w)$. A stochastic first-order oracle, when queried at $w_t\in\mathcal{W}$, returns $g_t=\nabla f(w_t;\xi_t)$ such that (unbiasedness)

where $\mathcal{F}_{t-1}=\sigma(\xi_1,\ldots,\xi_{t-1})$; the problem class $\mathcal{P}$ further specifies regularity/noise assumptions (e.g. a uniform second-moment bound $\mathbb{E}[\|g_t\|^2\mid \mathcal{F}_{t-1},w_t]\le G^2$ for all $t$ and $w_t\in\mathcal{W}$).

For $t\ge 1$, define the minimax expected excess-risk rate after $t$ oracle calls by

where the infimum ranges over all (possibly randomized) algorithms $A$ that make $t$ oracle queries and output $\hat w_t\in\mathcal{W}$ measurable with respect to $\mathcal{F}_t$.

Define a (stochastic) first-order algorithm to be non-adaptive if its query points are affine functions of past observed gradients with coefficients fixed before the run: there exist deterministic vectors $b_t\in\mathbb{R}^d$ and deterministic matrices $A_{t,j}\in\mathbb{R}^{d\times d}$ (allowed to depend on $t$ and on known problem parameters, but not on the realized oracle randomness) such that for all $t\ge 1$,

where $\Pi_{\mathcal{W}}$ is Euclidean projection onto $\mathcal{W}$.