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?


1 Answer 1


For the problem you describe, since the function is strongly convex and $x,y \in \mathbb{R}$ (so you don't have bound constraints), your solution is obtained by solving the system $\nabla f = 0$.

Now, if you only have approximations to the gradient, the resulting error largely depends on the algorithm you chose to use to solve this. For instance, since your function remains strongly convex, $\mu$ and $\epsilon$ would not affect each other at all if you simply solve the nonlinear system $\nabla f = 0$.

Solving this system of equations is a perfectly legitimate optimisation method, as this is what a solver would actually do in this case. In fact, the only reasons for a solver not to solve this system directly would be if the problem had bound constraints, or if there are memory limitations. Even in the case of bound constraints though, a good solver would first try solving the system and see if it has a solution within bounds before resorting to more expensive methods.


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.