#  LoGAH: Predicting 774-Million-Parameter Transformers using Graph
HyperNetworks with $\nicefrac{{1}}{{100}}$ Parameters

Xinyu Zhou
EPFL &Boris Knyazev
Samsung - SAIT AI Lab &Alexia Jolicoeur-Martineau
Samsung - SAIT AI Lab &Jie Fu
HKUST Corresponding Author.

###### Abstract

A good initialization of deep learning models is essential since it can help
them converge better and faster. However, pretraining large models is
unaffordable for many researchers, which makes a desired prediction for
initial parameters more necessary nowadays. Graph HyperNetworks (GHNs), one
approach to predicting model parameters, have recently shown strong
performance in initializing large vision models. Unfortunately, predicting
parameters of very wide networks relies on copying small chunks of parameters
multiple times and requires an extremely large number of parameters to support
full prediction, which greatly hinders its adoption in practice. To address
this limitation, we propose LoGAH (Low-rank GrAph Hypernetworks), a GHN with a
low-rank parameter decoder that expands to significantly wider networks
without requiring as excessive increase of parameters as in previous attempts.
LoGAH allows us to predict the parameters of 774-million large neural networks
in a memory-efficient manner. We show that vision and language models (i.e.,
ViT and GPT-2) initialized with LoGAH achieve better performance than those
initialized randomly or using existing hypernetworks. Furthermore, we show
promising transfer learning results w.r.t. training LoGAH on small datasets
and using the predicted parameters to initialize for larger tasks. We provide
the codes in https://github.com/Blackzxy/LoGAH.

##  1 Introduction

In vision and language domains, pretraining a large model from scratch
precedes solving downstream tasks (He et al., 2021; Devlin et al., 2019).
Recent models have been increasing in size dramatically, chasing state-of-the-
art performance: from around 100M to $\geq$65B parameters for Generative
Pretrained Transformers (GPTs) (Radford et al., 2018; Touvron et al., 2023;
AI@Meta, 2024) and from around 100M to $\geq$22B for Vision Transformers
(ViTs) (Dosovitskiy et al., 2021; Dehghani et al., 2023). Training such large
models requires large computing resources. In addition, many retraining
iterations are often required before the model is successfully trained, which
is exacerbated in larger models since they are often more unstable to train
and require more hardware and software tuning in addition to hyperparameter
and architecture tuning, data curation, etc. Thus, pretraining large models
has become very expensive even for big companies (Thompson et al., 2022; Zhai
et al., 2022).

(a) Comparison of parameter counts between GHN-3 and LoGAH for supportable
maximal widths in the predicted parameters (without their copying).

(b) Comparison of parameter counts between GHN-3 and LoGAH for supportable
network sizes (without copying predicted parameters).

Figure 1: Comparison of parameter counts between GHN-3 and LoGAH. GHN-3
requires a larger hidden size to support wider networks, which increases the
size of GHN-3 exponentially in Figure 1a. LoGAH can support much wider
networks (up to 2048-dimension), and larger networks (GPT-2-Large in
1280-dimension with 774M parameters) even using LoGAH-Tiny.

Currently, training vision and language tasks are generally done using similar
network architectures and datasets; architectures are generally based on
either Transformers (Vaswani et al., 2023) (for vision or language) or
Convolutional Neural Networks (CNNs) (Fukushima et al., 1983) (for vision),
while datasets are similar to either ImageNet (for vision) (Russakovsky et
al., 2015) or The Pile (for language) (Gao et al., 2020). Leveraging this
prior knowledge of the architecture and dataset may reduce the pretraining
cost. One approach to do so is Graph HyperNetworks (GHNs)(Zhang et al., 2018;
Knyazev et al., 2021, 2023); this approach allows one to predict initial
parameters of these neural networks that perform well and converge faster. We
describe the GHN approach below.

Using a set of neural network architectures $\\{f^{G}\\}$ as training data,
GHN $H_{\mathcal{D}}$, parameterized by $\theta$, is trained to predict the
parameters of these neural networks
($\textbf{w}_{\text{pred}}=H_{\mathcal{D}}(f^{G},\theta)$) to minimize the
loss function on the dataset $\mathcal{D}$. The predicted
$\textbf{w}_{\text{pred}}$ can serve as a stronger initialization compared to
random-based initialization methods, thus greatly reducing the pretraining
cost.

However, to predict parameters for very wide networks (often with a large
number of parameters), previous GHNs (Knyazev et al., 2021, 2023) had to copy
small chunks of parameters multiple times instead of fully predicting them due
to the sheer amount of parameters required to predict all parameters, thus
significantly limiting the performance of the resulting networks. Furthermore,
to unlock the capability of predicting parameters of a larger size, GHNs need
larger hidden sizes $d$, leading to an exponential increase in the number of
parameters growing as $\mathcal{O}(d^{3})$ (Figure 1a).

To overcome this limitation, we propose LoGAH, a GHN with a low-rank parameter
decoder. This novel approach not only supports significantly wider networks
but also does so without requiring an excessive number of parameters growing
as $\mathcal{O}(d^{2})$ instead of $\mathcal{O}(d^{3})$ (Figure 1b). For
instance, our smallest LoGAH-Tiny has only 2.5M parameters, yet it can predict
parameters with up to 2048 channels, including GPT-2-Large with 774M
parameters and potentially even larger networks.

In this work, we make the following contributions:

  * •

We propose LoGAH, with an improved low-rank decoder, that is more scalable and
can predict parameters of large networks without copying while having fewer
trainable parameters and a lower training cost (Section 3).

  * •

We create a new dataset of small ViT and GPT-2 architectures, allowing GHNs to
be trained on Transformers for both vision and language domains (Section 4).
LoGAH shows excellent generalized capability on larger models.

  * •

We outperform GHN-3 as an initialization approach in multiple vision and
language tasks by predicting more diverse and performant parameters (Section
5).

##  2 Preliminaries

###  2.1 Graph HyperNetworks

Graph HyperNetworks (GHNs) (Zhang et al., 2020; Knyazev et al., 2021) are
widely used for neural networks’ parameter prediction. The input fed to GHN
$H_{\mathcal{D}}(\theta)$ is a computational graph $f^{G}$ of a neural network
$f$; GHN predicts its parameters
$\textbf{w}_{\text{pred}}=H_{\mathcal{D}}(f^{G};\theta)$, where $\mathcal{D}$
is the training dataset. In our paper, $f$ can be a ViT model (Dosovitskiy et
al., 2021) (resp. GPT-2 (Radford et al., 2019)), and $\mathcal{D}$ can be the
image classification task (resp. causal language modeling task).

In Knyazev et al. (2021) work, GHN $H_{\mathcal{D}}$ is trained by SGD over
$M$ training architectures $\\{f_{a}^{G}\\}_{a=1}^{M}$ and $N$ training data
samples $\\{\textbf{x}_{j},y_{j}\\}_{j=1}^{N}$ on the following optimization
problem:

$\displaystyle\arg\min_{\theta}\frac{1}{NM}\sum_{j=1}^{N}\sum_{a=1}^{M}\mathcal{L}(f_{a}(\textbf{x}_{j};H_{\mathcal{D}}(f_{a}^{G};\theta)),y_{j}).$
(1)

A meta-batch of $m$ training architectures is sampled in the training stage
where $H_{\mathcal{D}}$ predicts parameters. Meanwhile, a mini-batch of $n$
training samples x is sampled and fed into the parameter-predicted $m$
architectures to get $m\times n$ predictions. The cross-entropy loss
$\mathcal{L}$ is computed for classification and language modeling tasks
(next-token prediction). Afterward, the loss is back-propagated to update the
parameters $\theta$ of $H_{\mathcal{D}}$ by gradient descent. In our work, we
created ViTs-1K and GPTs-1K datasets of small training architectures for
predicting parameters for larger ViT and GPT-2 models, respectively. We
describe the details in Section 4.

The computational graph $f^{G}=(V,E)$ for input is a Directed Acyclic Graph
(DAG), where $V$ denotes the operations (e.g., pooling, self-attention, etc.),
and $E$ corresponds to the forward pass flow of inputs through $f$. The
$d$-dimensional node features $\textbf{H}^{(1)}\in\mathbb{R}^{|V|\times d}$
are obtained by an embedding layer ($i$-th node:
$\textbf{h}_{i}^{(1)}=\text{Embed}(\textbf{h}_{i}^{(0)})$, where
$\textbf{h}_{i}^{(0)}$ is a one-hot vector representing for an operation) and
fed as the input for GHN. After $L$ Graphormer layers (Ying et al., 2021), the
node features $\textbf{H}^{(L)}\in\mathbb{R}^{|V|\times d}$ are fed to the
decoder described below.

###  2.2 GHN Decoder

Knyazev et al. (2021, 2023) have the decoder based on a simple MLP predicting
a tensor of shape $d\times d\times 16\times 16$, where $d$ is relatively small
($d=384$ even in the largest GHN-3). The decoder takes the output node
features of the last Graphormer layer to predict parameters
$\textbf{w}_{\text{pred}}$. This tensor is copied when the target weight has a
larger $d$ or sliced when the target is smaller. The parameter count of the
decoder in (Knyazev et al., 2021, 2023)111Please refer to Appendix A and
https://github.com/SamsungSAILMontreal/ghn3/blob/main/ghn3/nn.py for more
details is:

$\displaystyle\\#\text{Param}_{\text{GHN-decoder}}=4d^{2}\times 16\times
16+32d^{2}+8d^{3}+d\times\text{num\\_class}\in\mathcal{O}(d^{3}).$ (2)

##  3 Scalable Graph HyperNetworks: LoGAH

LoGAH model improves on the following aspects: (1) designing a novel low-rank
decoder not only with fewer amounts of parameters, but also avoiding
inefficient parameter repetitions on prediction, (2) supporting larger models
(often wider) prediction without involving extremely larger amounts of
parameters as in previous works, e.g. LoGAH-Tiny with only 2.5M parameters can
support GPT-2-Large, while existing methods (Knyazev et al., 2023) would
require at least $\sim 10^{5}$M parameters.

###  3.1 Low-Rank Decoder

In (Knyazev et al., 2023), the final output dimensionality of the decoder is
$d\times d\times 16\times 16$, where $d$ can be $64$ or $128$. In most cases,
$16\times 16$ can be a waste since convolutional parameters are generally in
$3\times 3$ or $7\times 7$. However, the bigger problem is that for large
networks, the tensor needs to be repeated to fill all channels because $d$ is
small.

Considering a convolutional weight $W$ with size: $(C_{out}\times C_{in}\times
h\times w)$, we can reshape it into a matrix $W$ of $(C_{out}\cdot
h)\times(C_{in}\cdot w)$ where $h,w$ are much smaller than $C_{out}$ and
$C_{in}$. Inspired by (Hu et al., 2021), we can now introduce the low-rank
decomposition:

$\displaystyle W=AB\in\mathbb{R}^{(C_{out}\cdot h)\times(C_{in}\cdot w)},$ (3)

where $A\in\mathbb{R}^{(C_{out}\cdot h)\times
r},B\in\mathbb{R}^{r\times(C_{in}\cdot w)}$, $r$ denotes the low-rank. In this
way, we reduce the amounts of parameters from $C_{out}\cdot C_{in}\cdot h\cdot
w$ to $r\cdot((C_{out}\cdot h)+(C_{in}\cdot w))$.

Therefore, the whole process is as follows: after the first MLPs (multilayer
perceptron) the input $\textbf{H}^{(L)}\in\mathbb{R}^{|V|\times d}$ is
transformed into $\tilde{W}\in\mathbb{R}^{|V|\times 2K\times r}$:

$\displaystyle\tilde{W}=\text{MLP}(\textbf{H}^{(L)})\in\mathbb{R}^{|V|\times
2K\times r},$ (4)

where $K:=\max(C_{out}\cdot h,C_{in}\cdot w)$ is called max mask, so that we
can avoid repetition operations in GHN-3. Then we split $\tilde{W}$ into two
matrices $A,B^{T}\in\mathbb{R}^{|V|\times K\times r}$ and only take the needed
bits to construct $W=AB$ in Eqn. (3). The architecture of the MLPs is shown in
Appendix B, which involves the low-rank transformation inside. In this way,
the number of parameters in the decoder of LoGAH is:

$\displaystyle\\#\text{Param}_{\text{LoGAH-decoder}}=4d^{2}+32d^{2}+8d\times
2r^{2}+r\times K.$ (5)

Theoretically, we can fix $r$ as a much smaller constant hyperparameter than
$d$, then Eqn. (5) would be in $\mathcal{O}(d^{2})$, less than the complexity
of original GHN’s decoder $\mathcal{O}(d^{3})$. In practice, considering a
small rank $r$ would hinder the model’s performance, so we set it to
$r\approx\frac{d}{2}$ as an increase of $d$. Under this setting, we compare
the amounts of two decoder’s parameters in detail as follows.

#Parameters Comparison. Without loss of generality, we assume $K=C_{out}\cdot
h$, and in our following settings for low-rank $r$ (details in Table
1)222Although in LoGAH-Large setting: $d=r=256$, Eqn. (9) will obtain
$16d\cdot(64d-2048)>0$ since $d$ is very large. We also tried $d=384,r=256$,
however, the training is unstable.:$r\approx\frac{d}{2}$. Then Eqn. (2) - Eqn.
(5) we obtain:

$\displaystyle\Delta\textbf{P}={\color[rgb]{0,0.88,0}4d^{2}\times(16^{2}-1)}$
$\displaystyle+8d\times(d^{2}-2r^{2})+d\times\text{num\\_class}{\color[rgb]{1,0,0.5}-r\times
C_{out}\cdot h}.$ (6)

Since $r\approx d/2$, $16^{2}-1\approx 16^{2}$, and in our experiments we set
$K=\max(C_{out}\cdot h,C_{in}\cdot w)=2048\cdot 16$, we can just compare the
first term and last term in Eqn . (6):

$\displaystyle\Delta_{1}$ $\displaystyle=4d^{2}\times(16^{2}-1)-r\times
C_{out}\cdot h$ (7) $\displaystyle\approx 4d^{2}\times 16^{2}-d\times
1024\cdot 16$ (8) $\displaystyle=16d\cdot(64d-1024).$ (9)

Therefore, $\Delta_{1}>0$ since in our settings $d=64,128,256$, etc, which
means that LoGAH’s decoder requires fewer parameters ($\Delta\textbf{P}>0$),
even if we let $r$ increase with $d$.

###  3.2 Predicting parameters in larger shapes with fewer parameters

Thanks to the low-rank mechanism, LoGAH can support predicting the parameter
tensors with a larger shape but with fewer parameters. The parameters
comparison between different versions of GHN-3 and LoGAH is shown in Figure 1.
Since GHN-3 can only support the predicted parameters as the same width as the
hidden size $d$, we fit the curve of GHN-3 and obtain the potential number of
parameters needed to fully predict parameters with larger shapes. Compared to
GHN-3, our LoGAH can support wider tensor shapes with much fewer parameters,
which can support larger models (often wider) in practice (referring to Table
C and Table C).

##  4 ViTs-1K and GPTs-1K Datasets

For sampling training architectures in previous GHN-related works, Knyazev et
al. (2021) built DeepNets-1M, a dataset of 1 million diverse computational
graphs. However, for generating Transformer models such as ViT and GPT-2,
DeepNets-1M is not optimal. Therefore we introduce ViTs-1K and GPTs-1K: these
new datasets contains 1K different ViT-style and GPT-2-style computational
graphs respectively, particularly for training GHNs to predict ViT and GPT-2’s
parameters.

ViTs-1K. We produce diverse ViT models by varying the number of layers $L$,
heads $H$ and hidden size $D$. Since ViT models have different scale versions
(as illustrated in Table C of Appendix C), we also need to ensure that our
training architectures will be diverse enough and uniformly distributed in
terms of parameter count. Therefore, when generating these architectures, for
deeper networks (with more layers) we control them to be narrower (with a
smaller hidden size) and vice versa. Figure 8a shows the distribution of the
amounts of parameters in ViTs-1K, which is almost uniformly distributed and
the maximum parameters of these architectures are restricted to 10M (only
around of half of ViT-Small’s parameters). The details of ViTs-1K dataset’s
generation can be found in Appendix E.

GPTs-1K. We follow the same above idea to get different GPT-2 models, by
varying the number of layers $L$, heads $H$ and hidden size $D$, to build
GPTs-1K. The parameter count distribution is shown in Figure 8b, and the
maximum parameter count is within 30M, which is much less than GPT2-Small with
110M parameters. The GPT-2 variants details are presented in Table C in
Appendix C and the ones for the GPTs-1K dataset’s generation can be found in
Appendix F.

Importantly, these datasets are smaller than Large Language Models (LLMs) and
similarly large vision models; this is by design. The purpose is to reduce the
computation required for learning to predict parameters while giving a
continuous range of scale (from tiny to large) so that LoGAH can generalize to
large models after training.

Table 1: Details of LoGAH variants and GHN-3 variants. All LoGAH variants are set with $K=2048\cdot 16$. We estimate the train time of each model based on meta-batch $m=1$ and the CIFAR-100 dataset for 300 epochs. Model | r | L | d | H | Max Width | P | Train Time
---|---|---|---|---|---|---|---
LoGAH-Tiny | 32 | 3 | 64 | 8 | 2048 | 2.5M | 7.05h
LoGAH-Small | 90 | 5 | 128 | 16 | 2048 | 21.4M | 7.25h
LoGAH-Base | 128 | 5 | 256 | 16 | 2048 | 78.2M | 10.30h
LoGAH-Large | 256 | 12 | 256 | 16 | 2048 | 289.4M | 21.0h
GHN-3-Tiny | - | 3 | 64 | 8 | 64 | 6.9M | 7.20h
GHN-3-Small | - | 5 | 128 | 16 | 128 | 35.8M | 7.75h
GHN-3-Large | - | 12 | 256 | 16 | 256 | 214.7M | 12.40h
GHN-3-XLarge | - | 24 | 384 | 16 | 384 | 654.4M | 24.0h

##  5 Experiments

We evaluate if networks (i.e. ViT and GPT-2) initialized with the parameters
$\textbf{w}_{\text{pred}}$ predicted by LoGAH can perform better than those by
GHN-3 and random initialization after fine-tuning.

LoGAH Variants. We provide four different scales of LoGAH from Tiny to Large,
by gradually increasing the number of layers $L$, hidden size $d$, heads $H$,
as well as the low-rank $r$. We also compare the number of parameters and
estimate the training time difference between LoGAH with GHN-3, shown in Table
1. We highlight that GHN-3 and LoGAH are trained only once on each dataset, so
that the same model can predict parameters for many architectures making the
training cost of GHN-3 and LoGAH amortized.

GHN Training Setup. The GHN models, including GHN-3 and our LoGAH, are trained
for $300$ epochs on ViTs-1K and GPTs-1K datasets. For ViT, we conduct
experiments on the following datasets: CIFAR-10, CIFAR-100 (Krizhevsky et al.,
2009) (with batch size $b=64$) and ILSVRC-2012 ImageNet (Russakovsky et al.,
2015) (with batch size $b=128$). We train the models using automatic mixed
precision in PyTorch with a cosine annealing learning rate schedule starting
at $lr=3e-4$, weight decay $\lambda=1e-2$, and predicted parameter
regularization $\gamma=3e-5$ (Knyazev et al., 2023). For GPT-2 experiments we
use the WikiText dataset (Merity et al., 2016), and use $lr=1e-4$ with batch
size $b=6$, while keeping the other hyperparameters as before. All GHN models,
including GHN-3 and LoGAH, are trained separately on each task dataset.

Table 2: CIFAR-10, CIFAR-100 and ImageNet top-1 accuracy (%) on ViT-Small and ViT-Base in different initialization settings. ViT models on CIFAR datasets are fine-tuned for 100 epochs in each initialization setting, while for ImageNet dataset, ViTs are fine-tuned for 30 epochs due to the time cost consideration. All GHN models can be trained on a single NVIDIA 4090 GPU when meta-batch $m=1$ with /m1 suffix. On ImageNet, we only train GHN-3-Tiny. Initialization | CIFAR-10 | CIFAR-100 | ImageNet
---|---|---|---
| ViT-Small | ViT-Base | ViT-Small | ViT-Base | ViT-Small | ViT-Base
RandInit | 83.93 | 84.74 | 58.73 | 57.00 | 62.15 | 63.61
OrthInit | 80.11 | 84.24 | 58.97 | 57.48 | 63.15 | 63.86
GHN-3-T/m1 | 81.29 | 78.18 | 56.33 | 56.70 | 38.79 | 31.89
GHN-3-S/m1 | 83.61 | 82.57 | 57.37 | 59.93 | - | -
GHN-3-L/m1 | 84.69 | 82.84 | 57.48 | 56.57 | - | -
LoGAH-T/m1 | 82.87 | 82.87 | 60.05 | 56.77 | 62.16 | 61.68
LoGAH-S/m1 | 86.09 | 86.35 | 61.05 | 62.38 | 62.49 | 63.29
LoGAH-B/m1 | 85.16 | 85.39 | 60.58 | 60.02 | 59.00 | 61.22
LoGAH-L/m1 | 83.22 | 84.40 | 62.19 | 63.47 | 63.00 | 63.70

###  5.1 ViT Experiments.

####  5.1.1 Overall Comparision on CIFAR-10, CIFAR-100 and ImageNet

We test ViT-small and ViT-base on CIFAR-10, CIFAR-100 (Krizhevsky et al.,
2009) and ILSVRC-2012 ImageNet (Russakovsky et al., 2015) shown in Table 2
with different initialization methods: (1) random initialization (RandInit)
implemented by default in PyTorch, (2) orthogonal initialization (OrthInit)
(Saxe et al., 2014), (3) parameters predicted by GHN-3, and (4) parameters
predicted by LoGAH. From Table 2, we observe that LoGAH generally outperforms
RandInit, OrthInit and GHN-3.

Figure 2: CIFAR-10 top-1 accuracy (%) on ViT-Small and ViT-Base where LoGAH is
trained with different meta-batch size $m$.

The ViT models are fine-tuned for 100 epochs on CIFAR, and 30 epochs on
ImageNet datasets. For ViT-Small, we set the learning rate range as
$\\{0.1,0.2,0.3,0.4,0.5\\}$. For ViT-Base and ViT-Large, we set it as
$\\{0.03,0.04,0.05,0.06,0.1\\}$. All ViT models are fine-tuned using SGD with
the same setting as Knyazev et al. (2023), but with weight decay $1e-2$. We
report the best validation accuracy among all learning rates.

CIFAR-10. LoGAH-Small presents the best performance (i.e. 2.16% improvement
than RandInit, and 1.4% improvement than GHN-3-L in ViT-small) with only
$21.41$M parameters, compared to GHN-3-L with $214.7$M parameters, $10$x
larger than LoGAH-Small, which demonstrates the effectiveness of our low-rank
decoder. For ViT-base models, GHN-3-L has the closest performance to our
smallest version of our models: LoGAH-Tiny.

CIFAR-100. LoGAH-Large outperforms other models with a big improvement,
especially compared to RandInit (3.46% on ViT-Small and 6.47% on ViT-Base),
while GHN-3’s performances are even worse than the random initializations on
ViT-Small.

ImageNet. Considering the time cost for training GHNs on ImageNet, for GHN-3,
we only train GHN-3-T/m1 in this dataset for comparison. The random
initialization methods, including RandInit and OrthInit, show comparable
performances with LoGAH. In this dataset, we do not observe a big improvement
as in CIFAR-10 and CIFAR-100. However, LoGAH-T performs much better than
GHN-3-T (62.16 vs. 38.79 for ViT-Small).

####  5.1.2 Effect of meta-batch size $m$ on LoGAH

In this section, we study the effect of the meta-batch size $m$ of LoGAH-Tiny
and LoGAH-Small on ViT-Small, ViT-Base and ViT-Large (shown in Figure 2 for
CIFAR-10 and Table 3 for CIFAR-100). We increase the value of $m$ from $1$ to
$4,8$ and train LoGAH respectively.

CIFAR-10. In Figure 2, we can notice that increasing the meta-batch size $m$
can significantly improve the ViT-Small’s performance (i.e. from $82.87$ to
$87.04$ by LoGAH-Tiny, and from $86.09$ to $87.35$ by LoGAH-Small when setting
$m=4$), which is even better than larger LoGAH models trained with $m=1$.
However, a reverse pattern is observed in ViT-Base, increasing $m$ to $4$ will
worsen the performance on CIFAR-10.

Table 3: CIFAR-100 top-1 accuracy (%) on ViT-Base and ViT-Large where $m=4,8$ for training LoGAH. Initialization | ViT-Base | ViT-Large
---|---|---
RandInit | 57.00 | 55.62
LoGAH-T/m1 | 56.77 | 55.07
LoGAH-T/m4 | 60.61 | 59.88
LoGAH-T/m8 | 51.12 | 50.39
LoGAH-S/m1 | 62.38 | 59.90
LoGAH-S/m4 | 55.00 | 54.62
LoGAH-S/m8 | 51.58 | 51.61

CIFAR-100. For the CIFAR-100 dataset, we extend to the larger model: ViT-
Large. Enlarging the meta-batch size properly can significantly improve the
small LoGAH’s performance and help it achieve similar results as the larger
one (e.g. LoGAH-T/m4 vs. LoGAH-S/m1). Another interesting finding is that when
setting the meta-batch size $m=8$, both LoGAH’s performance drops
dramatically. One potential reason might lie in the smaller model sizes in
ViTs-1K, and larger meta-batch may cause the overfitting problem.

###  5.2 GPT-2 Experiments

Considering the time and other resource costs333For example, we did not train
on the OpenWebText dataset (Gokaslan et al., 2019), since it is too large., we
only apply two smallest LoGAH, LoGAH-T/m2 and LoGAH-S/m2, in the GPT-2
experiments. This section investigates the Causal Language Modeling (CLM)
task. We test the model’s performance on the WikiText dataset(Merity et al.,
2016). In detail, we choose GPT-2-Small and GPT-2-Medium for the
`wikitext-2-raw-v1` dataset. For the `wikitext-103-raw-v1` dataset, we select
GPT-2-Medium and GPT-2-Large. All models are trained with the randomly-
initialized parameters (i.e. RandInit), which is implemented by default in
HuggingFace (Wolf et al., 2019).

GPT-2 Training Setup. All the GPT-2 models are fine-tuned for 100 epochs on
each dataset. We use DeepSpeed (Rajbhandari et al., 2020) for improved
training efficiency with GPT-2-Medium and GPT-2-Large on WikiText-103. With
6$\times$ NVIDIA 4090 GPUs, we train the models by AdamW with learning rate as
$3e-6$, weight decay as $1e-2$, batch size as $4$ for GPT-2-Medium and as $2$
for GPT-2-Large.

Results. Table 4 shows the results. The performance is improved more
significantly on larger GPT-2 models and larger datasets (e.g. training
GPT-2-Large on the WikiText-103 dataset), which demonstrates that even our
smallest model (2.5M) can predict much better parameters than a random
initialization for a large model (774M).

Table 4: Perplexity score of the GPT-2 experiments. Initialization | WikiText-2 | WikiText-103
---|---|---
| GPT-2-Small | GPT-2-Medium | GPT-2-Medium | GPT-2-Large
RandInit | 250 | 350 | 22.32 | 32.41
LoGAH-T/m2 | 227 | 219 | 18.79 | 27.18
LoGAH-S/m2 | 238 | 284 | 19.89 | 24.08

###  5.3 Qualitative Analysis

We analyze the diversity of predicted parameters following experiments in
Knyazev et al. (2023, 2021). In detail, we predict parameters for ViT and
GPT-2, and collect one or two frequently occurring tensor shapes in each
model. Then we compute the absolute cosine distance between all pairs of
parameter tensors of the same shape and average it (Table 5). LoGAH predicts
more diverse parameters than GHN-3 in general on ViT models, especially in
ViT-Small on CIFAR-100, which is also consistent with the better performance
in Table 2. Another interesting finding is that LoGAH-Tiny is better at
predicting more diverse square parameters (e.g. (768,768) and (1024,1024))
than LoGAH-Small.

Table 5: Diversity of the parameters predicted by GHN-3, LoGAH vs. Pretrained ($*$: or trained by SGD from RandInit if pretrained parameters are unavailable) measured on the ViT and GPT-2. Pretrain*: ViT-Small is trained by SGD from RandInit for 100 epochs on CIFAR-100; for ViT-Base and ViT-Large we use the parameters pretrained on ImageNet; for GPT-2-Medium, we also load the available pretrained parameters in HuggingFace (Wolf et al., 2019).  Method | Parameter Tensor Shape
---|---
| CIFAR-100 | ImageNet | ImageNet | WikiText-103
| ViT-S | ViT-B | ViT-L | GPT-2-M
| (1536,384) | (768,768) | (1024,1024) | (3072,1024) | (1024,1024) | (1024,4096)
Pretrain∗ | 0.647 | 0.747 | 0.878 | 0.842 | 0.839 | 0.894
GHN-3-T | 0.191 | 0.513 | 0.402 | 0.420 | - | -
GHN-3-S | 0.290 | - | - | - | - | -
LoGAH-T | 0.284 | 0.563 | 0.410 | 0.385 | 0.420 | 0.393
LoGAH-S | 0.442 | 0.413 | 0.232 | 0.329 | 0.400 | 0.496

###  5.4 Transfer Learning Experiments

Figure 3: GPT-2 transfer learning experiments. LoGAH are trained on WikiText-2
and GPT-2 models are fine-tuned on WikiText-103 based on LoGAH’s predicted
parameters.

In this section, we explore the setting when LoGAH is trained on one dataset,
but is used to produce a parameter initialization for another (potentially
more difficult) dataset. For the ViT experiments, we conduct the transfer
learning experiments from CIFAR-10 to CIFAR-100, and from CIFAR-100 to
ImageNet. For the GPT-2 experiments, we consider experiments from WikiText-2
to WikiText-103.

ViT Experiments. In detail, we re-initialize the classification layer (Knyazev
et al., 2023) using a Kaiming normal distribution (He et al., 2015) with 100
and 1,000 outputs, for transferring to CIFAR-100 and ImageNet respectively,
then we fine-tune the entire network. The results are shown in Figure 4. On
CIFAR-100, ViTs initialized by the LoGAH-S, LoGAH-B outperform random
initialization. It is still a demanding task for LoGAH to work on the ImageNet
dataset, and LoGAH-T is generally better than larger ones, which suggests that
parameters that work well on CIFAR-100 may not be optimal for ImageNet.
However, compared to GHN-3-T in Table 2, it shows superior performances in
both ViT-Small and ViT-Base.

Figure 4: ViT transfer learning experiments. We use LoGAH trained on CIFAR-10
(resp. CIFAR-100) to predict ViT’s parameters, then ViT is trained on
CIFAR-100 (resp. ImageNet). T, S, B and L denotes Tiny, Small, Base and Large
versions of LoGAH respectively.

.

GPT-2 Experiments. We keep the same setting as in Section 5.2, and fine-tune
GPT-2-Medium and GPT-2-Large on WikiText-103 loaded with LoGAH predicted
parameters, which are trained on the WikiText-2 dataset. According to Figure
3, LoGAH’s predicted parameters are also a good initialization for fine-tuning
GPT-2 models on WikiText-103, especially for GPT-2-Large.

According to the above results, the parameters predicted by LoGAH present a
desired transfer learning ability from one easier to another harder task. This
improvements are more significant if the data distribution is close (e.g. from
CIFAR-10 to CIFAR-100). Moreover, this property can help reduce the training
time for LoGAH to predict good parameters, where we do not need to train LoGAH
on a large-scale dataset.

##  6 Related Work

Large Models Pretraining. The large-scale pretrained models first appeared in
the NLP field (Yin et al., 2022; Guo et al., 2022). The improvement and
success are mainly attributed to self-supervised learning and Transformer
(Vaswani et al., 2023). More and more large language models are developed
based on it, extending to larger sizes for better performance under
pretraining with massive data (Devlin et al., 2019; Brown et al., 2020;
Touvron et al., 2023). Inspired by the advancement of Transformer, many
Transformer-based vision models are also proposed, and some pretraining
methods have been explored (Dosovitskiy et al., 2021; Carion et al., 2020; He
et al., 2021; Chen et al., 2020). Our work focuses on predicting parameters
for two Transformer-based models (ViT and GPT-2) to reduce pretraining costs.

