Motivated by a real-world problem, we study a novel setting for budgeted optimization where the goal is to optimize an unknown function f(x) given a budget. In our setting, it is not practical to request samples of f(x) ...