Research map / Learning theory and algorithms / Prediction and decision losses
Scalable Acceleration for Classification-Based Derivative-Free Optimization
Read the paperCheck 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.
Revisits the query-complexity bound of sequential classification-based DFO (SRACOS) via a new hypothesis-target shattering rate, and proposes RACE-CARS, which adds random region shrinking to SRACOS to accelerate convergence on synthetic functions and black-box LMaaS prompt tuning.
Problem
Derivative-free optimization of nonconvex black-box functions; existing query-complexity bounds for sequential classification-based DFO (SRACOS) are shown to overflow and be loose, and SRACOS converges slowly in high dimensions.
Approach
Introduce a hypothesis-target eta-shattering rate that avoids the error-target dependence assumption, derive a tighter query-complexity bound, and add a randomized region-shrinking projection step to the sampling distribution of SRACOS, which provably accelerates convergence.
Key results
- On synthetic functions with n=50 and n=500, RACE-CARS achieves better convergence and optimal values than SRACOS, with CMA-ES slightly better only on Sphere.
- On LMaaS black-box tuning with RoBERTa, RACE-CARS consistently accelerates SRACOS on SST-2 under a budget of 8000 API calls.
- On Yelp Polarity, AG's News, and RTE, CMA-ES performs better than RACE-CARS, which reaches comparable performance to CMA-ES.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add random region shrinking to SRACOS using RACE-CARS | SRACOS · Synthetic functions, n=50 and n=500 | best-so-far objective value | Helped |
| Add random region shrinking to SRACOS using RACE-CARS | SRACOS · SST-2 prompt tuning | training loss | Helped |
| Add random region shrinking to SRACOS using RACE-CARS | SRACOS · Yelp Polarity, AG's News, and RTE prompt tuning | training loss | Helped |
| Use RACE-CARS instead of CMA-ES | Black-box prompt tuning · Yelp Polarity, AG's News, and RTE | development accuracy | Mixed |
| Use RACE-CARS instead of CMA-ES | Synthetic optimization · Sphere | best-so-far objective value | Hurt |
| Set shrinking frequency to 0.004 rather than disable region shrinking (ablation) | RACE-CARS · Ackley, n=500, 30n calls | function value: 5.8 ± 0.1 -> 1.7 ± 0.4 | Helped |
| Set shrinking frequency to 0.002 rather than disable region shrinking (ablation) | RACE-CARS · Ackley, n=500, 30n calls | function value: 5.8 ± 0.1 -> 2.6 ± 0.4 | Helped |
| Increase shrinking frequency from 0.004 to 0.006 (ablation) | RACE-CARS · Ackley, n=500, 30n calls | function value: 1.7 ± 0.4 -> 3.1 ± 1.5 | Hurt |
| Set shrinking frequency to 0.022 rather than disable region shrinking (ablation) | RACE-CARS · Ackley, n=50, 30n calls | function value: 3.8 ± 0.2 -> 1.7 ± 0.3 | Helped |
| Increase shrinking frequency while dimension increases (ablation) | RACE-CARS · Ackley, dimensions 50 to 500 | function value | Mixed |
| Vary shrinking factor across dimensions (ablation) | RACE-CARS · Ackley, different dimensions | function value | No clear effect |
| Increase solution-space radius while varying shrinking factor (ablation) | RACE-CARS · Ackley, different solution-space radii | function value | Mixed |
Surprising findings
- CMA-ES outperforms RACE-CARS on Yelp Polarity, AG's News, and RTE, though it also overfits.
- The paper argues that the accuracy of trained hypotheses matters less than previously thought, since radical hypotheses can still be effective.
Limitations
- Acceleration theory applies to dimensionally local Holder continuous objectives, a restrictive condition.
- CMA-ES remains better on some tasks and on the Sphere function.
- Hyperparameters (shrinking rate and frequency) were tuned empirically, with guidance only from ablations on Ackley.
Experimental setup
Datasets: SST-2 Yelp polarity AG's News RTE
Benchmarks: Ackley Levy Rastrigin Sphere SST-2 Yelp polarity AG's News RTE
Metrics: best-so-far objective value training loss training accuracy development loss development accuracy
Baselines: SRACOS ZO-Adam differential evolution CMA-ES
Builds on: SRACOS RACOS CMA-ES
Closest papers by meaning
- Accelerating Optimization via Differentiable Stopping Time (NeurIPS 2025 · similarity 0.86)
- Tuning-Free Stochastic Optimization (ICML 2024 · similarity 0.85)
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.84)
- Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data (ICML 2024 · similarity 0.84)
- Taking the Road Less Scheduled with Adaptive Polyak Steps (NeurIPS 2026 · similarity 0.84)
- Evolution Fine-Tuning: Learning to Discover Across 371 Optimization Tasks (NeurIPS 2026 · similarity 0.83)
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.