Research map / Learning theory and algorithms / Prediction and decision losses

Adaptive Partitioning Schemes for Optimistic Optimization

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Determinantal point process inference

Read the paper Check your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Learns a rotated low-dimensional partitioning (via a single-hidden-layer network's top singular vectors) for SequOOL-style optimistic optimization, proving improved regret for multi-index functions and applying it to joint AWQ scale tuning for OPT-1.3B.

Problem

Optimistic optimization for black-box functions relies on a domain partitioning scheme whose quality strongly affects performance; the default axis-aligned partition scales poorly and fails to exploit low-dimensional structure in high-dimensional problems.

Approach

Learn an adaptive partitioning from the top right singular vectors of a neural network fit to function samples, defining cells in the estimated active subspace and optionally choosing split directions adaptively via a lookahead strategy on the surrogate; for multi-index functions this gives improved regret exponents over SequOOL.

Key results

On Rastrigin, the proposed method reaches zero regret while SequOOL reaches 4.22e-5.
For OPT-1.3B AWQ quantization, the proposed joint 72-dimensional optimization reduces the gap to the unquantized model from 2.45 (AWQ, PPL 16.92) to 2.21 (PPL 16.68), about 10% relative improvement.
For multi-index functions, the regret exponent improves from 1/eta to beta/eta with beta = 1 + (d-m)/(2m-1).

Measured effects reported in the paper

What was changed	Where	Measured	Effect
jointly optimize scaling factors across all layers rather than use separate 1D AWQ grid searches	OPT-1.3B quantization with Algorithm 2 · WikiText-2	PPL: 16.92 -> 16.68	Helped
jointly optimize scaling factors across all layers rather than use separate 1D AWQ grid searches	OPT-1.3B quantization with Algorithm 2 · Calibration set	PPL: 14.62 -> 14.29	Helped
use Algorithm 1 instead of AWQ grid search	OPT-1.3B quantization · WikiText-2	PPL: 16.92 -> 16.96	Hurt
use Algorithm 2 instead of SequOOL	OPT-1.3B quantization · Calibration set	PPL: 14.28 -> 14.29	Hurt
learn and use an adaptive partitioning scheme	black-box optimization method · Rastrigin	regret: 4.22 \times 10^{-5} -> zero	Helped
learn and use an adaptive partitioning scheme	black-box optimization method · Rastrigin	regret: 5.5 \times 10^{-3} -> zero	Helped
learn and use an adaptive partitioning scheme	black-box optimization method · Styblinski-Tang	function evaluations to reach zero regret: 2000 -> approximately 900	Helped
use 2:1 direction splitting instead of lookahead direction selection (ablation)	SequOOL with adaptive partitioning · Illustrative function from direction-selection example	regret: 5.68 \times 10^{-10} -> 1.8 \times 10^{-4}	Hurt
use 1:1 direction splitting instead of lookahead direction selection (ablation)	SequOOL with adaptive partitioning · Illustrative function from direction-selection example	regret: 5.68 \times 10^{-10} -> 1.98 \times 10^{-5}	Hurt

Surprising findings

On Sharp Ridge, Ellipsoid, and (x1-1)^2+(x72-1)^4, the proposed method performs slightly worse than RESOO, attributed to the large first-stage sample budget.
When the multi-index assumption fails (AWQ experiments), improvement over SequOOL is minimal.

Limitations

Requires estimating the subspace dimension m; choice is heuristic via 95% variance.
First-stage sampling consumes part of the evaluation budget.
Gains are minimal when the multi-index structure does not hold, as in the LLM quantization setting.

Experimental setup

Datasets: WikiText-2 Pile

Benchmarks: Rastrigin Sphere Styblinski-Tang Branin Hartmann-6 Sharp Ridge Ellipsoid WikiText-2

Metrics: simple regret perplexity

Baselines: SequOOL SOO RESOO REMBO HeSBO CMA-ES Dual Annealing DiRect Random Search AWQ grid search

Builds on: SequOOL SOO AWQ RESOO TuRBO

Closest papers by meaning

Learning Surrogates for Offline Black-Box Optimization via Gradient Matching (ICML 2024 · similarity 0.86)
BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability (NeurIPS 2026 · similarity 0.86)
ROOT: Rethinking Offline Optimization as Distributional Translation via Probabilistic Bridge (NeurIPS 2025 · similarity 0.86)
Posterior Inference in Latent Space for Scalable Constrained Black-box Optimization (NeurIPS 2026 · similarity 0.86)
Posterior Inference with Diffusion Models for High-dimensional Black-box Optimization (ICML 2025 · similarity 0.86)
A Study of First-Order Methods with a Deterministic Relative-Error Gradient Oracle (ICML 2024 · similarity 0.86)

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft