I am trying to solve an optimization problem:

Find a parameter vector $\theta$ so that $\sum_x \log f(\theta, x) \cdot y$ is minimized (it's a probability problem), subject to $\frac{\partial f_i}{\partial x_j}(\theta, x) \leq C$ for all $x$ in the input space.

My problem is that estimating the derivative of $f$ at a point $x$ is expensive, and my input space is really, really, really big. In fact, just computing $f(\theta, x)$ on some "fine" grid across my input space would be prohibitively expensive. Are there some handy theorems that may be of use here (even if they are only applicable to certain classes of functions)?

  • $\begingroup$ Do you know Kriging? $\endgroup$ – user251257 Oct 17 '17 at 18:11
  • $\begingroup$ I've done gaussian process regression before, and it was very slow for even small input spaces. Also, I think it would require me to, at a minimum, compute $f(\theta, x)$ on a "fine" grid across my input space, where "fine" is determined by the maximum size of some order of derivative.... but I don't know that maximum size. :) $\endgroup$ – Scott Oct 18 '17 at 21:57
  • $\begingroup$ I don’t have much experience with kriging. It might be very slow. Do you mean grid as a regular grid? It don’t think that it is necessary. With every approximative methods you can chose tolerance heuristically only. $\endgroup$ – user251257 Oct 19 '17 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.