  The efficacy of large language models (LLMs) in understanding and generating
natural language has aroused a wide interest in developing prompt-based methods
to harness the power of black-box LLMs. Existing methodologies usually
prioritize a global optimization for finding the global optimum, which however
will perform poorly in certain tasks. This thus motivates us to re-think the
necessity of finding a global optimum in prompt optimization. To answer this,
we conduct a thorough empirical study on prompt optimization and draw two major
insights. Contrasting with the rarity of global optimum, local optima are
usually prevalent and well-performed, which can be more worthwhile for
efficient prompt optimization (Insight I). The choice of the input domain,
covering both the generation and the representation of prompts, affects the
identification of well-performing local optima (Insight II). Inspired by these
insights, we propose a novel algorithm, namely localized zeroth-order prompt
optimization (ZOPO), which incorporates a Neural Tangent Kernel-based derived
Gaussian process into standard zeroth-order optimization for an efficient
search of well-performing local optima in prompt optimization. Remarkably, ZOPO
outperforms existing baselines in terms of both the optimization performance
and the query efficiency, which we demonstrate through extensive experiments.
