Scalable Acceleration for Classification-Based Derivative-Free Optimization

• (1)

  Our research extends the groundwork laid by (Yu, Qian, and Hu 2016; Hu, Qian, and Yu 2017), yet we discover that the upper bound they proposed for the SRACOS does not fully encapsulate its behavior, potentially allowing for an overflow. On the other hand, we construct a counter-example (eq. 3) illustrating the upper bound is not tight enough to delineate the convergence accurately.

• (2)

  We also identify a contentious assumption regarding the concept of error-target dependence that seems to underpin these limitations. In this paper, we introduce a novel learning theoretic concept termed the hypothesis-target $\eta$-shattering rate, which serves as a foundation for our reassessment of the upper bound on the computational complexity of SRACOS.

• (3)

  Inspired by the reanalysis, we recognize that the accuracy of the trained hypotheses is even less critical than previously thought. With this insight, we formulate a novel algorithm, RACE-CARS (an acronym for “RAndomized CoordinatE Classifying And Region Shrinking”), which perpetuates the essence of SRACOS while promises a theoretical enhancement in convergence. We design experiments on both synthetic functions and black-box tuning for LMaaS. These experiments juxtapose RACE-CARS against a selection of DFO algorithms, empirically highlighting the superior efficacy of RACE-CARS.

• (4)

  In discussion and appendix, we further substantiate the empirical prowess of RACE-CARS beyond the confines of continuity, also supported by theoretical framework. An ablation study is also conducted to demystify the selection of hyperparameters for our proposed algorithm.

The rest of the paper is organized in five sections, sequentially presenting the background, theoretical study, experiments, discussion and conclusion.

• (1)

  Overflow of the upper bound

  As assumptions entailed in (Yu, Qian, and Hu 2016; Hu, Qian, and Yu 2017), it can be observed that lower values of $\theta$ or $\gamma$ correlate with improved query complexity. However, this is not a hard-and-fast rule. Even with small values of these parameters, we can encounter scenarios where the expected performance does not materialize. Following the lemma given by (Yu, Qian, and Hu 2016): ${\mathbb{P}}(\mathcal{R}_{t})\leq{\mathbb{P}}(\mathcal{R}_{D_{t}})+m(\Omega)\sqrt{\frac{1}{2}D_{\mathrm{KL}}(D_{t}\|{\mathcal{U}}_{\Omega})}$, we have the following inequality:

  	$\displaystyle\Phi_{t}=$	$\displaystyle\biggl{(}1-\theta-{\mathbb{P}}(\mathcal{R}_{D_{t}})-m(\Omega)\sqrt{\frac{1}{2}D_{\mathrm{KL}}(D_{t}\|{\mathcal{U}}_{\Omega})}\biggr{)}\cdot|\Omega_{\alpha_{t}}|^{-1}$
  	$\displaystyle\leq$	$\displaystyle(1-\theta-{\mathbb{P}}(\mathcal{R}_{t}))\cdot|\Omega_{\alpha_{t}}|^{-1}.$

  The concept of error-target $\theta$-dependence reveals that a small $\theta$ does not guarantee small relative error ${\mathbb{P}}(\mathcal{R}_{t}).$ Contrarily, a small $\theta$ coupled with a large $({\mathbb{P}}(\Omega_{\epsilon}\cap\mathcal{R}_{t}))/|\Omega_{\epsilon}|$ can result in a significant ${\mathbb{P}}(\mathcal{R}_{t}),$ which can even be $1$ as long as $\Omega_{\alpha_{t}}$ is totally out of the active region of $h_{t},$ when the hypothesis $h_{t}$ is completely wrong. Problematically, as a divisor in the proof of Theorem 1, $\Phi_{t}\leq(1-\theta-{\mathbb{P}}(\mathcal{R}_{t}))\cdot|\Omega_{\alpha_{t}}|^{-1}$ is less or equal to 0, disrupting the established inequality. Nevertheless, in order that the inequality disrupt, ${\mathbb{P}}(\mathcal{R}_{t})$ is not necessary to be $1$ as $\theta$ is inherently nonnegative, highlighting that a series of inaccurate hypotheses can undermine the validity of the upper bound. This finding challenges the principle of SRACOS’s radical training strategy.

