Re:The zen of gradient descent
by alfiedotwtf on Monday October 10, 2016 @04:04AM
(#12675740)
How do these and other variants compare to simple Hill Climbing with random restarts, because I feel that gradient descent, simulated annealling etc are just local searches within the local search space.
Re:The zen of gradient descent
by akssri on Monday October 10, 2016 @04:15AM
(#12675775)
Nesterov's method attains super-linear convergence on Convex functions. They don't really (if I remember right) work otherwise; but then this is okay, since Convex problems are really the only ones we can solve in poly-time (esp. if P/=NP and UGC is true).
SA/RR are global optimization methods which come with very little (if any?) complexity guarantees.
SA/RR are global optimization methods which come with very little (if any?) complexity guarantees.
Ah thanks, I thought I missed something. That makes total sense.
"SA/RR are global optimization methods"
RR is definitely global, but (depending on your cooling function I guess) I would say SA is not.