Parameter Prediction. Hypernetworks (Ha et al., 2016) are often leveraged for
predicting model’s parameter. Many research works have extended the
hypernetwork’s capability to generalize on unseen architectures (Zhang et al.,
2018; Nirkin et al., 2021; Knyazev et al., 2021), datasets (Requeima et al.,
2020; Lin et al., 2021; Zhmoginov et al., 2022; Kirsch et al., 2024), or to
generate interpretable networks (Liao et al., 2023). Our paper is also based
on Graph HyperNetworks (GHNs), but overcomes the extreme increase of
parameters needed in previous GHNs. LoGAH can support larger models with just
$1\%$ parameters, showing a better ability to predict parameters for larger
networks.

Initialization and Learning to Grow Models. Several methods have improved on
random initialization by learning from data (Dauphin and Schoenholz, 2019;
Yang et al., 2022). However, GHN-3 (Knyazev et al., 2023) showed better
performance making it a favourable approach to build on. Other methods learn
to initialize a bigger model from a smaller pretrained model (Evci et al.,
2022; Wang et al., 2023). These methods reduce training time, however, a
smaller pretrained model of exactly the same architecture as the target model
is not always available, which limits the approach.

##  7 Limitations

Although our model LoGAH shows outstanding performances compared to GHN-3 and
other random initialization methods across the extensive experiments, there
are still limitations. Most importantly, due to the consideration of time and
resource costs, we conduct GPT-2 experiments only on the WikiText dataset and
only with our two smallest models. Furthermore, in order to predict parameters
for drastically novel architectures (e.g. (Gu and Dao, 2023)), the GHN might
be needed to be trained to avoid a big distribution shift. In future work, it
would be intriguing to show LoGAH’s ability on modern LLMs (Touvron et al.,
2023).

##  8 Conclusion

In this work, we propose LoGAH, a low-rank Graph HyperNetwork (GHN) that
addresses two issues of previous GHN-3. First, the low-rank decoder avoids
copying small chunks of parameters multiple times when predicting a large
shape parameter. Second, contrary to GHN-3, it does not require an exceptional
number of trainable parameters to support wider or larger models, and our
smallest LoGAH is only about 2.5M. We conduct extensive experiments on two
representative transformer-based models (ViT in vision and GPT-2 in language)
to show superior efficacy compared to GHN-3 and random initialization methods.
Furthermore, the generalization ability of LoGAH from a simple to another more
difficult dataset is also verified in the transfer learning experiments.

## References

  * He et al. [2021] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners, 2021.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In Jill Burstein, Christy Doran, and Thamar Solorio, editors, _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://aclanthology.org/N19-1423.
  * Radford et al. [2018] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al.  Improving language understanding by generative pre-training.  2018\.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open foundation and fine-tuned chat models, 2023.
  * AI@Meta [2024] AI@Meta.  Llama 3 model card.  2024\.  URL https://github.com/meta-llama/llama3/blob/main/MODEL_CARD.md.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale, 2021.
  * Dehghani et al. [2023] Mostafa Dehghani, Josip Djolonga, Basil Mustafa, Piotr Padlewski, Jonathan Heek, Justin Gilmer, Andreas Peter Steiner, Mathilde Caron, Robert Geirhos, Ibrahim Alabdulmohsin, et al.  Scaling vision transformers to 22 billion parameters.  In _International Conference on Machine Learning_ , pages 7480–7512. PMLR, 2023.
  * Thompson et al. [2022] Neil C. Thompson, Kristjan Greenewald, Keeheon Lee, and Gabriel F. Manso.  The computational limits of deep learning, 2022.
  * Zhai et al. [2022] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers, 2022.
  * Vaswani et al. [2023] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need, 2023.
  * Fukushima et al. [1983] Kunihiko Fukushima, Sei Miyake, and Takayuki Ito.  Neocognitron: A neural network model for a mechanism of visual pattern recognition.  _IEEE transactions on systems, man, and cybernetics_ , (5):826–834, 1983.
  * Russakovsky et al. [2015] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115:211–252, 2015.
  * Gao et al. [2020] Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al.  The pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Zhang et al. [2018] Chris Zhang, Mengye Ren, and Raquel Urtasun.  Graph hypernetworks for neural architecture search.  _arXiv preprint arXiv:1810.05749_ , 2018.
  * Knyazev et al. [2021] Boris Knyazev, Michal Drozdzal, Graham W. Taylor, and Adriana Romero-Soriano.  Parameter prediction for unseen deep architectures, 2021.
  * Knyazev et al. [2023] Boris Knyazev, Doha Hwang, and Simon Lacoste-Julien.  Can we scale transformers to predict parameters of diverse imagenet models?, 2023.
  * Zhang et al. [2020] Chris Zhang, Mengye Ren, and Raquel Urtasun.  Graph hypernetworks for neural architecture search, 2020.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Ying et al. [2021] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform bad for graph representation?, 2021.
  * Hu et al. [2021] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  Lora: Low-rank adaptation of large language models.  _arXiv preprint arXiv:2106.09685_ , 2021.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Merity et al. [2016] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher.  Pointer sentinel mixture models, 2016.
  * Saxe et al. [2014] Andrew M. Saxe, James L. McClelland, and Surya Ganguli.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, 2014.
  * Gokaslan et al. [2019] Aaron Gokaslan, Vanya Cohen, Ellie Pavlick, and Stefanie Tellex.  Openwebtext corpus.  http://Skylion007.github.io/OpenWebTextCorpus, 2019.
  * 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.
  * Rajbhandari et al. [2020] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He.  Zero: Memory optimizations toward training trillion parameter models, 2020\.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, 2015.
  * Yin et al. [2022] Da Yin, Li Dong, Hao Cheng, Xiaodong Liu, Kai-Wei Chang, Furu Wei, and Jianfeng Gao.  A survey of knowledge-intensive nlp with pre-trained language models, 2022\.
  * Guo et al. [2022] Shangwei Guo, Chunlong Xie, Jiwei Li, Lingjuan Lyu, and Tianwei Zhang.  Threats to pre-trained language models: Survey and taxonomy, 2022.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners, 2020.
  * Carion et al. [2020] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers, 2020.
  * Chen et al. [2020] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever.  Generative pretraining from pixels.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1691–1703. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/chen20s.html.
  * Ha et al. [2016] David Ha, Andrew Dai, and Quoc V. Le.  Hypernetworks, 2016.
  * Nirkin et al. [2021] Yuval Nirkin, Lior Wolf, and Tal Hassner.  Hyperseg: Patch-wise hypernetwork for real-time semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4061–4070, June 2021.
  * Requeima et al. [2020] James Requeima, Jonathan Gordon, John Bronskill, Sebastian Nowozin, and Richard E. Turner.  Fast and flexible multi-task classification using conditional neural adaptive processes, 2020.
  * Lin et al. [2021] Xixun Lin, Jia Wu, Chuan Zhou, Shirui Pan, Yanan Cao, and Bin Wang.  Task-adaptive neural process for user cold-start recommendation.  In _Proceedings of the Web Conference 2021_ , WWW ’21, page 1306–1316, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450383127.  doi: 10.1145/3442381.3449908.  URL https://doi.org/10.1145/3442381.3449908.
  * Zhmoginov et al. [2022] Andrey Zhmoginov, Mark Sandler, and Max Vladymyrov.  Hypertransformer: Model generation for supervised and semi-supervised few-shot learning, 2022.
  * Kirsch et al. [2024] Louis Kirsch, James Harrison, Jascha Sohl-Dickstein, and Luke Metz.  General-purpose in-context learning by meta-learning transformers, 2024\.
  * Liao et al. [2023] Isaac Liao, Ziming Liu, and Max Tegmark.  Generating interpretable networks using hypernetworks.  _arXiv preprint arXiv:2312.03051_ , 2023.
  * Dauphin and Schoenholz [2019] Yann N Dauphin and Samuel Schoenholz.  Metainit: Initializing learning by learning to initialize.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Yang et al. [2022] Yibo Yang, Hong Wang, Haobo Yuan, and Zhouchen Lin.  Towards theoretically inspired neural initialization optimization.  _Advances in Neural Information Processing Systems_ , 35:18983–18995, 2022.
  * Evci et al. [2022] Utku Evci, Bart van Merrienboer, Thomas Unterthiner, Max Vladymyrov, and Fabian Pedregosa.  Gradmax: Growing neural networks using gradient information.  _arXiv preprint arXiv:2201.05125_ , 2022.
  * Wang et al. [2023] Peihao Wang, Rameswar Panda, Lucas Torroba Hennigen, Philip Greengard, Leonid Karlinsky, Rogerio Feris, David Daniel Cox, Zhangyang Wang, and Yoon Kim.  Learning to grow pretrained models for efficient transformer training.  _arXiv preprint arXiv:2303.00980_ , 2023.
  * Gu and Dao [2023] Albert Gu and Tri Dao.  Mamba: Linear-time sequence modeling with selective state spaces.  _arXiv preprint arXiv:2312.00752_ , 2023.
  * Fukushima [1975] Kunihiko Fukushima.  Cognitron: A self-organizing multilayered neural network.  _Biological cybernetics_ , 20(3-4):121–136, 1975\.

##  Appendix A Details of the amounts of parameters of decoders in GHN-3

The theory amount of parameters of decoders in GHN-3 is shown below:

$\displaystyle 4\times\text{in\\_feature}\times d\times h\times
w+\text{MLP\\_d}_{1}\times\text{MLP\\_d}_{2}+\text{MLP\\_d}_{2}\times
d^{2}+d\times\text{num\\_class}$ (10)

where in_feature is the input feature’s dimension of the decoder (set as $d$
in GHN-3), and $\text{MLP\\_d}_{1},\text{MLP\\_d}_{2}$ denote the dimension of
$1_{\text{st}}$ and $2_{\text{nd}}$ layers of MLP (set as $4d$ and $8d$ in
experiments respectively), $h,w$ are the last two dimensions of the predicted
tensor’s shape (set as $16$) and num_class is the number of classes of the
dataset. Thereby, we can simplify Equation (10) to (2).

##  Appendix B Details of MLPs in the decoder of LoGAH

The MLPs has 4 layers and the activation function $\sigma(\cdot)$ is ReLU
Fukushima [1975]:

x
$\displaystyle=M_{3}\Bigg{(}\sigma\bigg{(}M_{2}\Big{(}\sigma\big{(}M_{1}(\textbf{H})\big{)}\Big{)}\bigg{)}\Bigg{)}$
(11) x $\displaystyle=\text{reshape}(\textbf{x})\in\mathbb{R}^{|V|\times
2r\times r}$ (12) x
$\displaystyle=\text{reshape}\big{(}M_{4}(\sigma(\textbf{x}))\big{)}\in\mathbb{R}^{|V|\times
2K\times r}$ (13)

where $M_{i},i\in\\{1,2,3,4\\}$ are learnable matrices:

