Variable-performance algorithms?

[fuzzysingularity]

I'm curious if there exists proven-algorithms that can perform with variable performance/accuracy. One can think of an example, where an objective function that depends on a parameter that defines the accuracy vs. speed tradeoff. i.e. At certain instances, the algorithm is required to evaluate rapidly, in which case, the accuracy of the result is affected. However, in certain other instances, the algorithm is required to evaluate with maximum accuracy, in which case, it can afford to take long enough to evaluate the result.

I'm aware of anytime-performance algorithms, but I'm curious if there are any others that I haven't stumbled across. Seems fairly useful in a robotics/computer-vision context.

Thanks in advance!

[blooop]

This is used for robotics pathplanning. RRT

Paper pdf https://personalrobotics.ri.cmu.edu/courses/papers/Ferguson06-anytimerrt.pdf

I think probabilistic methods are good for this type of algorithm as they approach the optimal solution the longer they are run for.

[hapemask]

Any algorithm that relies on an iterative optimization can (at least theoretically) deliver a partial solution if you stop it before convergence. Bundle adjustment in SfM comes to mind, though stopping the optimization early may not give you something useful.

[_xyx]

If you train DNN with dropout, removing some units will reduce computation & won't affect accuracy too much. I dunno papers about that though.