# Complexity in Bolza Surface

,  Bhola Nath Saha  Department of Mathematics and Statistics
Indian Institute of Technology
Kanpur, Uttar Pradesh-208016
India<EMAIL_ADDRESS>and  Bidyut Sanki  Department of Mathematics and
Statistics
Indian Institute of Technology
Kanpur, Uttar Pradesh-208016
India<EMAIL_ADDRESS>
###### Abstract.

A surface in the Teichmüller space, where the systole function attains its
maximum, is called a maximal surface. For genus two there exists a unique
maximal surface which is called the Bolza surface. In this article, we study
the complexity of the set of systolic geodesics on the Bolza surface. We show
that any non-systolic geodesic intersects the systolic geodesics in $2n$
points, where $n\geq 5$. Furthermore, we show that there are $12$ second
systolic geodesics on the Bolza surface and they form a triangulation of the
surface.

##  1\. Introduction

A Riemann surface of constant curvature $-1$ is called a _hyperbolic surface_.
A compact surface with empty boundary is called a _closed surface_. In this
article, by a surface we always mean a closed hyperbolic surface. For $g\geq
2$, let $\mathcal{T}_{g}$ denote the Teichmüller space of hyperbolic surfaces
of genus $g$ (see Section 10.1 [4]). A shortest essential closed geodesic on a
surface $X\in\mathcal{T}_{g}$ is called a _systolic geodesic_ of $X$. The
function $\mathrm{sys}:\mathcal{T}_{g}\to\mathbb{R}_{+}$, where
$\mathrm{sys}(X)$ is the length of a systolic geodesic of $X$ (see Section 1
[9]), is called the systole function on $\mathcal{T}_{g}$ and
$\mathrm{sys}(X)$ is called the systole of $X$.

The function $\mathrm{sys}$ has been studied extensively by P. Schmutz [9],
[10] H. Akrout [1] and others. In Theorem A [9], Schmutz has shown that
$\mathrm{sys}$ is a topological Morse function and studied the properties of
its critical points. It is an interesting and difficult problem to find the
critical points of the systole function explicitly. These are the surfaces
where $\mathrm{sys}$ attains its local maximum. For $g=2$, there is a unique
surface (up to isometry), namely the Bolza surface in $\mathcal{T}_{2}$, where
the systole function attains a global maximum (see Section 5 [10]). The Bolza
surface can be obtained by identifying the opposite sides of a regular
hyperbolic octagon with interior angle $\frac{\pi}{4}$ (Secttion 5 [10]). It
has $12$ systolic geodesics and this is the genus two hyperbolic surface with
the biggest automorphism group. In Theorem 3.1 [8], Sanki has given an
explicit description of the systolic geodesics on the Bolza surface and shown
that the set of all systolic geodesics forms a triangulation of the surface.
Furthermore, he has studied the complexity of the set of systolic geodesics to
some extent.

The $k$-th complexity of a given system of closed geodesics on a surface is
the number of simple closed geodesics which intersect the collection exactly
at $k$ many points. In this article, we further extend the study of complexity
of the systolic geodesics of the Bolza surface. We show that the $k$-th
complexity of systollic geodesics is zero when either $k<10$ or $k$ is an odd
integer. Furthermore, for any $k\geq 10$ even, the $k$-th complexity is finite
(see Theorem 3.1).

The set $\mathrm{Spec(X)}$ of lengths of all simple closed geodesics on a
surface $X\in\mathcal{T}_{g}$ is called the _length spectrum_ of $X$. The
length spectrum of a surface is a discrete subset of $\mathbb{R}_{+}$ (see
Lemma 12.4 [4]) and hence its elements can be arranged in an ascending order

$\mathrm{Spec(X)}=\\{l_{i}\mid l_{i+1}>l_{i},\text{ for all
}i\in\mathbf{N}\\}.$

The $i$-th element $l_{i}$ of $\mathrm{Spec}(X)$ is called the $i$-th systole
of $X$. A simple closed geodesic of length $l_{i}$ is called $i$-th systolic
geodesic. Note that, $l_{1}=\mathrm{sys}(X)$. It is a very difficult problem
to find the length spectrum of a given hyperbolic surface, in general. The
length spectrum of the Bolza surface has been extensively studied by R.
Aurich, F. Steiner and E. B. Bogomolny (see [2], [3]). In particular, the
authors have evaluated $i$-th systole on the Bolza surface, for certain values
of $i$. In Section 2 of [3], Aurich-Steiner have shown that the length of the
second systolic geodesic in the Bolza surface is
$2\cosh^{-1}{\left(3+2\sqrt{2}\right)}$. In this article, we show that there
are only $12$ second systolic geodesics on the Bolza surface and they form a
triangulation of the surface (see Theorem 4.1).

##  2\. Preliminaries

In this section, we recall the notion of complexity of a system of curves on a
surface, $(p,q,r)$-triangle and hyperelliptic surface. Also, we describe the
isometries of the Bolza surface. These are essential for the subsequent
sections.

######  Definition 2.1.

For a non-negative integer $k$, the _$k$ -th complexity_ of a system of curves
$\Omega$ on a surface $X$, denoted by $\mathcal{T}_{k}(\Omega)$, is the
cardinality of the set below

$\left\\{\gamma\in\mathcal{C}(X)\setminus\Omega\mid\sum_{\alpha\in\Omega}i(\alpha,\gamma)\leq
k\right\\},$

where $\mathcal{C}(X)$ denotes the collection of all simple closed curves on
$X$, pairwise distinct up to free homotopy.

######  Example 2.2.

Consider $\Omega=\\{\alpha,\beta\\}$, where $\alpha$, $\beta$ are simple
closed curves as given in Figure 2.1. The $0$-th complexity of
$\Omega,\mathcal{T}_{0}(\Omega)=0$, as the curves fill the surface. It is
straightforward to see that the $0$-th complexity of
$\Sigma=\\{\alpha,\gamma\\}$ is infinite.

$\gamma$$\alpha$$\beta$ Figure 2.1. Filling pair on $S_{2}$.

######  Definition 2.3.

Given positive integers $p,q,r$, satisfying
$\frac{1}{p}+\frac{1}{q}+\frac{1}{r}<1$, a $(p,q,r)$-triangle is the
hyperbolic triangle with angles $\frac{\pi}{p},\frac{\pi}{q},\frac{\pi}{r}$.

$\frac{\pi}{p}$$\pi/q$$\pi/r$ Figure 2.2. A hyperbolic triangle of type
$(p,q,r)$.

###  2.1. Isometries of Bolza surface

Consider a regular hyperbolic octagon with each interior angle $\frac{\pi}{4}$
and equipped with a side paring as indicated in Figure 2.3. After
identification of the sides in pair, the resulting surface is the Bolza
surface (see Section 5 [10]). The rotation of the octagon about the center by
an angle $\frac{\pi}{4}$ is side paring equivariant and hence induces an
isometry of order eight, denoted by $R$.

$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{2}$$a_{1}$$b_{2}$$b_{1}$$c_{2}$$c_{1}$$d_{2}$$d_{1}$$a_{1}$$a_{2}$$b_{1}$$b_{2}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$f_{1}$$f_{2}$$f_{3}$$f_{4}$$f_{5}$$f_{6}$$f_{7}$$f_{8}$
Figure 2.3. Triangulation of the octagon by $(4,4,4)$ triangles and isometry
of order $8$.

Now, we describe an order $3$ isometry of the Bolza surface. For this, we
consider the triangulated polygonal representation of the Bolza surface as
given in Figure 2.4 where each triangle is of the form $(4,4,4)$. We note that
this representation is obtained from the representation obtained from Figure
2.3 by cut and paste and therefore, they are equivalent. The rotations of the
polygons about the centers by an angle $\frac{2\pi}{3}$ as indicated in Figure
2.4 respect the side paring and hence induce an order $3$ isometry $L$ of the
Bolza surface. It is straightforward to see that the isometries $R$ and $L$
generates the full orientation preserving isometry group of the Bolza surface.

$e_{2}$$d_{1}$$c_{2}$$e_{8}$$f_{3}$$f_{8}$$e_{1}$$f_{2}$$f_{1}$$c_{1}$$d_{1}$$e_{6}$$f_{3}$$e_{8}$$f_{4}$$a_{1}$$b_{2}$$e_{3}$$f_{4}$$f_{7}$$e_{6}$$d_{2}$$e_{4}$$c_{1}$$f_{6}$$f_{5}$$e_{5}$$f_{8}$$e_{4}$$c_{2}$$d_{2}$$f_{7}$$e_{2}$$b_{1}$$e_{7}$$a_{2}$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 2.4. Order $3$ isometry.

###  2.2. Hyperelliptic involution in Bolza surface

A _hyperelliptic involution_ of a Riemann surface $\Sigma$ of genus $g$ is a
conformal automorphism $J:\Sigma\to\Sigma$ of order two with $2g+2$ fixed
points. The fixed points are the _Weierstrass points_. A surface $\Sigma$
admitting a hyperelliptic involution is called a _hyperelliptic surface_. Note
that, every hyperbolic surface of genus two is hyperelliptic. For more
details, we refer the readers to Section 3.7 of [5].

The rotation of the octagon (see Figure 2.5) about the center by an angle
$\pi$ induces the hyperelliptic involution of the Bolza surface. We recall the
result below due to Haas-Susskind [6] which is essential for the subsequent
sections.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$c$$d$$a$$b$$c$$d$$a$$b$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\pi$
Figure 2.5. Hyperelliptic involution of the Bolza Surface. $\bullet$
represents the fixed point of the involution.

######  Theorem 2.4 (Theorem 1 [6]).

Let $J$ be the hyperelliptic involution of a genus two Riemann surface $M$.
Then every simple closed geodesic on $M$ is mapped onto itself by $J$.
Furthermore, suppose $\alpha$ is a simple closed geodesic on $M$. If $\alpha$
is a separating curve then $J$ preserves the orientation of $\alpha$.
Otherwise, $J$ reverses the orientation of $\alpha$.

##  3\. Complexity

The goal of this section is to prove the theorem below.

######  Theorem 3.1.

Let $\mathrm{Sys}(S)$ be the set of all systolic geodesics on the Bolza
surface $S$. The $k$-th complexity $\mathcal{T}_{k}(\mathrm{Sys}(S))$ of
$\mathrm{Sys}(S)$ is zero for all odd integer $k$ and even integer $k<10$.

In Section 2.1, we have seen that the Bolza surface is obtained by identifying
the opposite sides of a regular hyperbolic octagon with each interior angle
$\frac{\pi}{4}$. There is an alternative construction of the Bolza surface
(Section 3 of [8]), by taking two identical copies of right angled regular
hyperbolic octagon and identifying the sides in pair as shown in Figure 3.1.
The sides $\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\}$, $\\{c_{1},c_{2}\\}$ and
$\\{d_{1},d_{2}\\}$ project onto simple closed geodesics on $S$. We denote
these geodesics by $a,b,c,d$ respectively and define
$\Omega_{1}=\\{a,b,c,d\\}$. Also, the diagonals joining opposite vertices of
each octagon project onto simple closed geodesics. We define $\Omega_{2}$ as
the collection of all such geodesics. In [8], Sanki has proved that
$\mathrm{Sys}(S)=\Omega_{1}\cup\Omega_{2}$ is the set of all systolic
geodesics in $S$.

Let $p:\mathbb{D}\to S$ be the universal covering map, where $\mathbb{D}$ is
the Poincare disc model of the hyperbolic plane. Then $p^{-1}(\Omega_{1})$ is
a tessellation $\mathbb{T}$ of $\mathbb{D}$ by regular right angled octagons.
Each tile of $\mathbb{T}$ maps under $p$ to one of the octagons $P_{1}$ or
$P_{2}$, as in Figure 3.1. A tile of $\mathbb{T}$ is called of Type I (or Type
II) if it maps to $P_{1}$ (or $P_{2}$ respectively).

We regard $\mathrm{Sys}(S)$ as a graph, where the vertices are the
intersection points of the systolic geodesics and the geodesic segments
between the vertices are the edges, which is called the systolic graph of $S$.

$c_{2}$$d_{2}$$a_{1}$$b_{1}$$c_{1}$$d_{1}$$a_{2}$$b_{2}$$c_{1}$$b_{2}$$a_{1}$$d_{1}$$c_{2}$$b_{1}$$a_{2}$$d_{2}$Octagon
$P_{1}$Octagon $P_{2}$ Figure 3.1. Alternative description of the Bolza
Surface.

######  Lemma 3.2.

The set $\Gamma$ of all non-systolic geodesics in $S$, intersecting the
systolic graph only at the vertices, has $16$ elements.

###### Proof.

Suppose $\delta\in\Gamma$ and $\tilde{\delta}$ denotes its path lift in
$\mathbb{D}$ with initial point at some vertex. Then $\tilde{\delta}$ is
contained in only the same type of tiles, otherwise $\tilde{\delta}$ will have
a non-tranversal intersection with a lift of a systolic geodesic. Furthermore,
$\tilde{\delta}$ passes through atmost two octagons, as $\delta$ is simple.
The arcs $\\{\gamma_{1},\gamma_{2}\\}$ and $\\{\beta_{1},\beta_{2}\\}$ in
Figure 3.2 project to two geodesics satisfying the properties of the lemma.
Using isometry of the Bolza surface and interchanging the octagons, we get the
remaining 14 geodesics.

$c_{2}$$d_{2}$$a_{1}$$b_{1}$$c_{1}$$d_{1}$$a_{2}$$b_{2}$$c_{1}$$b_{2}$$a_{1}$$d_{1}$$c_{2}$$b_{1}$$a_{2}$$d_{2}$$\gamma_{1}$$\gamma_{2}$$\beta_{1}$$\beta_{2}$Octagon
$P_{1}$Octagon $P_{2}$ Figure 3.2. Non-systolic geodesics on Bolza surface.

∎

For a non-systolic geodesic $\delta$ in $S$ with $\delta\notin\Gamma$, define

$i(\Omega_{1},\delta)\coloneqq\sum_{\alpha\in\Omega_{1}}i(\alpha,\delta).$

As $i(\Omega_{1},\delta)\neq 0$, there exists a path lift of $\delta$ in the
universal cover $\mathbb{D}$, with initial point on the boundary of a tile in
the tessellation described above. Furthermore, we can choose the initial point
in the interior of some side in $p^{-1}(\Omega_{1})$. Let $\tilde{\delta}$ be
such a path lift of $\delta$. Now, we prove a technical lemma below which is
used for the proof of Theorem 3.1.

######  Lemma 3.3.

$i(\Omega_{1},\delta)=|p^{-1}(\Omega_{1})\cap\tilde{\delta}|-1$.

###### Proof.

The curves considered here are geodesics and hence they are in pairwise
minimal position. The initial and the terminal points of $\tilde{\delta}$ are
identified implies $i(\Omega_{1},\delta)\leq|\Gamma\cap\tilde{\delta}|-1$. If
some interior points of $\tilde{\delta}$ are identified, then it contradicts
that $\delta$ is simple. ∎

Next, we prove two lemmas below (Lemma 3.4 and Lemma 3.5) which together imply
that the odd complexity of $\mathrm{Sys}(S)$ is zero.

######  Lemma 3.4.

If $\gamma$ is a non-systolic geodesic in the Bolza surface $S$, then
$i(\gamma,\Omega_{1})$ is an even integer.

###### Proof.

If $\gamma\in\Gamma$, then $i(\gamma,\Omega_{1})=2$. Now, suppose that
$\gamma\notin\Gamma$. As $\Omega_{1}$ is a filling system,
$i(\gamma,\Omega_{1})\neq 0$. Let $\tilde{\gamma}$ be a path lift of $\gamma$
with initial point in the interior of some side of a octagon determined by
$p^{-1}(\Omega_{1})$. Now, there are following two cases to be considered.

Case 1. If $\tilde{\gamma}$ does not pass through any of the vertices of the
octagons then $\tilde{\gamma}$ alternatively passes through octagons of Type I
and Type II. As $\gamma$ is simple and sides of Type I octagons are identified
with the sides of Type II octagons, so if $\tilde{\gamma}$ starts from a point
on a side of Type I octagon then it ends at a point on a side of Type II
octagon and vice versa. Therefore, $\tilde{\gamma}$ passes through an even
number of octagons, say $2n$. As $\tilde{\gamma}$ intersect each of them
twice. By Lemma 3.3, we have $i(\gamma,\Omega_{1})=2n$, which is even.

Case 2. If $\tilde{\gamma}$ passes through some vertices, then we perturb
$\tilde{\gamma}$ near the vertices and get a new arc $\tilde{\gamma}^{\prime}$
which does not pass through a vertex (see Figure 3.3). This arc
$\tilde{\gamma}^{\prime}$ has the same number of points of intersection with
$p^{-1}(\Omega_{1})$ as $\tilde{\gamma}$ and it alternatively passes the
octagons of Type I and Type II. A similar argument as in Case 1 implies that
$i(\gamma,\Omega_{1})$ is even.

$\tilde{\gamma}$$\tilde{\gamma}^{\prime}$$\longrightarrow$ Figure 3.3.
Perturbation of $\tilde{\gamma}$.

∎

######  Lemma 3.5.

Let $\tilde{\gamma}$ be an arc in $\mathbb{D}$ without self-intersection such
that the end points of $\tilde{\gamma}$ are in the same orbit and
$\tilde{\gamma}$ contains no vertices of $p^{-1}(\Omega_{1})$. Then,
$\tilde{\gamma}$ intersects $p^{-1}(\Omega_{2})$ at even number of points.

###### Proof.

$d_{2}$$a_{1}$$b_{1}$$c_{1}$$d_{1}$$a_{2}$$b_{2}$$c_{1}$$b_{2}$$a_{1}$$d_{1}$$b_{1}$$a_{2}$$d_{2}$$\delta$
Figure 3.4.

The arc $\tilde{\gamma}$ alternatively passes through octagons of Type I and
Type II, as $\tilde{\gamma}$ does not pass through the vertices. Since the
initial point and the end point are identified, $\tilde{\gamma}$ passes
through an even number of octagons, say $2n$. Now, we use mathematical
induction on $n$ to complete the proof of the lemma. If $n=1$, then
$p(\tilde{\gamma})$ is either homotopic to a systole $\alpha\in\Omega_{1}$ or
homotopic to a geodesic $\delta$, as shown in Figure 3.4. We have
$|\alpha\cap\Omega_{2}|=4$ and $|\delta\cap\Omega_{2}|=8$. Therefore, it
follows that $\tilde{\gamma}$ intersects $p^{-1}(\Omega_{2})$ at even number
of points.

Next, suppose that the lemma holds true for $n$, where $n\geq 1$. Let an arc
$\tilde{\gamma}$ passes through $2(n+1)$ octagons $P_{1},\dots,P_{2n+2}$.
Consider $\tilde{\gamma}^{\prime}$ which is union of $\delta_{i},i=1,\dots,4$
(see Figure 3.5). The arc $\tilde{\gamma}^{\prime}$ is homotopic to
$\tilde{\gamma}$ fixing the end points. By induction hypothesis
$|\delta_{1}\cap p^{-1}(\Omega_{2})|$ is even, the case $n=1$ implies
$|\delta_{3}\cap p^{-1}(\Omega_{2})|$ is even and $|\delta_{2}\cap
p^{-1}(\Omega_{2})|=|\delta_{4}\cap p^{-1}(\Omega_{2})|$. Hence,
$\tilde{\gamma}^{\prime}$ intersects $p^{-1}(\Omega_{2})$ at even number of
points and so does $\tilde{\gamma}$.

$c_{2}$$d_{2}$$a_{1}$$b_{1}$$c_{1}$$d_{1}$$a_{2}$$b_{2}$$c_{1}$$b_{2}$$a_{1}$$d_{1}$$b_{1}$$a_{2}$$d_{2}$$b_{2}$$a_{1}$$d_{1}$$c_{2}$$b_{1}$$a_{2}$$d_{2}$$c_{1}$$b_{1}$$c_{1}$$d_{1}$$a_{2}$$c_{2}$$d_{2}$$a_{1}$$b_{2}$$a_{1}$$d_{1}$$c_{2}$$b_{1}$$a_{2}$$d_{2}$$P_{1}$$P_{2}$$P_{2n}$$P_{2n+1}$$P_{2n+2}$$\delta_{1}$$\delta_{2}$$\delta_{3}$$\delta_{4}$$\tilde{\gamma}$
Figure 3.5. Deformation of the arc $\tilde{\gamma}$

∎

###### Proof of Theorem 3.1.

Let $\gamma$ be a non systolic simple closed geodesic on the Bolza surface
$S$. If $\gamma\in\Gamma$, Lemma 3.4 implies that
$i(\gamma,\mathrm{Sys}(S))=10$. In the remaining cases, we may assume that
$\gamma$ does not pass through any of the points of intersection of
$\mathrm{Sys}(S)$, otherwise we deform the curve as in Figure 3.3 and this
deformation does not change the number of points of intersection. As
$\Omega_{1}$ fills the surface $S$, $\gamma$ intersects at least one geodesic
of $\Omega_{1}$. Let $\tilde{\gamma}$ be a path lift of $\gamma$ with initial
point on $p^{-1}(\Omega_{1})$. Then, $\tilde{\gamma}$ satisfies all the
hypothesis of Lemma 3.5 and hence $\tilde{\gamma}$ intersects
$p^{-1}(\Omega_{2})$ at even number of points. This implies that
$i(\Omega_{2},\gamma)$ is even. The rest of the proof follows from Lemma 3.4.
∎

######  Proposition 3.6.

Let $\Gamma$ be a curve system on a hyperbolic surface $X$. Then the $k$-th
complexity $\mathcal{T}_{k}(\Gamma)$ is finite if and only if $\Gamma$ is a
filling.

###### Proof.

($\Leftarrow$) Suppose, $\Gamma$ is a filling system in $X$. Let
$X\approx\mathbb{H}/G$, where $G$ is a Fuchsian group and $\mathbb{H}$ is the
upper half plane. Let $F$ be a polygonal fundamental domain for $G$ determined
by the lifts of $\Gamma$. Let $\delta$ be a simple closed curve on $X$ with
$i(\delta,\Gamma)\leq k$ and $\tilde{\delta}$ be a path lift of $\delta$ with
initial point on the boundary of $F$. Then $\tilde{\delta}$ passes through at
most $k$ copies of $F$ and this implies that $l_{X}(\gamma)\leq k\cdot d_{F}$,
where $d_{F}$ is the diameter of $F$. As there are only finitely many simple
closed geodesics in a hyperbolic surface with bounded length (Lemma 12.4 [4]),
the result follows.

($\Rightarrow$) If $\Gamma$ is not a filling, then there exists a simple
closed curve $\beta$ such that $i(\beta,\Gamma)=0$. Now, we consider a simple
closed curve $\alpha_{0}$ with $i(\alpha_{0},\beta)\neq 0$ and the Dehn twist
$T_{\beta}$ about the curve $\beta$. Then the curves
$\alpha_{n}=T^{n}_{\beta}(\alpha_{0}),n\in\mathbb{Z},$ are all distinct and
satisfies $i(\alpha_{0},\Gamma)=i(\alpha_{n},\Gamma)$, for all
$n\in\mathbb{Z}$. This implies that $\mathcal{T}_{k_{0}}(\Gamma)$ is infinite,
where $k_{0}=i(\alpha_{0},\Gamma)$. ∎

######  Corollary 3.7.

$\mathcal{T}_{k}(\mathrm{Sys}(S))$ is finite for all $k\in\mathbb{Z}_{\geq
0}$.

An estimate of $\mathcal{T}_{k}(\mathrm{Sys}(S))$: Let $\gamma$ be a non-
systolic geodesic on $S$ with $i(\gamma,\mathrm{Sys}(S))\leq k$. Then a path
lift $\tilde{\gamma}$ of $\gamma$ passes through at most $k/2$ octagons. So,
the length of $\gamma$ is bounded above by $k/2$ times the diameter of an
octagon. That is, $l(\gamma)\leq k\cdot\cosh^{-1}\left(1+\sqrt{2}\right)$. By
using Theorem 4.1 [7] due to I. Rivin, we have

$\mathcal{T}_{k}(\mathrm{Sys}(S))\leq
c\left[k\cdot\cosh^{-1}\left(1+\sqrt{2}\right)\right]^{6},$

where $c$ is a constant.

##  4\. Second systoles

######  Theorem 4.1.

There are exactly $12$ second systolic geodesics on the Bolza surface and they
form a triangulation with each triangle of type $(4,3,3)$.

###### Proof.

Aurich-Steiner [3] have shown that the length $l_{2}$ of the second systole of
the Bolza surface $S$ is given by $\cosh(l_{2}/2)=3+2\sqrt{2}$. Consider the
Bolza surface as given in Figure 4.1(i). The diagonals of the octagon joining
opposite vertices project onto simple closed geodesics on $S$. Also, the
length of these geodesics is $l_{2}$. Using the isometries on these geodesics,
we get $12$ second systolic geodesics (see Figure 4.1). Now, we show that
these are the only second systolic geodesics on the Bolza surface.

Let $\alpha$ be a simple closed curve on $S$. If $\alpha$ is separating, then
$\alpha$ contains $4$ arcs joining non-consecutive sides of the octagon and
hence $l(\alpha)>l_{2}$. If $\alpha$ is non-separating, then by Theorem 2.4,
$\alpha$ passes through some fixed points of the hyperelliptic involution
$\sigma$ and in order to become a second systole, $\alpha$ must pass through
exactly two fixed points. This implies that the geodesics shown in Figure
4.1(ii) are the only $12$ second systoles on $S$. ∎

$c$$d$$a$$b$$c$$d$$a$$b$$c$$d$$a$$b$$c$$d$$a$$b$$(i)$$(ii)$ Figure 4.1. $(i)$
Arcs with same color (except black) project onto a second systole. $(ii)$ All
second systoles on Bolza Surface.

## References

  * [1] H. Akrout. Singularit´es topologiques des systoles g´en´eralis´ees. Topology, 42(2):291–308, 2003.
  * [2] R. Aurich, E. B. Bogomolny, and F. Steiner. Periodic orbits on the regular hyperbolic octagon. Phys. D, 48(1):91–101, 1991.
  * [3] R. Aurich and F. Steiner. On the periodic orbits of a strongly chaotic system. Phys. D, 32(3):451–460, 1988.
  * [4] Benson Farb and Dan Margalit. A primer on mapping class groups, volume 49 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 2012.
  * [5] H. M. Farkas and I. Kra. Riemann surfaces, volume 71 of Graduate Texts in Mathematics. SpringerVerlag, New York, second edition, 1992.
  * [6] Andrew Haas and Perry Susskind. The geometry of the hyperelliptic involution in genus two. Proc. Amer. Math. Soc., 105(1):159–165, 1989.
  * [7] Igor Rivin. Simple curves on surfaces. Geom. Dedicata, 87(1-3):345–360, 2001.
  * [8] Bidyut Sanki. Systolic fillings of surfaces. Bull. Aust. Math. Soc., 98(3):502–511, 2018.
  * [9] Paul Schmutz Schaller. Systoles and topological Morse functions for Riemann surfaces. J. Differential Geom., 52(3):407–452, 1999.
  * [10] P. Schmutz. Riemann surfaces with shortest geodesic of maximal length. Geom. Funct. Anal., 3(6):564–631, 1993.


# PromptBoosting: Black-Box Text Classification with Ten Forward Passes

Bairu Hou1, Joe O’Connor2, Jacob Andreas3, Shiyu Chang1, Yang Zhang4
1UC Santa Barbara, 2UC Los Angeles, 3MIT CSAIL, 4MIT-IBM Watson AI Lab

###### Abstract

We describe PromptBoosting, a query-efficient procedure for building a text
classifier from a neural language model (LM) without access to the LM’s
parameters, gradients, or hidden representations. This form of “black-box”
classifier training has become increasingly important as the cost of training
and inference in large-scale LMs has grown. But existing black-box LM
classifier learning approaches are themselves computationally inefficient,
typically specializing LMs to the target task by searching in a large space of
(discrete or continuous) prompts using zeroth-order optimization methods.
Instead of directly optimizing in prompt space, PromptBoosting obtains a small
pool of prompts via a gradient-free approach, and then constructs a large pool
of _weak learners_ by pairing these prompts with different elements of the
LM’s output distribution. These weak learners are then ensembled using the
AdaBoost algorithm. The entire learning process requires only a small number
of forward passes per batch and no backward pass. Experiments show that
PromptBoosting achieves state-of-the-art performance in multiple black-box
few-shot classification tasks, and matches or outperforms full fine-tuning in
both few-shot and standard learning paradigms, while training 10x faster than
existing black-box methods.111Codes are available at https://github.com/UCSB-
NLP-Chang/PromptBoosting

##  1 Introduction

Prompt-based learning has emerged as an effective method to adapt pretrained
language models (LMs) for downstream natural language processing (NLP) tasks.
A typical prompt-learning paradigm involves appending a specially-designed
sequence, called a prompt, to the input to a pre-trained LM, which will
thereby be repurposed for a given downstream task. Compared to the standard
fine-tuning, prompt-based learning is much more parameter-efficient.

Most prompt-based learning methods require searching for the optimal prompt
for the downstream task. When gradient information of the pre-trained LM is
available, such optimization can easily be performed by standard gradient-
based methods (Liu et al., 2021; Li & Liang, 2021; Lester et al., 2021; Zhang
et al., 2021; Liu et al., 2022). However, in many real-world scenarios, the
parameters, gradient or hidden representations of the LMs are not accessible,
_a.k.a._ the black-box tuning setting, which makes gradient-based prompt
learning very challenging (Sun et al., 2022).

To tackle the challenges, the most common existing black-box solution is to
resort to gradient-free optimization techniques to search for the optimal
prompt, such as the zeroth-order gradient approximation (Sun et al., 2022;
Diao et al., 2022) and reinforcement learning-guided optimization (Deng et
al., 2022). However, these methods would require a large number of queries of
the LMs, which, considering the ever-growing size and computation cost of the
pre-trained LMs, is highly inefficient and could lead to large approximation
errors.