• (2)

  Tightness of the upper bound

  Consider an extreme but plausible situation where the hypotheses generated at each step are defined as follows:

  $$h_{t}(x)=\begin{cases}1,&x\in\Omega_{\epsilon}\\ 0,&x\notin\Omega_{\epsilon}.\end{cases}$$

  (3)

  In the context of sequential-mode classification-based optimization algorithms, where the training sets are not only small but also potentially biased, it’s reasonable to expect large relative errors ${\mathbb{P}}(\mathcal{R}_{t})$. This scenario could lead to a series of hypotheses that are inaccurate with respect to $\Omega_{\alpha_{t}}$ but, by chance, accurate with respect to $\Omega_{\epsilon}.$ Consequently, the error-target dependence $\theta=\max_{1\leq t\leq T}{\mathbb{P}}(\mathcal{R}_{t})$ can be unexpectedly large. Even all $\Phi_{t}$ values being positive, the query complexity bound given in Theorem 1 is therefore not optimistic. However, the probability of failing to identify an $\epsilon$-minimum:

  		$\displaystyle\Pr\bigl{(}\min_{1\leq t\leq T}f(x_{t})-f^{*}\geq\epsilon\bigr{)}$
  	$\displaystyle=$	$\displaystyle(1-|\Omega_{\epsilon}|)^{r}\biggl{(}(1-\lambda)(1-|\Omega_{\epsilon}|)\biggr{)}^{T-r},$

  is less than $\delta$ for a reasonably sized $T$. This indicates that the upper bound may not be as tight as initially thought.

It’s evident that even minimal error-target dependence can not encapsulate issues arising from substantial relative error. This is because error-target dependence alone is insufficient to fully account for relative error. Intuitively, one might consider introducing an additional assumption to cap relative error. However, such an assumption would be impractical, given the inherently small and biased nature of training datasets in the process. To this end, we give a new concept that stands apart from the constraints of relative error:

The hypothesis-target shattering rate mirrors the error-target dependence in its relation to the hypothesis’s target-accuracy. Importantly, it provides a limitation for error-target dependence in conjunction with relative error:

This rate, $\eta$, measures the overlap between the target set $\Omega_{\epsilon}$ and the active region of a hypothesis. Crucially, it also mitigates the influence of relative error on error-target dependence. Utilizing the concept hypothesis-target shattering rate, we reexamine the upper bound of $(\epsilon,\delta)$-query complexity in the subsequent theorem.

In the analysis of $(\epsilon,\delta)$-query complexity for classification-based optimization, the focus shifts away from minimizing relative error ${\mathbb{P}}(\mathcal{R}_{t})$, as our goal is to identify optima, not to develop a sequence of accurate hypotheses. The counter-example in equation (3), despite a potentially high relative error, represents an optimal hypothesis scenario. This realization allows for the consideration of more radical hypotheses, directing our attention to the overlap between $\Omega\epsilon$ and the active region of the hypotheses, which is quantified by the hypothesis-target shattering rate.

The $\gamma$-shrinking rate, as defined in Definition 3, measures the decay of ${\mathbb{P}}(x\in\Omega\colon h_{t}(x)=1)$. However, the rapid decrease of $|\Omega_{\alpha_{t}}|$ as $\alpha_{t}$ approaches zero makes it impractical to sustain a series of hypotheses with a small $\gamma$ through our training process. Thus, the $\gamma$-shrinking assumption is often not feasible for minimal $\gamma$.

Moving beyond the pursuit of minimal relative error and $\gamma$-shrinking relative to $|\Omega_{\alpha_{t}}|$, we introduce Algorithm 4, which adaptively shrinks the sampling random vector ${\mathbf{Y}}_{t}$’s active region through a $Projection$ sub-procedure.

The operator $\|\cdot\|$ returns a tuple represents the diameter of each dimension of the region. For instance, when $\Omega=[\omega^{1}_{1},\omega^{1}_{2}]\times[\omega^{2}_{1},\omega^{2}_{2}],$ we have$\|\Omega\|=(\omega^{1}_{2}-\omega^{1}_{1},\omega^{2}_{2}-\omega^{2}_{1}).$ The projection operator $Proj(h_{t},\tilde{\Omega})$ generates a random vector ${\mathbf{X}}_{t}$ with probability distribution $D_{\tilde{h}_{t}}:=\tilde{h}_{t}/{\mathbb{P}}(\{x\in\Omega\colon\tilde{h}_{t}(x)=1\}),$ with $\tilde{h}_{t}(x)=1$ whenever $h_{t}(x)=1$ for $x\in\tilde{\Omega}.$ The sampling random vector ${\mathbf{Y}}_{t}$ is induced by ${\mathbf{X}}_{t}.$ The subsequent theorem presents the upper bound of query complexity for Algorithm 4.