$\displaystyle M_{1}$ $\displaystyle\in\mathbb{R}^{d\times
4d},M_{2}\in\mathbb{R}^{4d\times 8d}$ $\displaystyle M_{3}$
$\displaystyle\in\mathbb{R}^{8d\times 2r^{2}},M_{4}\in\mathbb{R}^{r\times K}$

We also provide the code implementation of it as shown in Figure 5.

⬇

class ConvDecoder3LoRA(nn.Module):

def __init__(self,

in_features,

ck=32,

r=32,

hid=(64,),

num_classes=None):

super(ConvDecoder3LoRA, self).__init__()

assert len(hid) > 0, hid

self.r = r

self.ck = ck

self.num_classes = num_classes

self.mlp = MLP(in_features=in_features,

hid=(*hid, r*2*r),

activation=’relu’,

last_activation=None)

self.l2 = nn.Linear(int(r), ck)

self.relu = nn.ReLU(inplace=True)

self.seq = nn.Sequential(

self.relu,

self.l2

)

def forward(self, x, max_shape=(1,1,1,1), class_pred=False, n_dim = 4):

if class_pred:

n_dim = 2

x = self.mlp(x).view(-1, 2*self.r, self.r) # [b, 2*r, r]

x = self.seq(x).view(-1, 2*self.ck, self.r) # [b, 2*ck, r]

A, B_t = torch.split(x, self.ck, dim=1) # A=[b, ck, r] and B=[b, ck, r]

B = B_t.transpose(1,2) # A=[b, ck, r] and B=[b, r, ck]

# fix shape of A and B before matmul through indexing

c_out, c_in, k_out, k_in = max_shape

A = A[:, :(c_out*k_out), :] # [b, c_out*k_out, r]

B = B[:, :, :(c_in*k_in)] # [b, r, c_in*k_in]

W = torch.bmm(A, B) # [b, c_out*k_out, c_in*k_in]

if n_dim == 1: # We want [c_out]

assert c_in == 1 and k_out == 1 and k_in == 1

W = W.reshape(-1, c_out)

elif n_dim == 2: # we already have a 2D matrix

pass

elif n_dim == 4:

W = W.reshape(-1, c_out, k_out, c_in, k_in).transpose(2, 3) # [b, c_out, c_in,
k_out, k_in]

else:

raise NotImplementedError("n_dim must be 1 or 2 or 3")

#print(W.shape)

return W

Figure 5: Code for Low-rank decoder in LoGAH.

⬇

layers = np.random.randint(3, 10)

if layers > 5:

dim_min = 128

dim_max = 256

elif layers > 3:

dim_min = 256

dim_max = 384

else:

dim_min = 384

dim_max = 512

hidden_dim = np.random.choice(np.arange(dim_min, dim_max+1, 32))

mlp_dim = hidden_dim * 4

if hidden_dim % 12 == 0:

heads = np.random.choice([3, 6, 12])

elif hidden_dim % 6 == 0:

heads = np.random.choice([3, 6])

elif hidden_dim % 3 == 0:

heads = 3

else:

heads = np.random.choice([4, 8])

net = _vision_transformer(

patch_size = 2,

num_layers = layers,

num_heads = heads,

hidden_dim = hidden_dim,

mlp_dim = mlp_dim,

num_classes = 100,

image_size = 32,

weights = None,

progress = False,

)

Figure 6: Code for generating ViT-style models used for ViTs-1K dataset.

⬇

n_layer = np.random.randint(3, 10)

if n_layer > 5:

dim_min = 72

dim_max = 176

elif n_layer > 3:

dim_min = 128

dim_max = 176

else:

dim_min = 176

dim_max = 256

n_embd = np.random.choice(np.arange(dim_min, dim_max+1, 8))

if n_embd % 8 == 0:

n_head = 8

elif n_embd % 6 == 0:

n_head = 6

elif n_embd % 4 == 0:

n_head = 4

config = GPT2Config(

bos_token_id=tokenizer.bos_token_id,

eos_token_id=tokenizer.eos_token_id,

n_embd=int(n_embd),

n_layer=int(n_layer),

n_head=int(n_head),

tie_word_embeddings=False,

)

model = GPT2LMHeadModel(config)

Figure 7: Code for generating GPT-2-style models used for GPTs-1K dataset.

##  Appendix C Details of variants of ViT and GPT-2

We provide the details of ViT and GPT-2 in different sizes. $L,D,H,P$ denotes
the numbers of layers, heads, hidden size and parameters, respectively.

Model | L | D | MLP size | H | P
---|---|---|---|---|---
ViT-S | 12 | 384 | 1536 | 6 | 22M
ViT-B | 12 | 768 | 3072 | 12 | 86M
ViT-L | 24 | 1024 | 4096 | 16 | 307M

tableDetails of ViT variants

Model | L | D | H | P
---|---|---|---|---
GPT-2-S | 12 | 768 | 12 | 110M
GPT-2-M | 24 | 1024 | 16 | 345M
GPT-2-L | 36 | 1280 | 20 | 774M

tableDetails of GPT-2 variants

##  Appendix D Distribution of ViTs-1K and GPTs-1K datasets

The distributions of ViTs-1K and GPTs-1K datasets are shown in Figure 8.

(a) The parameters distribution in ViTs-1K.

(b) The parameters distribution in GPTs-1K.

Figure 8: The parameters distribution of ViTs-1K and GPTs-1K datasets

##  Appendix E Details of generating ViTs-1K dataset

As mentioned above, we change the values in layers $L$, heads $H$, and hidden
size $D$ of ViT, as well as restricting these models size. The details are
shown in Figure 6.

##  Appendix F Details of generating GPTs-1K dataset

We also change the values in layers $L$, heads $H$ and hidden size $D$ of
GPT-2, and the details are shown in Figure 7.


A comparison is made between Exhaustive Search (ES) and Iterative Local Search (ILS). Such comparison was made using the Quantum Approximation Optimization Algorithm (QAOA). QAOA has been extensively researched due to its this potential to be implemented in actual quantum hardware, and its promising future in optimization problems and quantum machine learning. ES and ILS approaches were simulated to determine the pros and cons of these techniques for QAOA in local (classic computer) and real simulations (IBM quantum computer). These classic approaches were used in QAOA to approximate the optimal expected value in Max-Cut and Ising Spin Model (ISM) problems, both of these flavors have three simulated configurations called: linear, cyclic and complete (or full).

Keywords: Quantum computing, QAOA, Exhaustive Search, Iterative Local Search, Quantum Operators, Ising Spin Model, Max-Cut, Combinatorial Optimization Problems.

§ INTRODUCTION

Nowadays, quantum computing algorithms applied to all kinds of Optimization or Big data problems are of great importance. The actual quantum hardware is considered to be low or intermediate capacity, where most of the devices are not fault-tolerant, which is one of the reasons that quantum algorithms are not regarded as good candidates to be used in actual applications. <cit.> <cit.> <cit.>

For the case of the Quantum Approximation Optimization Algorithm the idea is different, this algorithm is considered a classic-quantum hybrid where some stages of the algorithm are quantum and some are classic, but the difference and the interest of this approach from other quantum algorithms is that QAOA is a low-depth algorithm, in other words, this algorithm does not need too much qubits and quantum gates to operate (only the necessary qubits to represent the problem), and also the QAOA has great fault-tolerant characteristics and due to the low-depth the decoherence factor does not affect considerably the implementation of the algorithm. <cit.> <cit.> <cit.>

Combinatorial optimization problems can be seen in several areas from hardware verification to artificial intelligence, some examples of these problems include the Knapsack problem, Traveling Salesman, Vehicle Routing, etc. These problems can fall into one of these categories: Max-Sat, Max-Cut, and Max-Clique, and as a general approximation we can represent the maximization problem in general. <cit.> <cit.> <cit.>

* There are $n$ binary decision variables $z_{i}$.

* $m$ binary functions (called clauses) of those variables contained in $C_{\alpha}(z)$.

* And $z_{i} \in \left \{  0, 1 \right \} \forall i \in \left \{1, 2, … , n\right \}$

\begin{equation}
maximize: \sum_{\alpha=1}^{m}C_{\alpha}(z)
\end{equation}

For the case of the ISM (or Ising Energy Model) it could be seen as an extension of the Max-Cut kind of problem where we also consider an extra part for the cost function. The classic Max-Cut problems only consider the connections between a set of nodes in a graph, but in ISM the presence of an external element known as the external magnetic field is also taken into account (these magnetic fields operate individually for every particle or node in the system).

§.§ Why QAOA ?

QAOA is considered a near-term quantum algorithm, this stands for an algorithm which can run in a small quantum computer (like IBM Q computers), this algorithm can solve useful problems, etc.

QAOA is a low-depth algorithm, in other words this algorithm does not need numerous quantum gates to be applicable, and this characteristics means that the algorithm shouldn't need too much coherence, and finally some results show that QAOA is fairly robust against errors. <cit.> <cit.>

The number of qubits needed to develop the algorithm, in theory, are the number of qubits to store the problem information.

§.§ Interpretation of C(z) in a QAOA Problem

As a general example for a problem that can be solved using QAOA is a problem with some set of variables which create a large space of combinations, where one of those combinations is our best result, is the combination which optimizes some criteria. This criteria is related to the Cost Function denoted by $C(z)$, where $z$ contains all the set of variables to $n$ be optimized.

\begin{equation}
z \equiv \left \{ z_{1}, z_{2}, ... , z_{n} \right \} ; z_{j} \left \{ -1, +1 \right \}
\end{equation}

Now, the problem is: how we translate the $C(z)$ cost function into a valid quantum problem, this translation of the problem consists in creating an operator $C$ which will return a value represented by the cost function. This operator $C$ can be seen as the diagonal matrix of $C(z)$ where each value in the diagonal is the possible values of $C(z)$.

\begin{equation}
C(z)\rightarrow C \ket{z} = C\ket{z_{1}z_{2}...z_{n}} = C(z)\ket{z_{1}z_{2}...z_{n}}
\end{equation}

Now, the representation for the $z_{j}$ variables can be expressed in a quantum computing way using the Pauli $Z$ operator, this operator follows the property that every value of $z$ should be ${+1,-1}$, the representation of the $Z$ operator is as follows.

\begin{equation*}
Z = \begin{pmatrix}
1 & 0\\
0 & -1
\end{pmatrix}
; I = \begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
\end{equation*}

With this representation of $Z$ in mind, now it can be established the new representation for the cost function using the $Z$ operator, the identity operator $I$ and tensor products between them.

\begin{equation}
C(Z) =  Z_{1} \otimes Z_{2} \otimes ... \otimes Z_{n} \otimes I_{n}
\end{equation}

Depending on the problem, the sequence and how the tensor products of $Z$ and $I$ are applied will be different.

\begin{equation*}
C(Z) = \begin{bmatrix}
1 & 0\\
0 & -1
\end{bmatrix}_{1} \otimes
\begin{bmatrix}
1 & 0\\
0 & -1
\end{bmatrix}_{2} \otimes ...
\end{equation*}

