Learning Reduced Order Dynamics via Geometric Representations
Imran Nasim, Melanie Weber
SCML 2024
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying to learn the value of the function for the minimum cost. We apply the competitive analysis of algorithms to this framework, designing algorithms that incur large cost only when the cost of the cheapest "proof for the value of f is also large. We provide algorithms that achieve the optimal competitive ratio for functions that include arbitrary Boolean AND/OR trees, and for the problem of searching in a sorted array. We also investigate a model for pricing in this framework and construct, for every AND/OR tree, a set of prices that satisfies a very strong type of equilibrium property. © 2002 Elsevier science (USA).
Imran Nasim, Melanie Weber
SCML 2024
A. Skumanich
SPIE OE/LASE 1992
Charles Micchelli
Journal of Approximation Theory
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence