These are from the first chapter of the book Introductory Lectures on Convex Optimization by Yurii Nesterov. It talks about the concept of resisting oracle (what does "create worst problem", "starts from ... in the worst possible way", "possible to reconstruct a problem ... accumulated by the algorithm" mean?) and go on to prove a lower bound using it. I could not understand what is resisting oracle and I also could not follow the subsequent proof using the it. Can someone explain it in a simpler to understand language and hopefully with examples?
It's probably easiest to start by considering gradient descent on a Lipschitz-smooth, convex function $f$ (a convex function whose gradient is Lipschitz-continuous). Gradient descent generates a sequence of points $\{x_k\}_{k\in\mathbb{N}}$ which all satisfy
$$x_{k+1} := x_k - \gamma \nabla f (x_k)$$
If you are interested in the worst case analysis, you want to know what is the "worst" sequence $\{x_k\}_{k\in\mathbb{N}}$ you could possibly get given by gradient descent, but under the assumption that $f$ is convex and Lipschitz-smooth. The "resisting" oracle here would give you "bad" values of $\nabla f (x_k)$ which lead to slow convergence, but which are still "possible" in the sense that they are values for which we can construct a convex Lipschitz-smooth function whose gradient evaluated at $x_k$ gives the right values.