In this paper, we propose PromptBoosting, a novel black-box prompt learning
approach which does not rely on searching an optimal prompt, and which can
thus drastically improve the computational efficiency over the existing
methods. Figure 1 illustrates the pipeline of PromptBoosting. Specifically,
rather than optimizing over the prompts, PromptBoosting constructs a small
pool of prompts via a gradient-free approach. These prompts are sub-optimal
because they are not optimized for any downstream tasks. Then, PromptBoosting
creates a large pool of _weak learners_ by pairing each prompt with different
elements of the LM’s output distribution, which is commonly known as the
_verbalizer_. Finally, these weak learners are ensembled using the AdaBoost
algorithm, where the optimization in each iteration is performed only over the
verbalizer, not the prompt. The entire process only needs to evaluate the LM’s
output with each of weak prompts, so it only involves a small number of
forward passes per batch, and no backward pass.

We evaluated our method on a number of downstream tasks and LM’s. The results
show that PromptBoosting achieves state-of-the-art performance and matches or
even outperforms full fine-tuning in both few-shot and standard learning
paradigms. Furthermore, PromptBoosting can run 10x faster than existing black-
box prompt-learning approaches, with only ten forward passes per batch.
PromptBoosting can inspire a new black-box prompt learning paradigm.

Figure 1: Overview of PromptBoosting.

##  2 Related Work

#### Prompt-based learning

Prompt-based learning has emerged as a new approach for adapting pre-trained
LMs for downstream tasks fueled by the success of GPT-3 (Brown et al., 2020).
Since the prompts directly influence the performance of prompt-based learning,
recent studies have focused on how to find the best prompts given a specific
task. AutoPrompt (Shin et al., 2020) designs a gradient-based discrete
optimization method to search for the optimal prompt. LM-BFF (Gao et al.,
2021) leverages the pre-trained T5 model (Raffel et al., 2020) to
automatically generate prompts and select the best one based on the
performance on the validation set. Since verifying the automatically-generated
prompts is still time-consuming, the PTR (Han et al., 2021) method
incorporates logic rules to construct prompts and to encode prior knowledge
into prompt-based learning.

Another line of work replaces the discrete prompt tokens with continuous
embeddings that have their own parameters. P-tuning (Liu et al., 2021) trains
a BiLSTM network to output continuous prompt embeddings. Prefix-tuning (Li &
Liang, 2021) inserts prompt embeddings to each transformer layer in LMs and
optimizes only the prompt embeddings during training. Prompt Tuning (Lester et
al., 2021) also keeps the LMs frozen but adds prompt embeddings only in the
input. In addition to adding prompt embeddings to each layer, P-tuning V2 (Liu
et al., 2022) replaces the language model head in LMs with a linear layer for
classification and shows that soft prompt tuning scales to medium-sized LMs
and hard sequence tagging tasks. Our work adopts the automatically generated
discrete prompts for prompt-based learning.

#### Black-box Tuning

Extremely large LMs such as GPT-3 are only provided as a service in the cloud,
resulting inaccessible parameters and gradients of LMs. Furthermore, from the
model provider’s perspective, sharing hidden representations or gradients of
LMs may reveal the vulnerability of the model and lead to security problems
(Tramèr et al., 2016). How to find the optimal prompts in such black-box
tuning setting has attracted various explorations. BBT (Sun et al., 2022)
employs the CMA evolution strategy, a derivative-free optimization method, to
optimize continuous prompt embeddings. However, BBT requires querying the LM
tens of thousands of times even in few-shot settings. Furthermore, BBT’s use
of soft prompts violates the black-box tuning setting because in realistic use
one can query the LM service with only textual input instead of prompt
embeddings. Other concurrent work (Diao et al., 2022) also uses gradient-free
techniques to optimize soft prompts. RLPrompt (Deng et al., 2022) is a more
realistic black-box tuning method where discrete prompt tokens are optimized
through reinforcement learning and the performance on downstream tasks serves
as the reward. GrIPS (Prasad et al., 2022) performs phrase-level editing to
generate discrete prompts for downstream tasks. Existing black-box tuning
methods suffer from poor efficiency and sub-optimal performance. In contrast,
our method achieves high efficiency by first generating only a small set of
prompts and achieves superior performance by then creating a set of weak
learners from these prompts and ensembling them together via AdaBoost (Freund
& Schapire, 1997).

#### Model ensemble.

Model ensembling is a commonly used technique in machine learning. Prior to
deep learning, Bagging (Breiman, 1996; 2001) and Boosting (Freund & Schapire,
1997; Friedman, 2001) showed the power of model ensembling. One of these
methods, AdaBoost (Freund & Schapire, 1997), sequentially learns a series of
weak learners and ensembles them for better generalization. During training,
each weak learner is tweaked by leveraging examples that were misclassified by
previous classifiers. Since the performance of each individual prompt can be
weak, our method adopts AdaBoost as the framework for learning and ensembling
multiple prompts.

#### Prompt ensemble.

As has been pointed out by prior work (Lester et al., 2021), ensembling
prompts is more efficient than ensembling entire fine-tuned models. Various
ensemble strategies have been explored in past work. Uniformly averaging the
predictions from different prompts has been used for factual probing (Jiang et
al., 2020), text generation (Yuan et al., 2021; Schick & Schütze, 2020), and
classification tasks (Schick & Schütze, 2021a; Lester et al., 2021).
Furthermore, some methods adopt a weighted averaging strategy for better
performance—the weight of each different prompt can be learned during training
(Jiang et al., 2020; Qin & Eisner, 2021) or defined using some heuristics
(Schick & Schütze, 2021a; b). Our method also falls into the prompt ensemble
category. The main difference is each prompt-based model is sequentially
learned conditioned on the classification errors of prior models.

##  3 Methodology

In this section, we will describe the PromptBoosting algorithm. For notation,
we use $|\mathcal{A}|$ to denote the size of a finite set $\mathcal{A}$; $[A]$
to denote an index set $\\{1,2,\cdots,A\\}$.

###  3.1 Problem Formulation and the Prompt-Learning Framework

Consider a text classification downstream task. Denote
$\mathcal{D}_{tr}=\bigcup_{i}\\{(\bm{x}_{i},y_{i})\\}$ as the training set,
where $\bm{x}_{i}$ denotes the input text sequence and $y_{i}$ denotes the
output label. We are given a pre-trained language model, denoted as
$\bm{p}_{i}=F^{*}(\bm{x}_{i})$, which, given the input $\bm{x}_{i}$, produces
a probability distribution over the vocabulary set, $\mathcal{V}$, at a given
location. In this paper, only the output distribution at where the input is
[mask] is relevant, so $\bm{p}_{i}\in\mathbb{R}^{|\mathcal{V}|\times 1}$ is
just a $|\mathcal{V}|$-dimensional vector specifying the output probability at
the [mask] location, where $|\mathcal{V}|$ denotes the vocabulary size. Our
goal is to adapt the LM $F^{*}(\cdot)$ to the downstream task using the
downstream training set $\mathcal{D}_{tr}$.

We adopt the common prompt-learning framework, where the parameters of
$F^{*}(\cdot)$ are frozen (hence we add a superscript ∗ to emphasize this).
Instead, the following two mechanisms are added to convert $F^{*}(\cdot)$ into
a text classifier for the given downstream tasks.

  1. 1.

Prompt A prompt is sequence of tokens that is concatenated to the input.
Formally, denote the prompt sequence as $\bm{q}$ and the concatenated input
sequence as $\bm{x}_{i}\|\bm{q}$. Then the LM is modified as
$F^{*}(\bm{x}_{i}\|\bm{q})$.

  2. 2.

Verbalizer To convert the output probability over the _vocabulary_ into that
over the _classes_ , a verbalizer is introduced to assign each token into
different classes. Formally, denote the number of classes of the downstream
class as $|\mathcal{Y}|$, then the verbalizer is an
$|\mathcal{Y}|$-by-$|\mathcal{V}|$ matrix, denoted as $\bm{M}$, where the
element in row $c$, column $v$ represents the assignment weight of the
$v$-token in the vocabulary into class $c$. Each row of $\bm{M}$ would sum up
to one. The predicted probability of all the classes can then be expressed as
$\bm{M}\bm{p}_{i}$.

To sum up, after the prompt and verbalizer are applied, the adapted LM becomes
$\bm{M}F^{*}(\bm{x}_{i}\|\bm{q})$. Therefore, the prompt-tuning process boils
down to learning an appropriate verbalizer $\bm{M}$ and prompt $\bm{q}$ for
the downstream task.

###  3.2 Algorithm Overview

Conventional black-box prompt learning methods commonly use a pre-set $\bm{M}$
while performing black-box optimization over $\bm{q}$, which results in a
large computation cost. On the contrary, PromptBoosting randomly chooses from
a small number of pre-generated prompts and performs optimization over
$\bm{M}$ instead. Due to the sub-optimality of pre-generated prompts and the
limited representation power of $\bm{M}$, the resulting classifiers are weak.
However, this process is able to quickly generate a large pool of such weak
learners, which can then be ensembled into a strong learner using the AdaBoost
approach. Since the optimization over $\bm{M}$ is computationally cheap, the
ensembling process is still much more efficient than the conventional black-
box methods.

More specifically, the AdaBoost algorithm iteratively generates $T$ weak
learners, and weaker learner $t$ is optimized under its respective loss
function, denoted as $\mathcal{L}_{t}(\bm{q},\bm{M})$, which is essentially a
weighted loss over the training set with larger weights on those that are
misclassified by the previous weak learners (More details of the AdaBoost
algorithm will be provided in Section 3.5). Then, as shown in Figure 1,
PromptBoosting consists of the following key steps.

Step 0: Generate a pool of prompts, $\mathcal{Q}=\bigcup_{j}\\{\bm{q}_{j}\\}$,
using a gradient-free method.

Step 1: Construct $T$ weak learners. For weak learner $t$, its prompt
$\bm{q}_{t}$ is uniformly randomly drawn from $\mathcal{Q}$; its verbalizer
$\bm{M}$ is determined by solving