The condition $\gamma\in(0,1)$ ensures that the term $2p/(\gamma^{-\rho}+\gamma^{-(T-r)\rho})$ is significantly less than 1. According to Theorem 3, the $(\epsilon,\delta)$-query complexity of the Algorithm 4 is lower than that of Algorithm 3 providing $\eta>0$.

Theorem 3 establishes an upper bound on the $(\epsilon,\delta)$-query complexity that is applicable to a wide range of scenarios, assuming only that the objective function $f$ is lower-bounded. Building on this, we identify a sufficient condition for acceleration that applies to dimensionally local Holder continuity functions (Definition 5), detailed in the appendix. Within this context, the SRACOS algorithm, which utilizes RACOS for $Training$ phase in Algorithm 3, exhibit polynomial convergence (Hu, Qian, and Yu 2017). We adopt the same RACOS approach for $Training$ sub-procedure in Algorithm 4, introducing ”RAndomized CoordinatE Classifying And Region Shrinking” (RACE-CARS) algorithm.

We commence our empirical experiments with four benchmark functions: Ackley, Levy, Rastrigin and Sphere. Their analytic forms and 2-dimensional illustrations are detailed in Appendix. Characterized by extreme non-convexity and numerous local minima and saddle points—with the exception of the Sphere function—each is minimized within the boundary $\Omega=[-10,10]^{n}$, with a global minimum value of $0$. We choose the dimension of solution space $n$ to be $50$ and $500,$ with corresponding function evaluation budgets of $5000$ and $50000$. Notably, as indicates, the convergence of the RACE-CARS requires only a fraction of this budget.

Region shrinking rate is configured to be $\gamma=0.9$ and $0.95$, with shrinking frequency of $\rho=0.01$ and $0.001$ for $n=50,500$, respectively. Each algorithm is executed over 30 trials, and the mean convergence trajectories of the best-so-far values are depicted in Figure 1 and Figure 2. The numerical values adjacent to the algorithm names in the legends represent the mean of the attained minima. It is evident that that RACE-CARS performs the best on both convergence speed and optimal value, with a slight edge to CMA-ES on the strongly convex Sphere function. Yet this comes at the cost of scalability due to CMA-ES’s reliance on an $n$-dimensional covariance matrix, which is significantly more computationally intensive compared to the other algorithms.

Prompt tuning for extremely large pre-trained language models (PTMs) has shown great power. PTMs such as GPT-3 (Brown et al. 2020) are usually released as a service due to commercial considerations and the potential risk of misuse, allowing users to design individual prompts to query the PTMs through black-box APIs. This scenario is called Language-Model-as-a-Service (LMaaS) (Diao et al. 2022; Sun et al. 2022). In this part we follow the experiments designed by (Sun et al. 2022) ¹¹1Code can be found in https://github.com/txsun1997/Black-Box-Tuning, where language understanding task is formulated as a classification task predicting for a batch of PTM-modified input texts $X$ the labels $Y$ in the PTM vocabulary, namely we need to tune the prompt such that the black-box PTM inference API $f$ takes a continuous prompt ${\mathbf{p}}$ satisfying $Y=f({\mathbf{p}};X).$ Moreover, to handle the high-dimensional prompt ${\mathbf{p}},$ (Sun et al. 2022) proposed to randomly embed the $D$-dimensional prompt ${\mathbf{p}}$ into a lower dimensional space $\mathbb{R}^{d}$ via random projection matrix ${\mathbf{A}}\in\mathbb{R}^{D\times d}.$ Therefore, the objective becomes:

where $\mathcal{Z}=[-50,50]^{d}$ is the search space and $\mathcal{L}(\cdot)$ is cross entropy loss.

In our experimental setup, we configure the search space dimension to $d=500$ and the prompt length to $50$, with RoBERTa (Liu et al. 2019a) serving as the backbone model. We evaluate performance on datasets SST-2 (Socher et al. 2013), Yelp polarity and AG’s News (Zhang, Zhao, and LeCun 2015), and RTE (Wang et al. 2018a). With a fixed API call budget of $T=8000,$ we pit RACE-CARS against SRACOS and the default DFO algorithm CMA-ES utilized in (Sun et al. 2022) ²²2 Our choice to exclude ZO-Adam and DE is based on their suboptimal performance with high-dimensional nonconvex black-box functions, as demonstrated in the last section..

