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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