$\min_{\bm{M}}\mathcal{L}_{t}(\bm{q}_{t},\bm{M}),\quad\mbox{s.t.}\quad\bm{M}_{cv}\geq
0,\forall
c\in[|\mathcal{Y}|],v\in[|\mathcal{V}|],\quad\sum_{c\in[|\mathcal{Y}|]}\bm{M}_{cv}=1,\forall
v\in[|\mathcal{V}|].$ (1)

Step 2: Ensemble the weak learners according to AdaBoost.

Section 3.3 will describe how to solve equation 1. Section 3.4 will describe
how the pool of prompts, $\mathcal{Q}$, is generated.

###  3.3 Learning the Verbalizer

As discussed, the loss function $\mathcal{L}_{t}$ as in equation 1 is
essentially a weighted sum of the individual loss over the training dataset
$\mathcal{D}_{tr}$, _i.e._

$\mathcal{L}_{t}(\bm{q}_{t},\bm{M})=\sum_{(\bm{x}_{i},y_{i})\in\mathcal{D}_{tr}}w_{ti}\ell(\bm{x}_{i},y_{i};\bm{q}_{t},\bm{M}),$
(2)

where $w_{ti}$ denotes the weight on training data point $i$ for learning weak
learner $t$ as determined by AdaBoost;
$\ell(\bm{x}_{i},y_{i};\bm{q}_{t},\bm{M})$ denotes the loss on data point
$(\bm{x}_{i},y_{i})$ with the parameters set to $\bm{q}_{t}$ and $\bm{M}$.
Since we focus on classification tasks, $\ell(\cdot)$ should ideally be the
cross-entropy loss. However, the optimization problem in equation 1 is
essentially a partition problem, which can easily lead to combinatorial
complexity. To derive the tractable solution, we adopt the following strategy.
First, solve equation 1 with $\ell(\cdot)$ set to the $\ell_{1}$ loss, which,
though not optimal for the classification task, bears a closed-form solution.
Second, further screen the token assignment by maximizing the training set
performance. The detailed method is described below.

#### Minimizing the $\ell_{1}$ loss

By replacing the $\ell(\cdot)$ in equation 2 with the $\ell_{1}$ loss, a
closed-form solution can be derived, which can establish a basis for the
subsequent steps for deriving a good verbalizer. Formally, let $\bm{h}_{i}$ be
the one-hot representation of the class label $y_{i}$, and let
$\bm{\pi}_{i}=F^{*}(\bm{x}_{i}\|\bm{q}_{t})$ represent the LM output
probability with the prompt $\bm{q}_{t}$ concatenated. Then, with the
$\ell_{1}$ loss, equation 2 becomes

$\displaystyle\mathcal{L}_{t}(\bm{q}_{t},\bm{M})$
$\displaystyle=\sum_{(\bm{x}_{i},y_{i})\in\mathcal{D}_{tr}}w_{ti}\lVert\bm{h}_{i}-\bm{M}\bm{\pi}_{i}\rVert_{1}=\sum_{(\bm{x}_{i},y_{i})\in\mathcal{D}_{tr}}w_{ti}\bm{1}^{T}|\bm{h}_{i}-\bm{M}\bm{\pi}_{i}|$
(3)
$\displaystyle=\sum_{(\bm{x}_{i},y_{i})\in\mathcal{D}_{tr}}w_{ti}\big{[}(-\bm{1})^{\bm{h}_{i}}\big{]}^{T}(\bm{h}_{i}-\bm{M}\bm{\pi}_{i}).$

Here, $\bm{1}$ represents a all-one column vector of dimension
$|\mathcal{Y}|$, and $(-\bm{1})^{\bm{h}_{i}}$ represents the element-wise
power operation. The last equality is because each element of
$\bm{M}\bm{\pi}_{i}$ is within $[0,1]$ and each element of $\bm{h}_{i}$ is
either $0$ or $1$, so we can easily remove the absolute sign depending on the
actual values of $\bm{h}_{i}$.

As shown in equation 3, the loss function is _linear_ with respect to
$\bm{M}$, so the optimization in equation 1 becomes a linear optimization
problem with linear constraints, which has closed-form corner solutions. For
notational brevity, define a score matrix, $\bm{S}$, as

$\bm{S}=\sum_{(\bm{x}_{i},y_{i})\in\mathcal{D}_{tr}}w_{ti}\bm{\pi}_{i}\big{[}(-\bm{1})^{\bm{h}_{i}}\big{]}^{T},$
(4)

which is the same size as $\bm{M}$ and is essentially the coefficients
multiplied on $\bm{M}$ in equation 3. Then, we state without detailed
derivations that the solution to equation 1 is such that each token is
assigned to the class for which it gets the highest score among all the
classes, _i.e._

$\bm{M}_{cv}=1,\quad\mbox{if
}c=\operatorname*{arg\,max}_{c^{\prime}\in[|\mathcal{Y}|]}\bm{S}_{c^{\prime}v},\quad\mbox{and
}0\mbox{ otherwise}.$ (5)

Since the $\ell_{1}$ loss does not generally work well for classification
tasks, we empirically find that the verbalizer derived in equation 5 is of
limited performance. However, this inspires us that the score matrix,
$\bm{S}$, is a good measure of how well each token should be selected for a
class. In the following step, we will further screen the tokens with the help
of the score matrix.

#### Screening the tokens

One issue with the verbalizer in equation 5 is that each token has to be
assigned to one class, even those tokens that are not well indicative of any
classes. Therefore, by removing the non-informative tokens and only retaining
the best tokens for each class, we can improve the verbalizer performance. To
reduce the computational complexity, we will retain only one token for each
class. Specifically, we first identify a candidate set of tokens for each
class by choosing the tokens with top-$k$ scores for that class, _i.e._ the
top-$k$ elements in $\bm{S}_{c:}$ for class $c$, where subscript $c:$ denotes
the $c$-th row. Then, we evaluate all the possible combinations that include
one token from the candidate set for each class (hence $k^{|\mathcal{Y}}|$
combinations in total) and choose the combination that achieves the best
training accuracy (weighted by $\\{w_{ti}\\}$).

###  3.4 Constructing the Prompt Set

To generate the pool of prompts, $\mathcal{Q}$ (step 0 in section 3.2), we
adopt the optimization-free method proposed by Gao et al. (2021), which
employs the T5 (Raffel et al., 2020) model. Specifically, we first construct a
small subset of the training set, denoted as $\mathcal{D}_{gen}$, to induce
the prompt generation ($\mathcal{D}_{gen}$ is exactly $\mathcal{D}_{tr}$ in
few-shot setting). Then, for each data point
$(\bm{x}_{i},y_{i})\in\mathcal{D}_{gen}$, we construct an input to the T5
model as <input> (for sentence-pair classification tasks,
the input to T5 becomes <input1><input2>). Here,  and
 are mask tokens in T5 representing spans to be filled in. <input>,
<input1> and <input2> represent the input text $\bm{x}_{i}$.  is
a pre-defined mapping to convert class labels to tokens in $\mathcal{V}$. For
example, positive label ($y_{i}=1$) in SST-2 (Socher et al., 2013) dataset is
mapped to token great while negative label ($y_{i}=0$) is mapped to terrible.
Given this input, the T5 model fills in the spans for  and . The
decoding process aims to maximize output probability conditioned on the input
over $\mathcal{D}_{gen}$. Then the T5 generated outputs, denoted as <output A>
and <output B> will be converted into prompts and concatenated to the training
input text, _i.e._ $\bm{x}_{i}\|\bm{q}$, in the form of <input><output
A>[mask]<output B> (for sentence-pair tasks, the form becomes <input1><output
A>[mask]<output B><input2>). As an example, on SST-2 dataset, one of the
generated outputs by T5 is <output A> = A truly, <output B> = movie. Then the
input sentence “I love it.” will be converted to “I love it. A truly [MASK]
movie”. With a wide beam search width (by default we use $100$), we select the
top-10 generated prompts according to the log-likelihood to form the prompt
pool, $\mathcal{Q}$. All the generated prompts used in our experiments can be
found in Table 6 in Appendix C Readers can refer to Gao et al. (2021) for
further details. The entire generation process does not involve any
optimization over the prompts, and thus is computationally efficient. It is
worth noting that the aforementioned approach can be replaced with any other
optimization-free prompt generation methods, such as manually creating the
prompts, making PromptBoosting flexible for realistic use.

Algorithm 1 Model Ensemble in PromptBoosting

1:Input: prompt set $\mathcal{Q}=\bigcup_{j}\\{\bm{q}_{j}\\}$, LM
$F^{*}(\cdot)$, $\mathcal{D}_{tr}$,

2:Output: weak learners $\bigcup_{t}\\{f_{t}(\cdot)\\}$ and their weights
$\bigcup_{t}\\{\alpha_{t}\\}$.

3:Set initial data weight to $w_{1i}=1/|\mathcal{D}_{tr}|$, $\forall
i\in[|\mathcal{D}_{tr}|]$

4:for Iteration $t=1,\ldots,T$ do

5: Randomly draw a prompt $\bm{q}_{t}$ from $\mathcal{Q}$

6: Learn the verbalizer $\bm{M}_{t}$ with weight $\\{w_{ti}\\}$

7: Set weak learner $t$ to $f_{t}(\cdot)=\bm{M}_{t}F^{*}(\cdot\|\bm{q}_{t})$

8: Compute weighted error as
$err^{(t)}=\sum_{i=1}^{|\mathcal{D}_{tr}|}w_{ti}\bm{1}_{\mathrm{y}_{i}\neq
f_{t}(x_{i})}/\sum_{i=1}^{|\mathcal{D}_{tr}|}w_{ti}$

9: Compute the weight on $f_{t}$ as
$\alpha_{t}=\log\frac{1-err^{(t)}}{err^{(t)}}+\log(|\mathcal{Y}|-1)$

10: Adjust dataset weight
$w_{(t+1)i}=w_{ti}\cdot\exp(\alpha_{t}\cdot\bm{1}_{y_{i}\neq f_{t}(x_{i})})$,
$\forall i\in[|\mathcal{D}_{tr}|]$

11: Re-normalize $\\{w_{(t+1)i}\\}$.

12:end for

###  3.5 Ensembling the Weak Learners

