I am going through a set of blog posts on the complexity of projected gradient method.
https://blogs.princeton.edu/imabandit/2013/03/15/orf523-oracle-complexity-large-scale-optimization/ defines the minimax oracle
A black-box optimization procedure is simply a sequence (over ${t=0,1, \ldots}$) of mappings ${\phi_t: \mathcal{X}^t \times ({\mathbb R}^n)^t \times {\mathbb R}^t \rightarrow \mathcal{X}}$. The algorithm given by these mappings runs iteratively as follows: initially it makes a query to the point ${x_0 =\phi_0(\emptyset)}$, and then at the ${t^{th}}$ step it queries
$\displaystyle x_t = \phi_t(x_0, \ldots, x_{t-1}, \nabla f(x_0), \ldots, \nabla f(x_{t-1}), f(x_0), \ldots, f(x_{t-1})) .$
The minimax oracle optimization error after ${t}$ steps, over a set of functions ${\mathcal{F}}$, is defined as follows:
$\displaystyle \mathrm{OC}_t(\mathcal{F}) = \inf_{\phi_0, \ldots, \phi_t} \sup_{f \in \mathcal{F}} \left( f(x_t) - \inf_{x \in \mathcal{X}} f(x) \right).$
... In the literature the results are often stated in terms of oracle complexity, which is the smallest ${T_{\epsilon}}$ such that ${\mathrm{OC}_{T_{\epsilon}}(\mathcal{F}) \leq \epsilon}$. We may use interchangeably the notions of oracle complexity and Oracle optimization error.
On the analysis of the project gradient immediately follows, https://blogs.princeton.edu/imabandit/2013/03/25/orf523-oracle-complexity-of-lipschitz-convex-functions/, it is written:
(Projected) Subgradient Descent with $\eta = \frac{R}{L \sqrt{t}}$ satisfies for $\bar{x}_t \in \left\{ \frac{1}{t} \sum_{s=1}^t x_s ; \mathrm{argmin}_{1 \leq s \leq t} f(x_s) \right\}$,
$$f(\bar{x}_t) - f^* \leq \frac{R L}{\sqrt{t}} .$$ ...To reach an $\epsilon$-optimal point, one needs to make $T_{\epsilon} = \frac{R^2 L^2}{\epsilon^2}$ calls to the $1^{st}$ order oracle. This result is astonishing, because $T_{\epsilon}$ is independent of the dimension! This fact is what makes gradient methods so suitable for large-scale optimization.
In the first box, it is clearly written that we need to evaluate the minimax oracle to obtain the smallest $T_\epsilon$
$$\displaystyle \mathrm{OC}_t(\mathcal{F}) = \inf_{\phi_0, \ldots, \phi_t} \sup_{f \in \mathcal{F}} \left( f(x_t) - \inf_{x \in \mathcal{X}} f(x) \right) \leq \epsilon.$$
However, in the actual evaluation of the oracle complexity, we simply needed to show:
$$f(\bar{x}_t) - f^* \leq \frac{R L}{\sqrt{t}} .$$
It seems that our result does not match our definition of oracle complexity.
A few questions:
Why is it in the definition of the minimax oracle, we need to evaluate the function that yields the largest $f(x_t) - f(x^*)$, when no such assumption was apparently made when evaluating the oracle complexity of the projected gradient descent? In other words, the oracle complexity applies for an arbitary Lipschitz and convex function, whereas in the definition of the minimax oracle, we require a function that satisfies the supremum $\sup_{f\in \mathcal{F}}$.
The minimax oracle provides the number of steps for $f(x_t) - f(x^*)$ to become smaller than $\epsilon$, but in the projected gradient case, it is the averaged iterates $f(\bar{x}_t) - f^*$. How does the definition apply?
How was the infininum on the black-box mappings taken into account for the projected gradient descent? In other words, clearly, no such functions $\phi_0, \phi_t$ used in the definition of the minimax oracle was constructed in the evaluation of oracle complexity of projected gradient. Again, how does the definition fit?
All in all, I expected the oracle complexity result for the projected gradient to be stated as:
$$\inf_{\phi_0, \ldots, \phi_t} \sup_{f \in \mathcal{F}} \left( f(x_t) - f^* \right) \leq \epsilon.$$
Instead as simply$$f(\bar{x}_t) - f^* \leq \frac{R L}{\sqrt{t}}$$ What happened to the $\inf$, what happened to the $\sup$, what happened to all those black-box mappings?
Can anyone provide assistance for reconciling between the definition of oracle complexity and how it is found in for the projected subgradient method?