For our tests, the shrinking rate is $\gamma=0.7$, with shrinking frequency of $\rho=0.002.$ Each algorithm is repeated 5 times independently with unique seeds. We assess the algorithms based on the mean and deviation of training loss, training accuracy, development loss and development accuracy. The SST-2 dataset results are highlighted in Figure 3, with additional findings for Yelp Polarity, AG’s News, and RTE detailed in the appendix. The results indicate that RACE-CARS consistently accelerates the convergence of SRACOS. While CMA-ES shows superior performance on Yelp Polarity, AG’s News, and RTE, it also exhibits signs of overfitting. RACE-CARS achieves comparable performance to CMA-ES, despite the latter’s hyperparameters being finely tuned. Notably, the hyperparameters for RACE-CARS were empirically adjusted based on the SST-2 dataset and then applied to the other three datasets without further tuning.

• (i)

  For discontinuous objective functions.

  Dimensionally local Holder continuity in Definition 5, imposes certain constraints on the objective through a set of continuous envelopes, whereas the objective is not supposed to be continuous. Beyond the continuous cases discussed in the previous section, RACE-CARS remains applicable to discontinuous objectives as well. Refer to appendix for a comprehensive understanding.

• (ii)

  For discrete optimization.

  Similar to SRACOS algorithm, RACE-CARS retains the capability to tackle discrete optimization problems. The convergence theorems, presented in Theorem 2 and Theorem 3, encompass this situation by altering the measure of probability space to be for example, induced by counting measure. We extend experiments on mixed-integer programming problems, substantiating the acceleration of RACE-CARS empirically. See appendix for details.

The concept hypothesis-target shattering, central to our discussion, draws inspiration from the established learning theory notion of shatter and its deep ties to the Vapnik-Chervonenkis (VC) theory (Vapnik et al. 1998). At the heart of VC theory lies the VC dimension, a measure of a hypothesis family’s capacity to distinguish among data points based on their labels. Specifically, for a collection of data points with binary labels, $S$, we say a subset $S^{\prime}\subseteq S$ is shattered by a hypothesis family $\mathcal{H}$ if there exists a hypothesis $h\in\mathcal{H}$ that perfectly aligns with the labels of points in $S^{\prime}$ and contrasts with those outside:

The shattering coefficient, $\mathcal{S}(\mathcal{H},n)$, signifies the variety of point-label combinations that $\mathcal{H}$ can produce for $n$ points. The VC dimension is then defined as $VC(\mathcal{H}):=\{\sup{n:\mathcal{S}(\mathcal{H},n)=2^{n}}\}$, indicating the maximum number of points that can be distinctly labeled by $\mathcal{H}$.

In the context of classification-based DFO, we represent the target-representative capability of a family of hypotheses through hypothesis-target shattering, measuring the overlap of hypothesis’s active region and the target. Therefore the quintessence of algorithm design hinges on maximizing this quantity. discerning the target-representative capacity within the intricate landscape of nonconvex, black-box optimization problems is nontrivial. Nonetheless, the target-representative capability of hypotheses family generated by RACOS, although proved under the previous framework, empirically suggests sufficient efficacy in scenarios where the objective function exhibits locally Holder continuouity. Looking ahead, altering the $Training$ and $Replacing$ sub-procedures inherited from SRACOS, which may ideally lead to a bigger shattering rate and maintain the easy-to-sample characterization, will be another extension direction of the current study.

While it’s an appealing goal to develop a universally effective DFO algorithm for black-box functions without the need for hyperparameter tuning, this remains an unrealistic aspiration. Our proposed algorithm, RACE-CARS, introduces two hyperparameters: shrinking-rate $\gamma$ and shrinking-frequency $\rho.$ For an $n$-dimensional optimization problem, we call $\gamma^{n\rho}$ shrinking factor of RACE-CARS. We take Ackley for a case study, design ablation experiments on the two hyperparameters of RACE-CARS to reveal the mechanism. We stipulate that we do not aim to identify a optimal combination of hyperparameters for maximizing the overlap with the target hypothesis. Instead, our aim is to provide empirical guidance for tuning these hyperparameters effectively. For further details, the reader is directed to the appendix.