Analysis of first-order methods for constrained convex optimization with approximate oracles

Question

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal methods, these oracles are the projection oracle, the (constrained) linear optimization oracle, and the prox. operator, respectively.

I could find some papers that analyze the convergence of the first-order methods considering inexact oracles with additive error. However, I could not find results on convergence analysis of these methods when we have inexact oracles with multiplicative error.

Let's take the projected gradient descent for example. Suppose that we are given an oracle $P_{\mathcal{C},\gamma}(x)$ that returns an approximate projection of any point $x$ onto the compact convex set $\mathcal{C}$ in the sense that

$$ \begin{align*} \|P_{\mathcal{C},\gamma}(x)-x\|&\leq(1+\gamma)\min_{y\in\mathcal{C}}\|y-x\|, \end{align*} $$ for a given $\gamma\geq 0$.

I would appreciate any pointer to references that analyze (approximate) convergence under this kind of oracle model.

Answer 1

Building on Nesterov's work, in his Ph.D thesis, Peter Richtarik considers first-order methods with relative error of approximation guarantees. I haven't looked in too closely, but I am sure that a large part of this analysis can be extended to the case of inexact oracles too.