\begin{equation*}
\begin{bmatrix}
1 & 0\\
0 & -1
\end{bmatrix}_{n} \otimes
\begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}_{n}
\end{equation*}

And this tensor products of the operators $Z_{n}$ and $I_{n}$ result on the diagonal matrix with the $C(z)$ expected values.

\begin{equation}
C(Z) = \begin{bmatrix}
C(Z_{1}) &  0&  0&  0&  0&  0 \\
0 &  C(Z_{2}) &  0&  0&  0&  0 \\
0 &  0&  . &  0&  0&  0 \\
0 &  0&  0&  . &  0&  0 \\
0 &  0&  0&  0&  . &  0 \\
0 &  0&  0&  0&  0& C(Z_{n})  \\
\end{bmatrix}
\end{equation}

The matrix representation allows identifying where the $C(Z)$ values appear, where each $C(Z_{i})$ element corresponds to a particular outcome from the classic cost function. After the diagonalization of the cost function, the matrix need to be unitary to be a valid quantum operator <cit.> <cit.>

§.§.§ Phase Operator $U(C,\gamma)$

So the next step is to convert $C(Z)$ into a unitary operator, this process can be achieved using the Phase Operator $U(C,\gamma)$. The Phase Operator is responsible to translate the optimization problem into a valid quantum operator, this operator establishes the connections between particles or nodes (depending on the type of problem analyzed) and the constraint factors (like in ISM where a function related to the external magnetic field is needed), which is defined as:

\begin{equation}
U(C,\gamma)= e^{-i \gamma C}
\end{equation}

The application of the phase operator also guarantees that the resulting matrix will be diagonal, but more important due to the fact that $U(C, \gamma)$ contains the imaginary element $i$ the resulting matrix elements will also contain the $i$ element. With these two properties of $C(Z)$ being diagonal and having the $e^{i}$ elements guarantees that the resulting matrix will be unitary.

\begin{equation*}
U(C,\gamma)= \begin{bmatrix}
e^{i C(Z_{1})  \gamma} &  0&  0&  0&  0&  0\\
0 &  e^{i C(Z_{2}) \gamma} &  0&  0&  0&  0\\
0 &  0&  . &  0&  0&  0\\
0 &  0&  0&  . &  0&  0\\
0 &  0&  0&  0&  . &  0\\
0 &  0&  0&  0&  0&   e^{i C(Z_{n}) \gamma}
\end{bmatrix}
\end{equation*}

In the equation from above, it can be seen that every element from the diagonal matrix form of the $C(Z)$ function is contained in the matrix $U(C,\gamma)$ in the form of phases.

In the case of the matrix of $C(Z)$, a new term is found $\gamma$, this value does not come from the application of the phase gate purely, this $\gamma$ variable is related to the optimization part of the QAOA, and as a brief mention, it will be added another variable named $\beta$, these two variables are the ones that will give us the superposition state which after a measurement should yield with high probability to the state that solves the optimization problem.

