Transformer-based models, such as BERT and ViT, have achieved state-of-the-art results across different natural language processing (NLP) and computer vision (CV) tasks. However, these models are extremely memory intensive during their fine-tuning process, making them difficult to deploy on GPUs with limited memory resources. To address this issue, we introduce a new tool called SlimFit that reduces the memory requirements of these models by dynamically analyzing their training dynamics and freezing less-contributory layers during fine-tuning. The layers to freeze are chosen using a runtime inter-layer scheduling algorithm. SlimFit adopts quantization and pruning for particular layers to balance the load of dynamic activations and to minimize the memory footprint of static activations, where static activations refer to those that cannot be discarded regardless of freezing. This allows SlimFit to freeze up to $95\%$ of layers and reduce the overall on-device GPU memory usage of transformer-based models such as ViT and BERT by an average of $2.2\times$, across different NLP and CV benchmarks/datasets such as GLUE, SQuAD 2.0, CIFAR-10, CIFAR-100 and ImageNet with an average degradation of $0.2\%$ in accuracy. For such NLP and CV tasks, SlimFit can reduce up to $3.1\times$ the total on-device memory usage with an accuracy degradation of only up to $0.4\%$. As a result, while fine-tuning of ViT on ImageNet and BERT on SQuAD 2.0 with a batch size of 128 requires 3 and 2 32GB GPUs respectively, SlimFit enables their fine-tuning on a single 32GB GPU without any significant accuracy degradation. The code of this paper is available at <https://github.com/arashardakani/SlimFit>.

§ INTRODUCTION

Over the past few years, various transformer-based models have been developed with the adoption of the attention mechanism that weighs the importance of each part of the input data differently. Pre-training of such transformer-based models on large data has led to a significant boost in accuracy when fine-tuned on various natural language processing (NLP) and computer vision (CV) downstream tasks [1, 2]. Despite their great performance in achieving state-of-the-art (SOTA) accuracy, these models are memory intensive and require a considerably large amount of on-device GPU memory during their fine-tuning phase when compared to the conventional convolutional and recurrent neural networks [3]. The memory requirement of current transformer-based models has made them difficult to fine-tune even on powerful GPUs. With the introduction of larger transformer-based models over the past few years, the on-device GPU memory has become a major bottleneck for their fine-tuning process [3, 4, 5].

The total on-device memory usage of GPUs consists primarily of activations, parameters, gradients, optimizer states, and the CUDA context. Among these factors, activations account for most of the memory usage due to batching, which makes them several orders of magnitude larger than other factors (see Fig. <ref>). Therefore, activation compressed training (ACT) has emerged as the primary solution for memory-efficient fine-tuning [6, 4]. This approach first compresses activations during the forward pass and then decompresses them during the backward pass. In this way, the memory footprint can be

The breakdown of memory usage of BERT when fine-tuned on different batch sizes including 32, 64, and 128.

significantly reduced by caching the compressed activations. In ACT, quantization [7, 8, 6, 4] has been a popular choice to compress activations among other compressors such as JPEG [9] or pruning [5]. The current SOTA ACT adaptively assigns quantization bits to each layer for a given architecture [4]. While the SOTA ACT successfully reduces the memory footprint of activations, its overall on-device GPU memory reduction is not significant. For instance, the total on-device GPU memory reduction of the SOTA ACT is limited to 0.1GB despite its $6.4\times$ reduction in the memory of activations when fine-tuning BERT on CoLA dataset with a batch size of 32. It is worth mentioning that we refer to the memory usage reported by “nvidia-smi” as the overall on-device memory in this paper (see Appendix <ref> for more information on memory management).

Tensor rematerialization [3, 10, 11, 12], also known as gradient checkpointing, is another prominent approach to reducing activation memory by trading computations for memory. In tensor rematerialization, only specific activations are stored during the forward pass, while the rest are recomputed in the backward pass. Of course, recomputing activations requires more operations and significantly prolongs the fine-tuning process [4]. Reduced precision training, as another approach, performs the computations of both forward and backward passes in low-precision [13, 14, 15, 16]. While these works can successfully train conventional models, few-bit model fine-tuning is not trivial. For instance, 8-bit quantization of BERT for inference results in a significant precision loss [17], which makes fine-tuning on few bits a challenging task.

Low-rank adaptation (LoRA) [18] is another key approach to reducing the overall on-device GPU memory where the transformer-based models are fine-tuned by inserting a small number of trainable parameters into each layer while keeping the pre-trained model parameters frozen. Such an approach enables fine-tuning transformer-based models with significantly less number of trainable parameters, leading to a reduction in the memory footprint of optimizer states and gradients. Such a memory reduction becomes significant for extremely large transformer models such as GPT [19] with over hundred billion parameters.

Different from these methods, we put forward a new approach to reducing the overall on-device memory usage by analyzing training dynamics. More precisely, we dynamically analyze the gradient contributions of layers in transformer-based models and perform parameter updates for specific layers only while the rest of layers are kept frozen. Training dynamics have been used to analyze the behavior of a model during its training/fine-tuning process [20, 21, 22]. However, our work uses training dynamics to detect and discard unimportant activations during fine-tuning by freezing their associated layers, leading to a reduction of the memory footprint. Our method is orthogonal to existing approaches including rematerialization and LoRA, which could be composed for further reductions.

Freezing layers or parameters has been studied in different domains, including transformer-based models to preserve previously learned information during fine-tuning [23]. Freezing parameters have also been used to regularize fine-tuning (e.g., over-fitting reduction) in pre-trained models [24]. Recently, freezing has been used to accelerate fine-tuning by progressively freezing model blocks [25, 26, 27]. However, since such an approach starts the fine-tuning process without freezing at least for a few training iterations, its overall on-device memory requirement remains similar to that of training without freezing. For instance, fine-tuning ViT on ImageNet with a batch size of 128 using such a freezing approach on a single 32GB GPU results in an out-of-memory error (see Appendix <ref> for more details).

To orchestrate effective layer-freezing decisions, we introduce a runtime inter-layer scheduling (ILS) algorithm. Our method finds and freezes a set of layers in transformer-based models that are less contributory, i.e., layers with fewer updates in their parameters, to the fine-tuning process at each iteration. While the ILS algorithm successfully detects and freezes unimportant layers, its memory reduction is not proportional to the freezing rate. The reason behind this disproportionality is twofold: the imbalanced number of activations among layers and the existence of static activations. Static activations refer to those that cannot be discarded regardless of freezing (e.g., activations of non-linear functions such as GELU). We address these two issues using quantization and pruning to even out the number of activations across all layers and to reduce the memory overhead of static activations. We use quantization and pruning for a few specific layers of transformer-based models as opposed to reduced precision training methods where all the layers are quantized. As a result, the impact of quantization and pruning on accuracy is insignificant in our work. For instance, the accuracy degradation due to quantization and pruning is only $0.1\%$ on the MRPC dataset.

By combining ILS with quantization and pruning, we introduce a performance tool called SlimFit for reducing the on-device GPU memory usage of transformer-based models during fine-tuning. We demonstrate the effectiveness of SlimFit in reducing the memory footprint on popular models of BERT and ViT. We show that SlimFit can freeze up to $95\%$ of layers and reduce the overall on-device memory usage by an average of $2.2\times$ when fine-tuning BERT and ViT models on different benchmarks and datasets, such as GLUE, SQuAD 2.0, CIFAR-10, CIFAR-100 and ImageNet with an average accuracy degradation of $0.2\%$. More precisely, SlimFit reduces the overall on-device memory usage of the fine-tuning process on GLUE from 6.1GB to 4.0GB ($1.5\times$ reduction) with a batch size of 32, on SQuAD 2.0 from 58.5GB to 19.1GB ($3.1\times$ reduction) with a batch size of 128, on CIFAR-10 from 7.2GB to 4.3GB ($1.7\times$ reduction) with a batch size of 32, on CIFAR-100 from 7.2GB to 4.5GB ($1.6\times$ reduction) with a batch size of 32, and on ImageNet from 77.4GB to 26.1GB ($3.0\times$) with a batch size of 128 at the cost of up to $0.4\%$ accuracy degradation. As a result, SlimFit enables performing memory-intensive fine-tuning processes on a single 32GB GPU such as fine-tuning ViT on ImageNet with a batch size of 128 while this  normally requires three 32GB GPUs.

§ PRELIMINARIES

Over the past few years, pre-training of attention-based models has led to significant advances on many NLP and CV tasks with the popular BERT [1] and ViT [2] models. The pre-training process provides a good initialization point such that these models can better generalize on unseen data of downstream tasks. Therefore, these models can achieve state-of-the-art results by fine-tuning through small adjustments to their parameters.

Architecturally, these models consist of an initial embedding layer, followed by repeated blocks of multi-head attention (MHA) fed into a feed-forward network (FFN) module (see Appendix <ref> for more details). The base architectures of BERT and ViT contain over a hundred layers built up in this manner.

Despite the large number of layers, not all need to be updated during fine-tuning to achieve decent performance on downstream tasks, as shown in [28]. Notably, the authors found that freezing approximately $60\%$ of early attention layers in BERT led to negligible performance degradation. This suggests that the fine-tuned model tends to preserve generic features learned during pre-training. Motivated by this study, we seek to analyze the training dynamics of pre-trained models and to automatically detect layers with less contributions to the fine-tuning process.

§ LEARNING THE IMPORTANCE OF LAYERS

Training dynamics is an active field of research that provides insight about the behavior of pre-trained models when fine-tuning on downstream tasks. The convergence proof of optimization algorithms such as stochastic gradient descent [29] shows that the distance between the parameters and the optimal solution is reduced over training iterations and accordingly, the weight distance (or the weight update amount) between consecutive iterations decreases. Therefore, it is possible that some layers can only receive minimal changes to their parameters as we approach the end of the training process. Of course, detecting and freezing such layers, when they show minimal updates, will not affect accuracy. Since transformer-based models are pre-trained, they already show small updates during fine-tuning compared to pre-training. As such, detecting and freezing layers with minimal updates (i.e., weight distance values) will not significantly affect the fine-tuning process and accordingly the final accuracy. Based on the above observations, we consider the $\ell_1$-norm of the update received by parameters of each layer through all the fine-tuning iterations as the training dynamics in this paper. It is also worth mentioning that freezing layers has no impact on training convergence as it causes a pause in the training procedure of frozen layers as shown by our theoretical analysis in Appendix <ref>.

§.§ Training Dynamics

Let us consider a pre-trained model with a set of parameters $\mathbf{W}$ where the parameters associated with the $i$th layer at iteration $t$ is denoted as $\mathbf{W}_i^t \in \mathbb{R}^{M \times I}$. The training dynamics of for the $i$th layer at iteration $t$ is defined as the $\ell_1$-norm of the distance between $\mathbf{W}_i^{t-1}$ and $\mathbf{W}_i^{t}$, i.e.,

\begin{equation}
d_i^t = \dfrac{1}{M \times I}\left\lVert\dfrac{W_i^{t} - W_i^{t-1}}{W_i^{t-1}} \right\rVert_{\ell_1},
\label{TD}
\end{equation}

where $\mathbf{d}^t \in \mathbb{R}_+^n$ containing all $d_i$s at iteration $t$ is referred to as distance vector, and $n$ denotes the total number of layers. In fact, Eq. (<ref>) calculates the normalized change in the parameters of the $i$th layer.

width=10cm, height = 5.5cm

The distance values of query weight matrix for the first, fifth and eleventh attention layers of BERT-base fine-tuned on (a) CoLA  and (b) MRPC datasets for 3 epochs.

§.§ Inter-Layer Scheduling Algorithm

We use the distance values as training dynamics to analyze the fine-tuning behavior of pre-trained models. For instance, consider the distance values across all the fine-tuning iterations for the CoLA [30] and MRPC [31] datasets. Fig. <ref> shows the distance values of the query weight matrix for the first, fifth and eleventh attention layers of BERT-base fine-tuned on CoLA dataset whereas Fig. <ref> depicts those of the same layers for BERT-based fine-tuned on MRPC dataset.

The overview of ILS algorithm. ILS freezes a certain number of layers depending on the freezing rate at every single iteration throughout the fine-tuning process for the total of $n$ training iterations.

