Scalable Acceleration for Classification-Based Derivative-Free Optimization

Tianyi Han, Jingya Li, Zhipeng Guo, Yuan JinAAAI 2025 · DOI

TL;DR

This paper introduces RACE-CARS, a novel derivative-free optimization (DFO) algorithm that accelerates convergence by strategically shrinking the search region. It addresses limitations in existing classification-based DFO methods by proposing a new theoretical concept, the "hypothesis-target η-shattering rate," and demonstrates RACE-CARS's superior performance on synthetic benchmarks and real-world language model tuning tasks.

What Problem Does This Paper Address?

Derivative-free optimization (DFO) algorithms are crucial for optimizing functions where gradients are unavailable or computationally expensive to obtain, such as in hyperparameter tuning for machine learning models or engineering design. While classification-based DFO methods have shown promise by learning a classifier to identify promising regions of the objective function, existing theoretical bounds on their performance have limitations. Specifically, the paper identifies issues with the "error-target 0-dependence" concept, which can lead to an "overflow" or inaccurate upper bounds on query complexity, especially in non-convex and high-dimensional scenarios. The authors aim to overcome these limitations by developing a more robust theoretical framework and a more efficient algorithm.

Methods

The core contribution of this paper is the RACE-CARS algorithm, which builds upon the sequential classification-based DFO framework. Key methodological advancements include:

  • Hypothesis-Target η-Shattering Rate: A new theoretical concept introduced to better characterize the relationship between a hypothesis (classifier) and the target sub-level set of the objective function. This concept aims to provide a more accurate measure of a hypothesis family's ability to distinguish promising regions, moving beyond the limitations of error-target dependence.
  • Region Shrinking Acceleration: RACE-CARS incorporates a novel "region shrinking" step. This step adaptively reduces the search space for generating new candidate points, guided by the learned hypothesis. This is a departure from methods that solely focus on accurately classifying the objective function.
  • Theoretical Re-analysis: The authors re-examine the query complexity upper bounds of existing algorithms like SRACOS, identifying flaws in previous theoretical analyses and proposing a new, more accurate bound based on the hypothesis-target η-shattering rate.
  • Algorithm 4 (RACE-CARS): This algorithm integrates the region shrinking mechanism with a projection sub-procedure to refine the sampling process.

Datasets

The paper evaluates RACE-CARS on:

  • Synthetic Functions: Ackley, Levy, Rastrigin, and Sphere functions are used to test the algorithm's performance on various types of objective functions, including those with extreme non-convexity and multiple local minima. Experiments are conducted in both 50 and 500 dimensions.
  • Language Model Tuning (LMaaS): The authors apply RACE-CARS to prompt tuning for pre-trained language models (PTMs) on the SST-2, Yelp Polarity, AG's News, and RTE datasets. This real-world application involves optimizing a high-dimensional prompt vector to achieve desired classification outcomes.

Key Insights and Ideas

  • Accuracy of Hypotheses is Less Critical Than Expected: The paper's theoretical re-analysis suggests that the accuracy of the learned hypothesis is not as paramount as previously thought. Instead, the overlap between the hypothesis's active region and the target sub-level set (captured by the shattering rate) is more crucial for efficient optimization.
  • Region Shrinking is a Powerful Acceleration Mechanism: The introduction of an adaptive region shrinking step in RACE-CARS significantly improves convergence speed and final solution quality, especially in high-dimensional and non-convex problems.
  • New Theoretical Framework for DFO: The "hypothesis-target η-shattering rate" offers a more nuanced way to analyze classification-based DFO algorithms, addressing limitations of prior theoretical concepts and leading to tighter complexity bounds.
  • Robustness to Discontinuities: Experiments show that RACE-CARS, unlike some other DFO methods, remains largely unaffected by discontinuous objective functions, making it more broadly applicable.

Key Results

  • Synthetic Functions: RACE-CARS consistently outperforms SRACOS and other baseline DFO algorithms (ZO-Adam, DE, CMA-ES) in terms of convergence speed and the quality of the final attained minimum across various synthetic functions and dimensions. For example, on the Ackley function with n=50, RACE-CARS achieves a value of 0.031 compared to SRACOS's 1.705.
  • LMaaS Tuning: In black-box tuning for language models, RACE-CARS demonstrates accelerated convergence compared to SRACOS on datasets like SST-2, Yelp P, AG's News, and RTE. While CMA-ES sometimes achieves comparable or slightly better final accuracy, RACE-CARS offers comparable performance with potentially simpler hyperparameter tuning and better scalability.
  • Discontinuous Objectives: RACE-CARS shows remarkable resilience to discontinuous objective functions, maintaining its performance advantage over baselines that suffer from oscillations or early stopping.
  • Discrete Optimization: The paper also demonstrates RACE-CARS's effectiveness in mixed-integer programming problems, maintaining its acceleration over SRACOS.

Limitations and Future Work

  • Hyperparameter Tuning: While the paper provides empirical guidance for tuning RACE-CARS's hyperparameters (shrinking rate $\gamma$ and shrinking frequency $p$), it acknowledges that finding universally optimal settings remains a challenge. Future work could explore more automated or adaptive hyperparameter selection strategies.
  • Extension to Other DFO Frameworks: The paper suggests that the concepts and techniques developed could be extended to other DFO algorithms and problem types.
  • Further Exploration of Discontinuous and Discrete Optimization: While experiments are presented, further investigation into the theoretical guarantees and practical performance of RACE-CARS on these challenging problem classes could be beneficial.
  • Altering Training and Replacing Sub-procedures: The authors mention that modifying the training and replacing sub-procedures inherited from SRACOS could potentially lead to larger shattering rates and maintain the easy-to-sample characterization, suggesting this as a future research direction.

Summary updated

BibTeX
@inproceedings{han2025scalable,
  author = {Tianyi Han and Jingya Li and Zhipeng Guo and Yuan Jin},
  title = {{Scalable Acceleration for Classification-Based Derivative-Free Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i16.33874},
}
Figure