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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.