We observe the following based on the experimental results of these two datasets. First, the updated amount for each layer becomes smaller over fine-tuning iterations. Second, the updated amount of each layer is task-specific and is independent of its position. Third, there are some layers showing smaller distance values w.r.t. other layers across almost all the iterations.

Finally, layers with a higher distance value in the beginning can become smaller over the fine-tuning iterations than layers starting with a lower distance value.

Given the above observations, we introduce an ILS algorithm to decide on updating priority of layers using their distance values. Fig. <ref> shows the overview of the ILS algorithm. At each iteration ranging from the first iteration to the last iteration, our ILS algorithm selects those layers with large distance values to be updated and those with small distance values to be frozen. More precisely, layers are first ranked based on their distance values at each training iteration and then those with small distance values are kept frozen according to the freezing rate as a hyper-parameter. The intuition is that layers with small distance values are less contributory to the fine-tuning process as their parameters are not being updated much. On the other hand, the layers with large distance values are learning task-specific patterns by making more significant adjustments to their parameters. Note that freezing middle layers does not interrupt the gradient propagation to the early layers of the network as shown through an example in Appendix <ref>.

The freezing rate of the ILS algorithm can be decided based on the on-device GPU memory budget. Of course, using an extremely high freezing rate may result in a performance degradation depending

figureAn example of the iterative freezing process using our ILS algorithm.

The pseudo code of the ILS algorithm performing iterative freezing.

Input: model, number of iterations as $itr$, number of layers as $L$, freezing rate $F$

$d$ = rand($L$)

$i$ in $itr$

$idx$ = argsort($d$)[:int(L*F)]

$j$ in $idx$

model.layer[$j$].requires_grad = False

Update $d$

on the downstream task, providing a worthwhile trade-off between accuracy and on-device GPU memory. On the other hand, while performance degradation is unlikely with a very small freezing rate, the memory reduction is insignificant as well.

Since there is no prior knowledge about the distance values of each layer at the beginning of the fine-tuning process, our ILS algorithm initializes the distance vector with large random values. Depending on the freezing rate, each layer along with its distance value are updated during the first few iterations once until all random numbers in the distance vector are substituted with an actual distance value. Afterwards, layers are kept frozen according to their actual distance value. The distance value of the active layers is only updated at each iteration while that of the frozen layers remains unchanged. The pseudo code of our ILS algorithm performing iterative freezing is shown in Algorithm <ref>.

To better understand the ILS algorithm, we illustrate the iterative freezing process using an example as shown in Fig. <ref>. Suppose we have an 8-layer transformer-based model and accordingly an 8-element distance vector at iteration $t$. Considering the freezing rate of $50\%$ for this example, 4 layers with the lowest distance values are kept frozen and the rest are updated at each iteration.

§ INTER-LAYER LOAD-BALANCING

So far, we have introduced our ILS algorithm that prioritizes updating particular layers while keeping the rest of layers frozen according to their distance value. For the given freezing rate of $50\%$ as an example, we expect to see a $2\times$ reduction in the memory footprint of activations. However, this is not the case in transformer-based models due to the imbalanced the number of activations across all the layers. In fact, the imbalance in the number of activations undermines the ability of our ILS algorithm in reducing the memory footprint during the fine-tuning as shown in Fig. <ref>.

Since the focus of this paper is on transformer-based models such as BERT and ViT, we analyze their architecture for imbalanced layers. Table <ref> summarizes the number of activations associated to the input of layers with trainable parameters in BERT or ViT. Among all trainable layers, there is only one imbalanced layer in the attention block which contains $4\times$ more activations than other layers.

To address the load-balancing issue in the number of activations for the aforementioned layer, we use quantization. Since the imbalance factor among layers is $4\times$,

we adopt 8-bit quantization for activations of the imbalanced layer where 4 bits are used for both the integer and fractional parts. In this way, the memory cost of the activations are evened out using quantization. In our quantization scheme, we cache the activations of the imbalanced layer using 8 bits during the forward pass. In the backward pass, we convert the 8-bit activations to 32-bit floating-point format. Therefore, all the forward and backward computations are still performed using single-precision floating-point format. The conversion process between 8-bit fixed-point and 32-bit floating-point formats are provided in Appendix <ref>.

§ DYNAMIC AND STATIC ACTIVATIONS

The type of activations in transformer-based models can be divided into two categories: dynamic and static. We refer to the activations that can be discarded by freezing their layer as dynamic activations. On the other hand, static activations cannot be discarded regardless of freezing. Among different

figureAn example of a model with imbalanced number of activations and its impact on the memory reduction.

tableThe number of activations associated to the input of layers with trainable parameters in BERT where $B$, $T$, $H$ denote the batch size, sequence length, hidden size, respectively. ViT has the same structure with different descriptions.

types of layers, GELU, MatMul, Softmax and LayerNorm contain static activations as shown Table <ref>. Note that MatMul and Softmax share the same activations. For the backward computations of Softmax, its output during the forward pass is saved as its activations. On the other hand, the input to MatMul is required for its backward computations as activations. Since the output of Softmax is an input to MatMul in the forward pass, they share the same activations.

GELU and MatMul/Softmax do not have any trainable parameters and accordingly cannot be frozen. Therefore, these two layers hold on to their activations throughout the fine-tuning process. The best approach to reduce their memory cost is quantization. We use 4 and 8 bits for quantization of activations in GELU and MatMul/Softmax, respectively. Since there is no 4-bit tensor support in PyTorch, we store each two 4-bit activations as a single 8-bit activations using shift operations. Note that using such bit-levels result in a negligible accuracy degradation while further quantization of those activations incurs a significant accuracy loss.

The type of activations of layers in MHA and FFN of BERT and ViT.

As opposed to GELU and MatMul/Softmax, LayerNorm contains trainable parameters and can be frozen by the ILS algorithm. However, its activations are still static. The forward pass of LayerNorm is computed by:

\begin{equation} %\vspace{-0.2cm}
\widetilde{\mathbf{x}} = \dfrac{\textbf{x} - \mathbb{E}(\textbf{x})}{\sqrt{\text{Var}(\textbf{x}) + \epsilon}},
\end{equation}

\begin{equation}
\textbf{y} = \widetilde{\mathbf{x}} * \mathbf{\gamma} + \mathbf{\beta},
\end{equation}

where $\gamma$ and $\beta$ are trainable parameters. The input and output to LayerNorm are denoted by $\textbf{x} \in \mathbb{R}^H$ and $\textbf{y}\in \mathbb{R}^H$, respectively. $\mathbb{E}(\cdot)$ and $\text{Var}(\cdot)$ compute the average and variance, respectively. The derivative of the loss with respect to $\gamma$ (i.e., $\widehat{\gamma}$) is computed by

\begin{equation}
\widehat{\gamma} = \widetilde{\mathbf{x}} * \widehat{\mathbf{y}},
\label{LNP} \vspace{-0.2cm}
\end{equation}

and with respect to $\beta$ (i.e., $\widehat{\beta}$) by:

\begin{equation}
\widehat{\beta} = \widehat{\mathbf{y}},
\end{equation}

where $\widehat{\mathbf{y}}$ denotes the derivative of the loss w.r.t. $y$. We also need to compute the derivative of the loss with respect to $\textbf{x}$ (i.e., $\widehat{\mathbf{x}}$) as:

\begin{equation}
\textbf{g} = \dfrac{\gamma * \widehat{\mathbf{y}}}{H * \sqrt{\text{Var}(\textbf{x}) + \epsilon}},
\end{equation}

\begin{equation}
\widehat{\mathbf{x}} = H * \textbf{g} - \sum_H \textbf{g} - \widetilde{\mathbf{x}} * \sum_H (\textbf{g} * \widetilde{\mathbf{x}}).
\label{LNI}
\end{equation}

When LayerNorm is frozen, there is no need to compute Eq. (<ref>). However, the activations of this layer cannot be discarded since they are still a part of the computations in Eq. (<ref>). More precisely, the standardized version of $\textbf{x}$ (i.e., $\widetilde{\mathbf{x}}$) is required even when this layer is frozen.

The contribution of the last term in Eq. (<ref>) (i.e., $\sum_H (\textbf{g} * \widetilde{\mathbf{x}})$) is significant for large values of $\widetilde{\mathbf{x}}$ only. Therefore, the small values of $\widetilde{\mathbf{x}}$ can be discarded. Ideally, we want to have all the activations of this layer to be discarded when this layer is frozen. However, this will results in an accuracy degradation. As such, we prune away the small values in $\widetilde{\mathbf{x}}$ and keep the top $10\%$ largest values. In this way, the memory load of activations is significantly reduced. Of course, when this layer is not frozen, the backpropagation is performed without any approximation. Such a trick converts LayerNorm from a static layer to a semi-static one. It is worth mentioning that the indices to pruned activations are also stored along with activations. The details of the pruning procedure is provided in Appendix <ref>.

§ SLIMFIT

SlimFit is a performance tool that exploits our ILS algorithm along with quantization and pruning to reduce the memory footprint of activations through an iterative freezing process. The total on-device GPU memory reduction of SlimFit is a result of the memory reduction in both dynamic and static activations. Static activations contribute a fixed amount of memory whereas the memory usage of dynamic activations depends on the freezing rate. Given a high freezing rate, the memory footprint of activations and accordingly the total on-device GPU memory usage can be significantly reduced. The choice of freezing rate depends on the memory budget of the user. By increasing the freezing rate up to a certain point, there will be no performance degradation. However, using an extremely high freezing rate trades off memory for accuracy. Finding the breaking point of the method is task dependent and varies from one dataset to another.

§ EXPERIMENTAL RESULTS

We use the base version of BERT and ViT for our experiments. We fine-tune these two models using SlimFit which is implemented on PyTorch. We evaluate BERT [1] using the GLUE benchmark [31] and SQuAD 2.0 [32]. For ViT [2], we use CIFAR-10, CIFAR-100 and ImageNet datasets [33, 34] for evaluation purposes. We discuss the memory usage of activations and the overall on-device GPU memory on the 32GB NVIDIA V100 GPU. We report the total on-device GPU memory usage using “nvidia-smi”. For all the experiments in this section, we use $3$ epochs for fine-tuning. The details about the CV/NLP tasks, measurements and hyper-parameter settings are provided in Appendix <ref>.

§.§ Accuracy Evaluation on GLUE and SQuAD 2.0

To evaluate the language understanding ability of BERT models, the GLUE benchmark is formed by a series of downstream tasks including sentiment classification (SST-2), natural language inference (RTE, QNLI, and MNLI), paraphrase detection (MRPC, QQP, and STS-B), and linguistic acceptability (CoLA). We use Spearman correlation for STS-B, Matthew's correlation for CoLA, percentage accuracy for RTE, MRPC, SST-2, QQP, QNLI and MNLI$_{m }$, and F1 score for SQuAD 2.0. In this work, we fine-tune the BERT-base model using SlimFit on the downstream tasks of the GLUE benchmark as well as the question answering task on SQuAD 2.0. Table <ref> shows the accuracy on the validation set of the aforementioned tasks and memory usage of SlimFit compared to the baseline. The results of the baseline were obtained without freezing. We report the results associated with the highest freezing rate that can achieve a similar accuracy to that of the baseline by varying the learning rate. The experimental results on the GLUE benchmark show that up to $95\%$ of dynamic activations can be discarded with up to $0.4\%$ accuracy degradation, leading to an average of 1.9GB reduction in the total on-device GPU memory usage. On the other hand, while fine-tuning SQuAD 2.0 without freezing requires the minimum of 2 32GB NVIDIA V100 GPUs on a batch size of 128, SlimFit enables its fine-tuning on a single 32GB NVIDIA V100 GPU, reducing the total on-device memory requirement of such a task from 58.5GB down to 19.1GB ($3.1\times$ reduction).

The accuracy and memory performance of SlimFit on the GLUE benchmark and SQuAD 2.0. The batch size of $32$ and $128$ were used for GLUE benchmark and SQuAD 2.0, respectively.

The total on-device GPU memory usage of SlimFit compared to the baseline across different batch sizes including 32, 64 and 128 on NLP and CV datasets.

