2
$\begingroup$

Suppose I want to find the minimum of a differentiable, strongly convex function $f:\mathbb{R}^n\to\mathbb{R}$ with constant $\mu>0$. That is, for all $x,y\in\mathbb{R}^n$, I have that: $$f(y) \geq f(x)+\nabla f(x)^{T}(y-x)+\frac{\mu}{2}\|y-x\|^{2}.$$ If I can efficiently evaluate $f$ and its gradient, then it is clear how to find the minimum of $f$ with first-order methods. But now assume that I only have access to approximate entries of $\nabla f(x)$, say up to an additive error $\epsilon$. What is the state of the art result on how small $\epsilon$ has to be compared to $\mu$ so that I can still ensure convergence of some optimization method to an approximate minimum? Thanks in advance!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.