We study zeroth-order optimization where solutions must minimize a cost d(s) while maintaining high probability under a complex generative prior L(s) (e.g., a parameterized model). This reduces to sampling from a target distribution proportional to L(s)e−T⋅d(s). Since classical model-based optimization (MBO) lacks finite-sample guarantees for expressive approximate learners, we introduce "coarse learnability", a flexible statistical assumption requiring only that a learned model covers the target's probability mass within a polynomial factor. Leveraging this assumption, we design an iterative MBO algorithm called \alift with a sample correction step that provably approximates the target using only a polynomial number of samples. We apply this framework to globally optimizing non-convex objectives bounded by a quadratic envelope in Rn, where we show this assumption is naturally satisfied for a family of "optimistic" posterior distributions. To reach global ε-optimality, this implies a sample complexity of O(log1/ε), a rate characteristic of optimistic space-partitioning methods. We further justify coarse learnability as an assumption for generative priors theoretically, proving that in simple settings, parametric maximum likelihood estimation and over-smoothed kernel density estimators naturally satisfy it. Finally, one motivation for our framework comes from inference-time alignment. Though our primary contribution pertains to the theoretical foundations of MBO, we provide qualitative evidence that, in simple settings, even primitive LLMs can shift their distributions toward lower-cost regions when fine-tuned with zeroth-order feedback.
Figures & tables
Figure 1: Optimization error trajectories ( ∣∣μ−x∗∣∣ ) versus iteration for ALDrIFT and TopIFT . (Left) Parameters: μd=0.5,A=2.0,ω=3.0,x0=6,μ0=0.1 . (Center) Parameters: μd=1.0,A=0.5,ω=4.0,x0=1.35,μ0=2.0 . (Right) Pr[\mboxAccept] of a sample versus the temperature τ in ALDrIFT .
Figure 2: Success rate of the models in finding a length k -cycle in a graph as a function of k . For each k , the graph is constructed by starting with a cycle of length k and randomly adding ⌈k/2⌉ other edges. For each cycle length k , we generate 50 random instances and compute the success rate, i.e., the fraction of times the model returns a length- k cycle. See Appendix B for the exact prompt used.
Figure 3: Box-plots of algorithm’s cost for the setting where the LLM’s visit time constraint is [1,20] . In (a), for 20 runs of TopIFT , the left two plots are the distribution of the algorithm’s cost for Best-of-LLM (N) baseline, while the right four plots are for TopIFT after r iterations. In (b), for one run of TopIFT , for different values of iteration r , the box-plot “ r:M ” is the distribution of the m⋅M=48 samples generated by the previous model, while “ r:T ” is the distribution of m=4 samples among these which have lowest algorithm’s cost (waiting time), and which are used for fine-tuning the new model.
Figure 4: Input graph and outputs of TopIFT and the various baselines. Note that (b) is simply the output of the base model L0 . The output of Best-of-ALG for N=600 and random spanning trees is comparable to (e), which means the model L0 assigns comparable probabilities to different random spanning trees.
Zeroth-order optimization uses function values or comparisons, rather than gradients, to optimize objectives when differentiation is unavailable or costly.