Figure <ref> shows the total on-device GPU memory usage of BERT when fine-tuned using SlimFit for different batch sizes at the freezing rate of $95\%$ on the GLUE benchmark and $80\%$ on SQuAD 2.0. According to the experimental results, SlimFit enables a reduction ranging from $1.5\times$ to $3.1\times$ in the total on-device GPU memory on NLP tasks. The reduction in the total on-device memory usage is more significant for larger batch sizes since the activations dominate the memory footprint.

§.§ Accuracy Evaluation on CIFAR and ImageNet

To assess the effectiveness of our method on CV tasks, we fine-tune the ViT-base model on CIFAR-10, CIFAR-100 and ImageNet datasets. We use the test set of CIFAR-10/CIFAR-100 and the validation set of ImageNet to evaluate their accuracy on ViT. Table <ref> shows that SlimFit can fine-tune the ViT-base model with the freezing rate of up to $95\%$ with up to $0.3\%$ loss in accuracy while significantly reducing the overall on-device GPU memory usage. More specifically, SlimFit reduces the overall memory usage of the fine-tuning process on CIFAR-10 from 7.2GB to 4.3GB ($1.7\times$ reduction) with a batch size of 32, on CIFAR-100 from 7.2GB to 4.5GB ($1.6\times$ reduction) with a batch size of 32, and on ImageNet from 77.4GB to 26.1GB ($3\times$ reduction) with a batch size of 128. Fig. <ref> also shows the total on-device GPU memory usage of SlimFit across different batch sizes on CV tasks.

The top-1 accuracy and memory performance of SlimFit on CV benchmarks using a batch size of $32$ for CIFAR datasets and $128$ for ImageNet dataset.

§ ABLATION STUDIES

In this section, we study different aspects of SlimFit in fine-tuning of transformer-based models through a series of ablation studies. Due to limited space, we discuss the impact of quantization/pruning and total wall-clock time in Appendix <ref> and Appendix <ref>, respectively. For all the experiments in this section, we use a batch size of 32 and $3$ epochs for fine-tuning.

The trade-off curve between accuracy and freezing rate for three different iterative freezing approaches (i.e., ILS, random and progressive methods) on (a) CoLA  and (b) MRPC datasets.

§.§ Accuracy vs Freezing Rate

In Section (<ref>), we discussed that our ILS algorithm orchestrates the freezing schedule based on a simple rule: layers with largest distance values are updated whereas those with lowest distance values are kept frozen for the given freezing rate. Of course, such an iterative freezing approach trades off between accuracy and freezing rate. To better show this trade-off, we measured and illustrated accuracy of CoLA and MRPC datasets across different freezing rates in Fig. <ref>.
The trade-off curve shows our ILS algorithm can maintain the accuracy at the same level of the baseline by freezing up to $95\%$ of layers.

Besides our ILS algorithm, the freezing schedule can be decided using random or progressive freezing approaches. In the random scheduling method, frozen layers are randomly selected at each iteration. In the progressive approach, on the other hand, early layers are progressively kept frozen whereas later layers are being updated throughout the fine-tuning process. Among these approaches, our ILS algorithm significantly stands out in terms of both accuracy and freezing rate as shown in Fig. <ref>. The

The frequency of update occurrence for each layer as a heatmap on (a) CoLA  and (b) MRPC datasets. The description of layers corresponding the indices are provided in Appendix <ref>.

reason behind its superior performance is that ILS allows more updates for layers with large distance values by keeping layers with minimal distance values frozen for a specific number of iterations. On the other hand, in the random approach, the layers are randomly selected to be updated. Therefore, layers with large distance values receive less number of updates in the random approach compared to ILS. Of course, the chance of layers with large distance values being randomly selected as active layers decreases as the freezing rate increases, which explains the accuracy gap between ILS and the random approach with freezing rate higher than 70% freezing rate. In the progressive freezing approach, the early layers receive no update during the fine-tuning process, resulting in a significant accuracy degradation for large freezing rates.

§.§ Frequency of Update Occurrence

To visualize the frequency of update occurrence for each layer, we use a heatmap as shown in Fig. <ref> for both CoLA and MRPC datasets where larger counts are associated with darker colorings. As shown in the heatmap, the dense layers inside the MHA module receive more updates than other layers for both datasets. Moreover, the update patterns of these datasets are similar for small freezing rates whereas they become more task-specific for high freezing rates. In fact, the ILS algorithm prioritizes the update of some specific layers over others for high freezing rates.

§ COMPARISON WITH STATE-OF-THE-ART TECHNIQUES AND LIMITATIONS