\begin{equation}
U(C,\gamma)\ket{s} = \frac{1}{2}(e^{iC(Z_{1})\gamma}\ket{0}^{\otimes N} + e^{iC(Z_{n})\gamma}\ket{1}^{\otimes N}
\label{eq:cz_phae_operator}
\end{equation}

§.§.§ Mixing Operator $U(B,\beta)$

After the application of the phase operator, every value of the original cost function is distributed as encoded phases in the $e^{-iC\gamma}$ terms seen on the Equation <ref>, but even if this representation is indeed unitary, when we measure this state every element has the same probability of occurrence, and this equal probability is not one of the thing we want from QAOA, we want QAOA to give us the optimum state with greater probability than the other possible states.

With this idea in mind, the next operator to be applied is the Mixing Operator, this operator has the property of mixing all the amplitudes of the possibles states (e.g. Equation <ref>) to create constructive and destructive interference, the interference pattern relate higher or lower amplitudes (and hence the probability) of every state.

* $X_{j}$ is the $X$ Pauli operator, and $j=1,2,...,N$.

\begin{equation*}
X = \begin{bmatrix}
0 && 1 \\
1 && 0
\end{bmatrix}
\end{equation*}

* $B$ is composed of $X$ operators.

* $\beta$ is the mixing free parameter.

\begin{equation}
B = \sum_{j}^{N}X_{j}
\end{equation}

\begin{equation}
U(B, \beta) = e^{i \beta B}
\end{equation}

The difference between the phase operator and the mixing operator, is that after the application of the exponentiation of the operator $B$ the result is no longer a diagonal matrix operator (due to the structure of the $X$ Pauli), and this led to the amplitude mixing.

Because $B$ is a linear sum of $X$ operator applied for each qubit in the system, the mixing operator $U(B, \beta)$ can be represented as follows:

\begin{equation}
U(B, \beta) = \coprod_{j}^{N}e^{i\beta X_{j}}
\label{eq:mo_coprod}
\end{equation}

In the Equation <ref> the $N$ corresponds to the number of qubits in the system. Each $e^{i\beta X_{j}}$ has the following structure:

\begin{equation}
e^{i\beta X} = R_{X}(\beta) = \begin{bmatrix}
cos(\beta) && i sin(\beta) \\
i sin(\beta) && cos(\beta)
\end{bmatrix}
\end{equation}

§.§.§ Expectation Value $F(\gamma,\beta)$

In general, the goal of QAOA is to minimize or maximize the expectation value of the cost function. This expectation value can be represented using the following equations.

\begin{equation}
\ket{\psi_{\gamma \beta}}=U(B,\beta) U(C,\gamma) \ket{s}
\label{eq:expectation_value}
\end{equation}

\begin{equation}
F(\gamma,\beta)=\bra{\psi_{\gamma \beta}}C(Z)\ket{\psi_{\gamma \beta}}
\end{equation}

The expectation value is obtained by repeated measurements over the same prepared quantum state, this repeated measurements try to approximate the wave-function of the system. The measurement process is repeated several times to improve the accuracy of the expectation value.

Sometimes the amplitudes related to the wave-function are said to be the real amplitude values for the possible state outcomes, and the measured values are called the approximation, as it was said, with the increase of the number of experiment measurements the accuracy increases but also the length of the algorithm increase and the execution time.

§.§ Max-Cut

Max-Cut problems are one of the most interesting and popular problems to implement QAOA on because Max-Cut is a problem that has been widely studied by a lot of researches of different fields in the past decades. Nowadays, the study of the Max-Cut problem has been leaded to the application of quantum algorithms, in specific, QAOA is one of the most promising ones. The general idea of the problem is to create two subsets of nodes from a general set of nodes (graph) where the connections between each subset is the maximum possible. <cit.> <cit.>

Max-Cut problem example with optimal solution.

The Figure <ref> is used as an example of how Max-Cut problems are solved, the main graph contains all the nodes $A_{1}$, $A_{2}$ and $B_{1}$, $B_{2}$; each node has one or more connections with the other ones (mostly depending on the configuration of the graph), the idea of how to solve the problem is to separate the nodes in two subsets (the green subset and the red subset) and count how many connections are between the two subsets, the figure from above show the one of the optimal solutions that is having the nodes $A_{1}$ and $A_{2}$ in the subset of green nodes and having the $B_{1}$ and $B_{2}$ in the subset of red nodes (the other optimal configuration is to exchange both nodes of the green subset to the red subset and vice versa). Normally these problems have at least two solutions (an optimal state and the inverse which only changes the labels between the subsets).

\begin{equation}
U(H_{p}) = U(C,\gamma)_{MC} = -\sum_{\left \langle i,j \right \rangle} J_{ij} z_{i}z_{j}
\label{eq:MC_phase_problem}
\end{equation}

The simple form for Max-Cut problem has only one consideration for the description of the problem, that is the connections between nodes, and the Equation <ref> represents these connections between nodes.

\begin{equation*}
U(C, \gamma) = e^{-i\gamma C} = e^{-i\gamma (\sum_{\left \langle i,j \right \rangle}Z_{i}Z_{j}) }
\end{equation*}

\begin{equation*}
= e^{-i\gamma (\sum_{\left \langle i,j \right \rangle} Z_{i}Z_{j})}
\end{equation*}

\begin{equation}
= \prod_{\left \langle i,j \right \rangle}e^{-i\gamma Z_{i}Z_{j}}
\label{eq:MC_phase_operator}
\end{equation}

The Equation <ref> represents the phase operator, where it is only considered the interaction (connection) between nodes of the graph, every pair of $\left \langle i,j \right \rangle$ elements corresponds to a pair of nodes ($node_{i}$ connects to $node_{j}$) which share a connection between them, this connection does not have any specific direction.

Also, as the example from above, we can replace $z_{i}$ and $z_{j}$ for the $Z$ operator where $Z_{i}$ and $Z_{j}$ can only take values from ${-1,+1}$. Seeing the Equation <ref> it can be established that the neighbors who have the same spin direction result in a $+1$ for the first summation on the equation, and the result is $-1$ if the nodes have different spin orientation.

The spin orientation is related to the way the nodes are separated, in other words if a qubit (node) is on a state $\ket{0}$ (one spin orientation) it can be interpreted as the qubit been on a specific subset and if the qubit is on the state $\ket{1}$ (another spin orientation) it will represent that the qubit is on the opposite subset.

The representation for the mixing operator is the following:

\begin{equation}
C(U, \beta) =  \prod_{ i } e^{-i \beta X_{i}}
\label{eq:mixing_operator_MC}
\end{equation}

The Equation <ref> is understood as the application of the mixing operator (due to the matrix form of the $X_{i}$ quantum gate) which generates the constructive or destructive interference patterns for the states of the system.

§.§.§ Max-Cut problems

The specific problems that explored of the class Max-Cut have three configurations, the first configuration corresponds to a $3$ ($P_{1}$, $P_{2}$ and $P_{3}$) nodes with linear configuration.

Max-Cut $3$ nodes with linear configuration problem.

The Figure <ref> represents the linear problem, in this case the problem has three nodes with connections $P_{1}$ with $P_{2}$ and $P_{2}$ with $P_{3}$. The optimal solutions for the problem (represented using BRA-KET notation for the state that is going to be obtained) are $\ket{010}$ and the inverse $\ket{101}$, these states have the nodes $P_{1}$ and $P_{3}$ in one subset and the node $P_{2}$ on the opposite subset. The evaluation value for the optimal states is $2$.

Max-Cut $4$ nodes with cyclic configuration problem.

The next problem in the Figure <ref> which has $4$ nodes in cyclic configuration, due to the configuration this problem has also two optimal state which are the states $\ket{0101}$ and the inverse $\ket{1010}$, the nodes $P_{1}$ and $P_{3}$ are in one subset and the nodes $P_{2}$ and $P_{4}$ belong to the other subset, the expected value evaluation for the optimal states is $4$.

Max-Cut $5$ nodes with complete (or full) configuration problem.

The last instance for the Max-Cut problems is in the Figure <ref> that represents the $5$ nodes with complete (or full) configuration graph, due to the type of configuration this problem in particular has a lot of optimal state some of them are the states $\ket{00011}$, $\ket{01110}$, $\ket{10110}$, etc. The expected value evaluation for any of the optimal states is $6$.

§.§ Ising Spin Model

The Ising Spin Models (ISM) or Ising Energy Models are real examples of problems that can be used to be optimized by QAOA algorithm. These systems are defined by a $d$ dimensional arrangement of $n$ number of spins $z_{i}$, one spin in every lattice cell $i$, and every particle (with associated spin) is affected by their nearest neighbors and the individual external magnetic field for every particle in the arrangement. The equation called the nearest-neighbor Edwards-Anderson Hamiltonian represents the energy of the system given by the nearest neighbors $\left \langle i,j \right \rangle$, $z_{i}$ and $z_{j}$ are the spins for the couple of particles, $J_{ij}$ is the coupling of $i$ and $j$, and $h_{i}$ is the individual (local) magnetic field for each particle. <cit.>

Ising Spin Model (ISM) or Ising Energy Model

\begin{equation}
U(H_{p}) = U(C,\gamma)_{ISM} = -\sum_{\left \langle i,j \right \rangle} J_{ij} z_{i}z_{j} - \sum_{i=1}^{n} h_{i} z_{i}
\label{eq:ising_model}
\end{equation}

The Equation <ref> shows the phase operator for the ISM, this phase operator is also known as the Problem Hamiltonian, as we said before, the main purpose of the phase operator is to translate the optimization problem to a valid quantum operator.

The optimal solution for these kinds of problems is a certain combination of the spins of the particles which are part of the quantum system, the number of possible combinations of $n$ spins is $2_{n}$ possible combinations, and it can be deduced that the ISM problem increases in complexity very fast as the number of particles in the system increases, and with fairly lager number of $n$ the number of combinations cannot be tracked by classical computers.

The encoded cost function from Equation <ref> in terms of a valid matrix operator for quantum computing, is represented in the next formula.

\begin{equation*}
U(C, \gamma) = e^{-i\gamma C} = e^{-i\gamma (-\sum_{\left \langle i,j \right \rangle}Z_{i}Z_{j}-\sum_{i}h_{i}Z_{i})}
\end{equation*}

\begin{equation*}
e^{i\gamma (\sum_{\left \langle i,j \right \rangle} Z_{i}Z_{j})} e^{i\gamma(\sum_{i}h_{i}Z_{i})}
\end{equation*}

\begin{equation}
\prod_{\left \langle i,j \right \rangle}e^{i\gamma Z_{i}Z_{j}} \prod_{i} e^{i\gamma h_{i}Z_{i}}
\label{eq:ising_coded_function}
\end{equation}

Now, the second part of the preparation for the ISM problem to be compatible with QAOA is to create the mixing operator for the problem, as a general idea all the mixing operators in the most basic form are equal for different problems as it can be seen in the mixing operator for the Max-Cut problem (sign changed).

\begin{equation}
C(U, \beta) =  \prod_{ i } e^{i \beta X_{i}}
\label{eq:mixing_operator_ISM}
\end{equation}

§.§.§ ISM problems

The problems analyzed for the ISM class are the following, these problems are the direct equivalent problem for the Max-Cut class in the sense that the problems are $3$ particles in linear configuration, $4$ particles in cyclic configuration and $5$ particles in complete configuration.

ISM $3$ particles with linear configuration problem.

In the Figure <ref> is described the problem for ISM with $3$ particles in linear configuration, the general idea of the problem is relatively similar to the instance for Max-Cut, but in this case the problem acquires a new element that corresponds to the external magnetic field.

ISM $4$ particles with cyclic configuration problem.

The Figure <ref> represents the problem for the $4$ particles case, in this configuration there is a connection between the first and last particle to complete the cycle.

ISM $5$ particles with complete (or full) configuration problem.

The last problem is shown in the Figure <ref>, in this case we have the complete or full configuration of the problem with $5$ particle, the name of the configuration stands for the connections allowed for each node, this configuration establishes that each particle of the system has a direct connection with all the other particles in the system.

§ GENERAL IMPLEMENTATION OF QAOA

After obtaining the Phase Operator $U(C,\gamma)$ and the Mixing Operator $U(B,\beta)$, the general preparation of the QAOA is listed below.

* Prepare the initial state: $\ket{\psi}=H^{\otimes N}\ket{0} = \ket{s}$, where $N$ is the number of qubits in the system.

* Select the free parameters $\gamma$ and $\beta$ (free or implemented by a function).

* Apply the phase operator and mixing operator: $U(B,\beta) U(C,\gamma) \ket{s}$.

* Apply the measurement in the computational basis $\ket{z{}'}$.

* Check $C(z{}')$

* Repeat 1,3,4,5 and compute the expectation value $F(\gamma,\beta)=\bra{\psi_{\gamma \beta}} C(Z) \ket{\psi_{\gamma \beta}}$.

* Search for the optimal values for $\gamma$ and $\beta$ for the step 2.

* Based on the classic optimization step, establish the best $C(z{}')$.

Finding the values for $\gamma$ and $\beta$ who maximizes or minimizes (depending on the problem) the $F(\gamma, \beta)$ which will lead to the measurement (with greater probability) of the $\ket{z{}'}$ state which is the state that optimizes our classic cost function, these parameters are found with classical methods, unfortunate nowadays there is no known a good quantum algorithm that can perform the finding steps of these variables. The parameters $\gamma$ and $\beta$ span the full range of rotations from $0$ to $2\pi$.

The quantum circuit for the example in the Max-Cut subsection (Figure <ref> is showed in the next diagram, the circuit represents the $4$ nodes with cyclic configuration Max-Cut.

|0⟩_1 (1)      H (2)     1        1

|0⟩_2     H          R_z(2γ)          1         1

|0⟩_3     H                      R_z(2γ)

|0⟩_4     H

3         3 (3)     R_x(β) (4)

1         1                 R_x(β)

R_z(2γ)                R_z(2γ)          R_x(β)

Quantum circuit for the $4$ nodes with linear configuration Max-Cut problem.

The quantum circuit diagram for the example showed in the Figure <ref> which is the $3$ particles with linear configuration ISM problem, the main difference between this quantum circuit and the one for the $4$ nodes with cyclic configuration Max-Cut problem (besides the configuration of the graph and the number of qubits) is that this circuit has a extra section in the phase operator, this section adds the external magnetic field for the particles.

|0⟩_1 (1)      H (2)     1        1

|0⟩_2     H          R_z(2γ)          1         1

|0⟩_3     H                      R_z(2γ)

…    (3)     R_z(h_1γ)     (4)     R_x(β)     (5)

…        R_z(h_2γ)         R_x(β)

…        R_z(h_3γ)         R_x(β)

Quantum circuit for the $3$ particles with linear configuration ISM problem.

§ OPTIMIZATION METHODS

In this paper, we tested two different methods to optimize the parameters for the phase operator and the mixing operator in QAOA. As it was mentioned, these two methods are classical optimization approaches that are used to generate the best combination of parameters for QAOA. <cit.>

§.§ Exhaustive Search

To prove that the QAOA algorithm approach works, two kinds of simulations were developed. The first approach tested was the Exhaustive Search (ES), this method is not used to probe the benefits of this technique because is already known that all this type of brute force algorithms are good to explore a search space (through a certain degree) but all of them are really expensive in terms of time and computational resources. The idea behind the use of ES is to create a base solution which can be compared to the other approach, to know if the other optimization method generates a good solution or if the solution is completely different from the one we expect. <cit.> <cit.> <cit.>

Exhaustive Search (ES) illustration.

In the Figure <ref> is represented how the ES method works, in the base model of the QAOA there are two parameters to be optimized, each parameter can be thought as a variable that takes one value from a range of values at a time. In ES every parameter explored is going to take all the values of the range allowed, the only restriction that ES has is the precision of the values, in the sense that the range of values for the parameters in QAOA is a continued set of values from $0$ to $2 \pi$ and ES is limited to explore a discrete number of values of that set.

§.§ Iterative Local Search

The heuristic of Iterative Local Search (ILS) or Iterated Local Search next method to be applied and analyzed in QAOA, this heuristic is based on an improved version of the Stochastic Hill Climbing (SHC) with random starts. <cit.> <cit.> <cit.> <cit.>

Iterative Local Search (ILS) illustration.

The Figure <ref> illustrates the ILS approach. ILS starts with a random point in a search space (blue cloud), once the starting point is established and evaluated using SHC, in each iteration of the ILS a random point of an area (green oval) is selected (relatively near the starting point), this selection of random points in an area is called Local Search, using this random points then the SHC algorithm is applied to find the best point in an even more reduced area, this process continues until the number of iterations of ILS is reached. The green area that represents the local search moves (or changes its amplitude) inside the search space during the ILS iteration, in other word, the local search area is not static (doesn't have a constant area). <cit.>

§ SIMULATIONS AND RESULTS

The simulation and results were separated in two subsections, the simulations using Exhaustive Search (ES) are on the first subsection and the Iterative Local Search are developed on the second subsection. Both of the classical optimization approaches were tested in local and real simulations.

The application of the classical optimization method is reserved only for the local simulations, that is because IBM only allows a limited time for running a quantum circuit in their devices and since running the classical optimization is always going to be executed on a classical computer, the differences between running the optimization method on a classic local device and in a classic computer from IBM are practically negligible. With that said, the best combinations for the values of the QAOA parameters obtained for each problem in the local simulations are the combinations of values used on the real simulations.

Another important mention to say is related to the type of quantum computers used in the real simulations, because the majority of the quantum circuits programs were tested using the quantum computer ibmq_manila, but some simulations were executed on the quantum computer ibmq_santiago, these two quantum computers have different quantum processors and technologies, and these differences help also to analyze the contrast between them.

§.§ Exhaustive Search Simulations

Starting with the ES, all the results for all the problems in the local and real simulations were compiled in the next table.

6|c|[rgb]1,0.714,0.424Exhaustive Search

5c|[rgb]0.867,0.91,0.796ISM for 3 particles

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|[rgb]0.878,0.761,0.804Opt-Loc     1l|[rgb]0.878,0.761,0.804Opt-Real

2p     -2.8496                            -2.64919                          -3.5                             -0.6504                                                              -0.85081

5c|[rgb]0.867,0.91,0.796ISM for 4 particles

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                                                1l|

2p     -4.8044                            -4.0834                           -5.9                             -1.0956                                                              -1.8166

3p     -3.8814                            -1.7432                           -5.9                             -2.0186                                                              -4.1568

5c|[rgb]0.867,0.91,0.796ISM for 5 particles

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                                                1l|

2p     -7.9012                            -3.3192                           -10.9                            -2.9988                                                              -7.5808

3p     -6.7092                            -2.1216                           -10.9                            -4.1908                                                              -8.7784

4p     -8.1286                            -0.2806                           -10.9                            -2.7714                                                              -10.6194

5c|[rgb]1,0.847,0.808Max-Cut for 3 nodes

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                                                1l|

2p     1.658                              1.5499                            2                                0.342                                                                0.4501

5c|[rgb]1,0.847,0.808Max-Cut for 4 nodes

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                                                1l|

2p     2.088                              1.9819                            4                                1.912                                                                2.0181

3p     2.618                              2.312                             4                                1.382                                                                1.688

4p     3.9819                             2.8439                            4                                0.0181                                                               1.1561

5c|[rgb]1,0.847,0.808Max-Cut for 5 nodes

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                                                1l|

2p     3.514                              2.9619                            6                                2.486                                                                3.0381

3p     3.634                              2.608                             6                                2.366                                                                3.392

4p     3.65                               2.636                             6                                2.35                                                                 3.364

Exhaustive Search optimization compilation.

Starting with the Table <ref> description, on the far left column is the type of model used for QAOA, the types can be $2p$, $3p$ or $4p$ each type stands for the number of parameters used in the operators for QAOA, for the case $2p$ it was used one parameter called $\gamma$ for the phase operator and $\beta$ for the mixing operator, for the $3p$ we also have one parameter $\gamma$ but it was used two parameters $\beta_{1}$ and $\beta_{2}$ for the mixing operator, and finally for the $4p$ it was used two phase operators and two mixing operators connected consecutively, the $4p$ case has two $\gamma$ parameters (for each phase operator) and two $\beta$ parameters (for each mixing operator).

Each of the problem's results for the ES method were compiled on the table from before, for every simulation generated it was calculated a value called EEV which stands for Expected Energy Value, this EEV value is very similar to the Expectation Value for the QAOA general implementation, EEV was obtained for the local and real simulations (EEV Local and EEV Real respectively). The main focus of QAOA is two approximate the EEV to the optimum value calculated, the optimum value represents that you can measure the optimal state with $100\%$ probability, if the EEV is near the optimum that tell us the probability to measure the optimal state is greater, and also the probability to measure states near the optimal is greater.

In the last two columns Opt-Loc and Opt-Real is the difference between the local and real results with respect to the optimum result.

§.§ Iterative Local Search Simulations

Now, for the Iterative Local Search (ILS) method, it was used the same table distribution as in the ES method.

6|c|[rgb]1,0.714,0.424Iterative Local Search

5c|[rgb]0.867,0.91,0.796ISM for 3 particles

1c|EEV Local     1c|EEV Real     1c|Optimum     [rgb]0.878,0.761,0.804Opt-Loc     [rgb]0.878,0.761,0.804Opt-Real

2p     -2.9734                            -2.4612                           -3.5                             -0.5266                                         -1.0388

5c|[rgb]0.867,0.91,0.796ISM for 4 particles

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                           1l|

2p     -4.8908                            -4.1362                           -5.9                             -1.0092                                         -1.7638

3p     -4.0956                            -3.3936                           -5.9                             -1.8044                                         -2.5064

4p     -4.7374                            -1.99739                          -5.9                             -1.1626                                         -3.90261

5c|[rgb]0.867,0.91,0.796ISM for 5 particles

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                           1l|

2p     -8.3734                            0.8364                            -10.9                            -2.5266                                         -11.7364

3p     -7.3026                            -0.6258                           -10.9                            -3.5974                                         -10.2742

4p     -7.3473                            0.30479                           -10.9                            -3.5527                                         -11.20479

5c|[rgb]1,0.847,0.808Max-Cut for 3 nodes

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                           1l|

2p     1.716                              1.5049                            2                                0.284                                           0.4951

5c|[rgb]1,0.847,0.808Max-Cut for 4 nodes

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                           1l|

2p     2.144                              1.956                             4                                1.856                                           2.044

3p     2.6919                             2.156                             4                                1.3081                                          1.844

4p     4                                  2.498                             4                                0                                               1.502

5c|[rgb]1,0.847,0.808Max-Cut for 5 nodes

1c|EEV Local     1c|EEV Real     1c|Optimum     1l|                           1l|

2p     3.6879                             2.6859                            6                                2.3121                                          3.3141

3p     3.7499                             2.484                             6                                2.2501                                          3.516

4p     3.758                              2.828                             6                                2.242                                           3.172

Iterative Local Search optimization compilation.

The Table <ref> has all the values from the simulations of the problems for ISM and Max-Cut using ILS in local and real experiments, the only difference with ES table is that for the ISM $4$ particles problem it was also simulated using $4p$ model of QAOA.

§.§ Comparative average results for the classical optimization methods

Using the results of the Tables <ref> and <ref> two comparative tables were made. The first table has the average values for the Exhaustive Search optimization method.

2|c|[rgb]1,0.714,0.424Exhaustive Search

Average Opt-Loc                  Average Opt-Real

[rgb]0.867,0.91,0.796 ISM      ISM

-2.2876                 -5.63

[rgb]1,0.847,0.808 Max-Cut     Max-Cut

1.55                    2.16

Average comparative results for ES.

Now, the next table shows the average results for the ILS method.

2|c|[rgb]1,0.714,0.424Iterative Local Search

Average Opt-Loc                  Average Opt-Real

[rgb]0.867,0.91,0.796 ISM      ISM

-2.03                   -6.06

[rgb]1,0.847,0.808 Max-Cut     Max-Cut

1.46                    2.27

Average comparative results for ILS.

Analyzing both Tables <ref> and <ref> it can be seen that the ILS heuristic presents better average results for the local simulations for both ISM and Max-Cut class of problems. It is curious to see that the results for the real simulations are better with ES approach, but due to the different factors that can alter the real simulations, in this work we are going to keep the ILS as a better method to be applied with QAOA. And if the complexity analysis of both classical optimization methods is taken into account, ILS still has the lead over the ES method. In all the simulations developed (local and real) the values generated for the parameters (for $2p$, $3p$ and $4p$ models) were better with ILS but when some values from ILS are implemented in the quantum computer, due to their precision (how specific is the value of that parameter), it makes harder for the quantum computer to replicate the exact quantum gate using the specific value of rotation, and that could be one of the reasons why the ES values perform better (from the experimental results) in the real simulations.

With respect to the Tables <ref> and <ref> from the compilation results, another interesting result can be discussed, this results is shown in relation between the real and local simulations using the different QAOA models ($2p$, $3p$ or $4p$) because in the case of the local simulations with the increase of the parameters in the QAOA model most of the time the response of the algorithm was improved (the value of EEV got closer to the optimum) however for the real simulations the results usually got worst with more parameters, and these phenomena can also be seen in the Tables <ref> and <ref> where all the average values for both ES and ILS were worst in the case of the real simulations. These two results show the state of NISQ computers compared to the ideal results (from local simulations), the actual NISQ devices still have a lot of problems with noise and decoherence, and when the number of quantum gates or qubits increase, the noise and decoherence also increases, and even when in real simulations it was used the best values for the parameters of QAOA, the local results were much better than the real simulations results.

The final result obtained is from the compilation tables for ES and ILS, because the majority of the results from the Max-Cut problems were closer (even the real simulation results) to the optimum. With this in mind, it can be said that the Max-Cut problems perform better with QAOA, one important factor in contrast from Max-Cut to ISM is that Max-Cut has at least two optimal states (and since QAOA is an approximation algorithm) it makes it easier for QAOA to find one or more solutions in all the search space that are approximated to the optimum, instead of ISM where QAOA needs to find only one solution.

§ CONCLUSION

The first conclusion established from all the simulations developed in this paper is related to the classical optimization method, Iterative Local Search showed that is a better optimization heuristic to be implemented with QAOA for the ISM and Max-Cut problems. However, for the quantum circuits in the real simulations it is harder to implement the exact values obtained from ILS in the quantum gates, and in the actual state of the quantum computers, it can alter the parameter values and consequently the results may vary from the ideal expected results.

Another important conclusion, is in relation to the state of NISQ computers, these devices still have noise and decoherence problems, the experiments exhibited the difference between the local simulations that use ideal conditions to calculate the quantum circuits phenomena and the real simulations which are affected by the imprecision of today's devices. The greatest number of errors among the results generated were when there were models with more number of quantum gates and higher number of qubits.

The last conclusion, represents the difference between the types of problems that work better with QAOA. The results for Max-Cut problems were better than ISM problems, it can be said that is easier for QAOA to approximate the EEV to the optimum for those problems because QAOA is an approximation optimization algorithm and allowing QAOA to be able to find more than one solution in a search space is simpler than finding only one optimum (like in ISM). Also, as it was mentioned, the Max-Cut problem translation to a quantum circuit needs less quantum gates and this allows, in the case of the real simulations, to maintain a lower number of quantum gates compared with the ISM problems which translates into a response that is closer to the optimum.

§ ACKNOWLEDGMENT

Thanks to Universidad Autónoma Metropolitana (Unidad Azcapotzalco), for the education given for the development of this article.

Thanks to Fis. José de Jesús Cruz Guzmán and Professor Zbigniew Oziewicz for the initiation of the quantum computing paradigm and all the priceless talks in different areas of physics and mathematics.

Thanks to Dr. Alvaro Salas Brito for the mentorship on my master's degree thesis, and also for teaching the quantum computing fundamentals, which helped in the development of this paper.

And, thanks Dr. Roman Anselmo Mora Gutierrez for the guidance on my master's degree, helping to understand the basics of heuristics and combinatorial optimization problems.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitlearXiv e-prints
titleQuantum algorithm implementations for beginners

booktitle40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039)
titleOn universal and fault-tolerant quantum computing: a novel basis and a new constructive proof of universality for Shor's basis

booktitleProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
titleOptimizing quantum optimization algorithms via faster quantum gradient computation

journaltitlePhysical Review Letters
titleLow-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms

titleQuantum Computing: An Applied Approach

journaltitlePhysical Review E
titleSimulating Ising spin glasses on a quantum computer

journaltitlearXiv preprint arXiv:2106.02812
titleOptimizing Ansatz Design in QAOA for Max-cut

Cambridge University Press

titleQuantum Computation and Quantum Information

titleMathematics of Quantum Computing

booktitle2019 tenth international green and sustainable computing conference (IGSC)
titleEvaluating quantum approximate optimization algorithm: A case study

booktitle2019 IEEE High Performance Extreme Computing Conference (HPEC)
titleMultistart methods for quantum approximate optimization

titleQAOA: Quantum Approximate Optimization Algorithm

journaltitlearXiv preprint arXiv:1712.05304
titleA quantum algorithm to train neural networks using low-depth circuits

booktitleAPS March Meeting Abstracts
titleQAOA Performance Benchmarks using Max-Cut

journaltitleBulletin of the American Physical Society
titleStochastic Gradient Descent for Hybrid Quantum-Classical Optimization

Academic Press

titleQuantum machine learning: what quantum computing means to data mining

booktitleMathematical and Scientific Machine Learning
titlePolicy gradient based quantum approximate optimization algorithm