Re:Implement your own source transformation AD with Julia
by LolWolf on Thursday June 11, 2020 @05:38PM
(#23493538)
> All optimal points
Sorry I screwed up a bit when writing that: an optimal point exists which lies on the extremal points of the feasible domain. In many cases, it can be shown that the optimal point lies on the extremal points of the feasible domain (when the objective is linear)
Re:Implement your own source transformation AD with Julia
by ssivark on Friday June 12, 2020 @10:46AM
(#23499730)
Yes, but we’re going to be restricted to O(L) final accuracy no matter what, for gradient descent (we could choose second order optimizations, etc, but that’s an orthogonal point — we’re happy to get within an epsilon ball of the answer).
Re:Implement your own source transformation AD with Julia
by LolWolf on Friday June 12, 2020 @03:27PM
(#23502718)
> Yes, but we’re going to be restricted to O(L) final accuracy no matter what
This is not, in general, true for smooth functions so long as L is small enough (you can reach arbitrary accuracy with GD if L is smaller than ~ the reciprocal of the Lipchitz constant of a differentiable objective function but it need not be arbitrarily small).
All optimal points (for, say, optimizing a linear function) will lie on the extremal points of the feasible domain, many of which will be points where the constraint functions are not differentiable. In all cases you can turn nonlinear objective function optimization (say over f) into linear objective function optimization by adding a constraint f(x) ≤ t and moving t to the objective.
Now, I will agree that smooth optimization algorithms will work ok, but try optimizing abs(x) with GD; you'll find that the best possible error you can achieve (other than by sheer luck) will be ~O(L) where L is your stepsize.