Next, we compare SlimFit with state-of-the-art compression methods targeting memory reduction, i.e., GACT [4] and DropIT [5]. Table <ref> summarizes the comparison results in terms of accuracy, memory and latency. For fair comparison, we measure their performance under the same framework and hyper-parameters (i.e., the batch size and the number of training epochs) during fine-tuning of BERT on CoLA. The experimental results of GACT and DropIT were obtained using their official PyTorch libraries. According to the experimental results, GACT shows the lowest memory amount for activations. However, in terms of on-device GPU memory usage, SlimFit outperforms GACT. In terms of accuracy, all models show a comparable accuracy on CoLA w.r.t. the baseline. Finally, in terms of speed, SlimFit shows the fastest fine-tuning speed among existing works while it still falls short w.r.t. the baseline (see Appendix <ref> for more details on SlimFit's computing speed). Despite the better accuracy of SlimFit on CoLA, it shows up to $0.4\%$ degradation in accuracy across different CV/NLP tasks which is another limitation of SlimFit besides its fine-tuning speed w.r.t. the baseline.

Comparison with state-of-the-arts when fine-tuning BERT on CoLA dataset.

§ CONCLUSION

In this paper, we presented a performance tool called SlimFit that reduces the memory usage of activations and accordingly the overall on-device GPU memory usage of transformer-based models through an iterative freezing of layers during fine-tuning. SlimFit adopts an inter-layer scheduling method to orchestrate the freezing schedule at each iteration. To balance the number of activations across all layers and to reduce the memory usage of static activations, SlimFit uses quantization and pruning for a few specific layers. We evaluated the performance of SlimFit across different NLP and CV tasks. We showed that SlimFit significantly reduces the on-device GPU memory usage of the fine-tuning process by up to $3.1\times$ when using a batch size of $128$.

[1]
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep
bidirectional transformers for language understanding,” 2018, cite
arxiv:1810.04805Comment: 13 pages. [Online]. Available:

[2]
A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai,
T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit,
and N. Houlsby, “An image is worth 16x16 words: Transformers for image
recognition at scale,” in International Conference on Learning
Representations, 2021. [Online]. Available:

[3]
P. Jain, A. Jain, A. Nrusimha, A. Gholami, P. Abbeel, J. Gonzalez, K. Keutzer,
and I. Stoica, “Checkmate: Breaking the memory wall with optimal tensor
rematerialization,” in Proceedings of Machine Learning and Systems,
I. Dhillon, D. Papailiopoulos, and V. Sze, Eds., vol. 2, 2020, pp. 497–511.
[Online]. Available:

[4]
X. Liu, L. Zheng, D. Wang, Y. Cen, W. Chen, X. Han, J. Chen, Z. Liu, J. Tang,
J. Gonzalez, M. Mahoney, and A. Cheung, “GACT: Activation compressed
training for generic network architectures,” in Proceedings of the
39th International Conference on Machine Learning, ser. Proceedings of
Machine Learning Research, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari,
G. Niu, and S. Sabato, Eds., vol. 162.1em plus 0.5em minus 0.4emPMLR, 17–23 Jul 2022, pp. 14 139–14 152. [Online]. Available:

[5]
J. Chen, K. Xu, Y. Wang, Y. Cheng, and A. Yao, “DropIT: Dropping
intermediate tensors for memory-efficient DNN training,” in The
Eleventh International Conference on Learning Representations, 2023.
[Online]. Available: <https://openreview.net/forum?id=Kn6i2BZW69w>

[6]
J. Chen, L. Zheng, Z. Yao, D. Wang, I. Stoica, M. Mahoney, and J. Gonzalez,
“Actnn: Reducing training memory footprint via 2-bit activation compressed
training,” in International Conference on Machine Learning.1em
plus 0.5em minus 0.4emPMLR, 2021, pp. 1803–1813.

[7]
A. Chakrabarti and B. Moseley, “Backprop with approximate activations for
memory-efficient network training,” 2019. [Online]. Available:

[8]
F. Fu, Y. Hu, Y. He, J. Jiang, Y. Shao, C. Zhang, and B. Cui, “Don’t waste
your bits! Squeeze activations and gradients for deep neural networks via
TinyScript,” in Proceedings of the 37th International Conference
on Machine Learning, ser. Proceedings of Machine Learning Research, H. D.
III and A. Singh, Eds., vol. 119.1em plus 0.5em minus 0.4emPMLR, 13–18 Jul 2020, pp. 3304–3314. [Online]. Available:

[9]
R. D. Evans, L. Liu, and T. M. Aamodt, “Jpeg-act: Accelerating deep learning
via transform-based lossy compression,” in 2020 ACM/IEEE 47th Annual
International Symposium on Computer Architecture (ISCA), 2020, pp. 860–873.

[10]
T. Chen, B. Xu, C. Zhang, and C. Guestrin, “Training deep nets with sublinear
memory cost,” arXiv preprint arXiv:1604.06174, 2016.

[11]
O. Beaumont, L. Eyraud-Dubois, and A. Shilova, “Efficient combination of
rematerialization and offloading for training dnns,” in Advances in
Neural Information Processing Systems, M. Ranzato, A. Beygelzimer,
Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34.1em plus 0.5em
minus 0.4emCurran Associates, Inc., 2021, pp. 23 844–23 857.
[Online]. Available:

[12]
M. Kirisame, S. Lyubomirsky, A. Haan, J. Brennan, M. He, J. Roesch, T. Chen,
and Z. Tatlock, “Dynamic tensor rematerialization,” in International
Conference on Learning Representations, 2021. [Online]. Available:

[13]
P. Micikevicius, S. Narang, J. Alben, G. Diamos, E. Elsen, D. Garcia,
B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh, and H. Wu, “Mixed
precision training,” 2017, cite arxiv:1710.03740Comment: Published as a
conference paper at ICLR 2018. [Online]. Available:

[14]
S. Wu, G. Li, F. Chen, and L. Shi, “Training and inference with integers in
deep neural networks,” in International Conference on Learning
Representations, 2018. [Online]. Available:

[15]
N. Wang, J. Choi, D. Brand, C.-Y. Chen, and K. Gopalakrishnan, “Training deep
neural networks with 8-bit floating point numbers,” in Advances in
Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle,
K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31.1em plus
0.5em minus 0.4emCurran Associates, Inc., 2018. [Online]. Available:

[16]
R. Banner, I. Hubara, E. Hoffer, and D. Soudry, “Scalable methods for 8-bit
training of neural networks,” ser. NIPS'18.1em plus 0.5em minus
0.4emRed Hook, NY, USA: Curran Associates Inc., 2018, p. 5151–5159.

[17]
O. Zafrir, G. Boudoukh, P. Izsak, and M. Wasserblat, “Q8bert: Quantized 8bit
bert,” in 2019 Fifth Workshop on Energy Efficient Machine Learning and
Cognitive Computing - NeurIPS Edition (EMC2-NIPS), 2019, pp. 36–39.

[18]
E. J. Hu, yelong shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and
W. Chen, “LoRA: Low-rank adaptation of large language models,” in
International Conference on Learning Representations, 2022. [Online].
Available: <https://openreview.net/forum?id=nZeVKeeFYf9>

[19]
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal,
A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss,
G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter,
C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark,
C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, “Language
models are few-shot learners,” in Advances in Neural Information
Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and
H. Lin, Eds., vol. 33.1em plus 0.5em minus 0.4emCurran
Associates, Inc., 2020, pp. 1877–1901. [Online]. Available:

[20]
S. Swayamdipta, R. Schwartz, N. Lourie, Y. Wang, H. Hajishirzi, N. A. Smith,
and Y. Choi, “Dataset cartography: Mapping and diagnosing datasets with
training dynamics,” in Proceedings of the 2020 Conference on Empirical
Methods in Natural Language Processing (EMNLP).1em plus 0.5em minus
0.4emOnline: Association for Computational Linguistics, Nov. 2020, pp.
9275–9293. [Online]. Available:

[21]
R. Teehan, M. Clinciu, O. Serikov, E. Szczechla, N. Seelam, S. Mirkin, and
A. Gokaslan, “Emergent structures and training dynamics in large language
models,” in Proceedings of BigScience Episode #5 – Workshop on
Challenges & Perspectives in Creating Large Language Models.1em
plus 0.5em minus 0.4emvirtual+Dublin: Association for Computational
Linguistics, May 2022, pp. 146–159. [Online]. Available:

[22]
Z. Fang, M. Shahbazi, T. Probst, D. P. Paudel, and L. Van Gool, “Training
dynamics aware neural network optimization with stabilization,” in
Proceedings of the Asian Conference on Computer Vision (ACCV),
December 2022, pp. 4276–4292.

[23]
Y. Lee, A. S. Chen, F. Tajwar, A. Kumar, H. Yao, P. Liang, and C. Finn,
“Surgical fine-tuning improves adaptation to distribution shifts,”
arXiv preprint arXiv:2210.11466, 2022.

[24]
V. V. Ramasesh, E. Dyer, and M. Raghu, “Anatomy of catastrophic forgetting:
Hidden representations and task semantics,” in International
Conference on Learning Representations, 2021. [Online]. Available:

[25]
Y. Liu, S. Agarwal, and S. Venkataraman, “Autofreeze: Automatically freezing
model blocks to accelerate fine-tuning,” CoRR, vol. abs/2102.01386,
2021. [Online]. Available: <https://arxiv.org/abs/2102.01386>

[26]
S. Li, G. Yuan, Y. Dai, Y. Zhang, Y. Wang, and X. Tang, “SmartFRZ: An
efficient training framework using attention-based layer freezing,” in
The Eleventh International Conference on Learning Representations,
2023. [Online]. Available: <https://openreview.net/forum?id=i9UlAr1T_xl>

[27]
C. He, S. Li, M. Soltanolkotabi, and S. Avestimehr, “Pipetransformer:
Automated elastic pipelining for distributed training of large-scale
models,” in Proceedings of the 38th International Conference on
Machine Learning, ser. Proceedings of Machine Learning Research, M. Meila
and T. Zhang, Eds., vol. 139.1em plus 0.5em minus 0.4emPMLR,
18–24 Jul 2021, pp. 4150–4159. [Online]. Available:

[28]
A. Merchant, E. Rahimtoroghi, E. Pavlick, and I. Tenney, “What happens to
BERT embeddings during fine-tuning?” in Proceedings of the Third
BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for
NLP.1em plus 0.5em minus 0.4emOnline: Association for
Computational Linguistics, Nov. 2020, pp. 33–44. [Online]. Available:

[29]
S. Shalev-Shwartz and S. Ben-David, Understanding Machine Learning - From
Theory to Algorithms.1em plus 0.5em minus 0.4emCambridge
University Press, 2014.

[30]
A. Warstadt, A. Singh, and S. R. Bowman, “Neural network acceptability
judgments,” arXiv preprint arXiv:1805.12471, 2018.

[31]
A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. Bowman, “GLUE: A
multi-task benchmark and analysis platform for natural language
understanding,” in Proceedings of the 2018 EMNLP Workshop
BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP.1em plus 0.5em minus 0.4emBrussels, Belgium: Association for
Computational Linguistics, Nov. 2018, pp. 353–355. [Online]. Available:

[32]
P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang, “SQuAD: 100,000+
Questions for Machine Comprehension of Text,” arXiv e-prints, p.
arXiv:1606.05250, 2016.

[33]
A. Krizhevsky, “Learning multiple layers of features from tiny images,” pp.
32–33, 2009. [Online]. Available:
<https://www.cs.toronto.edu/ kriz/learning-features-2009-TR.pdf>

[34]
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A
large-scale hierarchical image database,” in 2009 IEEE conference on
computer vision and pattern recognition.1em plus 0.5em minus
0.4emIeee, 2009, pp. 248–255.

[35]
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin,
A. Desmaison, L. Antiga, and A. Lerer, “Automatic differentiation in
pytorch,” in CUDA semantics - PyTorch 2.0 documentation, 2017.
[Online]. Available: <https://pytorch.org/docs/stable/notes/cuda.html>

§ APPENDIX

§ MEMORY MANAGEMENT

The on-device memory of modern GPUs is limited to a few tens of gigabytes depending on their model (e.g., 32GB NVIDIA V100). If the memory requirement of the training/fine-tuning of neural networks goes beyond the available memory on GPUs, an out-of-memory error will occur. The memory requirement of the under-run code on GPUs can be viewed by “nvidia-smi”. For a training/fine-tuning process, this memory requirement is determined by the size of the model, cached activations, gradients, gradient moments from the optimizer and CUDA contents after the first training iterations. It is worth mentioning that the memory usage of the training/fine-tuning process remains constant after the first iteration if the following iterations are performing the same computations (see Fig. <ref>). If the memory requirement of each iteration is different from others, PyTorch reports the memory requirement of the iteration using the maximum memory among other iterations as the total on-device GPU memory usage of the program in “nvidia-smi” [35]. Therefore, the unused memory of tensors in progressive memory optimization over training iterations will still show as used in “nvidia-smi”. To reduce the overall memory usage of the training/fine-tuning process given the above explanations, we need to balance the memory usage of all iterations from the first iterations to the last one (see Fig. <ref>). SlimFit aims at reducing the overall memory usage of large transformer-based models during fine-tuning.

Memory of Activations

Total On-device Memory

The total on-device GPU memory and memory of activations during different training iterations when fine-tuning  ViT on ImageNet with a batch size of 128 with the freezing rate of $95\%$ compared to the baseline. SlimFit balances the memory usage of activations using freezing to reduce the total on-device memory usage of the fine-tuning process. While the memory usage of activations changes at each iteration when using SlimFit, the changes are relatively small thanks to the load-balancing technique described in Section <ref>.

§ COMPARISON WITH EXISTING FREEZING APPROACHES

Here, we describe the main differences between SlimFit and other freezing approaches including SmartFRZ [26], PipeTransformer [27] and AutoFreeze [25]. The main difference is that the aforementioned works mainly focus on exploiting freezing to accelerate the training/fine-tuning process. Conceptually, SmartFRZ, PipeTransformer and AutoFreeze progressively freeze layers as the training process proceeds. In these methods, the first training iteration starts without freezing where all layers are updated. In the following iterations, these methods then progressively start freezing from the early layers down to the latest layers in the model in an orderly fashion. For instance, AutoFreeze performs the first epoch without freezing, the second epoch while freezing the first 5 layers, the third epoch while freezing the first 8 layers and the fourth epoch while freezing the first 11 layers when fine-tuning BERT. In this example, the memory and computation requirement of each epoch is different from others as each epoch presents a different degree of freezing. This allows to exploit the unused computing and memory resources to further accelerate the process by increasing batch sizes as the memory decreases throughout the training iterations [25] or increasing data-parallel width through pipelining [27]. Since the first training iteration (or even epoch) of these methods performs the training process without freezing, their overall memory requirement reported by “nvidia-smi” is similar to that of training without freezing as discussed in Appendix <ref>. In other words, the under-use GPU must still be able to meet the memory requirement of training without freezing. For instance, fine-tuning of ViT with a batch size of 128 on a single 32GB NVIDIA V100 using such methods results in an out-of-memory error.

SlimFit, on the other hand, focuses on reducing the overall memory requirement of the fine-tuning process using freezing. As opposed to the aforementioned methods (i.e., SmartFRZ, PipeTransformer and AutoFreeze), SlimFit freezes layers at every single training iterations from the first iteration to the last one with a fixed freezing rate. With load-balancing using quantization, SlimFit ensures that the memory requirement of every single iteration remains roughly the same throughout the fine-tuning process. This enables SlimFit performing memory-intensive fine-tuning processes with large batch sizes on a single 32GB GPU such as ViT on ImageNet with a batch size of 128  while this normally requires three 32GB GPUs.

§ ARCHITECTURE OF TRANSFORMER-BASED MODELS

Fig. <ref> shows the overall architecture of transformer-based models including an initial embedding layer, followed by repeated blocks of multi-head attention (MHA) and feed-forward network (FFN). The details of each layer inside the MHA and FFN modules are provided in Table <ref>.

figureThe main architecture of BERT. Note that ViT has a similar architecture with LayerNorms located before the MHA block. $L$ denotes the number of attention layers.

tableThe details of layers in MHA and FFN modules of BERT where $B$, $T$, $H$ denote the batch size, sequence length, hidden size, respectively. ViT has the same structure with different descriptions.

§ THEORETICAL ANALYSIS

§.§ Convergence Analysis

In this section, we provide a convergence analysis for our freezing strategy. More precisely, we prove convergence of stochastic gradient descent (SGD) when considering freezing during update iterations. Given the loss function $f$, we assume that the parameters are initialized with some value and denoted as the vector $\textbf{w}_0 \in \mathbb{R}^d$. Given the training example, the parameters are updated by

\begin{equation}
\textbf{w}_{t+1} = \textbf{w}_t - \gamma_t \nabla f(\textbf{w}_t),
\label{update_eq}
\end{equation}

where $\textbf{w}_t$ denotes the parameter vector at time $t$, $\gamma_t$ is the learning rate, and $\nabla f$ represents the gradient of the loss function. We assume that the magnitude of the gradient samples are bounded by a constant $G > 0$ for all $\textbf{x}$ in the space such that

\begin{equation}
||\nabla f(\textbf{x})|| \leq G.
\label{cond1}
\end{equation}

Also, we assume that there exists a constant $L > 0$ for any vector $\textbf{u} \in \mathbb{R}^d$ where we have

\begin{equation}
|\textbf{u}^T \nabla^2 f(\textbf{x})\textbf{u}| \leq L ||\textbf{u}||^2.
\label{cond2}
\end{equation}

Given Eq. (<ref>) and Eq. (<ref>), performing Taylor expansion on Eq. (<ref>) similar to [29] results in

\begin{equation}
\mathbb{E}[f(\textbf{w}_{t+1})] \leq \mathbb{E}[f(\textbf{w}_t)] - \gamma_t \mathbb{E}[||\nabla f(\textbf{w}_t)||^2] + \dfrac{\gamma_t^2G^2L}{2},
\label{taylor_eq}
\end{equation}

where $\mathbb{E}$ denotes the expected value.

Now, let us assume that the layer containing the parameter vector is frozen at the training iteration $t$. In this case, $\nabla f(\textbf{w}_t)$ is equal to $0$ and consequently $\textbf{w}_{t+1}$ is equal to $\textbf{w}_t$. In this freezing scenario, Eq. (<ref>) still holds true since $\dfrac{\gamma_t^2G^2L}{2}$ is greater than $0$.

By rearranging the terms in Eq. (<ref>), summing over $T$ iterations and telescoping the sum, we obtain

\begin{align}
\sum_{t=0}^{T-1} \gamma_t \mathbb{E}[||\nabla f(\textbf{w}_t)||^2] & \leq \sum_{t=0}^{T-1} (\mathbb{E}[f(\textbf{w}_t)] - \mathbb{E}[f(\textbf{w}_{t+1})]) + \sum_{t=0}^{T-1}\dfrac{\gamma_t^2G^2L}{2},\\
& = f(\textbf{w}_0) - f(\textbf{w}_T) + \dfrac{G^2L}{2} \sum_{t=0}^{T-1} \gamma_t^2,\\
& \leq f(\textbf{w}_0) - f(\textbf{w}_*) + \dfrac{G^2L}{2} \sum_{t=0}^{T-1} \gamma_t^2,
\end{align}

where $\textbf{w}_*$ indicates an optimal solution. Given the above inequality, we showed that the convergence proof of SGD remains intact while introducing freezing for specific training iterations.

§.§ Backpropagation With a Frozen Layer

Here, we provide a simple example demonstrating how gradients are backpropagated to the first layer of a neural network while its middle layer is frozen. To this end, let us perform the backpropagation using a 3-layer network as an example. Mathematically, the architecture of this network can be described as follows:

\begin{align}
\textbf{y}_1 &= \textbf{x}\textbf{W}_1 + \textbf{b}_1,\\
\textbf{y}_2 &= \textbf{y}_1\textbf{W}_2 + \textbf{b}_2,\\
\textbf{y}_3 &= \textbf{y}_2\textbf{W}_3 + \textbf{b}_3,
\end{align}

where $\textbf{W}_1$, $\textbf{W}_2$, $\textbf{W}_3$, $\textbf{b}_1$, $\textbf{b}_2$ and $\textbf{b}_3$ are the weights and biases of the network. In this example, $\textbf{x}$, $\textbf{y}_1$ and $\textbf{y}_2$ are inputs to the first layer, the second layer and the third layer, respectively. Now, let us derive the backpropagation equations with the loss
$\mathcal{L}$ using the chain rule as follows (please note that we obtain $\dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3}$ by computing the loss where $\partial$ denotes the partial derivative):