We follow the AdaBoost algorithm to ensemble the weak learners. As discussed,
each weak learner minimizes a weighted loss over the training set (equation
2). The final prediction is produced by taking a weighted average over the
weak classifiers’ output. Further details, including how the weights are
computed, are shown in Algorithm 1. It is worth mentioning that we can
generate many weak learners at a very low computational cost, because we only
need to evaluate the LM’s output distribution with each of the pre-generated
prompts in $\mathcal{Q}$, beyond which no extra forward pass is needed when
learning each weak learner. Since the number of pre-generated prompts is
small, typically ten in our implementation, the entire learning process
involves no more than ten forward passes per batch in the training set, no
matter how many weak learners are generated.

##  4 Experiments

###  4.1 Experiment Setup

#### Datasets

We conduct experiments on a wide range of tasks including sentiment analysis
(SST-2 (Socher et al., 2013) and MR (Pang & Lee, 2005)), topic classification
(TREC (Voorhees & Tice, 2000) and AG’s News (Zhang et al., 2015)), and natural
language inference (SNLI (Bowman et al., 2015), MNLI-m (Williams et al.,
2018), RTE (Dagan et al., 2005), and QNLI (Rajpurkar et al., 2016)). The
dataset statistics can be found in Table 4 in Appendix A.

#### Evaluation Setting

We mainly evaluate the performance of PromptBoosting in few-shot settings.
This is reasonable especially for black-box model tuning scenarios, where the
maximum allowed query times may be limited. We randomly sample $k$ examples
per class from the original training set to construct a $k$-shot training set
$\mathcal{D}_{tr}$ for model training. Following previous work (Gao et al.,
2021; Zhang et al., 2021; Sun et al., 2022), we also construct the validation
set $\mathcal{D}_{val}$ by randomly sampling another $k$ examples per class
from the original training set (i.e.,
$|\mathcal{D}_{tr}|=|\mathcal{D}_{val}|$). By default we set $k=16$ for our
main experiments. Also, while previous work splits the training and validation
sets in this way and we do so for direct comparison, we also explore
integrating the validation set into the training set—in a truly few-shot
setting, we should make full use of as many examples as we can, and we show
this leads to an improvement in performance. As for evaluation, we use the
whole testing set. For SNLI (Bowman et al., 2015) and the datasets from the
GLUE benchmark (Wang et al., 2018), we use the original validation set for
evaluation.

#### Backbone Models

In the main experiments, we adopt the widely-used RoBERTa-large model (Liu et
al., 2019) for evaluation in order to allow for direct comparison with
baselines.

#### Baselines

We compare PromptBoosting with fine-tuning and state-of-the-art black-box
tuning methods described below. For reference, we also include white-box
prompt-based learning methods that are designed for few-shot setting.
Implementation details can be found in Appendix A. (1) Fine-tuning is just
standard model fine-tuning in a few-shot setting. (2) LM-BFF (Gao et al.,
2021) is a prompt-based fine-tuning method. In LM-BFF, all input will be
transformed using automatically generated prompts. Then the whole model is
fine-tuned based on the transformed data. (3) DART (Zhang et al., 2021)
replaces the discrete prompts in LM-BFF with trainable prompt embeddings,
which can reduce the prompt generation cost. (4) Feature-based MLP uses LMs as
feature extractors, which is a simple yet effective way to train LMs in black-
box settings. We take the manual prompt from past work (Gao et al., 2021) and
query the LMs to get the the masked token prediction $\mathbf{p}$. Then a
3-layer MLP is trained on the extracted features. (5) BBT (Sun et al., 2022)
is a black-box tuning method for few-shot learning which employs zeroth-order
gradients to optimize the continuous prompts. (6) RLPrompt (Deng et al., 2022)
models the black-box optimization of discrete prompts as a reinforcement
learning problem and adopts Q-learning to find the best prompt.

Table 1: Performance of proposed PromptBoosting and baseline methods in few-
shot setting ($k=16$) measured by classification accuracy (%). All methods use
RoBERTa-large (Liu et al., 2019) as the backbone LM for fair comparison. Two
white-box methods are included for reference including LM-BFF (Gao et al.,
2021) and DART (Zhang et al., 2021). Feature-MLP, BBT (Sun et al., 2022), and
RLPrompt (Deng et al., 2022) are the main black-box baselines.
PromptBoosting-32 combines both training and validation set for training. Mean
accuracy (and standard deviation) is reported over 5 different splits.

Method | SST-2 | MR | AG’s News | TREC | SNLI | MNLI | QNLI | RTE | Avg.
---|---|---|---|---|---|---|---|---|---
Fine-tuning | 81.4 (3.8) | 82.7 (3.6) | 86.2 (1.4) | 88.8 (2.1) | 48.4 (4.8) | 45.8 (6.4) | 56.3 (1.5) | 54.4 (3.9) | 68.0
LM-BFF | 92.3 (1.5) | 87.4 (0.6) | 87.1 (1.2) | 83.4 (2.7) | 76.5 (2.6) | 68.7 (2.0) | 64.4 (4.6) | 66.6 (6.4) | 78.3
DART | 93.5 (0.5) | 88.2 (1.0) | 86.8 (0.5) | 87.1 (3.8) | 75.8 (1.6) | 67.5 (2.6) | 66.7 (3.7) | 59.0 (2.5) | 78.1
Feature-MLP | 84.9 (3.8) | 82.1 (1.6) | 74.1 (2.0) | 25.3 (2.4) | 57.8 (3.2) | 48.5 (1.8) | 54.4 (4.5) | 55.5 (4.7) | 60.3
BBT | 88.2 (1.7) | 82.8 (2.6) | 81.2 (2.7) | 39.3 (5.2) | 44.7 (4.0) | 42.3 (2.8) | 56.8 (2.0) | 49.1 (3.3) | 60.6
RLPrompt | 90.5 (1.5) | 86.2 (2.5) | 76.2 (2.7) | 37.3 (3.5) | 42.9 (1.8) | 40.7 (4.7) | 52.1 (2.9) | 52.2 (2.2) | 59.8
PromptBoosting | 87.6 (3.0) | 84.6 (2.5) | 85.2 (0.9) | 81.6 (4.0) | 61.3 (3.5) | 52.5 (1.5) | 58.0 (3.3) | 60.0 (5.5) | 71.4
PromptBoosting-32 | 87.6 (3.3) | 84.7 (2.1) | 84.2 (1.1) | 84.5 (1.4) | 62.0 (2.7) | 53.8 (1.2) | 58.3 (2.8) | 60.3 (2.4) | 71.9

Table 2: Deployment efficiency of proposed PromptBoosting and baseline methods
in few-shot setting ($k=16$). With all methods use RoBERTa-large (335M
parameters) as the backbone LM, some baselines introduce additional
parameters, leading to the slight variation in total parameters. Wall time is
reported to measure the training time efficiency. Query efficiency is
evaluated by #Forward and #Backward, which refer to the number of
forward/backward passes per batch during training respectively.

Method |  Trainable param |  Total param | AG’s News | RTE
---|---|---|---|---
Acc | Wall Time | #Forward | #Backward | Acc | Wall Time | #Forward | #Backward
Fine-tuning | 335M | 335M | 86.2 | 13 min | 100 | 100 | 54.4 | 19 min | 100 | 100
LM-BFF | 335M | 335M | 87.1 | 5min | 32 | 32 | 66.6 | 9 min | 60 | 60
DART | 335M | 335M | 86.8 | 15 min | 30 | 30 | 59.0 | 5 min | 120 | 120
Feature-MLP | 5M | 340M | 74.1 | 0.5 min | 1 | 0 | 55.5 | 0.3 min | 1 | 0
BBT | 25k | 335M | 81.2 | 88 min | 8K | 0 | 49.1 | 52 min | 8K | 0
RLPrompt | 3M | 420M | 77.2 | 117 min | 1K | 0 | 52.2 | 90 min | 1K | 0
PromptBoosting |  $<$1k | 335M | 85.2 | 8 min | 10 | 0 | 60.0 | 4 min | 10 | 0

#### Implementation Details

The implementations of standard fine-tuning and feature-based MLP are based on
the Huggingface transformers library (Wolf et al., 2019). For all other
baselines, we use their official implementations and hyper-parameters. Please
refer to more details in Appendix A. For our method, we sequentially train
weak classifiers and add them to our ensemble—we stop when validation
performance plateaus or when we reach the maximum number of weak classifiers.

###  4.2 Evaluation Results

#### Overall Comparison

We first evaluate the effectiveness of PromptBoosting in a few-shot setting
with experiment results in Table 1. Although there is some variance across
datasets, PromptBoosting achieves state-of-the-art performance compared to
existing black-box tuning methods.

We emphasize the effectiveness of model ensembling in PromptBoosting. Firstly,
on the SST-2 and MR datasets, which are sentiment analysis tasks, even
individual weak learners in PromptBoosting can achieve 100% accuracy on the
training set, making the model ensemble inapplicable (note that AdaBoost
cannot ensemble classifiers that achieve 100% accuracy). Therefore, we
directly train 10 weak learners using 10 prompts on the unweighted training
set and then select the weak learner that performs best on the validation set
as the final model. Since the advantage of model ensemble is limited on SST-2
and MR dataset, it is not surprising that PromptBoosting performs slightly
worse than BBT and RLPrompt. However, PromptBoosting is still better than
fine-tuning an-MLP, demonstrating the effectiveness of our proposed verbalizer
learning method.

Secondly, on the other 6 datasets, PromptBoosting consistently outperforms all
baselines. PromptBoosting also outperforms standard fine-tuning on the 4 NLI
tasks. It is worth noting that on the TREC dataset, all of the black-box
baselines performs very badly except for PromptBoosting, which even achieves a
level of accuracy close to that of white-box methods. One potential reason is
that the TREC dataset is harder for prompt-based learning. For example, the
manual prompt on the TREC dataset achieves only 32% accuracy Gao et al.
(2021). According to our experiments, individual weak learners trained on the
unweighted training set using our verbalizer learning method can only achieve
30%-50% accuracy. However, after employing model ensembling, the performance
is largely improved, demonstrating the effectiveness of PromptBoosting.

