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!


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.