\begin{align}
\dfrac{\partial \mathcal{L}}{\partial \textbf{W}_3} & = \dfrac{\partial \textbf{L}}{\partial \textbf{y}_3} \dfrac{\partial \textbf{y}_3}{\partial \textbf{W}_3} = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \textbf{y}_2, \label{partial_1} \\
\dfrac{\partial \mathcal{L}}{\partial \textbf{b}_3} & = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \dfrac{\partial \textbf{y}_3}{\partial \textbf{b}_3} = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} 1 = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3}, \\
\dfrac{\partial \mathcal{L}}{\partial \textbf{W}_2} & = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \dfrac{\partial \textbf{y}_3}{\partial \textbf{y}_2} \dfrac{\partial \textbf{y}_2}{\partial \textbf{W}_2} = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \textbf{W}_3^T \textbf{y}_1, \label{partial_2} \\
\dfrac{\partial \mathcal{L}}{\partial \textbf{b}_2} & = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3}  \dfrac{\partial \textbf{y}_3}{\partial \textbf{y}_2} \dfrac{\partial \textbf{y}_2}{\partial \textbf{b}_2} = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \textbf{W}_3^T 1 = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \textbf{W}_3^T, \\
\dfrac{\partial \mathcal{L}}{\partial \textbf{W}_1} & = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \dfrac{\partial \textbf{y}_3}{\partial \textbf{y}_2} \dfrac{\partial \textbf{y}_2}{\partial \textbf{y}_1} \dfrac{\partial \textbf{y}_1}{\partial \textbf{W}_1} = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \textbf{W}_3^T \textbf{W}_2^T \textbf{x}, \label{partial_3} \\
\dfrac{\partial \mathcal{L}}{\partial \textbf{b}_1} & = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \dfrac{\partial \textbf{y}_3}{\partial \textbf{y}_2} \dfrac{\partial \textbf{y}_2}{\partial \textbf{y}_1} \dfrac{\partial \textbf{y}_1}{\partial \textbf{b}_1} = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \textbf{W}_3^T \textbf{W}_2^T 1 = \dfrac{\partial \mathcal{L}}{\partial \textbf{y}_3} \textbf{W}_3^T \textbf{W}_2^T.\label{partial_4}
\end{align}

Given the above equations, to update the network weights (i.e., $\textbf{W}_1$, $\textbf{W}_2$, and $\textbf{W}_3$), we need to store $\textbf{x}$, $\textbf{y}_1$ and $\textbf{y}_2$ during the forward computations since they are required in Eq. (<ref>), Eq. (<ref>) and Eq. (<ref>) during the back computations.

Now, suppose the middle layer is frozen. In this case, there is no need to compute Eq. (<ref>) and therefore there is no need to store $\textbf{y}_1$ during the forward computations. Of course, discarding $\textbf{y}_1$ does not affect the backward computations of the first layer since Eq. (<ref>) and Eq. (<ref>) are independent of $\textbf{y}_1$.

§ CONVERSION BETWEEN 8-BIT INTEGER AND 32-BIT FLOATING-POINT

Algorithm <ref> shows the conversion process between 8-bit fixed-point and 32-bit floating-point formats. It is worth mentioning that the same procedure can be used for the conversion between 4-bit fixed-point and 32-bit floating-point formats. Moreover, the quantization function is used to compress the cached tensors during the forward propagation only. Of course, both the forward and backward computations are still performed using 32-bit floating-point computations as shown in Algorithm <ref> where the “compress” function in this case is the quantization function (i.e., the conversion from 32-bit floating-point to 8-bit integer) and the “decompress” function performs the reverse computations (i.e., the conversion from 8-bit integer to 32-bit floating-point).

The conversion between 8-bit integer and 32-bit floating-point.

The description of the pruning process during the forward computations and the restoring process during the backward computations.

§ PRUNING ALGORITHM

The pruning algorithm is performed in a few steps. In the first step, the input vector is sorted from largest to smallest values along with their indices and the size of the dense vector. We then only keep and cache the top $10\%$ largest values of the input vector for the backward computations as the second step. It is worth mentioning that pruning beyond $90\%$ results in a significant accuracy degradation. During backpropagation, we create a zero-valued tensor using the size of the dense vector and then replace zero values with the top $10\%$ largest values using their corresponding indices. Algorithm <ref> shows the pruning process during the forward computations and the restoring process during the backward computations. It is worth mentioning that the pruning function is used to compress the cached tensors during the forward propagation only. Of course, both the forward and backward computations are still performed using 32-bit floating-point computations as shown in Algorithm <ref> where the “compress” function in this case is the pruning function and the “decompress” function performs the restoring computations.

§ DETAILS OF CV/NLP TASKS, MEASUREMENTS AND HYPER-PARAMETER SETTINGS

For language understanding tasks and CV tasks, we used BERT-base-cased and ViT-base throughout this paper, respectively. The BERT-base and ViT-base pre-trained on ImageNet-21k were configured according to [1] and [2], respectively. We used AdamW ($\beta_1 = 0.9$, $\beta_2 = 0.999$ and $L2$ weight decay of 0.01) as the optimizer and linear decay of the learning rate with warmup ranging from 0 to 0.1 for both models. We evaluate BERT-base on several downstream tasks from the GLUE benchmark and SQuAD 2.0. We use Spearman correlation for STS-B, Matthews correlation for CoLA, accuracy for RTE, MRPC, SST-2 QQP, QNLI and MNLI$_m$ (matched), and F1 score for SQuAD 2.0. For the downstream tasks from the GLUE benchmark, we used the sequence length of 128 whereas we adopted the sequence length of 384 for the question answering task on SQuAD 2.0. For CIFAR-10, CIFAR-100 and ImageNet, we use top-1 accuracy as our evaluation metric. For the image classification tasks, we used the patch size of 16 with the resolution of 224 for CIFAR-10/CIFAR-100 and the resolution of 384 for ImageNet. Depending on the task, the learning rate varies from 4e-5 to 1.8e-4. For all the experiments in this paper, we used 3 epochs for fine-tuning. The hyper-parameter settings of each task are summarized in Table <ref>. It is worth mentioning that ViT models can also be fine-tuned using SGD. However, fine-tuning ViT models using SGD requires more epochs w.r.t. AdamW to obtain a similar accuracy.

In this paper, we measured our experimental results directly from 32GB NVIDIA V100 GPU(s) without any memory swapping between CPU and GPU(s). The total on-device GPU memory usage of the fine-tuning process is measured using “nvidia-smi”. We measured the wall-clock time (i.e., latency) of the fine-tuning process using the CUDA's event API in PyTorch (i.e., “torch.cuda.Event”). The memory footprint of activations on the GPU(s) was measured using the PyTorch's memory management API (i.e., “torch.cuda.memory_allocated”).

The hyper-parameter settings of each NLP/CV task.

§ IMPACT OF QUANTIZATION AND PRUNING

In this work, we used quantization and pruning for a few specific layers to balance the number of activations across all layers and to reduce the memory footprint of static activations. We used 8-bit quantization for the activations of the imbalanced linear layer and MatMul. We also quantized the activations of GELU using 4 bits. The pruning of LayerNorm was performed when this layer is kept frozen. It is worth mentioning that both quantization and pruning have no impact on the forward computations. They are only used to compress activations for caching. To show the impact of such compression methods, we report the accuracy evaluation of BERT on CoLA and MRPC datasets with and without quantization or pruning in Table <ref>. The experimental results show no notable performance loss due to the compression techniques.

The impact of quantization and pruning on the accuracy evaluation.

§ DISCUSSION ON WALL-CLOCK TIME

Compared to training without freezing, SlimFit introduces extra computations and also skips weight gradient computations for the frozen layers at the same time. The main source of computational overhead in SlimFit is quantization and pruning of activations. The quantization overhead is due to the conversion between different precision levels (i.e., between 8 bits and 32-bit floating-point format) as discussed in Appendix <ref>. Pruning also requires sorting of values to keep their top $10\%$ largest values, which causes an additional computational overhead. Computing the weight distance metric is another source of computational overhead.

The description of skipping weight gradient computations when the layer is frozen. In this example, we assume the activations of the frozen layer require compression (e.g., an imbalanced linear layer or LayerNorm). Activations are denoted as “input” and are cached using either quantization or pruning depending on the type of the layer as a compression method. The compression and decompression functions are denoted as “compress” and “decompress”. Since weights are defined as “Parameter” in PyTorch, caching weights does not introduce any extra memory.

Wall-clock time of fine-tuning ViT on ImageNet with a batch size of 32 across different freezing rates.

On the other hand, SlimFit skips the weight gradients computations of frozen layers using PyTorch “requires_grad” as shown in Algorithm <ref>. When an activate layer is frozen, there is no need to compute its weight gradients as discussed in Appendix <ref>, which reduces the wall-clock time. The amount of speedup due to the skipped computations highly depends on the hyper-parameters of the networks such as freezing rate. Therefore, the wall-clock time of each network varies from one to another depending on the hyper-parameters. For instance, Fig. <ref> shows the wall-clock time of fine-tuning ViT on ImageNet using a batch size of 32 across different freezing rates. According to the experimental results, the computational overhead of SlimFit is dominant for small freezing rates. However, as the freezing rate increases, the speedup of the skipped gradient computations overcomes the computational overhead of SlimFit where SlimFit with the freezing rate of $95\%$ results in a similar wall-clock time as of the baseline. It is worth mentioning that the baseline is the point at the freezing rate of $0$ where no freezing was used during the fine-tuning process.

§ DESCRIPTION OF LAYERS IN THE HEATMAP

The description of layers associated to the indices in Fig. <ref> is provided in Algorithm <ref>. It is worth mentioning that the layers denoted by “bert.encoder.layer[i].attention” belong to the MHA module whereas the remaining layers inside the loop belong to the FFN module.

The description of layers associated to the indices in Fig. <ref>.


# A lower bound for essential covers of the cube

Gal Yehuda  Department of Computer Science, Technion-IIT
<EMAIL_ADDRESS>and  Amir Yehudayoff  Department of Mathematics,
Technion-IIT<EMAIL_ADDRESS>
###### Abstract.

Essential covers were introduced by Linial and Radhakrishnan as a model that
captures two complementary properties: (1) all variables must be included and
(2) no element is redundant. In their seminal paper, they proved that every
essential cover of the $n$-dimensional hypercube must be of size at least
$\Omega(n^{0.5})$. Later on, this notion found several applications in
complexity theory. We improve the lower bound to $\Omega(n^{0.52})$, and
describe two applications.

##  1\. Introduction

The vertices of the hypercube can be embedded in Euclidean space as $\\{\pm
1\\}^{n}$. A hyperplane $h=\\{z\in\mathbb{R}^{n}:\langle z,v\rangle=\mu\\}$
covers the vertex $x$ if $x\in h$. What is the minimum number of hyperplanes
that are needed to cover all vertices? This question is motivated by problems
in combinatorial geometry [8], combinatorics [1, 7], proof complexity [4, 5]
and more. For an introduction to this and related topics, see the survey by
Saks [11].

The two hyperplanes $\\{z_{1}=1\\}$ and $\\{z_{1}=-1\\}$ cover all vertices.
This solution is optimal but also degenerate and not so interesting. There are
two standard ways for defining non-degenerate covers: skew and essential
covers. In a skew cover, all normal vectors have full support (see e.g. [11,
13] and references within). In an essential cover, all variables must appear
and no hyperplane is redundant [7]. Our focus is on the latter.

######  Definition 1 (Linial and Radhakrishnan [7]).