Finally, we incorporate a variant of PromptBoosting, namely PromptBoosting-32,
which skips the hyper-parameter tuning and directly integrates the validation
set into training. The hyper-parameter, i.e., the number of weak classifiers,
is determined manually according to its value when the validation set is
available. By expanding the training set, one can observe a slight improvement
on the performance with lower variance.

#### Deployment efficiency

Another concern with black-box model tuning is the deployment efficiency. As
we have discussed above, directly adopting zeroth-order gradient optimization
techniques suffers from the need to query many times, making it less
applicable in realistic scenarios. We visualize the deployment efficiency of
different methods in Table 2. AG’s News and RTE datasets are adopted due to
the average input length (see Table 4). The metrics include parameter
efficiency (number of trainable parameters and total parameters), wall time of
training, and number of forward/backward passes per batch. In terms of
trainable parameters, PromptBoosting optimizes only less than 1k parameters
($|\mathcal{Y}|*200$) and does not introduce any extra parameters. In
contrast, RLPrompt uses another network, DistilGPT2 (Sanh et al., 2019), in
addition to the backbone RoBERTa model and consequently increases the training
cost. In terms of wall time, PromptBoosting improves the efficiency over
existing black-box tuning baselines (BBT and RLPrompt) by more than 10 times.
The query time is also significantly lower. Only 10 forward passes per batch
of training data are required during the training of PromptBoosting. By
contrast, our baselines require thousands of forward passes, which makes them
hard to use in realistic scenarios.

(a) Performance on SST-2 (b) Performance on MR (c) Performance on SNLI (d)
Performance on MNLI

Figure 2: Model performance as a function of training set size on different
datasets. For NLI tasks (SNLI and MNLI), we also include prompt refinement for
better performance.

#### Effect of training data size

We also study the performance of PromptBoosting as the size of the training
set increases (see Figure 2). Note that we still fix $k=16$ for the validation
set regardless of the training set size. Results on AG’s News, TREC, QNLI, and
RTE dataset are shown in Figure 3 in Appendix B. The conclusions are in three
dimensions. Firstly, on the SST-2 and MR datasets, PromptBoosting consistently
outperforms fine-tuning with lower variance, demonstrating the effectiveness
of our method. Secondly, on the AG News and TREC datasets, PromptBoosting
performs worse than fine-tuning. A similar phenomenon also exists in past work
(Gao et al., 2021), where even a white-box prompt-based few-shot learning
method can achieve performance that is at most only comparable with fine-
tuning. However, we remark that our method still maintains large advantages
compared to all black-box baseline methods and achieves highly usable
performance. Finally, as the amount of training data increases, the
performance of fine-tuning improves and gradually outperforms our method on
the four NLI datasets. This finding is possibly due to the fact that pre-
trained LMs before fine-tuning are not good at tasks involving sentence pairs.

#### Refinement of prompts

The performance of the weak learner in PromptBoosting directly depends on the
prompt. As has been shown in previous work, different prompts have significant
influence on the performance of prompt-based methods (Shin et al., 2020; Gao
et al., 2021). However, in PromptBoosting, the prompts are fixed and will not
be optimized during training. Therefore, we consider a simple yet effective
way to improve the performance through prompt refinement. Specifically,
because we automatically generate 100 prompts for each dataset but only use 10
of them, we may select top-10 prompts following some heuristics to improve the
quality of prompts. Before training, we first evaluate the performance on the
validation set by training a weak classifier using the method in Section 3.3
on the unweighted few-shot training set. Then we construct the prompt pool by
selecting the top-10 prompts according to the accuracy of the corresponding
weak learner on validation set. Please note that the few-shot setting makes
the refinement process very efficient. Later on, PromptBoosting is trained
using the refined prompts. We mainly evaluate the effectiveness of the prompt
refinement on SNLI, MNLI, and QNLI dataset where the gap between
PromptBoosting and standard fine-tuning is relatively large with the increase
of training data. Experiment results can be found in Figure 2. One can observe
consistent improvements on few-shot performance across three NLI tasks,
especially on QNLI dataset where the performance of PromptBoosting was far
from satisfactory without prompt refinement. Overall, the prompt refinement
leads to a trade-off between training cost and model performance.

#### Effect of the number of prompts

In our main experiments, we use 10 prompts by default. Intuitively, a large
prompt pool increase the diversity of weak classifiers which could improve the
performance. However, the training/inference cost will also increase if more
prompts are included for model training. We empirically study the relationship
between the number of prompts and the model performance in Table 3. In
general, more prompts benefit the performance for most datasets (except QNLI).
We highlight the effectiveness of multiple prompts on AG’s News and TREC
dataset, on which the performance becomes better and more stable. As we have
discussed in the few-shot experiments in Table 1, individual prompt performs
very bad on TREC dataset. This is also proved by PromptBoosting-1 that only
achieves 41.3% accuracy. However, by using our prompt ensemble framework, the
performance can be boosted to 84.6% when 10 prompts are provided. Finally, the
performance improvement is relatively small when the number of prompts
increase from 10 to 20, implying that 10 prompts should be good enough for
PromptBoosting.

Table 3: Performance of PromptBoosting with different numbers of prompts in
few-shot setting ($k=16$).PromptBoosting-$d$ means top-$d$ prompts (sorted
according to the beam search score) are used for model training. Mean accuracy
(and standard deviation) is reported over 5 different splits.

| SST-2 | MR | AG’s News | TREC | SNLI | MNLI | QNLI | RTE | Avg.
---|---|---|---|---|---|---|---|---|---
PromptBoosting-1 | 86.1 (1.0) | 85.1 (5.0) | 73.3 (3.7) | 41.3 (4.3) | 53.4 (4.0) | 49.5 (3.5) | 58.0 (2.4) | 56.5 (5.7) | 62.9
PromptBoosting-5 | 88.8 (1.9) | 87.9 (1.6) | 83.5 (4.2) | 78.0 (2.5) | 59.1 (3.5) | 50.9 (4.8) | 56.5 (2.1) | 57.0 (4.5) | 70.2
PromptBoosting-10 | 87.6 (3.0) | 84.6 (2.5) | 85.2 (0.9) | 81.6 (4.0) | 61.3 (3.5) | 52.5 (1.5) | 58.0 (3.3) | 60.0 (5.5) | 71.4
PromptBoosting-20 | 88.1 (2.6) | 84.0 (2.3) | 86.4 (1.3) | 81.9 (2.7) | 60.8 (3.9) | 55.2 (1.2) | 57.0 (4.4) | 57.1 (3.2) | 71.3

#### Full data training

Due to its efficiency, PromptBoosting can also generalize to full data
training instead of just the few-shot setting. We compare with fine-tuning on
the entire training dataset for SST, MR, TREC, and RTE. Experimental results
can be found in Table 5 in the Appendix B.

##  5 Conclusion

In this paper, we propose PromptBoosting, an effective black-box model tuning
framework. Without access to the parameters and gradients of pre-trained LMs,
PromptBoosting can adapt LMs for various downstream tasks. The efficient weak
learner construction method, together with the AdaBoost model ensemble
algorithm, makes PromptBoosting achieve state-of-the-art performance in black-
box tuning setting with at least 10x run-time efficiency.

For future directions, we will explore how to generalize PromptBoosting beyond
the classification tasks to generation tasks. Also, we will study how to
combine the prompt ensemble idea in PromptBoosting with gradient-based
optimization and further improve the performance of existing prompt-based
learning methods.

## References

  * Bowman et al. (2015) Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pp. 632–642, 2015.
  * Breiman (1996) Leo Breiman.  Bagging predictors.  _Machine learning_ , 24(2):123–140, 1996.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine learning_ , 45(1):5–32, 2001.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Dagan et al. (2005) Ido Dagan, Oren Glickman, and Bernardo Magnini.  The pascal recognising textual entailment challenge.  In _Machine learning challenges workshop_ , pp. 177–190, 2005.
  * Deng et al. (2022) Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu.  Rlprompt: Optimizing discrete text prompts with reinforcement learning.  _arXiv preprint arXiv:2205.12548_ , 2022.
  * Diao et al. (2022) Shizhe Diao, Xuechun Li, Yong Lin, Zhichao Huang, and Tong Zhang.  Black-box prompt learning for pre-trained language models.  _arXiv preprint arXiv:2201.08531_ , 2022.
  * Freund & Schapire (1997) Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of computer and system sciences_ , 55:119–139, 1997.
  * Friedman (2001) Jerome H Friedman.  Greedy function approximation: a gradient boosting machine.  _Annals of statistics_ , pp. 1189–1232, 2001.
  * Gao et al. (2021) Tianyu Gao, Adam Fisch, and Danqi Chen.  Making pre-trained language models better few-shot learners.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 3816–3830, 2021.
  * Han et al. (2021) Xu Han, Weilin Zhao, Ning Ding, Zhiyuan Liu, and Maosong Sun.  Ptr: Prompt tuning with rules for text classification.  _arXiv preprint arXiv:2105.11259_ , 2021.
  * Jiang et al. (2020) Zhengbao Jiang, Frank F Xu, Jun Araki, and Graham Neubig.  How can we know what language models know?  _Transactions of the Association for Computational Linguistics_ , 8:423–438, 2020.
  * Lester et al. (2021) Brian Lester, Rami Al-Rfou, and Noah Constant.  The power of scale for parameter-efficient prompt tuning.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 3045–3059, 2021.
  * Li & Liang (2021) Xiang Lisa Li and Percy Liang.  Prefix-tuning: Optimizing continuous prompts for generation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 4582–4597, 2021.
  * Liu et al. (2021) Xiao Liu, Yanan Zheng, Zhengxiao Du, Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang.  Gpt understands, too.  _arXiv:2103.10385_ , 2021.
  * Liu et al. (2022) Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Tam, Zhengxiao Du, Zhilin Yang, and Jie Tang.  P-tuning: Prompt tuning can be comparable to fine-tuning across scales and tasks.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , 2022.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Pang & Lee (2005) Bo Pang and Lillian Lee.  Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales.  In _Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05)_ , pp. 115–124, 2005.
  * Prasad et al. (2022) Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal.  Grips: Gradient-free, edit-based instruction search for prompting large language models.  _arXiv preprint arXiv:2203.07281_ , 2022.
  * Qin & Eisner (2021) Guanghui Qin and Jason Eisner.  Learning how to ask: Querying lms with mixtures of soft prompts.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 5203–5212, 2021.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21(140):1–67, 2020.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang.  Squad: 100,000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pp. 2383–2392, 2016.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  In _NeurIPS $EMC^{2}$ Workshop_, 2019.
  * Schick & Schütze (2020) Timo Schick and Hinrich Schütze.  Few-shot text generation with pattern-exploiting training.  _arXiv preprint arXiv:2012.11926_ , 2020.
  * Schick & Schütze (2021a) Timo Schick and Hinrich Schütze.  Exploiting cloze-questions for few-shot text classification and natural language inference.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pp. 255–269, 2021a.
  * Schick & Schütze (2021b) Timo Schick and Hinrich Schütze.  It’s not just size that matters: Small language models are also few-shot learners.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 2339–2352, 2021b.
  * Shin et al. (2020) Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh.  Autoprompt: Eliciting knowledge from language models with automatically generated prompts.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 4222–4235, 2020.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 conference on empirical methods in natural language processing_ , pp. 1631–1642, 2013.
  * Sun et al. (2022) Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu.  Black-box tuning for language-model-as-a-service.  In _Proceedings of ICML_ , 2022.
  * Tramèr et al. (2016) Florian Tramèr, Fan Zhang, Ari Juels, Michael K Reiter, and Thomas Ristenpart.  Stealing machine learning models via prediction $\\{$APIs$\\}$.  In _25th USENIX security symposium (USENIX Security 16)_ , pp. 601–618, 2016.
  * Voorhees & Tice (2000) Ellen M Voorhees and Dawn M Tice.  Building a question answering test collection.  In _Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval_ , pp. 200–207, 2000.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , 2018.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel Bowman.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pp. 1112–1122, 2018.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_ , 2019.
  * Yuan et al. (2021) Weizhe Yuan, Graham Neubig, and Pengfei Liu.  Bartscore: Evaluating generated text as text generation.  _Advances in Neural Information Processing Systems_ , 34:27263–27277, 2021.
  * Zhang et al. (2021) Ningyu Zhang, Luoqiu Li, Xiang Chen, Shumin Deng, Zhen Bi, Chuanqi Tan, Fei Huang, and Huajun Chen.  Differentiable prompt makes pre-trained language models better few-shot learners.  In _International Conference on Learning Representations_ , 2021.
  * Zhang et al. (2015) Xiang Zhang, Junbo Jake Zhao, and Yann LeCun.  Character-level convolutional networks for text classification.  In _NIPS_ , 2015.

