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.



Analysis of first-order methods for constrained convex optimization with approximate oracles
Building on [Nesterov's work](http://pubsonline.informs.org/doi/pdf/10.1287/moor.1080.0348), in his [Ph.D thesis](http://www.maths.ed.ac.uk/~prichtar/papers/thesis.pdf), 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.