The hyperplanes $h_{1},\ldots,h_{k}$ form an essential cover of the $n$-cube
if

  1. (E1)

for every vertex $x\in\\{\pm 1\\}^{n}$, there is $i\in[k]$ so that $x\in
h_{i}$.

  2. (E2)

for every $j\in[n]$, there is $i\in[k]$ such that the normal $v_{i}$ of
$h_{i}$ satisfies $v_{i,j}\neq 0$.

  3. (E3)

for every $i\in[k]$, there is a vertex $x$ so that $x$ is covered only by
$h_{i}$.

Condition (E1) means that $h_{1},\ldots,h_{k}$ form a cover. Condition (E2)
says that every variable “appears” in at least one of the hyperplanes.
Condition (E3) means that no strict subset of $h_{1},\ldots,h_{k}$ form a
cover (“criticality” or “minimality”).

Linial and Radhkrishnan proved that the smallest size $e(n)$ of an essential
cover of the $n$-cube satisfies

$\tfrac{1}{2}(\sqrt{4n+1}+1)\leq e(n)\leq\lceil\tfrac{n}{2}\rceil.$

When the hyperplanes are assumed to be positive, a sharp $n+1$ lower bound was
proved by Saxton [12]. Saxton also reduced the general case to a problem on
permanents of matrices. We provide the first improvement over the lower bound
from [7].

######  Theorem.

$e(n)\geq\Omega(n^{0.52})$.

Our proof-plan is straightforward. Show that few hyperplanes must miss a
vertex of the cube. But this is false; two hyperplanes can cover the whole
cube. We must use the essential condition. How? Our high-level approach is
inspired by ideas from [13] where a lower bound for the slicing problem was
proved. Specifically, we rely on the connection to convex geometry that was
established in [13]. The lower bound is based on Bang’s solution of Tarski’s
plank problem [3, 2].

Proving lower bounds for the slicing problem is in general harder than for
covering problems. For example, any lower bound for the slicing problem
immediately implies a lower bound for the skew covering problem [13]. In the
slicing problem, however, we can assume that the normal vectors are generic.
This assumption is powerful, e.g., when proving anti-concentration results. In
essential covers, a major difficulty is that the hyperplanes are not generic;
a small perturbation of a cover is not a cover. This leads to several new
challenges, and requires developing a better structural understanding of the
few but unknown hyperplanes.

###  1.1. Applications

The theorem immediately implies two new lower bounds in proof complexity, as
we briefly describe next.

The first lower bound is for resolution over linear equations
$\text{Res}(\text{lin}_{\mathbb{Q}})$. This proof system was introduced by Raz
and Tzameret [10] as an extension of resolution with “counting capabilities”.
Part and Tzameret [9] studied tree-like proofs in this system. They proved the
following lower bound. Let $g_{1},\ldots,g_{N}$ be linear functions in $n$
variables over $\mathbb{Q}$ where each depends on at least $\frac{n}{2}$
variables. Then, any tree-like $\text{Res}(\text{lin}_{\mathbb{Q}})$
derivation of a tautology of the form $\vee_{j\in[N]}g_{j}=0$ is of size
$2^{\Omega(\sqrt{n})}$. The $\Omega(\sqrt{n})$ in the exponent is in fact
$\Omega(e(n))$ and follows from Linial and Radhkrishnan’s lower bound. Our
result immediately improves the lower bound to $2^{\Omega(n^{0.52})}$.

The second application is in the stabbing planes proof system. This proof
system was introduced by Beame et al. as an extension of cutting planes that
is more similar to algorithms that are used in practice [4]. Dantchev, Galesi,
Ghani, and Martin proved a lower bound of $\Omega(n)$ on the refutation-size
of Tseitin formulas over the $n\times n$ grid [5]. Their lower bound is in
fact of the form $\Omega(e(n^{2}))$. Our result thus yields the better lower
bound $\Omega(n^{1.04})$.

##  2\. Finding the uncovered vertex

Assume towards a contradiction that the $k\leq\tfrac{n^{0.52}}{10}$
hyperplanes defined by $v_{1},\ldots,v_{k}\in\mathbb{R}^{n}$ and
$\mu_{1},\ldots,\mu_{k}\in\mathbb{R}$ form an essential cover of the hypercube
for large $n$. Our goal is to locate a vertex $u$ that is not covered. This is
done in three phases. In each phase we “discover” some more coordinates in
$u$.

###  2.1. Finding structure

Let $V$ be the $k\times n$ matrix whose rows are $v_{1},\ldots,v_{k}$. The
analysis is based on a structural lemma for $V$ that is stated below. Figure 1
may help in understanding the lemma. The proof of the lemma is deferred to
Section 3. To state the lemma, we need the following definitions. Denote by
$\|v\|_{0}$ the sparsity of $v\in\mathbb{R}^{n}$; i.e., $\|v\|_{0}$ is the
number of non-zero entries in $v$.

######  Definition 2 ([13]).

Let $C_{0}>1$ be the constant from Claim 10 in [13]. A vector
$v\in\mathbb{R}^{n}$ has many scales if $v$ can be partitioned into
$S:=\lfloor n^{0.001}\rfloor$ vectors $v^{(1)},v^{(2)},\ldots,v^{(S)}$ such
that

$\|v^{(s)}\|_{2}\geq C_{0}\|v^{(s+1)}\|_{2}$

for all $s<S$. The smallest scale of $v$ is defined to be $\|v^{(S)}\|_{2}$.

######  Lemma 3.

Let $V\in\mathbb{R}^{k\times n}$ be the matrix defined above (its rows are
$v_{1},\ldots,v_{k}$ and $k\leq\frac{n^{0.52}}{10}$). Then, there is a
partition of the rows of $V$ to four parts $[k]=K_{1}\cup K_{2}\cup K_{3}\cup
K_{4}$ and a partition of the columns to three parts $[n]=N_{1}\cup N_{2}\cup
N_{3}$ with $|N_{1}|\geq\tfrac{n}{2}$ such that the following hold:

  1. (1)

Every column in $N_{1}\cup N_{2}$ has sparsity at most $n^{0.04}$.

  2. (2)

For every row $i\in K_{1}$, the $N_{1}\cup N_{2}$ coordinates of $v_{i}$ are
zero.

  3. (3)

For every row $i\in K_{2}$, the $N_{1}$ coordinates of $v_{i}$ are zero, and
there are at least $4|K_{2}|^{2}$ non-zero elements in the $N_{2}$ coordinates
of $v_{i}$.

  4. (4)

For $i\in K_{3}$, let $v^{\prime}_{i}$ be the projection of $v_{i}$ to the
$N_{1}$ coordinates. The vector $v^{\prime}_{i}$ is non-zero. Let $\phi_{i}>0$
be so that $\|\phi_{i}v^{\prime}_{i}\|_{2}=1$. For every column $j\in N_{1}$,

(2.1) $\displaystyle\sum_{i\in
K_{3}}\phi_{i}^{2}{v^{\prime}}^{2}_{ij}<n^{-0.196}.$

In particular, item (1) implies

(2.2) $\displaystyle\sum_{i\in
K_{3}}|\phi_{i}v^{\prime}_{ij}|<\sqrt{n^{0.04}n^{-0.196}}\leq n^{-0.078}.$

  5. (5)

For every row $i\in K_{4}$, the projection of $v_{i}$ to the $N_{1}\cup N_{2}$
coordinates has many scales, its smallest scale is non-zero, and the position
of the smallest scale contains $N_{1}$.

Figure 1. The decomposition of $V$.

###  2.2. Phase I

In this phase, we fix the $N_{3}$ coordinates in $u$. We know that
$|N_{3}|<n$. Condition (E2) implies that $K_{1}\neq[k]$. Condition (E3)
implies that there is a vertex $x$ that is not covered by the hyperplanes in
$K_{1}$. For every $j\in N_{3}$ set $u_{j}=x_{j}$. The rest of the entries in
$u$ shall be determined in later phases. Denote the part of $u$ that was just
fixed by $u^{(I)}$. The $u^{(I)}$ part of $u$ deals with all hyperplanes in
$K_{1}$.

###  2.3. Phase II

In this phase, we fix the $N_{2}$ coordinates in $u$. This is done with the
aid of randomness. The randomness simultaneously deals with rows in $K_{2}$
and in $K_{4}$. We denote by $v^{\prime}_{i}$ the projection of $v_{i}$ to the
$N_{1}$ coordinates, by $v^{\prime\prime}_{i}$ the projection to the $N_{2}$
coordinates, and by $v^{(I)}_{i}$ the projection to coordinates in $N_{3}$.

######  Claim 4.

There is $x^{\prime\prime}\in\\{\pm 1\\}^{N_{2}}$ so that

  1. (1)

For every $i\in K_{2}$,

$\langle x^{\prime\prime},v_{i}^{\prime\prime}\rangle+\langle
u^{(I)},v_{i}^{(I)}\rangle\neq\mu_{i}.$

  2. (2)

For every $i\in K_{4}$ and $x^{\prime}\in\\{\pm 1\\}^{N_{1}}$,

$|\langle x^{\prime\prime},v_{i}^{\prime\prime}\rangle+\langle
u^{(I)},v_{i}^{(I)}\rangle-\mu_{i}|>|\langle
x^{\prime},v_{i}^{\prime}\rangle|.$

Choose the $N_{2}$ coordinates of $u$ to be $x^{\prime\prime}$. Denote this
part of $u$ by $u^{(II)}$. The first condition implies that $u^{(II)}$ deals
with all rows in $K_{2}$. The second condition implies that it deals with all
rows in $K_{4}$, regardless of the future choice of the $N_{1}$ coordinates in
$u$.

In order to prove the claim, we need the following two anti-concentration
results. The first is known as the Littlewood-Offord lemma [8] and was proved
by Erdős [6]. The second appears in [13]. We denote by $x\sim\\{\pm 1\\}^{n}$
a uniformly random vertex of the cube.

######  Claim 5 ([8, 6]).

For all $v\in\mathbb{R}^{n}$ so that $\|v\|_{0}>0$ and $a\in\mathbb{R}$,

$\Pr_{x\sim\\{\pm 1\\}^{n}}[\langle
x,v\rangle=a]\leq\frac{1}{\sqrt{\|v\|_{0}}}.$

######  Lemma 6 ([13]).

There is a constant $C_{1}>1$ so that the following holds. If
$v\in\mathbb{R}^{n}$ has many scales and its smallest scale is $\delta>0$,
then for every $a\in\mathbb{R}$ and $b\geq 2$ we have

$\Pr_{x\sim\\{\pm 1\\}^{n}}[|\langle x,v\rangle-a|\leq
b\delta]<C_{1}\exp\Big{(}-\frac{S}{C_{1}}+C_{1}\log(b)\Big{)}.$

###### Proof of Claim 4.

Pick $x^{\prime\prime}$ uniformly at random. First, consider $i\in K_{2}$. By
Claim 5, because $\|v^{\prime\prime}_{i}\|_{0}\geq 4|K_{2}|^{2}$,

$\Pr_{x^{\prime\prime}}[\langle
x^{\prime\prime},v_{i}^{\prime\prime}\rangle+\langle
u^{(I)},v_{i}^{(I)}\rangle=\mu_{i}]\leq\frac{1}{2|K_{2}|}.$

Second, consider $i\in K_{4}$. Row $v_{i}$ has many scales and
$v^{\prime}_{i}$ is part of its smallest scale. Let $\alpha$ be the vector
consisting of the largest $S-1$ scales of $v_{i}$. The vector of the smallest
scale in $v_{i}$ has two parts: $v^{\prime}_{i}$ and the part outside the
$N_{1}$ columns which we denote by $\beta$. Partition $x^{\prime\prime}$ to
$x_{\alpha}$, $x_{\beta}$ accordingly. Let $\delta>0$ be the smallest scale of
$\alpha$. By Cauchy-Schwartz, for all $x^{\prime}\in\\{\pm 1\\}^{N_{1}}$,

$|\langle
x^{\prime},v^{\prime}_{i}\rangle|\leq\sqrt{n}\|v^{\prime}_{i}\|_{2}<\sqrt{n}\delta.$

By Lemma 6, conditioned on the value of $x_{\beta}$,