##  Appendix A Implementation Details

#### Dataset Statistics

The dataset statistics can be found in Table 4. For fair comparison, the few-
shot training/validation/testing split generation is strictly following the
implementation of Gao et al. (2021).

#### Training of baselines

For standard fine-tuning, we adopt the Huggingface transformers library (Wolf
et al., 2019) to load RoBERTa-large backbone model and use its Trainer for
fine-tuning. The learning rate is set to 1e-5. We use AdamW optimizer as the
optimizer and the learning rate linearly decays to 0. The training batch size
is set to 16 and total training epochs is 100. For Feature-MLP method, we use
a three-layer MLP with hidden dimension 100. The learning rate is set to 1e-3
without learning rate decay. We also train the MLP for 100 epochs. For other
baselines, we use their the official implementation with default hyper-
parameters including LM-BFF (Gao et al., 2021), DART (Zhang et al., 2021), BBT
(Sun et al., 2022), and RLPrompt (Deng et al., 2022). For RLPrompt, because of
its low efficiency, we set its training epochs to 1000 instead of the 12000
used in their paper. This is reasonable since it takes nearly 2 hours for
RLPrompt to finish 1000 epochs of optimization.

Table 4: The dataset statistics. $|\mathcal{Y}|$ is the number of classes,
Avg.#W is the average number of words in the input, and #Train/#Test refer the
number of examples in training/testing dataset.

Category | Dataset | $|\mathcal{Y}|$ | Avg. #W | #Train | #Test
---|---|---|---|---|---
single sentence | SST-2 | 2 | 17 | 6920 | 872
MR | 2 | 20 | 8662 | 2000
AG’s News | 4 | 47 | 120000 | 7600
TREC | 6 | 10 | 5452 | 500
sentence pair | SNLI | 3 | 22 | 549367 | 9842
MNLI | 3 | 33 | 392702 | 9815
QNLI | 3 | 41 | 104743 | 5463
RTE | 3 | 59 | 2490 | 277

##  Appendix B Additional Experiments

#### Performance on full dataset

The high efficiency of PromptBoosting makes it possible to generalize to
medium-sized datasets. We evaluate the performance of PromptBoosting on SST-2,
MR, TREC, and RTE datasets. We sample 10% of the original training set to
construct the validation set and use the original validation set for testing
if the labeled test set is unavailable. The experiment results can be found in
Table 5. PromptBoosting achieves comparable performance with standard fine-
tuning on SST-2 and MR datasets, which is impressive given the fact that
PromptBoosting has no access to the parameters and gradients of the LM. For
TREC dataset, standard fine-tuning outperforms PromptBoosting, but we still
remark that the performance is still highly usable in black-box setting.
Finally, the gap between PromptBoosting and fine-tuning is relatively large on
RTE dataset, which is consistent with our previous discovery that it seems
pre-trained LMs are not good at sentence pair classification tasks before
fine-tuning.

Table 5: Performance of full data training

| SST-2 | MR | TREC | RTE
---|---|---|---|---
Fine-tuning | 95.5 (0.4) | 91.5 (0.6) | 97.2 (0.2) | 81.9 (1.1)
PromptBoosting | 94.1 (0.3) | 89.7 (0.4) | 90.5 (1.2) | 71.7 (2.0)

#### Effect of training data size

For AGNews, TREC, QNLI, and RTE datasets, we shown the performance of
PromptBoosting as the size of the training set increases in Figure 3.

(a) Performance on AG (b) Performance on TREC (c) Performance on QNLI (d)
Performance on RTE

Figure 3: Model performance as a function of training set size on different
datasets. For QNLI dataset, we also include prompt refinement for better
performance.

##  Appendix C Generated Prompts

In this section, we visualize the prompts we used in our experiments for each
dataset in Table 6. Regardless of different few-shot training/validation
splits, we use the same 10 prompts for model training.

Table 6: Prompts used by PromptBoosting on different datasets.

|  SST-2 |  MR
---|---|---
1 | [Input] It’s [MASK]. | [Input] It’s [MASK].
2 | [Input] A [MASK] movie. | [Input] It’s [MASK]!
3 | [Input] A [MASK] film. | [Input] A [MASK] piece of work.
4 | [Input] A [MASK] piece of work. | [Input] It’s [MASK].
5 | [Input] A truly [MASK] film. | [Input] A [MASK] waste of time.
6 | [Input] This is [MASK]. | [Input] A truly [MASK] film.
7 | [Input] It was [MASK]. | [Input] I thought it was [MASK].
8 | [Input] A [MASK] waste of time. | [Input] It’s just [MASK].
9 | [Input] It’s [MASK]! | [Input] A truly [MASK] movie.
10 | [Input] A truly [MASK] movie. | [Input] The film is [MASK].
|  AG’s News |  TREC
1 | [Input] This entry was posted in [MASK]. | [Input] What is [MASK]?
2 | [Input] U.S. [MASK] News. | [Input] What is the [MASK]?
3 | [Input] U.S. [MASK]. | [Input] What [MASK]?
4 | [Input] This entry was posted in [MASK] News. | [Input] The [MASK].
5 | [Input] The [MASK] Journal reports. | [Input] See [MASK].
6 | [Input] The [MASK] Journal has more. | [Input] Which [MASK]?
7 | [Input] Read more at [MASK] News Now. | [Input] The [MASK]?
8 | [Input] The New York Times [MASK]. | [Input] Full [MASK].
9 | [Input] The New York Times [MASK] Report. | [Input] How many [MASK]?
10 | [Input] Read more at[MASK] Insider. | [Input] 1.[MASK].
|  SNLI |  MNLI
1 | [Input1]. [MASK], [Input2] | [Input1]. [MASK], [Input2]
2 | [Input1]. [MASK]. [Input2] | [Input1]. [MASK], but [Input2]
3 | [Input1]. [MASK] and [Input2] | [Input1]. [MASK]. [Input2]
4 | [Input1]. [MASK], but [Input2] | [Input1]! [MASK], [Input2]
5 | [Input1]. [MASK]: [Input2] | [Input1]. [MASK]. But [Input2]
6 | [Input1]. [MASK] one of [Input2] | [Input1]? [MASK], [Input2]
7 | [Input1]. [MASK]... [Input2] | [Input1]. [MASK] and [Input2]
8 | [Input1]. [MASK], just [Input2] | [Input1]. [MASK], and [Input2]
9 | [Input1]. [MASK] it is [Input2] | [Input1]. [MASK] but [Input2]
10 | [Input1]. [MASK]; [Input2] | [Input1]. [MASK]... [Input2]
|  QNLI |  RTE
1 | [Input1]? [MASK], [Input2] | [Input1]. [MASK], [Input2]
2 | [Input1]? [MASK], but [Input2] | [Input1]. [MASK]. [Input2]
3 | [Input1]? [MASK]. [Input2] | [Input1]. [MASK], but [Input2]
4 | [Input1]? [MASK]. But [Input2] | [Input1]. [MASK] and [Input2]
5 | [Input1]? [MASK]. In fact, [Input2] | [Input1]. [MASK]: [Input2]
6 | [Input1]? [MASK]; [Input2] | [Input1]. [MASK], the [Input2]
7 | [Input1]? [MASK]. However, [Input2] | [Input1]. [MASK]; [Input2]
8 | [Input1]? [MASK], and [Input2] | [Input1]. [MASK]-[Input2]
9 | [Input1]? [MASK]: [Input2] | [Input1]. [MASK], and [Input2]
10 | [Input1]. [MASK], [Input2] | [Input1]. [MASK] but [Input2]