Open Thread February 25 - March 3

Scott Garrabrant

Open Thread February 25 - March 3 — LessWrong

Comment Permalink

Does anyone have advice on how to optimize the expectation of a noisy function? The naive approach I've used is to sample the function for a given parameter a decent number of times, average those together, and hope the result is close enough to stand in for the true objective function. This seems really wasteful though.

Most of the algorithms I'm coming (like modelling the objective function with gaussian process regression) would be useful, but are more high-powered than I need. Any simple techniques better than the naive approach? Any recommendations among sophisticated approaches?

witzvo12y10

You may find better ideas under the phrase "stochastic optimization," but it's a pretty big field. My naive suggestion (not knowing the particulars of your problem) would be to do a stochastic version of Newton's algorithm. I.e. (1) sample some points (x,y) in the region around your current guess (with enough spread around it to get a slope and curvature estimate). Fit a locally weighted quadratic regression through the data. Subtract some constant times the identity matrix from the estimated Hessian to regularize it; you can choose the constant ... (read more)

2VincentYu12y

There are some techniques that can be used with simulated annealing to deal with noise in the evaluation of the objective function. See Section 3 of Branke et al (2008) for a quick overview of proposed methods (they also propose new techniques in that paper). Most of these techniques come with the usual convergence guarantees that are associated with simulated annealing (but there are of course performance penalties in dealing with noise). What is the dimensionality of your parameter space? What do you know about the noise? (e.g., if you know that the noise is mostly homoscedastic or if you can parameterize it, then you can probably use this to push the performance of some of the simulated annealing algorithms.)

2Lumifer12y

That rather depends on the particulars, for example, do you know (or have good reasons to assume) the characteristics of your noise? Basically you have a noisy sample and want some kind of an efficient estimator, right?

See in context

13

Open Thread February 25 - March 3

13

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

13

13

Open Thread February 25 - March 3

13

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

13