$\displaystyle\Pr_{x_{\alpha}}[|\langle
x^{\prime\prime},v^{\prime\prime}_{i}\rangle+\langle u^{(I)},v_{i}^{(I)}$
$\displaystyle\rangle-\mu_{i}|\leq\sqrt{n}\delta]\leq
C_{1}\exp\Big{(}-\frac{S-1}{C_{1}}+C_{1}\log n\Big{)}.$

The same bound holds when we average over $x_{\beta}$ as well.

Finally, the union bound over $K_{2}\cup K_{4}$ completes the proof. ∎

###  2.4. Phase III

It remains to choose the $N_{1}$ coordinates in $u$. Let $\tilde{u}\in\\{\pm
1\\}^{N_{2}\cup N_{3}}$ denote the part of $u$ that was already fixed (it is
comprised of $u^{(I)}$ and $u^{(II)}$). Let $\tilde{v}_{i}$ be projection of
$v_{i}$ to the $N_{2}\cup N_{3}$ coordinates.

######  Claim 7.

There is $x^{\prime}\in\\{\pm 1\\}^{N_{1}}$ so that for all $i\in K_{3}$,

$\langle
x^{\prime},v^{\prime}_{i}\rangle+\langle\tilde{u},\tilde{v}_{i}\rangle\neq\mu_{i}.$

Before proving the final claim, let us see how it completes the proof of the
theorem. The final part $u^{(III)}$ of $u$ is $x^{\prime}$. The vertex $u$ is
indeed not covered by any of the hyperplanes: All hyperplanes in $K_{1}$ are
avoided due to $u^{(I)}$, because the rest of their entries are zero. All
hyperplanes in $K_{2}$ are avoided due to $u^{(II)}$, because the rest of
their entries are zero. All hyperplanes in $K_{3}$ are avoided due to
$u^{(III)}$. All hyperplanes in $K_{4}$ are avoided due to $u^{(II)}$ as well,
because $u^{(III)}$ has no real affect.

A key piece of the argument is a lemma that Ball isolated from Bang’s solution
of Tarski’s plank problem [3, 2].

######  Lemma 8 ([3, 2]).

Let $M$ be a $k\times k$ real symmetric matrix with ones on the diagonal. Let
$\gamma_{1},\ldots,\gamma_{k}\in\mathbb{R}$ and $\theta\geq 0$. Then, there is
$\epsilon\in\\{\pm 1\\}^{k}$ so that for every $i\in[k]$,

$|\theta(M\epsilon)_{i}-\gamma_{i}|\geq\theta.$

###### Proof of Claim 7.

For $i\in K_{3}$, let $\phi_{i}>0$ be so that
$\|\phi_{i}v^{\prime}_{i}\|_{2}=1$ and let

$\gamma_{i}=\phi_{i}(\mu_{i}-\langle\tilde{u},\tilde{v}_{i}\rangle).$

Let $V^{\prime}$ be the matrix with rows
$\phi_{i}v^{\prime}_{i}\in\mathbb{R}^{N_{1}}$ for $i\in K_{3}$. Consider the
$K_{3}\times K_{3}$ matrix $M=V^{\prime}V^{\prime T}$. Let

$\theta=n^{0.078}.$

By Bang’s lemma, there is $\epsilon\in\\{\pm 1\\}^{K_{3}}$ so that for each
$i\in K_{3}$,

(2.3)
$\displaystyle|\langle\phi_{i}v^{\prime}_{i},z\rangle-\gamma_{i}|\geq\theta,$

where

$z=\theta V^{\prime T}\epsilon.$

By (2.2),

$\|z\|_{\infty}\leq 1.$

We round $z$ to a vertex of the cube $\\{\pm 1\\}^{N_{1}}$ in two steps. The
first step uses linear algebra as in [13].

######  Claim 9 ([13]).

There is $w\in\mathbb{R}^{N_{1}}$ so that the following hold:

  1. (1)

For each $i\in K_{3}$, we have $\langle w,v_{i}^{\prime}\rangle=\langle
z,v_{i}^{\prime}\rangle$.

  2. (2)

$\|w\|_{\infty}\leq 1$.

  3. (3)

Let $N_{0}$ be the set of coordinates in $w$ that are not $\pm 1$. Then
$|N_{0}|\leq k$.

If $N_{0}$ is empty then we are done, in light of (2.3) and because
$w\in\\{\pm 1\\}^{N_{1}}$ is so that

$\langle
w,v^{\prime}_{i}\rangle+\langle\tilde{u},\tilde{v}_{i}\rangle=\mu_{i}\quad\Leftrightarrow\quad\langle
w,\phi_{i}v^{\prime}_{i}\rangle=\gamma_{i}.$

Otherwise, we need to round the coordinates in $N_{0}$ to $\pm 1$. This is
done using extra randomness. Let $\delta\in\mathbb{R}^{N_{1}}$ be a random
vector distributed as follows. Its coordinates are independent so that
$\delta_{j}+w_{j}$ takes values in $\\{\pm 1\\}$ and $\mathbb{E}\delta_{j}=0$.
Its marginals can be computed by

$w_{j}=\mathbb{E}[\delta_{j}+w_{j}]=2\Pr[\delta_{j}=1-w_{j}]-1$

so that

$\Pr[\delta_{j}=1-w_{j}]=\frac{1+w_{j}}{2}$

and

$\displaystyle\mathbb{E}[\delta_{j}^{2}]$
$\displaystyle=\frac{1+w_{j}}{2}(1-w_{j})^{2}+\frac{1-w_{j}}{2}(-1-w_{j})^{2}=1-w_{j}^{2}.$

Consider the random vertex

$x^{\prime}=\delta+w\in\\{\pm 1\\}^{N_{1}}.$

The rest of the analysis is split between two cases. For each $i\in K_{3}$,
let

$\sigma_{i}^{2}=\sum_{j\in
N_{1}}(1-w_{j}^{2})\phi_{i}^{2}{v^{\prime}_{ij}}^{2}.$

First, consider some $i$ so that $\sigma_{i}^{2}\leq n^{0.151}$; if there are
no such $i$’s then continue to case two. We use the following concentration of
measure.

######  Theorem 10 (Bernstein).

Let $z_{1},\ldots,z_{\ell}$ be independent random variables with mean zero
that are almost surely at most two in absolute value. Let
$\sigma^{2}=\sum_{j}\mathbb{E}[z_{j}^{2}]$. Then, for all $t>0$, we have
$\Pr\big{[}\sum_{j}z_{j}\geq
t\big{]}\leq\exp\big{(}-\frac{t^{2}}{2\sigma^{2}+2t}\big{)}$.

By (2.3), by the choice of $\theta$ and by Claim 9,

$\displaystyle\Pr[\langle
x^{\prime},\phi_{i}v_{i}^{\prime}\rangle=\gamma_{i}]=\Pr[\langle\delta,\phi_{i}v_{i}^{\prime}\rangle=\gamma_{i}-\langle
z,\phi_{i}v_{i}^{\prime}\rangle]\leq\Pr[|\langle\delta,\phi_{i}v_{i}^{\prime}\rangle|\geq
n^{0.078}].$

By Bernstein’s inequality,

$\displaystyle\Pr[|\langle\delta,\phi_{i}v_{i}^{\prime}\rangle|\geq
n^{0.078}]$ $\displaystyle\leq
2\exp\Big{(}-\frac{n^{0.154}}{2n^{0.151}+2n^{0.078}}\Big{)}.$

This probability is small enough so that we can safely apply the union bound
over all such $i$’s.

We now move to the second and final case. We harness anti-concentration one
more time (for the proof see Section 4).

######  Claim 11.

There is a constant $C>0$ so that the following holds. Let $P$ be a product
distribution on $\\{\pm 1\\}^{n}$. Let $\sigma^{2}$ be the variance of
$\sum_{j}z_{j}$ for $z\sim P$. Assume that $\sigma^{2}>0$. For every vector
$v\in\mathbb{R}^{n}$ so that $\|v\|_{0}=n$ and $\gamma\in\mathbb{R}$, we have
$\Pr_{z\sim P}[\langle v,z\rangle=\gamma]\leq\frac{C}{\sigma}$.

Fix some $i$ so that $\sigma_{i}^{2}>n^{0.151}$. Let $J$ be the set of non-
zero coordinates in $v^{\prime}_{i}$. The variance of $\sum_{j\in
J}x^{\prime}_{j}$ is $\sigma_{J}^{2}=\sum_{j\in J}\tfrac{1-w_{j}^{2}}{4}$.
Using (2.1),

(2.4) $\displaystyle 4n^{-0.196}\sigma_{J}^{2}\geq\sum_{j\in
J}(1-w_{j}^{2})\phi^{2}_{i}{v^{\prime}_{ij}}^{2}=\sigma_{i}^{2}>n^{0.151}.$

By Claim 11, the probability that $\langle
x^{\prime},\phi_{i}v^{\prime}_{i}\rangle=\gamma_{i}$ is at most
$\frac{2C}{n^{0.1735}}$.

We need to justify the final union bound. By (2.1) again,

$\displaystyle\sum_{i\in K_{3}}\sigma_{i}^{2}=\sum_{j\in
N_{1}}(1-w_{j}^{2})\sum_{i\in
K_{3}}\phi_{i}^{2}{v^{\prime}_{ij}}^{2}<n^{-0.196}|N_{0}|\leq n^{0.324}.$

It follows that the number of $i$’s with $\sigma_{i}^{2}>n^{0.151}$ is at most
$n^{0.324-0.151}\leq n^{0.173}$. The probability that there exists $i$ with
$\sigma_{i}^{2}>n^{0.151}$ so that $\langle
x^{\prime},\phi_{i}v^{\prime}_{i}\rangle=\gamma_{i}$ is at most

$n^{0.173}\cdot\tfrac{2C}{n^{0.1735}}\leq n^{-0.0004}.\qed$

##  3\. Decomposing the matrix

For the proof of Lemma 3, we need a version of Lemma 13 in [13]. For
completeness, we include its proof below.

######  Lemma 12 ([13]).

Let $V\in\mathbb{R}^{k\times n}$ be a matrix so that $k\leq n^{0.52}$. Then,
there is a partition of the rows of $V$ to two parts $[k]=L_{1}\cup L_{2}$ and
a partition of the columns to two parts $[n]=M_{1}\cup M_{2}$ with
$|M_{2}|\leq n^{0.7171}$ such that the following hold:

  1. (1)

Let $V^{\prime}=(v^{\prime}_{ij})$ be the submatrix of $V$ defined by rows in
$L_{1}$ and columns in $M_{1}$; normalize the non-zero rows in $V^{\prime}$ to
have $\ell_{2}$-norm one. For every column $j\in M_{1}$, we have $\sum_{i\in
L_{1}}{v^{\prime}}^{2}_{ij}<n^{-0.196}$.

  2. (2)

Every row $i\in L_{2}$ has many scales, and the position of its smallest scale
contains the $M_{1}$ columns.

###### Proof.

We use the following terminology. The mass of a vector $w$ is $\|w\|_{2}^{2}$.
Initialize $L_{1}=[k],L_{2}=\emptyset,M_{1}=[n]$ and $M_{2}=\emptyset$. If
there is no column $j\in M_{1}$ with mass

$\sum_{i}{v_{ij}}^{2}\geq n^{-0.1961},$

then we are done. Otherwise, there are such columns. Start moving them one-by-
one from $M_{1}$ to $M_{2}$. When we move a column, the norm inside $M_{1}$ of
each row changes, but we do not immediately renormalize it.

Let $\tau>0$ be so that $\tfrac{1-\tau}{\tau}=C^{2}_{0}$, where $C_{0}$ is
from Definition 2. If for a given row $i\in L_{1}$, after the removal of a
column, the total current mass inside $M_{1}$ becomes less than $\tau$, then
mark a “drop” for row $i$. At the same time, if row $i$ is non-zero inside
$M_{1}$, renormalize it so that its norm inside $M_{1}$ is one.

When a drop occurs, we get one more scale for $v_{i}$, by the choice of
$\tau$. If a row is dropped more than $S=\lfloor n^{0.001}\rfloor$ times, then
move it from $L_{1}$ to $L_{2}$. Each row in $L_{2}$ has many scales and the
position of its minimum scale contains $M_{1}$.

