If I understand your notation correctly, CLOP can get C = 1/3 for smooth functions.
In theory, regression with a polynomial of degree d gets C = 0.5 * d / (d + 1) if the function is as smooth as the polynomial with bounded (d+1)th derivative. There is an experiment in the CLOP paper that confirms emprically the C = 3/8 for d = 3. But these are asymptotic rates that may not be very relevant in practice. The CLOP paper has references to papers with these bounds (Chen-1988 for the proof that it is not possible to do better. IIRC, some variations of stochastic gradient have been proved to match the bound, so the bound is tight). Rémi On 7 févr. 2013, at 13:00, Olivier Teytaud wrote: > Hi; > as many of you I guess, I often try to optimize parameters of strategies. > > In games, if I optimize against a fixed opponent, this is a noisy > optimization problem: I want the parameters with the best success rate > against the chosen opponent, > which can be evaluated thanks to repeated (time-consuming) games. > > The state of the art in noisy optimization is slightly unreadable. > > For most tools there are properties such as > << log( distance to optimum ) ~ - C log( number of evaluations) >> > for some positive C. > > In some cases, C=1/2 (or something close to 1/2 depending on derivability > conditions), but this is restricted to easy problems. > > For other families of functions and under some technical assumptions aimed at > getting rid of too simple objective functions, > Basically, one then get rates such as C=1/4, for a quadratic objective > function. However, the bounds are C<=1/2, so there is still a gap. > > So basically one can get nearly any result depending on the assumptions :-) > > I'd like to know which rates you get on your favorite optimization problems. > Maybe many people here don't care about noisy optimization > from a maths point of view, but I'm pretty sure that people here work on real > noisy optimization problem and if they plot curves such as the equation > above it will provide interesting information. > > Thanks for any feedback :-) > > Best regards, > Olivier > > > _______________________________________________ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
