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 (just) big enough to enforce that the move won’t exceed some maximum step size. Set your current guess to the maximizer of the regularized quadratic. Repeat re-using old data if convenient.
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 (just) big enough to enforce that the move won’t exceed some maximum step size. Set your current guess to the maximizer of the regularized quadratic. Repeat re-using old data if convenient.