Let $\sigma_{t}$ be the mass of the column that was added to $M_{2}$ at time
$t$, with the normalization at time $t$. So, for all $t$, we have
$\sigma_{t}\geq n^{-0.1961}$. If there are $T$ iterations, then

$\sum_{t}\sigma_{t}\geq n^{-0.1961}T.$

Let $\sigma_{t,i}$ be the contribution of row $i$ to $\sigma_{t}$; it is zero
if the row is in $L_{2}$ at time $t$. Because every row is dropped at most $S$
times, for each row $i$, we have $\sum_{t}\sigma_{t,i}<S$. So,

$\sum_{t}\sigma_{t}<Sk\leq n^{0.521}.$

After $T\leq n^{0.7171}$ steps, we get a matrix $V^{\prime}$ so that the mass
of every column $j\in M_{1}$ in it is

$\sum_{i\in L_{1}}{v^{\prime}_{ij}}^{2}<n^{-0.1961}.$

The rows of this matrix are not yet normalized. The norm of each row is either
zero or at least $\sqrt{\tau}$. The renormalization can not increase the norm
of the columns by more than $\frac{1}{\sqrt{\tau}}$. After the final
renormalization we get

$\sum_{i\in
L_{1}}{v^{\prime}_{ij}}^{2}<\frac{n^{-0.1961}}{\sqrt{\tau}}<n^{-0.196}.\qed$

###### Proof of Lemma 3.

We start by using the main lemma from [7] which is proved using polynomial
algebra. The lemma relies on the fact that
$v_{1},\mu_{1},\ldots,v_{k},\mu_{k}$ define an essential cover.

######  Lemma 13 ([7]).

For all $i\in[k]$, we have $\|v_{i}\|_{0}<2k$.

Lemma 13 implies that the total number of non-zero entries in $V$ is at most
$2k^{2}\leq\frac{n^{1.04}}{50}$. Let $N_{4}$ be the set of columns with more
than $n^{0.04}$ non-zero entries. Thus, $|N_{4}|\leq\frac{n}{50}$.

Construct a nested sequence of matrices $V^{(0)},V^{(1)},\ldots,V^{(T)}$ by
repeatedly applying Lemma 12 as follows. The matrix $V^{(0)}$ is obtained from
$V$ by removing the $N_{4}$ columns. All columns in $V^{(0)}$ are therefore
sparse. Apply Lemma 12 to $V^{(0)}$ to get $L_{1},L_{2}$ and $M_{1},M_{2}$.
Let $Z_{1}$ be the set of rows in $V^{(0)}$ so that their $M_{1}$ part is
zero. That is, for $i\in Z_{1}$ the projection $v_{i}|_{M_{1}}$ of $v_{i}$ to
the $M_{1}$ coordinates is zero. Rows in $Z_{1}$ may come from $L_{1}$ as well
as $L_{2}$. Let $k_{1}=|Z_{1}|$ and $n_{1}=|M_{2}|$. Check if the following
two conditions hold:

(3.1) $\displaystyle k_{1}>n_{1}^{0.332}$

and there is $i^{*}\in Z_{1}$ so that the projection of $v_{i^{*}}$ to
coordinates in $M_{2}$ has few non-zero entries:

(3.2) $\displaystyle\|v_{i^{*}}|_{M_{2}}\|_{0}\leq 4k_{1}^{2}.$

If (3.1) holds:

Let $L^{\prime}_{1}=[k]\setminus Z_{1}$. Let $V^{(1)}$ be the
$L^{\prime}_{1}\times M_{1}$ submatrix of $V^{(0)}$, and apply the same
procedure on $V^{(1)}$ to construct the matrices $V^{(2)},\ldots,V^{(T)}$.

If (3.1) does not hold but (3.2) holds:

Let $L^{\prime}_{1}=[k]\setminus\\{i^{*}\\}$ and let $M^{\prime}_{1}$ be the
zero coordinates of $v_{i^{*}}$. Let $V^{(1)}$ be the $L^{\prime}_{1}\times
M^{\prime}_{1}$ submatrix of $V^{(0)}$ and apply the procedure on $V^{(1)}$ to
get $V^{(2)},\ldots,V^{(T)}$.

If both conditions do not hold:

Output the $(L_{1}\setminus Z_{1})\times M_{1}$ submatrix of the input matrix
$V^{(0)}$.

We got a sequence of nested matrices $V^{(0)},\ldots,V^{(T)}$ and a
corresponding sequence $(n_{1},k_{1}),\ldots,(n_{T},k_{T})$. The matrix
$V^{(T)}$ satisfies both (3.1) and (3.2) but a priori it may be empty.

#### The partitions

It can be helpful to recall Figure 1.

Set $N_{3}$ to be the set of columns that are not in $V^{(T-1)}$; this
includes all the dense columns $N_{4}$, so that all columns not in $N_{3}$ are
sparse. Set $N_{2}$ to be the set of columns in $V^{(T-1)}$ but not in
$V^{(T)}$. And set $N_{1}$ to be the set of columns in $V^{(T)}$.

Set $K_{1}$ to be the set of rows outside $V^{(T-1)}$; the
$K_{1}\times(N_{1}\cup N_{2})$ submatrix of $V$ is zero. Set $K_{2}$ to be
$Z_{T}$; the $K_{2}\times N_{1}$ submatrix of $V$ is zero, and no row in the
$K_{2}\times N_{2}$ submatrix of $V$ is sparse (condition (3.2)). Set $K_{3}$
to be the rows inside $V^{(T)}$; the norm of the columns in the $K_{3}\times
N_{1}$ submatrix of $V$ can be bounded via item 1 in Lemma 12. Set $K_{4}$ to
be the non-zero rows with many scales in $V^{(T-1)}$ and not in $V^{(T)}$. No
row in the $(K_{3}\cup K_{4})\times N_{1}$ submatrix of $V$ is zero, by
construction of $Z_{T}$.

#### The size of $N_{1}$

We already know that $N_{4}$ is small. It remains to show that $N_{2}\cup
N_{3}$ is small as well. The total number of columns removed due to condition
(3.1) is smaller than $\frac{n}{8}$, because otherwise we get a contradiction
via the following claim.

######  Claim 14.

Let $\lambda\in(0,1]$ and $\xi_{1},\ldots,\xi_{m}\in[0,A]$ be so that
$\sum_{t\in[m]}\xi_{t}\geq B$ then
$\sum_{t\in[m]}\xi_{t}^{\lambda}\geq\tfrac{B}{2A}A^{\lambda}$.

###### Proof.

Partition $[m]$ to sets $R_{1},R_{2},\ldots,R_{Q}$ so that for all $q\in[Q]$
we have $A\leq\sum_{t\in R_{q}}\xi_{t}\leq 2A$ and $Q\geq\tfrac{B}{2A}$. Use
the inequality $\alpha^{\lambda}+\beta^{\lambda}\geq(\alpha+\beta)^{\lambda}$
that is valid for all $\alpha,\beta\geq 0$. For each $q$, we have $\sum_{t\in
R_{q}}\xi_{t}^{\lambda}\geq A^{\lambda}$. Summing over all $q$ completes the
proof. ∎

Denote by $\tau\subseteq[T]$ the set of times at which condition (3.1) is
applied. Summing over these times we get

$\displaystyle k\geq\sum_{t\in\tau}k_{t}\geq\sum_{t\in\tau}n_{t}^{0.332}.$

By Lemma 12, we know that $n_{t}\leq n^{0.7171}$ for all $t$. The condition
$\sum_{t\in\tau}n_{t}\geq\tfrac{n}{8}$ hence implies

$\displaystyle\sum_{t\in\tau}n_{t}^{0.332}\geq\frac{n}{16n^{0.7171}}\cdot(n^{0.7171})^{0.332}\geq
n^{0.52},$

which is a contradiction.

The total number of columns removed when (3.1) does not hold and (3.2) holds
can be bounded as follows. Because the number of $t\not\in\tau$ is at most
$k$, and because $n_{t}\leq n^{0.7171}$ for all $t$, the number of columns is
at most

$\sum_{t\not\in\tau}4k^{2}_{t}\leq\sum_{t\not\in\tau}4n_{t}^{0.664}\leq
4n^{0.477}k<\frac{n}{8}.\qed$

##  4\. Antichains

Here we prove the last anti-concentration bound we need (Claim 11). The set
$\\{\pm 1\\}^{n}$ has a standard partial order: $x\leq y$ iff $x_{j}\leq
y_{j}$ for all $j\in[n]$. An antichain in $\\{\pm 1\\}^{n}$ is a set of
incomparable vertices. The following theorem states that antichains do not
have large mass in general product measures.111The assumption that $P$ is non-
trivial in the theorem from [13] can be removed by restricting to the non-
trivial part of $P$.

######  Theorem 15 ([13]).

There is a constant $C>0$ so that the following holds. Let $P$ be a product
distribution on $\\{\pm 1\\}^{n}$. Assume that the variance $\sigma_{P}^{2}$
of $\sum_{j}z_{j}$ for $z\sim P$ is positive. Then, for every antichain
$A\subset\\{\pm 1\\}^{n}$, we have $\Pr_{z\sim P}[z\in
A]\leq\frac{C}{\sigma_{P}}$.

###### Proof of Claim 11.

Let $s\in\\{\pm 1\\}^{n}$ be so that $s_{j}v_{j}>0$ for all $j$. Let
$P^{\prime}$ be the distribution of $z^{\prime}=z\odot s$ where $z\sim P$ and
$\odot$ is coordinate-wise multiplication. The distribution $P^{\prime}$ is a
product distribution and $\sigma_{P}=\sigma_{P^{\prime}}$. Because $\langle
z^{\prime},v\odot s\rangle=\langle z,v\rangle$, we need to bound $\Pr[\langle
z^{\prime},v\odot s\rangle=\mu]$. The set $A$ of vertices $x$ so that $\langle
x,v\odot s\rangle=\mu$ is an antichain. The reason is that if $x<y$ then
$\langle x,v\odot s\rangle<\langle y,v\odot s\rangle$. Theorem 15 completes
the proof. ∎

### Acknowledgement

We thank Nati Linial for helpful conversations.

## References

  * [1] Noga Alon and Zoltán Füredi, _Covering the cube by affine hyperplanes_ , European journal of combinatorics 14 (1993), no. 2, 79–83.
  * [2] Keith Ball, _The plank problem for symmetric bodies_ , Inventiones mathematicae 104 (1991), no. 1, 535–543.
  * [3] Thøger Bang, _A solution of the “plank problem”_ , Proceedings of the American Mathematical Society 2 (1951), no. 6, 990–993.
  * [4] Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, and Robert Robere, _Stabbing planes_ , arXiv:1710.03219 (2017).
  * [5] Stefan Dantchev, Nicola Galesi, Abdul Ghani, and Barnaby Martin, _Depth lower bounds in stabbing planes for combinatorial principles_ , arXiv:2102.07622 (2021).
  * [6] Paul Erdös, _On a lemma of Littlewood and Offord_ , Bulletin of the American Mathematical Society 51 (1945), no. 12, 898–902.
  * [7] Nathan Linial and Jaikumar Radhakrishnan, _Essential covers of the cube by hyperplanes_ , Journal of Combinatorial Theory, Series A 109 (2005), no. 2, 331–338.
  * [8] John E. Littlewood and Albert C. Offord, _On the number of real roots of a random algebraic equation. II_ , Mathematical Proceedings of the Cambridge Philosophical Society, vol. 35, Cambridge University Press, 1939, pp. 133–148.
  * [9] Fedor Part and Iddo Tzameret, _Resolution with counting: Dag-like lower bounds and different moduli_ , Computational Complexity 30 (2021), no. 1, 1–71.
  * [10] Ran Raz and Iddo Tzameret, _Resolution over linear equations and multilinear proofs_ , Annals of Pure and Applied Logic 155 (2008), no. 3, 194–224.
  * [11] Michael E. Saks, _Slicing the hypercube_ , London Mathematical Society Lecture Note Series, pp. 211–256, Cambridge University Press, 1993.
  * [12] David Saxton, _Essential positive covers of the cube_ , Journal of Combinatorial Theory, Series A 120 (2013), no. 5, 971–975.
  * [13] Gal Yehuda and Amir Yehudayoff, _Slicing the hypercube is not easy_ , arXiv:2102.05536 (2021).