11institutetext: Universidad de Chile, Santiago, Chile 22institutetext: AMTC,
Santiago, Chile
22email<EMAIL_ADDRESS>
# YotoR-You Only Transform One Representation

José Ignacio Díaz Villa 11 0009-0005-4531-2336 Patricio Loncomilla 22
1111-2222-3333-4444 Javier Ruiz-del-Solar 1122 2222–3333-4444-5555

###### Abstract

This paper introduces YotoR (You Only Transform One Representation), a novel
deep learning model for object detection that combines Swin Transformers and
YoloR architectures. Transformers, a revolutionary technology in natural
language processing, have also significantly impacted computer vision,
offering the potential to enhance accuracy and computational efficiency. YotoR
combines the robust Swin Transformer backbone with the YoloR neck and head. In
our experiments, YotoR models TP5 and BP4 consistently outperform YoloR P6 and
Swin Transformers in various evaluations, delivering improved object detection
performance and faster inference speeds than Swin Transformer models. These
results highlight the potential for further model combinations and
improvements in real-time object detection with Transformers. The paper
concludes by emphasizing the broader implications of YotoR, including its
potential to enhance transformer-based models for image-related tasks.

###### Keywords:

Object Detection Transformers Yolo

##  1 Introduction

Convolutional neural networks have revolutionized computer vision applications
in the last decade, enabling task-solving like object detection, image
segmentation, and instance segmentation, among others. Despite the improvement
of the convolutional network backbones in recent years, even surpassing human
performance for several tasks, the use of Transformers [22] in computer vision
tasks remained elusive for several years.

The first application of transformers for computer vision tasks was proposed
in 2020 [8]. However, because of the high resolution of images, the use of
Transformers was limited to low-resolution applications like image
classification. High-resolution tasks like object detection required the
development of more specialized Transformers architectures like the Swin
Transformer [16], which circumvent the computing limitations of Transformers
by dynamically changing the attention window and allowing them to be used as a
general purpose backbone for multiple vision tasks. Also, object detector
heads based on transformers like DETR [3] have become state-of-the-art in
tasks previously dominated by convolutional neural networks.

On the other hand, real-time object detectors, exemplified by the Yolo / YoloR
family [19] [25], remain indispensable for tasks dependent on high frame
rates, such as autonomous driving, or on platforms constrained by limited
hardware resources. Despite recent advancements in Transformers for computer
vision, real-time object detection predominantly relies on convolutional
neural networks. Their established reliability and computational efficiency in
feature extraction have been a challenge for Transformers to overcome. Then,
combining transformers with Yolo-like object detectors could deliver novel
architectures able to achieve both high frame rates and high detection
accuracies.

This paper introduces YotoR (You Only Transform One Representation), a novel
deep learning model for object detection that combines Swin Transformers and
YoloR architectures. YotoR combines the robust Swin Transformer backbone with
the YoloR neck and head. In our experiments, YotoR models TP5 and BP4
consistently outperform YoloR P6 and Swin Transformers in various evaluations,
delivering improved object detection performance and faster inference speeds
than Swin Transformer models. These results highlight the potential for
further model combinations and improvements in real-time object detection with
Transformers.

The contributions of this paper are:

1) A new family of object detection architectures named YotoR, which is
composed of backbones based on Swin Transformers and heads based on YoloR.

2) An exhaustive evaluation of different YotoR variants, which shows that
YotoR models TP5 and BP4 consistently outperform YoloR P6 and Swin
Transformers in various evaluations that consider both object detection
performance and inference speed.

The code will be released upon acceptance of the paper.

##  2 Related work

###  2.1 Real-time CNN-based object detection

CNN-based object detectors, which started with Faster R-CNN [20], have become
a widely used approach to solving object detection tasks. In some
applications, in which real-time processing is needed or there are hardware
limitations, lightweight object detectors are needed.

The most widely used real-time object detectors are based on FCOS [21] or the
YOLO family of detectors [19] [23]. Progress in this area has been made by
improving the backbones, the necks, the detection heads, the loss functions,
and the training procedures used. The backbone is the section of the network
whose task is to obtain embeddings that encode the input images. In the case
of the backbones, the improvements have been led by the use of building blocks
inspired by RepVGG [7], CSP [24], ELAN [4], and VoVNet [13]. The task of the
neck is to further process the embeddings to make them useful for generating
the detections. In the case of the necks, the most successful approaches are
inspired by RepVGG [7] and PAN [18]. Finally, the detection heads generate the
output detections of the network. In the case of the YOLO family of detectors,
there are several heads, each one dedicated to detecting objects of different
sizes. Then, a good design of the backbones, necks, and detection heads is
critical for obtaining architectures capable of performing real-time detection
without sacrificing performance.

###  2.2 Multi-task-oriented real-time CNN architectures

The use of multi-task architectures is promising, as they can integrate
several information modalities for improving performance on all of the tasks.
However, designing architectures able to perform multiple tasks in real time
is challenging because using ensembles of per-task networks negatively affects
the runtime of the system.

An architecture named YoloR [25] was proposed to solve real-time multitask
problems. The system is based on using a single unified architecture for
solving several tasks. YoloR is based on modeling two sources of knowledge:
explicit knowledge and implicit knowledge. Traditionally, explicit knowledge
is strongly tied to the inputs of the network, and it is represented by the
first layers of the network, while the dependence of the implicit knowledge on
the inputs is lower, and it is encoded by the deeper layers. For achieving
multi-task capabilities with a unified architecture, it is proposed that
instead the explicit knowledge is modeled by weights shared by all of the
input modalities, while the implicit knowledge is modeled as input-independent
parameters in deep layers of the network. The weights related to the implicit
knowledge can modify the internal network embeddings by applying operations
like concatenation, addition, and multiplication. By using this approach, a
single network architecture can benefit from being trained for multiple tasks,
as the network weights related to the explicit knowledge can condense the
information from all of the input modalities at the same time.

(a) Traditional multi-task architecture with a single analyzer.

(b) Unified multi-task network with explicit and implicit knowledge.

Figure 1: Diagrams of the different approaches to a multi-task network as
proposed by YoloR.

###  2.3 Transformer-based object detection

While transformers have been used successfully in natural language processing
[22], their use in computer vision has been delayed because the amount of
computing processing needed squares quadratically with the number of tokens
(patches) in the image. The first work which used plain ViT (visual
transformers) for classification [8] used patches of size 16x16 as tokens, and
the transformer architecture consisted of a sequence of encoders. Despite the
ViTs being able to process all of the tokens at the same time, they have no
inductive biases like translation invariance, which are intrinsic to the CNNs
architectures. Then, the largest ViT model proposed in that work needed over
300M images to achieve a better performance than state-of-the-art CNN models
like ResNets trained with BiT [12]. Also, the problems of the quadratic
increase in computational computing power by the number of tokens, the large
size of the patches, and the lack of multiscale processing cause the plain ViT
architecture to be unable to be used for tasks like object detection or image
segmentation.

An efficient visual-transformer-based backbone able to replace CNN-based ones,
named Swin Transformer, was proposed in [16]. Swin transformers work by using
small patches with size $4\times 4$ as tokens and dividing the image into
windows. Then, an encoder is applied to all of the tokens contained on each of
the windows independently. This strategy enables the computing power
requirement to remain low. As the windows are processed independently, their
information must be combined in subsequent layers of the network. Then, after
the application of encoders on the windows of a layer, the windows of the
following layer are shifted. In other words, each window in a layer can
integrate information from four windows in the previous layer. Also, after the
application of a nonshifted and a shifted window layer, the tokens are merged,
which increases the embedding dimension while decreasing the number of tokens.
Also, the patch merging strategy enables the architecture to generate feature
pyramids which are useful for tasks involving multiscale processing. Then,
Swin transformers can be used instead of CNN-based backbones for tasks like
object detection, object instance segmentation, and semantic segmentation.

In recent years, there has been a surge in proposals suggesting innovative
combinations of architectures featuring Transformers for object detection.
Notably, the authors of [27] present a distinctive fusion involving the
anchor-free implementation of YOLO, namely YOLOX [10], and the Swin
Transformer. An increase of 6.1% in the mAP performance in their private
dataset was observed for the detection of obstacles for autonomous driving,
setting a good precedent for the combination of the Swin Transformer backbone
with the Yolo family of detectors. Our proposal differs from the YOLOX-S
models by keeping the YoloV3 anchors on the detection heads and implementing
the improvements added by YoloV4 and YoloR like the new BoG and BoS techniques
and the implicit knowledge modeling. Also, the proposed method was trained on
the MSCOCO dataset to directly compare with the rest of the state-of-the-art.

Another strong contender has been the DETR [3] family of transformer-based
object detection architectures, with some variants like the Co-DETR [28]
achieving state-of-the-art performance. The DETR works by using an encoder-
decoder Transformer over features extracted by a backbone. This allows the
model to achieve better accuracy and the ability to handle complex relations
between the objects while keeping a simple structure for the architecture.

##  3 YotoR

In this work, a family of network architectures is introduced that merges the
Swin Transformer backbone with the YoloR head. Inspired by Yolo’s
nomenclature, these architectures are named YotoR, short for "You Only
Transform One Representation". This reflects the use of a single unified
representation generated by Transformer blocks, versatile and suitable for
multiple tasks. The idea behind this proposal is to use the powerful Swin
Transformers feature extraction to improve detection accuracy, while also
having the ability to solve multiple tasks with fast inference times by using
the YoloR heads.

YotoR models following the YoloR architecture are named using the following
convention:

YotoR {Backbone Swin}{Head YoloR}{# Blocks}

For a clearer understanding, consider the following examples:

  * •

YotoR TP5 has a Swin-T backbone, YoloR P6 head and neck, and a 5-block
backbone.

  * •

YotoR BP4 has a Swin-B backbone, YoloR P6 head and neck, and a 4-block
backbone.

  * •

YotoR LD4 has a Swin-L backbone, YoloR D6 head and neck, and a 4-block
backbone.

Similar to the relationship between YoloR and its base model P6, YotoR TP4 is
the starting point for YotoR models, representing the most basic combination
of components.

Using the unaltered SwinT backbone also comes with a significant advantage,
allowing for the application of transfer learning techniques. This is because,
by not altering the Swin Transformer’s structure, the publicly provided
weights from its creators can be used. This simplifies the transfer of pre-
trained Swin Transformer weights onto other datasets, speeding up the training
process and improving performance.

###  3.1 Architecture

####  3.1.1 Backbone:

In Figure 2, the Swin Transformer’s simplified architecture used for the
backbone is presented, particularly the T (tiny) version known as Swin T. The
main part of the architecture has four stages; it starts by dividing the image
into small $4\times 4\times 3$ patches, which are then transformed into
tokens. These tokens go through a linear embedding layer to convert them into
tokens with a certain size, referred to as $C$, which are then fed into the
first Swin Transformer Block array that constitutes the first stage. The other
three are composed of a patch merging block that merges patches by $2\times 2$
groups, reducing the feature maps width and height resolution by half, which
is then passed on to a corresponding array of Swin Transformer Blocks.

Apart from Swin T, there are three more architectures: Swin S, Swin B, and
Swin L. They are quite similar but differ in the number of Swin Transformer
Blocks and channels. The details for each architecture can be found in Table
1.

For the object detection task in the Swin Transformer article [16], Mask R-CNN
[11] and Cascade R-CNN [2] were the main heads used. In models B and L, they
also used a framework named HTC++, which includes HTC [5], instaboost [9], and
more advanced training methods with higher resolutions. While HTC++ gives
better results, it is worth noting that it has not been made publicly
available. Therefore, most of our focus will be on models without HTC++,
unless we specify otherwise.

Figure 2: Diagram of the Swin Transformer T backbone. Table 1: Specification of the Swin Transformer architecture. |  | output
---
size
Swin-T | Swin-S | Swin-B | Swin-L
stage 1 |  4x (56x56) |  | concat 4x4,
---
96-d, LN
| concat 4x4,
---
96-d, LN
| concat 4x4,
---
128-d, LN
| concat 4x4,
---
192-d, LN
|  | [ws 7x7,
---
dim 96,
head 3]
x2 |  | [ws 7x7,
---
dim 96,
head 3]
x2 |  | [ws 7x7,
---
dim 128,
head 4]
x2 |  | [ws 7x7,
---
dim 192,
head 6]
x2
stage 2 |  8x (28x28) |  | concat 2x2,
---
192-d, LN
| concat 2x2,
---
192-d, LN
| concat 2x2,
---
256-d, LN
| concat 2x2,
---
384-d, LN
|  | [ws 7x7,
---
dim 192,
head 6]
x2 |  | [ws 7x7,
---
dim 192,
head 6]
x2 |  | [ws 7x7,
---
dim 256,
head 8]
x2 |  | [ws 7x7,
---
dim 384,
head 12]
x2
stage 3 |  16x (14x14) |  | concat 2x2,
---
384-d, LN
| concat 2x2,
---
384-d, LN
| concat 2x2,
---
512-d, LN
| concat 2x2,
---
768-d, LN
|  | [ws 7x7,
---
dim 384,
head 12]
x6 |  | [ws 7x7,
---
dim 384,
head 12]
x18 |  | [ws 7x7,
---
dim 512,
head 16]
x18 |  | [ws 7x7,
---
dim 768,
head 24]
x18
stage 4 |  32x (7x7) |  | concat 2x2,
---
768-d, LN
| concat 2x2,
---
768-d, LN
| concat 2x2,
---
1024-d, LN
| concat 2x2,
---
1536-d, LN
|  | [ws 7x7,
---
dim 768,
head 24]
x2 |  | [ws 7x7,
---
dim 768,
head 24]
x2 |  | [ws 7x7,
---
dim 1024,
head 32]
x2 |  | [ws 7x7,
---
dim 1536,
head 48]
x2

####  3.1.2 Head

To build the YoloR models, the authors decided to base them on the
architecture of Scaled YoloV4 [1]. In particular, they started with
YoloV4-P6-light as their foundation and sequentially modified it to create
different versions of YoloR: P6, W6, E6, and D6. The changes between each of
these versions are as follows:

  * •

YoloR-P6: Replaced the Mish activation functions of YoloV4-P6-light with SiLU.

  * •

YoloR-W6: Increased the number of channels in the outputs of the backbone
blocks.

  * •

YoloR-E6: Multiplied the number of channels from W6 by 1.25 and replaced the
downsampling convolutions with CSP convolutions [24].

  * •

YoloR-D6: Increased the depth of the backbone.

####  3.1.3 YotoR models

Selecting the YotoR models for implementation involved considering two
essential aspects. Firstly, the discrepancy between the feature pyramid
dimensions generated by the Swin Transformer backbone and the dimensions
required by the YoloR head was analyzed. A significant disparity between these
dimensions could create bottlenecks in the network, limiting its performance.
Second, to adapt the connections, the Swin Transformer features had to be re-
shaped back to images with the attention maps. This is then normalized and
passed through a $1\times 1$ convolution to adjust the number of channels.
This is done to give the YoloR head the same feature size as the DarknetCSP
backbone [1] and to soften the information bottlenecks between the
connections.

Based on these considerations, we selected the YotoR TP4, YotoR TP5, YotoR
BP4, and YotoR BB4 models, which are described below:

  * •

YotoR TP4

The smallest model among the proposed combinations, YotoR TP4, uses a Swin
Transformer Tiny backbone with the YoloR P6 head and neck. However, this
combination poses a challenge because the connections between these parts have
drastically different dimensions, potentially leading to information
bottlenecks.

  * •

YotoR TP5

To address the bottleneck issue in YotoR TP4, it was decided to retain the B6
block, which matches the last CSPDarknet block in the YoloR backbone. This
choice allowed for more coherent connections between both parts, preventing
information loss in the transition to the neck. The "5" in its name refers to
the inclusion of the additional B6 CSPDarknet block in addition to the four
Swin Transformer blocks.

  * •

YotoR BP4

It follows a similar premise and structure as YotoR TP4, but it replaces the
Swin Transformer Tiny (T) backbone with a Swin Transformer Basic (B) backbone.
The decision to opt directly for the Basic backbone, rather than the Small (S)
backbone, is based on the similarity in connection sizes with the YoloR P6
backbone to avoid connection discrepancies, as the case in YotoR TP4.

  * •

YotoR BB4

As the final proposed model, YotoR BB4 takes a different approach to its
design. Instead of adapting the connections between the YoloR P6 neck and the
Swin B backbone, we decided to completely redesign the P6 head, following the
dimensions of the Swin B embeddings. This results in an expansion of
dimensions in the deeper parts of the network while reducing them in the
shallower layers. In YotoR BB4, all model dimensions are directly in
accordance, with no adapting convolutional layers, unlike the previous models.

Figure 3 shows the YotoR BP4 architecture. It introduces the STB (Swin
Transformer Block), representing the Swin Transformer blocks used in the
different YotoR architectures. Additionally, there is an inclusion of a Linear
Embedding block between these components. This Linear Embedding block comes
from the Swin Transformer implementation for object detection and is
incorporated into the YotoR implementation without alterations.

These four models were chosen because they are composed of the base
architectures of YoloR and Swin Transformer, allowing for a valid comparison
to assess the proposed model’s validity. While training and evaluating larger
models like YotoR BW4 or YotoR BW5 were considered, resource limitations on a
V100 GPU made this option unfeasible.

Figure 3: Architecture of YotoR BP4.

##  4 Experimental Results

The experiments to test and compare the models were implemented on the MSCOCO
dataset. This dataset was chosen because of its common use for benchmarking
object detectors.

###  4.1 Experimental Setup

Both training and evaluation were performed on a V100 GPU with 32 GB and 16 GB
respectively. 111All provided speed evaluations of the implemented models were
performed on a similar V100 GPU with 16 GB and no TensorRT, and are therefore
not directly comparable with those reported by other groups on COCO val2017
The training parameters used are the same as YoloR as shown in Table 2. The
YoloR training schedule was followed and trained for 300 epochs first, then
fine-tuned using 125 epochs, and finally trained for an extra 25 epochs using
a lower mosaic count.

Table 2: Training parameters. Parameter | Training | Tuning | End
---|---|---|---
num epochs | 300 | 125 | 25
initial learning rate | 0.01 | 0.01 | 0.01
final learning rate | 0.2 | 0.2 | 0.2
momentum | 0.937 | 0.937 | 0.937
optimizer weight decay | 0.0005 | 0.0005 | 0.0005
warmup epochs | 3.0 | 3.0 | 3.0
warmup initial momentum | 0.8 | 0.8 | 0.8
warmup initial bias lr | 0.1 | 0.1 | 0.1
box loss gain | 0.05 | 0.05 | 0.05
cls loss gain | 0.5 | 0.5 | 0.5
cls BCELoss positive_weight | 1.0 | 1.0 | 1.0
obj loss gain | 1.0 | 1.0 | 1.0
obj BCELoss positive weight | 1.0 | 1.0 | 1.0
IoU training threshold | 0.2 | 0.2 | 0.2
anchor-multiple threshold | 4.0 | 4.0 | 4.0
focal loss gamma | 0.0 | 0.0 | 0.0
image HSV-Hue augmentation | 0.015 | 0.015 | 0.015
image HSV-Saturation augmentation | 0.7 | 0.7 | 0.7
image HSV-Value augmentation | 0.4 | 0.4 | 0.4
image rotation | 0.0 | 0.0 | 0.0
image translation | 0.5 | 0.5 | 0.5
image scale | 0.5 | 0.8 | 0.8
image shear | 0.0 | 0.0 | 0.0
perspective | 0.0 | 0.0 | 0.0
image flip up-down | 0.0 | 0.0 | 0.0
image flip left-right | 0.5 | 0.5 | 0.5
image mosaic probability | 1.0 | 1.0 | 1.0
image mosaic quantity | 4.0 | 9.0 | 4.0
image mixup | 0.0 | 0.2 | 0.2

###  4.2 Results of Inference Speed

From the results shown in Table 5, it is clear that none of the YotoR models
can match the speed of YoloR. However, all the YotoR models have increased
inference speeds compared to their respective Swin backbones. In particular,
TP5 is notable for its inference frame rate that more than doubles compared to
Swin-T, while BP4 and BB4 increase by just over 80% to Swin B.

Due to significant variation in time measurements across models, we conducted
all timing evaluations on a consistent platform: a 16GB V100 GPU, operating at
a resolution of $1280\times 1280$, without non-maximum suppression (NMS) or
TensorRT acceleration. Each timing measurement represents the mean of three
consecutive runs performed sequentially within a single session. Despite our
best efforts, the recorded times were approximately half of those reported in
the papers for YoloR and Swin Transformer models. This suggests that there is
potential to double the speed results through further optimization.

Table 3: Results of the inference speed evaluation. model | inference time (ms) | frames per second (fps)
---|---|---
Swin T | 135.1 | 7.4
Swin B | 196.1 | 5.1
YoloR P6 | 34.7 | 28.8
YotoR TP4 | 51.9 | 19.3
YotoR TP5 | 48.6 | 20.6
YotoR BP4 | 106.2 | 9.4
YotoR BB4 | 103.9 | 9.6

###  4.3 Results on COCO val2017

The mAP (mean Average Precision) of the four YotoR models on val2017 is shown
in Table 5. TP5 and BP4 models outperform all the baselines, even YoloR P6,
which serves as a reference due to its high mAP performance. The only model
that does not surpass it is BB4. However, considering that BB4 is built solely
from Swin B without using the YoloR P6 head, this result was expected.
However, BB4 manages to outperform Swin B in terms of performance, suggesting
the possibility of exploring solutions in larger models such as Swin L, which
surpasses the performance of YoloR D6.

The advantages of YotoR models become evident when comparing inference time in
milliseconds with mAP, as shown in Figure 4. It allows us to analyze the
relationship between inference speed and model performance, which is essential
because there is typically a trade-off between both. Speed tends to decrease
when aiming for higher accuracy, and vice versa. In this figure, it is clear
how all the YotoR models outperform their equivalent Swin detectors in both
performance and speed, representing a significant improvement for all these
models. Although YoloR P6 still has a considerable advantage in inference
time, its performance can be surpassed by YotoR TP5 and YotoR BP4, despite
using the same head architecture.

Figure 4: Comparison between the time and mAP of each model in COCO val2017. Table 4: Evaluation results in val2017. |  |  |  | Swin T | Swin B | YoloR P6 | YotoR TP4 | YotoR TP5 | YotoR BP4 | YotoR BB4
---|---|---|---|---|---|---|---|---|---|---
AP | IoU=.5:.95 | area=all | maxDets=100 | 0.505 | 0.519 | 0.525 | 0.234 | 0.529 | 0.533 | 0.523
AP | IoU=.5 | area=all | maxDets=100 | 0.693 | 0.705 | 0.707 | 0.555 | 0.712 | 0.720 | 0.713
AP | IoU=.75 | area=all | maxDets=100 | 0.549 | 0.564 | 0.575 | 0.163 | 0.580 | 0.583 | 0.569
AP | IoU=.5:.95 | area=s | maxDets=100 | - | 0.354 | 0.371 | 0.138 | 0.384 | 0.388 | 0.369
AP | IoU=.5:.95 | area=m | maxDets=100 | - | 0.552 | 0.569 | 0.251 | 0.576 | 0.577 | 0.567
AP | IoU=.5:.95 | area=l | maxDets=100 | - | 0.673 | 0.661 | 0.352 | 0.661 | 0.675 | 0.673
AR | IoU=.5:.95 | area=all | maxDets= 1 | - | 0.638 | 0.392 | 0.196 | 0.391 | 0.390 | 0.388
AR | IoU=.5:.95 | area=all | maxDets= 10 | - | 0.638 | 0.652 | 0.433 | 0.643 | 0.639 | 0.631
AR | IoU=.5:.95 | area=all | maxDets=100 | - | 0.638 | 0.714 | 0.523 | 0.699 | 0.693 | 0.683
AR | IoU=.5:.95 | area=s | maxDets=100 | - | 0.478 | 0.578 | 0.373 | 0.567 | 0.553 | 0.534
AR | IoU=.5:.95 | area=m | maxDets=100 | - | 0.673 | 0.753 | 0.576 | 0.738 | 0.732 | 0.721
AR | IoU=.5:.95 | area=l | maxDets=100 | - | 0.782 | 0.840 | 0.648 | 0.820 | 0.818 | 0.818

###  4.4 Results on COCO testdev

Looking at Table 6, it can be observed that the YotoR models TP5 and BP4
outperform the YoloR P6 model in all mAP metrics. This confirms the
significant improvement in the performance of these models. These results are
publicly available thanks to the CodaLab team, making it easy to compare them
with other participants in the COCO competition.

In addition to the traditional metrics, Table 6 includes measurements of FLOPs
(Floating-Point Operations) and the number of parameters for each model, which
provide interesting insights. YotoR models have fewer FLOPs than YoloR P6,
even though they have longer inference times. This could be explained by the
nature of floating-point operations in YotoR, which, although less numerous,
might be more computationally intensive or less optimized than those in YoloR.
This suggests the potential for optimizing the inference time of YotoR models
by improving their operations. On the other hand, the number of parameters in
YotoR models falls in between Swin and YoloR models, as expected, since they
combine elements from both.

These results are promising, especially when considering that the YotoR models
were implemented using the most basic versions of YoloR and the Swin
Transformer. This opens the door to exploring new combinations between models
from the YOLO family and Swin Transformer, either to create a real-time object
detection model with Transformers or to advance the state of the art in
performance.

Table 5: Results comparing the YotoR models and the baselines. | YotoR Tp5 | YotoR Bp4 | YotoR BB4
---|---|---|---
| mAP.5:.95 |  | FPS |  | mAP.5:.95 |  | FPS |  | mAP.5:.95 |  | FPS |
| 52.9% | 20.6 | 53.6% | 9.4 | 52.3% | 9.6
Swin T | 50.4% | +2.5% | 7.4 | +178% | 50.4% | +3.2% | 7.4 | +27% | 50.4% | +1.9% | 7.4 | +30%
Swin B | 51.9% | +1.0% | 5.1 | +303% | 51.9% | +1.7% | 5.1 | +84% | 51.9% | +0.4% | 5.1 | +88%
YoloR P6 | 52.5% | +0.4% | 28.8 | \- 28% | 52.5% | +1.1% | 28.8 | \- 70% | 52.5% | \- 0.3% | 28.8 | \- 67%
Table 6: Comparison of YotoR in testdev Model | Size | FPS | FLOPs | # parameters | $AP^{test}$ | $AP^{test}_{50}$ | $AP^{test}_{75}$ | $AP^{test}_{S}$ | $AP^{test}_{M}$ | $AP^{test}_{L}$
---|---|---|---|---|---|---|---|---|---|---
YoloR P6 | 1280 | 28.8 | 326G | 37M | 52.6% | 70.6% | 57.6% | 34.7% | 56.6% | 64.2%
Swin T | 1280 | 7.4 | 745G | 86M | - | - | - | - | - | -
Swin B | 1280 | 5.1 | 982G | 145M | - | - | - | - | - | -
YotoR TP5 | 1280 | 20.6 | 107G | 56M | 52.9% | 70.9% | 57.7% | 35.3% | 56.5% | 64.7%
YotoR BP4 | 1280 | 9.4 | 296G | 117M | 53.4% | 71.8% | 58.2% | 35.1% | 57.1% | 66.5%
YotoR BB4 | 1280 | 9.6 | 281G | 131M | 52.4% | 71.0% | 57.1% | 33.8% | 56.1% | 65.7

In Figure 5, we showcase instances of detections executed by the YotoR BP4
model on the val2017 and testdev datasets. These examples demonstrate the
model’s proficiency in effectively detecting objects of varying sizes, even
when they overlap within a group.

Figure 5: Left: Images from val2017 and testdev. Right: Predictions from YotoR
BP4.

###  4.5 Comparison with the state of the art

In Table 7, we present a detailed comparison between the YotoR models and
various state-of-the-art object detection models, which encompass different
sizes and architectures. Our focus specifically centers on models of similar
sizes and structures. This table provides insights into the performance of
these models in both the COCO val2017 and testdev datasets.

While it is evident that the YotoR models exhibit lower performance compared
to some of the latest and larger models, it is important to note that only the
smaller versions of YotoR were implemented, featuring the smallest number of
channels in the connections. This choice accounts for their comparatively
lower performance compared to YoloR-W6, YOLOv7-W6, and their larger variants.
Despite this, the YotoR models still outperform its individual components like
YoloR-P6 and Swin Transformer B. It is worth mentioning that the performance
surpasses that of the Swin Transformer without HTC++, albeit with certain
details not publicly disclosed and some adaptations made to the YoloR head for
processing images of varying resolutions.

In essence, the YotoR models appear to strike a commendable balance between
performance and speed. It’s noteworthy that this equilibrium could potentially
be further optimized by incorporating larger models within the YotoR family,
such as YotoR LE5 or YotoR LD5. The implementation of these larger variants
holds promise for enhancing the competitiveness of the models, opening up
intriguing avenues for future exploration.

Table 7: Comparison with the state of the art (batch=1, GPU=V100). * indicates our own confirmed measurements using a 16GB V100 GPU . model | # parameters | FLOPs | size | $FPS^{V100}$ | $AP^{val}$ | $AP^{test}$ | $AP^{test}_{50}$ | $AP^{test}_{75}$
---|---|---|---|---|---|---|---|---
YOTOR-TP4 | 55M | 111.5G | 1280 | 19.3* | 23.9% | 23.5% | 54.9% | 15.7%
YOTOR-TP5 | 56M | 107G | 1280 | 20.6* | 52.9 % | 52.9 % | 70.9 % | 57.7 %
YOTOR-BP4 | 117M | 296G | 1280 | 9.4* | 53.6 % | 53.4 % | 71.8 % | 58.2 %
YOTOR-BB4 | 131M | 281G | 1280 | 9.6* | 52.3 % | 52.4 % | 71.0 % | 57.1 %
YOLOR-P6 | 37M | 326G | 1280 | 76/28.8* | 52.5% | 52.6% | 70.6% | 57.6%
YOLOR-P6D | 37M | 326G | 1280 |  | - | 53.0% | 71.0% | 58.0%
YOLOR-W6 | 80M | 454G | 1280 | 66 | 54.0% | 54.1% | 72.0% | 59.2%
YOLOR-E6 | 116M | 684G | 1280 | 45 | 54.6% | 54.8% | 72.7% | 60.0%
YOLOR-D6 | 152M | 937G | 1280 | 34 | 55.4% | 55.4% | 73.3% | 60.6%
YOLOv7 | 36.9M | 104.7G | 640 | 161 | 51.2% | 51.4% | 69.7% | 55.9%
YOLOv7-W6 | 70.4M | 360.0G | 1280 | 84 | 54.6% | 54.9% | 72.6% | 60.1%
YOLOv7-E6 | 97.2M | 515.2G | 1280 | 56 | 55.9% | 56.0% | 73.5% | 61.2%
YOLOv7-D6 | 154.7M | 806.8G | 1280 | 44 | 56.3% | 56.6% | 74.0% | 61.8%
YOLOv4-CSP-P5 [1] | 71M | 328G | 896 | 41 | 51.7% | 51.8% | 70.3% | 56.6%
YOLOv4-CSP-P6 [1] | 128M | 718G | 1280 | 30 | 54.4% | 54.5% | 72.6% | 59.8%
YOLOv4-CSP-P7 [1] | 287M | 1639G | 1536 | 16 | 55.3% | 55.5% | 73.4% | 60.8%
YOLOv6-L6 [14] | 140M | 773.4G | - | 26 | 57.2% | - | - | -
PRB-FPN6-E-ELAN [6] | - | - | - | 31 | - | 56.9% | 74.1% | 62.7%
Swin T-T (C-M-RCNN) | 86M | 745G | - | 15.3/7.4* | 50.5% | - | - | -
Swin T-S (C-M-RCNN) | 107M | 838G | - | 12 | 51.8% | - | - | -
Swin T-B (C-M-RCNN) | 145M | 982G | - | 11.6/5.1* | 51.9% | - | - | -
Swin T-B (HTC++) | 160M | 1043G | - | 11.6 | 56.4% | - | - | -
Swin T-L (HTC++) | 284M | 1470G | - | - | 57.1% | 57.7% | - | -
SwinV2-L(HTC++) [15] | 197M | - | 1536 | - | 60.2% | 60.8% | - | -
SwinV2-G(HTC++) [15] | 3.0B | - | 1536 | - | 62.5% | 63.1% | - | -
DETR [3] | 41M | 86G | <1333 |  | 42.0% |  |  |
DETR-DC5 [3] | 41M | 187G | <1333 |  | 43.3% |  |  |
DETR-R101 [3] | 60M | 152G | <1333 |  | 43.5% |  |  |
DETR-DC5-R101 [3] | 60M | 253G | <1333 |  | 44.9% |  |  |
Co-DETR [28] | 348M | - | - |  | 65.9% | 66.0% | - | -
InternImage-H [26] | 2180M | - | - |  | 65.0% | 65.4% | - | -
RT-DETR-R50 [17] | 42M | 136G | 640 | 108(T4) | 53.1% |  |  |
RT-DETR-R101 [17] | 76M | 259G | 640 | 74(T4) | 54.3% |  |  |
RT-DETR-L [17] | 32M | 110G | 640 | 114(T4) | 53.0% |  |  |
RT-DETR-X [17] | 67M | 234G | 640 | 74(T4) | 54.8% |  |  |

##  5 Conclusions

In this article, we introduced YotoR, a hybrid architecture that combines the
Swin Transformer and YoloR models for object detection. YotoR outperforms its
constituent models in both accuracy and inference speed. Although this study
focused on four specific YotoR configurations, it opens avenues for exploring
larger models and adaptations to new architectures beyond YoloR and Swin
Transformer.

The fact that Transformer-based backbones can be combined with Yolo-like heads
has broader implications, extending to the design of new hybrid models for
different kinds of image-related tasks.

Further experiments are necessary to fully understand the impact of Yolo-style
heads and implicit knowledge, as well as to address performance challenges in
real-time processing.

Future research directions include upgrading YotoR’s backbone, investigating
implicit knowledge integration, exploring novel techniques for head
enhancements, considering multi-modal networks, and incorporating language
tasks into the predictions.

## References

  * [1] Bochkovskiy, A., Wang, C.Y., Liao, H.Y.M.: Yolov4: Optimal speed and accuracy of object detection (2020)
  * [2] Cai, Z., Vasconcelos, N.: Cascade r-cnn: Delving into high quality object detection (2017)
  * [3] Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A., Zagoruyko, S.: End-to-end object detection with transformers. In: Vedaldi, A., Bischof, H., Brox, T., Frahm, J.M. (eds.) Computer Vision – ECCV 2020. pp. 213–229. Springer International Publishing, Cham (2020)
  * [4] Chen, G., Zheng, Y.D., Chen, Z., Wang, J., Lu, T.: Elan: Enhancing temporal action detection with location awareness. pp. 1020–1025 (07 2023). https://doi.org/10.1109/ICME55011.2023.00179
  * [5] Chen, K., Pang, J., Wang, J., Xiong, Y., Li, X., Sun, S., Feng, W., Liu, Z., Shi, J., Ouyang, W., Loy, C.C., Lin, D.: Hybrid task cascade for instance segmentation (2019)
  * [6] Chen, P.Y., Chang, M.C., Hsieh, J.W., Chen, Y.S.: Parallel residual bi-fusion feature pyramid network for accurate single-shot object detection. IEEE Transactions on Image Processing 30, 9099–9111 (2021)
  * [7] Ding, X., Zhang, X., Ma, N., Han, J., Ding, G., Sun, J.: Repvgg: Making vgg-style convnets great again (2021)
  * [8] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., Houlsby, N.: An image is worth 16x16 words: Transformers for image recognition at scale (2021)
  * [9] Fang, H.S., Sun, J., Wang, R., Gou, M., Li, Y.L., Lu, C.: Instaboost: Boosting instance segmentation via probability map guided copy-pasting (2019)
  * [10] Ge, Z., Liu, S., Wang, F., Li, Z., Sun, J.: Yolox: Exceeding yolo series in 2021 (2021)
  * [11] He, K., Gkioxari, G., Dollár, P., Girshick, R.: Mask r-cnn (2018)
  * [12] Kolesnikov, A., Beyer, L., Zhai, X., Puigcerver, J., Yung, J., Gelly, S., Houlsby, N.: Big transfer (bit): General visual representation learning (2020)
  * [13] Lee, Y., Park, J.: Centermask : Real-time anchor-free instance segmentation (2020)
  * [14] Li, C., Li, L., Geng, Y., Jiang, H., Cheng, M., Zhang, B., Ke, Z., Xu, X., Chu, X.: Yolov6 v3. 0: A full-scale reloading. arXiv preprint arXiv:2301.05586 (2023)
  * [15] Liu, Z., Hu, H., Lin, Y., Yao, Z., Xie, Z., Wei, Y., Ning, J., Cao, Y., Zhang, Z., Dong, L., Wei, F., Guo, B.: Swin transformer v2: Scaling up capacity and resolution (2022)
  * [16] Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., Guo, B.: Swin transformer: Hierarchical vision transformer using shifted windows (2021)
  * [17] Lv, W., Zhao, Y., Xu, S., Wei, J., Wang, G., Cui, C., Du, Y., Dang, Q., Liu, Y.: Detrs beat yolos on real-time object detection (2023)
  * [18] Ma, Z., Li, M., Wang, Y.: Pan: Path integral based convolution for deep graph neural networks (2019)
  * [19] Redmon, J., Divvala, S., Girshick, R., Farhadi, A.: You only look once: Unified, real-time object detection (2016)
  * [20] Ren, S., He, K., Girshick, R., Sun, J.: Faster r-cnn: Towards real-time object detection with region proposal networks. Advances in neural information processing systems 28 (2015)
  * [21] Tian, Z., Shen, C., Chen, H., He, T.: Fcos: A simple and strong anchor-free object detector (2020)
  * [22] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I.: Attention is all you need. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. p. 6000–6010. NIPS’17, Curran Associates Inc., Red Hook, NY, USA (2017)
  * [23] Wang, C.Y., Bochkovskiy, A., Liao, H.Y.M.: Yolov7: Trainable bag-of-freebies sets new state-of-the-art for real-time object detectors (2022)
  * [24] Wang, C.Y., Liao, H.Y.M., Yeh, I.H., Wu, Y.H., Chen, P.Y., Hsieh, J.W.: Cspnet: A new backbone that can enhance learning capability of cnn (2019)
  * [25] Wang, C.Y., Yeh, I.H., Liao, H.Y.M.: You only learn one representation: Unified network for multiple tasks (2021)
  * [26] Wang, W., Dai, J., Chen, Z., Huang, Z., Li, Z., Zhu, X., Hu, X., Lu, T., Lu, L., Li, H., et al.: Internimage: Exploring large-scale vision foundation models with deformable convolutions. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 14408–14419 (2023)
  * [27] Zhang, H., Lu, C., Chen, E.: Obstacle detection: improved yolox-s based on swin transformer-tiny. Optoelectronics Letters 19, 698 – 704 (2023), https://api.semanticscholar.org/CorpusID:265297393
  * [28] Zong, Z., Song, G., Liu, Y.: Detrs with collaborative hybrid assignments training. 2023 IEEE/CVF International Conference on Computer Vision (ICCV) pp. 6725–6735 (2022), https://api.semanticscholar.org/CorpusID:253802116


# Sample Efficient Subspace-based Representations for Nonlinear Meta-Learning

###### Abstract

Constructing good representations is critical for learning complex tasks in a
sample efficient manner. In the context of meta-learning, representations can
be constructed from common patterns of previously seen tasks so that a future
task can be learned quickly. While recent works show the benefit of subspace-
based representations, such results are limited to linear-regression tasks.
This work explores a more general class of nonlinear tasks with applications
ranging from binary classification, generalized linear models and neural nets.
We prove that subspace-based representations can be learned in a sample-
efficient manner and provably benefit future tasks in terms of sample
complexity. Numerical results verify the theoretical predictions in
classification and neural-network regression tasks.

Index Terms—  representation learning, binary classification, generalized
linear models, nonlinear problems

##  1 Introduction

Meta-learning (and multi-task learning) has proved to be a efficient when
available training data is limited. The central idea is exploiting the
information (e.g. training data) provided by earlier related tasks to quickly
adapt a new task using few samples. This idea has a rich history [1, 2] and
has shown promise in modern machine learning tasks, e.g., in image
classification [3], machine translation [4] and reinforcement learning [5],
all of which may involve numerous tasks to be learned with limited data per
task.

Modern deep learning algorithms typically exploit the shared information
between tasks by learning useful representations [6, 7]. The multi-task system
was studied by [1], and the idea of meta-learning or transfer learning is
investigated empirically in modern machine learning framework, showing that
the shared representation benefits for training on the new tasks [8, 9, 10].
An instructive and well-studied problem for meta-learning is mixed linear
regression, for which efficient algorithms and sample complexity bounds are
discussed in [11, 12, 13]. If the tasks lie on a shared low-dimensional
subspace, learning this subspace would serve as an efficient representation
which helps reduce the search space for future tasks. Once the search space is
low dimensional, in order to get the same accuracy, the amount of data
required for training is reduced compared to training over the full parameter
space. [14, 15, 16] propose sample complexity bounds for representation
learning for linear multi-task systems. There are study of mixed linear tasks
combined with other structures, such as boolean combination of features [17],
half-spaces [18] and sparse representations [19].

The recent papers [20, 21] propose meta-learning procedures that involve
dimension reduction, clustering and few-shot learning. Here a low-dimensional
task subspace is used as the search space for few-shot learning for the new
task. Another related approach [22, 23] sets up a nonconvex optimization
problem with matrix factors of appropriate sizes, which captures the low
dimensional structure. One can apply gradient descent to this nonconvex
problem, and studying its behavior requires a nontrivial landscape analysis of
the matrix factorization problem.

However, existing provable algorithms for representation learning are
restricted to linear-regression tasks, whereas typical machine learning tasks
involve nonlinearity. This can arise from the use of nonlinear models as well
as nonlinear label link function (e.g. generalized linear models). A good
example is classification problems including computer vision and natural
language processing [3, 4]. In classification tasks, the model is a map from
images/text to labels, and the labels are discrete and not linear with respect
to the input (i.e. logistic link function). Another example is the use of
nonlinear models such as deep networks The existing results for representation
learning for the linear-regression setting cannot be easily extended to the
nonlinear case.

_Can we learn efficient subspace representations for nonlinear tasks such as
generalized linear models and neural nets?_

We consider a realizable setup where the input data is high-dimensional, the
_relevant features_ lie in a low dimensional subspace and the labels depend
only on the _relevant features_. These assumptions are the same as in the
existing literature, however we additionally allow for the scenario where
labels are possibly an arbitrary nonlinear function of the relevant features.
We make the following contributions.

$\bullet$ Efficient representations for nonlinear tasks: We show that subspace
found via method-of-moments (MOM) leads to a consistent estimate of the
ground-truth subspace despite arbitrary task nonlinearities, when the data is
normally distributed. We combine this with non-asymptotic learning results to
establish sample complexity bounds for representation learning.

$\bullet$ Few-shot learning and Applications: We specialize our results to
practical settings with tasks involving binary classification and neural nets.
We theoretically and empirically show that subspace-based representation can
greatly improve sample efficiency of future tasks.

##  2 Problem Formulation

The meta-learning setup that will be considered in this work consists of two
phases: (i) meta-training: prior tasks are used to learn a good representation
and (ii) few-shot learning: the new task is learned with few samples. In the
meta-training phase, we learn the low dimensional space spanned by parameters.
In the few-shot learning phase, we use the subspace to learn the model of a
new task ideally with few samples.

In the first phase, there are multiple task vectors to infer from.We consider
a realizable model where the input and label is associated via a labeling
function. One accesses batches of data, each of whom is collected from a task.
Below, we denote the ground-truth representation by a matrix
$\bm{W}\in\mathbb{R}^{r\times d}$ whose row space corresponds to the subspace
of interest.

######  Definition 2.1.

Meta-training data. Fix a matrix $\bm{W}\in\mathbb{R}^{r\times d}$ satisfying
$\bm{W}\bm{W}^{T}={\bm{I}}$. The $j$-th task is associated with function
$f^{j}:\mathbb{R}^{r}\rightarrow\mathbb{R}$. Given input
${\mathbf{x}}\in\mathbb{R}^{d}$, the label $y$ is distributed as
$p_{j}(y|{\mathbf{x}})=p_{j}(y|\bm{W}{\mathbf{x}})$111In words, the label only
depends on the relevant features induced by $\bm{W}$. and the expectation
satisfies $\bm{E}(y)=f^{j}(\bm{W}{\mathbf{x}})$. Suppose there are $n_{j}$
samples from the $j$-th task sampled i.i.d. from this distribution and we
denote the dataset
$\mathcal{S}^{j}=({{\mathbf{x}}_{i,j}},{y_{i,j}})_{i=1}^{n_{j}}$. Define the
full meta-training dataset to be
$\mathcal{S}=\bigcup_{j=1}^{k}\mathcal{S}^{j}$.

Here, $f^{j}$ is allowed to be any Lipschitz nonlinear function, i.e., a
neural network222In our theoretical results, we treat $f$ as a general linear
function, and in experiments we will use a neural network with a specific
structure..

######  Definition 2.2.

Binary classification. Suppose $f^{j}$ takes values over $[0,1]$,

$\displaystyle{y_{i,j}}=\begin{cases}\text{1,}&{\mbox{with probability
}f^{j}(\bm{W}{{\mathbf{x}}_{i,j}}),}\\\ \text{0,}&{\mbox{with probability
}1-f^{j}(\bm{W}{{\mathbf{x}}_{i,j}}).}\\\ \end{cases}$

######  Definition 2.3.

Generalized linear models (GLM) (which include logistic/linear regression) can
be modeled by choosing $f^{j}$ to be parameterized by a vector
$\bm{\theta}_{j}\in\mathbb{R}^{r}$ and a link function
$\phi:\mathbb{R}\rightarrow\mathbb{R}$ as
$f^{j}(\bm{W}{{\mathbf{x}}_{i,j}}):=\phi(\bm{\theta}_{j}^{T}\bm{W}{{\mathbf{x}}_{i,j}})$.

When the dimension of the span of parameters is small, [20] performs a
dimension reduction algorithm to find the low-dimensional subspace that the
parameters span. This is done by selecting the top eigenvectors of the
covariance estimate of the cross-correlation between input and labels.

######  Definition 2.4.

Moment estimator of covariance. We define the covariance estimator as

$\begin{split}\hat{\bm{M}}&=\mathop{\scalebox{1.8}{$\sum$}}_{j=1}^{k}\frac{2}{n_{j}^{2}}\left[(\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}})(\sum_{i=n_{j}/2+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}})^{\top}\right.\\\
&\quad\quad\quad\quad\left.+(\sum_{i=n_{j}/2+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}})(\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}})^{\top}\right].\end{split}$
(2.1)

Define

$\displaystyle\bm{h}^{j}(\bm{W}):\mathbb{R}^{r\times
d}\rightarrow\mathbb{R}^{d}=\bm{E}_{{\mathbf{x}}}[f^{j}(\bm{W}{\mathbf{x}}){\mathbf{x}}]$
$\displaystyle\bm{M}:=\bm{W}^{\top}\bm{W}\left(\frac{1}{k}\sum_{j=1}^{k}\bm{h}^{j}(\bm{W})(\bm{h}^{j}(\bm{W}))^{\top}\right)\bm{W}^{\top}\bm{W}.$

We will prove that $\hat{\bm{M}}$ is a finite sample estimate of $\bm{M}$.
Subspace estimation. To estimate the subspace $\bm{W}$, we use rank-$r$
approximation of $\hat{\bm{M}}$ to retrieve its principal eigenvector
subspace. Let $\hat{\bm{U}}\hat{\bm{{\Lambda}}}\hat{\bm{U}}^{\top}$ be the
eigen-decomposition of $\hat{\bm{M}}$. Denote $\hat{\lambda}_{j}$ as the $j$th
eigenvalue of $\hat{\bm{{\Lambda}}}$. Let $\hat{\bm{U}}_{r}$ be the first $r$
columns of $\hat{\bm{U}}$, thus the rank-$r$ approximation is
$\hat{\bm{M}}_{r}=\hat{\bm{U}}_{r}\mathrm{diag}(\hat{\lambda}_{1},...,\hat{\lambda}_{r})\hat{\bm{U}}_{r}^{\top}$.
In the next section, we will prove that the range of $\hat{\bm{U}}$ is close
to the row space of $\bm{W}$.

In Algorithm 1, the output $\hat{\bm{U}}_{r}$ is the estimator of the task
subspace $\bm{W}$. $\hat{\bm{U}}_{r}$ is used as a training step for the few-
shot learning phase. For the new task, we search for the function $f^{*}$ that
minimizes the population loss. We shall provide an instructive analysis for a
general class of functional family and loss.

######  Assumption 1.

$\mathcal{F}$ is a set of functions satisfying: For any function
$f\in\mathcal{F}$, any orthonormal matrix ${\bm{Q}}\in\mathbb{R}^{r\times r}$
and any representation matrix ${\bm{P}}\in\mathbb{R}^{r\times d}$, there
exists $g\in\mathcal{F}$ such that
$f({\bm{P}}{\mathbf{x}})=g({\bm{Q}}{\bm{P}}{\mathbf{x}})$.

In this assumption, we basically mean that the $\mathcal{F}$ is invariant with
orthonormal rotation ${\bm{Q}}$. In other words, we only need to find the $r$
dimensional row space $\mathrm{row}({\bm{P}})$ (to project the features onto
it as a low dimensional representation), and don’t worry the exact matrix
${\bm{P}}$ itself.

Let us introduce population risk $\mathcal{L}$ and empirical risk
$\mathcal{L}_{e}$ based on any single loss function between model prediction
and true label.

$\displaystyle\mathcal{L}(f;{\bm{P}})=\bm{E}_{\mathscr{P}_{x,y}}\mathrm{loss}(f({\bm{P}}{\mathbf{x}}),y)$
$\displaystyle\mathcal{L}_{e}(f;{\bm{P}})=\frac{1}{n}\sum_{i=1}^{n}\mathrm{loss}(f({\bm{P}}{\mathbf{x}}_{i}),y_{i}).$

We make the following assumption on the population risk.

######  Assumption 2.

Suppose population loss $\mathcal{L}$ and empirical loss $\mathcal{L}_{e}$
satisfy the following assumptions:

  1. 1.

$\mathcal{L}$ is $L$ Lipschitz in ${\bm{P}}{\mathbf{x}}$.

  2. 2.

$\min_{{\bm{P}}}\mathcal{L}(f;{\bm{P}})=\mathcal{L}(f;\bm{W})$.

Example: Suppose $f$ is an $L$-Lipschitz function with range in $(0,1)$ and
the true labels $y_{i}$ are from $\\{0,1\\}$. The cross entropy function
satisfies the assumptions.

$\displaystyle\mathcal{L}(f;{\bm{P}})=-\bm{E}_{\mathscr{P}_{x,y}}($
$\displaystyle y\log f({\bm{P}}{\mathbf{x}})$ (2.2)
$\displaystyle+(1-y)\log(1-f({\bm{P}}{\mathbf{x}}))).$
$\displaystyle\mathcal{L}_{e}(f;{\bm{P}})=-\frac{1}{n}\sum_{i=1}^{n}($
$\displaystyle y_{i}\log(f({\bm{P}}{\mathbf{x}}_{i}))$ (2.3)
$\displaystyle+(1-y_{i})\log(1-f({\bm{P}}{\mathbf{x}}_{i}))).$

With an abuse of notation, we can define the loss with respect to
parameterization of the function $f$. For example, if we use the model in Def.
2.3, then we can write the empirical loss as

$\displaystyle\mathcal{L}_{e}(\bm{\theta};{\bm{P}})=-\frac{1}{n}\sum_{i=1}^{n}($
$\displaystyle y_{i}\log(\phi(\bm{\theta}^{\top}{\bm{P}}{\mathbf{x}}_{i}))$
(2.4)
$\displaystyle+(1-y_{i})\log(1-\phi(\bm{\theta}^{\top}{\bm{P}}{\mathbf{x}}_{i}))).$

######  Definition 2.5.

Few-shot classification (Population). In the few-shot learning phase, suppose
${\mathbf{x}},y\sim\mathscr{P}_{x,y}$ satisfy
$\bm{E}[y~{}|~{}{\mathbf{x}}]=f^{*}(\bm{W}{\mathbf{x}})$. Let $\mathcal{F}$ be
a family of functions as the search space for few-shot learning model. Let
Assumptions 1 and 2 hold. We search for the solution induced by
$\hat{{\bm{U}}}_{r}$ by

$\displaystyle\hat{f}$
$\displaystyle=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\
\mathcal{L}(f;\hat{{\bm{U}}}_{r}^{\top})$ (2.5)

Observe that, without representation learning, one has to search for both $f$
and $\bm{W}$. However with representation learning, we use
$\hat{{\bm{U}}}_{r}^{\top}$ as the representation matrix and only search for
$f$.

######  Remark 2.1.

For the GLM Definition 2.3, we can choose $\mathcal{F}$ to be the $\ell_{2}$
norm constrained functions for some $a\leq\infty$

$\displaystyle\mathcal{F}=\\{{\mathbf{x}}\rightarrow\phi(\bm{\theta}^{T}{\mathbf{x}})~{}\big{|}~{}\|\bm{\theta}\|_{2}\leq
a,~{}\bm{\theta}\in\mathbb{R}^{r}\\},$ (2.6)

Let the new data be generated with
$f^{*}(\bm{W}{\mathbf{x}})=\phi({\bm{\theta}^{*}}^{\top}\bm{W}{\mathbf{x}})$
for some ground-truth parameter $\bm{\theta}^{*}$. We use
$\mathcal{L}(\bm{\theta};{\bm{P}})$ to denote the cross-entropy loss in this
setting. $\hat{f}$ (parameterized by $\hat{\bm{\theta}}$) is given by

$\displaystyle\hat{\bm{\theta}}$
$\displaystyle=\mathop{\mathrm{argmin}}_{\bm{\theta}}\
\mathcal{L}(\bm{\theta};\hat{\bm{U}}_{r}^{\top}),\mbox{~{}such~{}that~{}}\|\bm{\theta}\|\leq
a.$ (2.7)

######  Definition 2.6.

Few-shot learning (Finite sample GLM). Suppose there are $n$ samples for new
task $({\mathbf{x}}_{i},y_{i})_{i=1}^{n}$ and $({\mathbf{x}}_{i},y_{i})$
satisfies $\bm{E}(y_{i}|{\mathbf{x}}_{i})=f^{*}(\bm{W}{\mathbf{x}}_{i})$. Let
$\mathcal{L}_{e}$ be empirical loss, satisfying Assumptions 1 and 2. Given
norm constraint $a\leq\infty$, the empirical risk minimizer (ERM) is defined
as

$\displaystyle\hat{\bm{\theta}}_{e}$
$\displaystyle=\mathop{\mathrm{argmin}}_{\bm{\theta}}\
\mathcal{L}_{e}(\bm{\theta};\hat{\bm{U}}_{r}^{\top})\quad\text{such~{}that}\quad\|\bm{\theta}\|_{2}\leq
a.$ (2.8)

Algorithm 1 Meta-training and Few-shot Learning

0: Dataset $\mathcal{S}$, representation size $r$, function space
$\mathcal{F}$

Compute $\hat{\bm{M}}$ via method-of-moments (2.1).

Rank $r$
approximation:$\quad\hat{\bm{M}}_{r}\leftarrow\hat{\bm{U}}_{r}\mathrm{diag}(\hat{\bm{{\Lambda}}}_{1,1},...,\hat{\bm{{\Lambda}}}_{r,r})\hat{\bm{U}}_{r}^{\top}$.

Either $\hat{f}\leftarrow\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\
\mathcal{L}(f;{\bm{U}}_{r}^{\top})$.

Or $\hat{f}_{e}\leftarrow\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\
\mathcal{L}_{e}(f;{\bm{U}}_{r}^{\top})$.

return $\hat{\bm{U}}_{r}$ and $\hat{f}$ or $\hat{f}_{e}$.

##  3 Main Results

In this section, we shall establish error bounds for Algorithm 1. This
involves three parts. Theorem 3.2 establishes the quality of the moment
estimator $\hat{\bm{M}}$. Theorem 3.4 upper bounds the population cross-
entropy risk of $\hat{f}$ in the few-shot learning stage. Theorem 3.5 upper
bounds the population risk of the ERM estimator $\hat{f}_{e}$, which is
learned from finite data.

###  3.1 Results on Meta-training

######  Lemma 3.1.

$\bm{M},\hat{\bm{M}}$ satisfies the following. (a) $\text{rank}(\bm{M})\leq
r$. (b) $\text{range-space}(\bm{M})\subset\text{row-space}(\bm{W})$. (c)
$\bm{E}[\hat{{\bm{M}}}]=\bm{M}$.

In words, $\bm{M}$ returns a consistent estimate of the representation space
in the sense that its range is guaranteed to be the subspace of the
representation. Observe that to fully recover representation, $\bm{M}$ should
contain a diverse set of tasks that can _cover_ the representation subspace.
For GLM, one needs at least $k\geq r$ tasks to ensure range of $\bm{M}$ is
equal to the row-space of $\bm{W}$. Additionally, $\hat{{\bm{M}}}$ estimator
is also consistent.

We next present the error on the estimator $\hat{\bm{M}}$. This theorem
applies to standard normal data ${\mathbf{x}}\sim\mathcal{N}(0,{\bm{I}})$.
While this may initially seem restrictive, we remark that identity covariance
is mostly used for notational convenience. Additionally, in similar spirit to
Central Limit Theorem, machine learning and signal processing algorithms often
exhibit distributional universality: For instance, subgaussian distributions
often behave very similar or even identical to gaussian distributions in
sufficiently high-dimensions [24, 25]. We leave such generalizations to more
general distributions as a future work.

######  Theorem 3.2 (Moment Estimator).

Suppose the data is generated as in Def. 2.1, $n_{j}\geq N$ for all $j$ and
${{\mathbf{x}}_{i,j}}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,{\bm{I}})$.
Suppose for some $\sigma>0$ and for all tasks, the label-input product
$y{\mathbf{x}}$ is a subGaussian random vector with covariance upper bounded
by $\|\mathbf{Cov}(y{\mathbf{x}})\|\leq\sigma^{2}$. (These conditions hold
when $|f^{j}({\mathbf{x}})|<\sigma$.) Let $\delta\in(0,1)$ and
$\epsilon\in(0,1)$. Then there exists a constant $c>0$ such that if

$\displaystyle
k\geq\frac{cd}{N}\log^{2}(\frac{kd}{\delta})\max\\{\frac{1}{\epsilon^{2}},\frac{1}{\epsilon}\log(\frac{kd}{\delta})\\},$

$\|\hat{\bm{M}}-\bm{M}\|\leq\epsilon\sigma^{2}$ with probability at least
$1-\delta$.

Recall that $\hat{\bm{M}}=\hat{\bm{U}}\hat{\bm{{\Lambda}}}\hat{\bm{U}}^{\top}$
and $\hat{\bm{U}}_{r}$ is the first $r$ columns of $\hat{\bm{U}}$. Denote the
estimate of $\bm{W}$ via $\hat{\bm{W}}$ given by adjusting $\hat{\bm{U}}_{r}$

$\displaystyle\hat{\bm{W}}$
$\displaystyle=(\hat{\bm{U}}_{r}\hat{\bm{Q}})^{\top},\
\hat{\bm{Q}}=\mathop{\mathrm{argmin}}_{{\bm{Q}}\in\mathbb{R}^{r\times
r},{\bm{Q}}{\bm{Q}}^{\top}=I}\ \|\hat{\bm{U}}_{r}{\bm{Q}}-\bm{W}^{\top}\|$
(3.1)

With the definition of $\hat{\bm{W}}$, $\|\hat{\bm{W}}-\bm{W}\|$ defines a
distance between the row space of $\bm{W}$ and the column space of
$\hat{\bm{U}}_{r}$. If the span of the two subspaces are the same, then there
exists an orthonormal matrix ${\bm{Q}}$ such that
$\hat{\bm{U}}_{r}{\bm{Q}}=\bm{W}^{\top}$.

The previous lemma builds upon the assumption that $\|\hat{\bm{W}}-\bm{W}\|$
is small. In Theorem 3.2, we have got
$\|\hat{\bm{M}}-\bm{M}\|\leq\epsilon\sigma^{2}$, then with the extra
assumption that $\bm{M}$ is rank $r$, we have the following result from [26].

######  Lemma 3.3.

If $\|\hat{\bm{M}}-\bm{M}\|\leq\epsilon\sigma^{2}$,
$\lambda_{r}(\bm{M})>\epsilon\sigma^{2}$, then

$\|\hat{\bm{W}}-\bm{W}\|\leq\epsilon\sigma^{2}(\lambda_{r}(\bm{M})-\epsilon\sigma^{2})^{-1}.$

###  3.2 Results on Few-shot Learning

In the next step, we will use $\hat{\bm{U}}_{r}$ for few shot learning and
find $\hat{f}$ that minimize the population loss.

######  Theorem 3.4.

Let Assumptions 1 and 2 hold. Let $\hat{\bm{W}}$ be the same as in (3.1) and
$\hat{f}$ be the same as in (2.5). Then we have

$\displaystyle\mathcal{L}(\hat{f};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}(f^{*};\bm{W})\lesssim
L\sqrt{r}\|\hat{\bm{W}}-\bm{W}\|.$

$\mathcal{L}(f^{*};\bm{W})$ assumes the knowledge of the true function $f^{*}$
and the representation $\bm{W}$. This shows that the inaccuracy of the moment
estimator $\hat{M}$ costs us $O(L\sqrt{r}\|\hat{\bm{W}}-\bm{W}\|)$.

Theorem 3.4 bounds the population risk of $\hat{f}$, when we use
$\hat{\bm{U}}_{r}^{\top}$ as the representation subspace. Next we discuss the
population risk of the finite sample solution $\hat{f}_{e}$, which should be
worse than $\hat{f}$ due to the limited samples.

######  Theorem 3.5.

Consider the setup in Def. 2.6 with $n$ i.i.d. examples with ground-truth
model $\bm{\theta}^{*}$. Solve for $\hat{\bm{\theta}}_{e}$ via (2.8). There
exist constants $c>1$, $\delta\in(0,1)$, with probability at least
$1-n^{-c+1}-\delta$, the solution pair
$(\hat{\bm{\theta}}_{e},\hat{\bm{U}}_{r})$ satisfies

$\displaystyle\quad\mathcal{L}($
$\displaystyle\hat{\bm{\theta}}_{e};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}(\bm{\theta}^{*};\bm{W})$
$\displaystyle\leq\frac{caL(\sqrt{r}+\log(n))(1+\sqrt{\log(1/\delta)})}{\sqrt{n}}+L\sqrt{r}\|\hat{\bm{W}}-\bm{W}\|.$

Note that the first term grows as $\sqrt{r/n}$. This means the amount of data
$n$ we request for few-shot learning is $n\approx r$, as compared to $n\approx
d$ if representation learning is not excecuted.

##  4 Numerical Experiments

We generate synthetic datasets with $k$ different tasks and $n$ samples for
all tasks. As dimension of the data and dimension of the subspace we choose
$d=50$ and $r=5$, respectively.

We study two different setups. In the first one data is generated according to
Def. 2.3. For the second setup, there is an underlying 3-layer neural network
that fits the data. In both setups our only aim is to retrieve subspace
representations of the data using Algorithm 1.

(a)

(b)

Fig. 1: Subspace correlations with fixed number of tasks. (a) Binary
classification (b) Neural network.

For neural network experiments, we assume that the data are generated from a
ground truth neural network which has 3 layers, defined as

${y_{i,j}}=f^{j}({{\mathbf{x}}_{i,j}})+\epsilon_{i,j}=\bm{W}_{j3}(\bm{W}_{j2}(\bm{W}_{j1}(\bm{W}{{\mathbf{x}}_{i,j}}))_{+})_{+}+\epsilon_{i,j}$

where $\epsilon_{i,j}\sim\mathcal{N}(0,1)$ is gaussian noise, $(\cdot)_{+}$ is
the ReLU activation function, $\bm{W}\in\mathbb{R}^{5\times 50}$ is
representation matrix which is same for all $j$’s. The weight matrices
$\bm{W}_{j1},\bm{W}_{j2}$ and $\bm{W}_{j3}$ are different for each task and
they are random gaussian matrices in $\mathbb{R}^{20\times
5},\mathbb{R}^{20\times 20},\mathbb{R}^{20}$ respectively.

In Fig. 1 we use the subspace correlation as the metric for evaluating the
accuracy of subspace recovery, which is defined by
$\frac{\|{\hat{\bm{U}_{r}}^{\top}\bm{U}_{r}}\|^{2}}{\|\bm{U}_{r}\|^{2}}$. In
Fig. 1, $k=100$ is fixed but $n$’s vary from $20$ to $200$. It can be seen
from Fig. 1 that as $nk$ gets bigger, the subspace correlation becomes closer
to $1$, which is compatible with Theorem 3.2

In Fig. 2(a), the downstream task accuracies for binary classification are
depicted. For the new task, a new 1-layer neural network without any
activation function is trained with and without the retrieved representations
of the earlier tasks. We find the parameters of the neural network by
minimizing the cross entropy loss via SGD. For this setup, during meta-
training, we set $n=50$ for all tasks and $k=2000$, to have almost perfect
representation. We evaluate the test error with $1000$ new samples.

Fig. 2: (a) Accuracy for downstream task, binary classification (b) Accuracy
for downstream the task, MNIST

If the number of few-shot training samples is small, accuracy improves much
faster when we use representation learning. This validates that dimension
reduction reduces the degrees-of-freedom for few-shot learning, so the optimal
model can be learned with fewer samples. As the sample size grows, the
relative benefit of representation is smaller but still noticeable.

In Fig. 2(b), Algorithm 1 is also tested in MNIST dataset. $d=784$ and $r$ is
not known. We assume that we have different binary classification tasks among
pairs of digits such as 0-1;2-3;0-8;8-4 etc. There exist 15 meta-training
tasks (i.e., $k=15$). For each task we have 500 samples in each classes. We
choose a different pair of classes as few-shot learning task. We choose binary
classification among images of 1 and 9, which is not included in the meta-
learning phase. We tune the predicted subspace dimensions and number of
samples to get Fig. 2(b). It can be concluded that when $r=20$, The downstream
task is not learnt well so we need to expand the subspace. For $r=50$ and
$r=100$ subspace learning helps for few-shot learning, as when the number of
training samples $n$ is between 8-56 they outperform the case without
representation. When $r$ gets closer to $d$, the few-shot sample size has to
be large to succeeed due to higher degree of freedom.

## References

  * [1] Rich Caruana,  “Multitask learning,”  Machine learning, vol. 28, no. 1, pp. 41–75, 1997.
  * [2] Jonathan Baxter,  “A model of inductive bias learning,”  Journal of artificial intelligence research, vol. 12, pp. 149–198, 2000.
  * [3] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei,  “Imagenet: A large-scale hierarchical image database,”  in 2009 IEEE conference on computer vision and pattern recognition. Ieee, 2009, pp. 248–255.
  * [4] Ondřej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, et al.,  “Findings of the 2014 workshop on statistical machine translation,”  in Proceedings of the ninth workshop on statistical machine translation.
  * [5] Chelsea Finn, Pieter Abbeel, and Sergey Levine,  “Model-agnostic meta-learning for fast adaptation of deep networks,”  in International Conference on Machine Learning, 2017, pp. 1126–1135.
  * [6] Jürgen Schmidhuber,  Evolutionary principles in self-referential learning, or on learning how to learn: the meta-meta-… hook,  Ph.D. thesis, Technische Universität München, 1987.
  * [7] Sebastian Thrun and Lorien Pratt,  Learning to learn,  Springer Science & Business Media, 2012.
  * [8] Yoshua Bengio, Aaron Courville, and Pascal Vincent,  “Representation learning: A review and new perspectives,”  IEEE transactions on pattern analysis and machine intelligence, vol. 35, no. 8, pp. 1798–1828, 2013.
  * [9] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey,  “Meta-learning in neural networks: A survey,”  arXiv preprint arXiv:2004.05439, 2020.
  * [10] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson,  “How transferable are features in deep neural networks?,”  in Advances in neural information processing systems, 2014, pp. 3320–3328.
  * [11] Kai Zhong, Prateek Jain, and Inderjit S Dhillon,  “Mixed linear regression with multiple components,”  in Advances in neural information processing systems, 2016, pp. 2190–2198.
  * [12] Yuanzhi Li and Yingyu Liang,  “Learning mixtures of linear regressions with nearly optimal complexity,”  in Conference On Learning Theory, 2018, pp. 1125–1144.
  * [13] Sitan Chen, Jerry Li, and Zhao Song,  “Learning mixtures of linear regressions in subexponential time via fourier moments,”  in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.
  * [14] Karim Lounici, Massimiliano Pontil, Sara Van De Geer, Alexandre B Tsybakov, et al.,  “Oracle inequalities and optimal inference under group sparsity,”  The annals of statistics, vol. 39, no. 4, pp. 2164–2204, 2011.
  * [15] Giovanni Cavallanti, Nicolo Cesa-Bianchi, and Claudio Gentile,  “Linear algorithms for online multitask classification,”  The Journal of Machine Learning Research, vol. 11, pp. 2901–2934, 2010.
  * [16] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes,  “The benefit of multitask representation learning,”  The Journal of Machine Learning Research, vol. 17, no. 1.
  * [17] Maria-Florina Balcan, Avrim Blum, and Santosh Vempala,  “Efficient representations for lifelong learning and autoencoding,”  in Conference on Learning Theory.
  * [18] Irina Rish, Genady Grabarnik, Guillermo Cecchi, Francisco Pereira, and Geoffrey J Gordon,  “Closed-form supervised dimensionality reduction with generalized linear models,”  in Proceedings of the 25th international conference on Machine learning, 2008, pp. 832–839.
  * [19] Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil,  “Convex multi-task feature learning,”  Machine learning, vol. 73, no. 3, pp. 243–272, 2008.
  * [20] Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh,  “Meta-learning for mixed linear regression,”  arXiv preprint arXiv:2002.08936, 2020.
  * [21] Weihao Kong, Raghav Somani, Sham Kakade, and Sewoong Oh,  “Robust meta-learning for mixed linear regression with small batches,”  arXiv preprint arXiv:2006.09702, 2020.
  * [22] Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei,  “Few-shot learning via learning the representation, provably,”  arXiv:2002.09434, 2020.
  * [23] Nilesh Tripuraneni, Chi Jin, and Michael I Jordan,  “Provable meta-learning of linear representations,”  arXiv preprint arXiv:2002.11684, 2020.
  * [24] Samet Oymak and Joel A Tropp,  “Universality laws for randomized dimension reduction, with applications,”  Information and Inference: A Journal of the IMA, vol. 7, no. 3, pp. 337–446, 2018.
  * [25] Ehsan Abbasi, Fariborz Salehi, and Babak Hassibi,  “Universality in learning from linear measurements,”  in Advances in Neural Information Processing Systems, 2019, pp. 12372–12382.
  * [26] Chandler Davis and William Morton Kahan,  “The rotation of eigenvectors by a perturbation. iii,”  SIAM Journal on Numerical Analysis, vol. 7, no. 1, pp. 1–46, 1970\.
  * [27] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan,  “A short note on concentration inequalities for random vectors with subgaussian norm,”  arXiv preprint arXiv:1902.03736, 2019.
  * [28] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar,  Foundations of machine learning,  MIT press, 2018.
  * [29] Beatrice Laurent and Pascal Massart,  “Adaptive estimation of a quadratic functional by model selection,”  Annals of Statistics, pp. 1302–1338, 2000.

##  Appendix A Proof of main theorems

We sketch the proof at the beginning. First we compute the expectation of
$y{\mathbf{x}}$ in Lemma A.2. That leads to the proof of Lemma 3.1. Then in
Lemma A.4 we bound the difference between sum of $y{\mathbf{x}}$ and its mean
using concentration. The concentration of covariance estimator is studied
later in Lemma A.5 and A.6, which leads to Theorem 3.2.

####  A.0.1 Proof of Lemma 3.1

We first state Lemma 3.1 below.

######  Lemma A.1.

Let

$\displaystyle\hat{\bm{M}}$
$\displaystyle=\mathop{\scalebox{1.8}{$\sum$}}_{j=1}^{k}\frac{2}{n_{j}^{2}}\left[(\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}})(\sum_{i=n_{j}/2+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}})^{\top}\right.$
(A.1a)
$\displaystyle\quad\quad\quad\quad\left.+(\sum_{i=n_{j}/2+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}})(\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}})^{\top}\right].$

And

$\displaystyle\bm{h}^{j}(\bm{W}):\mathbb{R}^{r\times
d}\rightarrow\mathbb{R}^{d}=\bm{E}_{{\mathbf{x}}}[f^{j}(\bm{W}{\mathbf{x}}){\mathbf{x}}]$
$\displaystyle\bm{M}:=\bm{W}^{\top}\bm{W}\left(\frac{1}{k}\sum_{j=1}^{k}\bm{h}^{j}(\bm{W})(\bm{h}^{j}(\bm{W}))^{\top}\right)\bm{W}^{\top}\bm{W}.$

Then $\bm{M},\hat{\bm{M}}$ satisfies the following. (a)
$\text{rank}(\bm{M})\leq r$. (b) $\text{range-space}(\bm{M})\subset\text{row-
space}(\bm{W})$. (c) $\bm{E}[\hat{{\bm{M}}}]=\bm{M}$.

###### Proof.

Part (a) and (b) are easy to see. $\bm{W}\in\mathbb{R}^{r\times d}$ so that
$\text{rank}(\bm{M})\leq r$, and since $\bm{M}$ is the product of
$\bm{W}^{\top}$ and another matrix, then $\text{range-
space}(\bm{M})\subset\text{row-space}(\bm{W})$. Now we will prove Part (c). We
first give the lemma for the mean of the random vector $y{\mathbf{x}}$.

######  Lemma A.2.

We assume that the data is generated as in Def. 2.1, and we study the $j$-th
task whose activation function is $f^{j}$. Define

$\displaystyle\bm{h}^{j}(\bm{W}):\mathbb{R}^{r\times
d}\rightarrow\mathbb{R}^{d}=\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}f^{j}(\bm{W}{\mathbf{x}}){\mathbf{x}}$

Denote the joint distribution of $({\mathbf{x}},y)$ as $\mathscr{P}_{x,y}$.
Then
$\bm{E}_{({\mathbf{x}},y)\sim\mathscr{P}_{x,y}}(y{\mathbf{x}})=\bm{W}^{\top}\bm{W}\bm{h}^{j}(\bm{W})$.

_Proof of Lemma A.2._ The expectation can be expanded as

$\displaystyle\bm{E}_{({\mathbf{x}},y)\sim\mathscr{P}_{x,y}}(y{\mathbf{x}})$
$\displaystyle=\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}f^{j}(\bm{W}{\mathbf{x}}){\mathbf{x}}$
$\displaystyle=\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}\left(f^{j}(\bm{W}{\mathbf{x}})\bm{W}^{\top}\bm{W}{\mathbf{x}}+f^{j}(\bm{W}{\mathbf{x}})(I-\bm{W}^{\top}\bm{W}){\mathbf{x}}\right).$

Note that, because ${\mathbf{x}}\sim\mathcal{N}(0,I)$ so $\bm{W}{\mathbf{x}}$
and $(I-\bm{W}^{\top}\bm{W}){\mathbf{x}}$ are Gaussian.
$\bm{W}\bm{W}^{\top}=I$ implies

$\displaystyle\quad{\bm{E}}(\bm{W}{\mathbf{x}}){\mathbf{x}}^{\top}((I-\bm{W}^{\top}\bm{W}))$
$\displaystyle=\bm{W}(I-\bm{W}^{\top}\bm{W})=0.$

So $\bm{W}{\mathbf{x}}$ and $(I-\bm{W}^{\top}\bm{W}){\mathbf{x}}$ are
independent, so

$\displaystyle\quad\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}f^{j}(\bm{W}{\mathbf{x}})(I-\bm{W}^{\top}\bm{W}){\mathbf{x}}$
$\displaystyle=(\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}f^{j}(\bm{W}{\mathbf{x}}))(\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}(I-\bm{W}^{\top}\bm{W}){\mathbf{x}})=0$

Then

$\displaystyle\bm{E}_{({\mathbf{x}},y)\sim\mathscr{P}_{x,y}}(y{\mathbf{x}})$
$\displaystyle=\bm{W}^{\top}\bm{W}(\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}f^{j}(\bm{W}{\mathbf{x}}){\mathbf{x}})$
$\displaystyle=\bm{W}^{\top}\bm{W}\bm{h}_{j}(\bm{W}).$

Denote

$\displaystyle{\bm{H}}^{j}(\bm{W})=\bm{W}^{\top}\bm{W}\bm{h}^{j}(\bm{W})$
(A.2)

Because $\frac{2}{n_{j}}\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}}$ and
$\frac{2}{n_{j}}\sum_{i={n_{j}/2}+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}}$ are
independent, and their expectation are both ${\bm{H}}^{j}(\bm{W})$, so that

$\displaystyle\quad\bm{E}(\frac{2}{n_{j}}\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}})(\frac{2}{n_{j}}\sum_{i={n_{j}/2}+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}})^{\top}$
$\displaystyle={\bm{H}}^{j}(\bm{W})({\bm{H}}^{j}(\bm{W}))^{\top}.$

At then end

$\displaystyle\hat{\bm{M}}$
$\displaystyle=\frac{1}{k}\sum_{j=1}^{k}\bm{E}(\frac{2}{n_{j}}\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}})(\frac{2}{n_{j}}\sum_{i={n_{j}/2}+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}})^{\top},$
$\displaystyle\bm{M}$
$\displaystyle=\frac{1}{k}\sum_{j=1}^{k}{\bm{H}}^{j}(\bm{W})({\bm{H}}^{j}(\bm{W}))^{\top},$

so we can prove Part (c) that $\bm{E}(\hat{\bm{M}})=\bm{M}$. ∎

####  A.0.2 Proof of Theorem 3.2

We restate Theorem A.3 below.

######  Theorem A.3.

Suppose the data is generated as Def. 2.1. Let $\delta\in(0,1)$,
$\epsilon\in(0,1)$. Suppose $y{\mathbf{x}}$ is a subGaussian random vector
with covariance upper bounded by

$\displaystyle\|\mathbf{Cov}(y{\mathbf{x}})\|\leq\sigma^{2}.$ (A.3)

Define

$\displaystyle\bm{h}^{j}(\bm{W}):\mathbb{R}^{r\times
d}\rightarrow\mathbb{R}^{d}=\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}f^{j}(\bm{W}{\mathbf{x}}){\mathbf{x}}$

And let

$\displaystyle\bm{M}=\bm{W}^{\top}\bm{W}\left(\frac{1}{k}\sum_{j=1}^{k}\bm{h}^{j}(\bm{W})(\bm{h}^{j}(\bm{W}))^{\top}\right)\bm{W}^{\top}\bm{W}$

Then there exists a constant $c$, with probability at least $1-\delta$, let

$\displaystyle
k=\frac{cd}{n}\log^{2}(\frac{kd}{\delta})\max\\{\frac{1}{\epsilon^{2}},\frac{1}{\epsilon}\log(\frac{kd}{\delta})\\}$

we have

$\displaystyle\|\hat{\bm{M}}-\bm{M}\|\leq\epsilon\sigma^{2}.$

###### Proof.

The following lemmas are similar to [20] Section A.1. We extend the
concentration inequalities from bounded random vectors to Gaussian random
vectors. For completeness we place the lemmas here.

######  Lemma A.4.

([27] Cor. 7) Let $\|\mathbf{Cov}(y{\mathbf{x}})\|\leq\sigma^{2}$,
$\delta\in(0,1)$, $t>0$, ${\bm{H}}^{j}(\bm{W})$ be defined in (A.2). With
probability $1-\delta$, there exists a constant $c>0$ such that for every $j$,

$\displaystyle\|\frac{1}{t}\sum_{i=1}^{t}{y_{i,j}}{{\mathbf{x}}_{i,j}}-{\bm{H}}^{j}(\bm{W})\|\leq
c\sigma\sqrt{\frac{d}{t}\log(\frac{kd}{\delta})}$ (A.4)

Denote this event as $\mathcal{E}$.

With the covariance of $y{\mathbf{x}}$ being bounded by $\sigma^{2}$, the
following inequalities are true [20].

$\displaystyle{\bm{E}}\left((\bm{v}^{T}\cdot(\frac{1}{t}\sum_{i=1}^{t}{y_{i,j}}{{\mathbf{x}}_{i,j}}-\theta^{j}))^{2}\right)$
$\displaystyle\leq\sigma^{2}/t,\mbox{~{}for~{}}\|\bm{v}\|=1.$
$\displaystyle{\bm{E}}\left(\|\frac{1}{t}\sum_{i=1}^{t}{y_{i,j}}{{\mathbf{x}}_{i,j}}-\theta^{j}\|^{2}\right)$
$\displaystyle\leq\sigma^{2}d/t.$

######  Lemma A.5.

Define

$\displaystyle\bm{Z}_{j}$
$\displaystyle=(\frac{2}{n_{j}}\sum_{i=1}^{n_{j}/2}{y_{i,j}}{{\mathbf{x}}_{i,j}})(\frac{2}{n_{j}}\sum_{i={n_{j}/2}+1}^{n_{j}}{y_{i,j}}{{\mathbf{x}}_{i,j}})^{\top}$
$\displaystyle\quad-{\bm{H}}^{j}(\bm{W})({\bm{H}}^{j}(\bm{W}))^{\top},$

Then there exists a constant $c$ such that on the event $\mathcal{E}$ (thus
with probability $1-\delta$), for all $j=1,...,k$,

$\displaystyle\|\bm{Z}_{j}\|\leq\frac{c\sigma^{2}d}{n_{j}}\log(\frac{kd}{\delta}).$
(A.5)

The proof is almost same as [20], the only difference is that we replace the
bound in ([20] Prop A.1) by (A.4). With the similar replacement, we propose
the following lemma.

######  Lemma A.6.

Let $\delta\in(0,1)$. There exists a constant $c$, such that for any
$\epsilon\in(0,1)$, and

$\displaystyle
k=\frac{cd}{n_{j}}\log^{2}(\frac{kd}{\delta})\max\\{\frac{1}{\epsilon^{2}},\frac{1}{\epsilon}\log(\frac{kd}{\delta})\\},$
(A.6)

with probability $1-\delta$,

$\displaystyle\|\frac{1}{k}\sum_{j=1}^{k}\bm{Z}_{j}\|\leq\epsilon\sigma^{2}.$

This means that when (A.6) is true, with probability $1-\delta$,

$\displaystyle\left\|\hat{\bm{M}}-\bm{W}^{\top}\bm{W}\left(\frac{1}{k}\sum_{j=1}^{k}\bm{h}^{j}(\bm{W})(\bm{h}^{j}(\bm{W}))^{\top}\right)\bm{W}^{\top}\bm{W}\right\|\leq\epsilon\sigma^{2}.$

Note that $\bm{M}$ is defined as

$\bm{M}=\bm{W}^{\top}\bm{W}\left(\frac{1}{k}\sum_{j=1}^{k}\bm{h}^{j}(\bm{W})(\bm{h}^{j}(\bm{W}))^{\top}\right)\bm{W}^{\top}\bm{W}.$

So we have proven that with probability $1-\delta$,

$\displaystyle\left\|\hat{\bm{M}}-\bm{M}\right\|\leq\epsilon\sigma^{2}.$

∎

###  A.1 Proof of Theorem 3.4

Now we will prove Theorem 3.4. We first review the notations and assumptions
mentioned in the theorem.

####  A.1.1 Review of Notations and Assumptions

We define the SVD of $\hat{\bm{M}}$ as
$\hat{\bm{U}}\hat{\bm{{\Lambda}}}\hat{\bm{V}}^{\top}$. Let the first $r$
columns of $\hat{\bm{U}}$ be ${\bm{U}}_{r}$.

Let $\hat{\bm{W}}$ be defined as

$\displaystyle\hat{\bm{W}}$ $\displaystyle=\hat{\bm{U}}_{r}\hat{\bm{Q}},$
(A.7) $\displaystyle\hat{\bm{Q}}$
$\displaystyle=\mathop{\mathrm{argmin}}_{{\bm{Q}}\in\mathbb{R}^{r\times
r},{\bm{Q}}{\bm{Q}}^{\top}=I}\ \|\hat{\bm{U}}_{r}{\bm{Q}}-\bm{W}\|.$ (A.8)

The population cross entropy loss is defined as

$\displaystyle\mathcal{L}(f;{\bm{P}}):\mathcal{F}\times\mathbb{R}^{r\times
d}\rightarrow\mathbb{R}=$
$\displaystyle-\bm{E}_{{\mathbf{x}},y\sim\mathscr{P}_{x,y}}(y\log
f(\hat{\bm{P}}{\mathbf{x}})+(1-y)\log(1-f(\hat{\bm{P}}{\mathbf{x}}))).$

We will search for a function $f^{*}\in\mathcal{F}$.

######  Assumption 3.

$\mathcal{F}$ is a set of functions satisfying: For any function
$f\in\mathcal{F}$, any orthonormal matrix ${\bm{Q}}\in\mathbb{R}^{r\times r}$
and any matrix ${\bm{P}}\in\mathbb{R}^{r\times d}$, there exists
$g\in\mathcal{F}$ such that
$f({\bm{P}}{\mathbf{x}})=g({\bm{Q}}{\bm{P}}{\mathbf{x}})$.

Now we define a general loss function $\mathcal{L}$ and $\mathcal{L}_{e}$.

######  Assumption 4.

Suppose $\mathcal{L}$ satisfies the following assumptions:

  1. 1.

$\mathcal{L}$ has the form
$\mathcal{L}(f;{\bm{P}})=\bm{E}_{\mathscr{P}_{x,y}}{\cal{L}}^{\mathrm{single}}(f({\bm{P}}{\mathbf{x}}),y)$.
$\mathcal{L}_{e}$ has the form
$\mathcal{L}_{e}(f;{\bm{P}})=\frac{1}{n}\sum_{i=1}^{n}{\cal{L}}^{\mathrm{single}}(f({\bm{P}}{\mathbf{x}}_{i}),y_{i})$.

  2. 2.

${\cal{L}}^{\mathrm{single}}$ is $L$ Lipschitz in ${\bm{P}}{\mathbf{x}}$.

  3. 3.

$\min_{{\bm{P}}}\mathcal{L}(f;{\bm{P}})=\mathcal{L}(f;\bm{W})$.

We solve for $\hat{f}$, defined as

$\displaystyle\hat{f}$
$\displaystyle=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\
\mathcal{L}(f;\hat{\bm{U}}_{r}^{\top}).$ (A.9)

####  A.1.2 Proof of Theorem 3.4

Now we are ready to restate Theorem 3.4 and prove it.

######  Theorem A.7.

With Assumptions 3 and 4, we have that

$\displaystyle\mathcal{L}(\hat{f};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}(f^{*};{\bm{U}}_{r}^{\top})\lesssim
L\sqrt{r}\|\hat{\bm{W}}-\bm{W}\|.$

###### Proof.

We learn the model from the following optimization algorithm.

$\displaystyle\hat{f}$
$\displaystyle=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\
\mathcal{L}(f;\hat{\bm{U}}_{r}^{\top})$

Denote $\tilde{f}\in\mathcal{F}$ as the function such that
$\tilde{f}(\hat{\bm{W}}{\mathbf{x}})=\hat{f}(\hat{\bm{U}}_{r}^{\top}{\mathbf{x}})$.
So that
$\mathcal{L}(\hat{f};\hat{\bm{U}}_{r}^{\top})=\mathcal{L}(\tilde{f};\hat{\bm{W}})$.
Since $\hat{f}$ minimizes the cross entropy loss, we have that
$\mathcal{L}(\tilde{f};\hat{\bm{W}})\leq\mathcal{L}(f^{*};\hat{\bm{W}})$.

Now we have

$\displaystyle\quad\mathcal{L}(\tilde{f};\hat{\bm{W}})-\mathcal{L}(f^{*};\bm{W})$
$\displaystyle\leq\mathcal{L}(f^{*};\hat{\bm{W}})-\mathcal{L}(f^{*};\bm{W})$
$\displaystyle\leq\bm{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I)}L\|(\hat{\bm{W}}-\bm{W})x\|$
$\displaystyle\lesssim L\sqrt{r}\|\hat{\bm{W}}-\bm{W}\|.$

The last step uses the fact that $\hat{\bm{W}}$ and $\bm{W}$ are rank $r$. ∎

###  A.2 Proof of Theorem 3.5

We first state Theorem 3.5 below.

######  Theorem A.8.

Suppose we generate $n$ sample data for few shot learning solve for
$\hat{\theta}_{e}$ from

$\displaystyle\hat{\bm{\theta}}_{e}$
$\displaystyle=\mathop{\mathrm{argmin}}_{\bm{\theta}}\
\mathcal{L}_{e}(\bm{\theta};{\bm{U}}_{r}^{\top})\quad\text{such~{}that}\quad\|\bm{\theta}\|_{2}\leq
a.$ (A.10)

Suppose Assumptions 3 and 4 hold. There exist constants $c>0$,
$\delta\in(0,1)$, with probability at least $1-n^{-c+1}-\delta$, the solution
$\hat{\theta}_{e}$ and $\hat{\bm{U}}_{r}$ satisfy

$\displaystyle\quad\mathcal{L}(\hat{\theta}_{e};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}(\theta^{*};\bm{W})$
$\displaystyle\lesssim\frac{caL(\sqrt{r}+\log(n))(1+\sqrt{\log(1/\delta)})}{\sqrt{n}}+L\sqrt{r}\|\hat{\bm{W}}-\bm{W}\|.$

###### Proof.

We sketch the proof of Theorem A.8. After reviewing the notations, we quote a
standard generalization bound via Rademacher complexity in Lemma A.9. Then we
use the smoothness of the loss function to link to the generalization error of
linear functions (A.15), and then use Lemma A.10 to compute (A.15) and finish
the proof.

In few-shot learning, the true parameter is $\theta^{*}$, and the empirical
loss function with finite data is

$\displaystyle\mathcal{L}_{e}(\theta;{\bm{P}}):\mathcal{F}\times\mathbb{R}^{r\times
d}\rightarrow\mathbb{R}=\frac{1}{n}\sum_{i=1}^{n}{\cal{L}}^{\mathrm{single}}(f({\bm{P}}{\mathbf{x}}_{i}),y_{i})$
(A.11)

Denote each term in the summation as

$\displaystyle\quad\mathcal{L}_{e}^{i}(\theta;{\bm{P}}):\mathcal{F}\times\mathbb{R}^{r\times
d}\rightarrow\mathbb{R}={\cal{L}}^{\mathrm{single}}(f({\bm{P}}{\mathbf{x}}_{i}),y_{i}).$

We search for the solution by

$\displaystyle\hat{\theta}_{e}$
$\displaystyle=\mathop{\mathrm{argmin}}_{\theta}\
\mathcal{L}_{e}(\theta;{\bm{U}}_{r}^{\top}),\mbox{~{}such~{}that~{}}\|\theta\|\leq
a.$ (A.12)

In Theorem A.7, we know that

$\displaystyle\mathcal{L}(\hat{\theta};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}(\theta^{*};{\bm{U}}_{r}^{\top})\lesssim
L\sqrt{r}\|\hat{\bm{W}}-\bm{W}\|.$

Denote

$\displaystyle M=\max_{\|\theta\|\leq
a}|\theta^{\top}\hat{\bm{U}}_{r}^{\top}{\mathbf{x}}_{i}|\leq
a\max\|\hat{\bm{U}}_{r}^{\top}{\mathbf{x}}_{i}\|.$ (A.13)

We will bound the difference between $\mathcal{L}$ and $\mathcal{L}_{e}$ by
Rademacher complexity theory.

######  Lemma A.9.

[28]

Let ${\mathscr{U}}$ be the independent random variables uniformly chosen from
$\\{-1,1\\}$. Let $\mathcal{R}$ be the Rademacher complexity of the logistic
functionals defined on the data,

$\displaystyle\mathcal{R}$
$\displaystyle=\frac{1}{n}{\bm{E}}_{\epsilon_{i}\in{\mathscr{U}}}\sup_{\|\theta\|\leq
a}\sum_{i=1}^{n}\epsilon_{i}\mathcal{L}_{e}^{i}(\theta;\hat{\bm{U}}_{r}^{\top})$
$\displaystyle K$
$\displaystyle=\max_{i}\mathcal{L}_{e}^{i}(\theta;\hat{\bm{U}}_{r}^{\top})\leq
M.$

with probability $1-\delta$, we have that

$\displaystyle|\mathcal{L}_{e}(\theta;{\bm{U}}_{r}^{\top})-\mathcal{L}(\theta;{\bm{U}}_{r}^{\top})|\leq\mathcal{R}+\frac{\sqrt{\log(1/\delta)}}{\sqrt{n}}K.$

Thus we have that

$\displaystyle|\mathcal{L}(\hat{\theta}_{e};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}_{e}(\hat{\theta}_{e};\hat{\bm{U}}_{r}^{\top})|$
$\displaystyle\leq\mathcal{R}+\frac{\sqrt{\log(1/\delta)}}{\sqrt{n}}K,$
$\displaystyle|\mathcal{L}(\hat{\theta};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}_{e}(\hat{\theta};\hat{\bm{U}}_{r}^{\top})|$
$\displaystyle\leq\mathcal{R}+\frac{\sqrt{\log(1/\delta)}}{\sqrt{n}}K.$

Because $\hat{\theta}_{e}$ minimizes the empirical loss $\mathcal{L}_{e}$,

$\displaystyle\mathcal{L}_{e}(\hat{\theta}_{e};\hat{\bm{U}}_{r}^{\top})\leq\mathcal{L}_{e}(\hat{\theta};\hat{\bm{U}}_{r}^{\top}).$

Thus

$\displaystyle\mathcal{L}(\hat{\theta}_{e};\hat{\bm{U}}_{r}^{\top})-\mathcal{L}(\hat{\theta};\hat{\bm{U}}_{r}^{\top})\leq
2\left(\mathcal{R}+\frac{\sqrt{\log(1/\delta)}}{\sqrt{n}}K\right).$ (A.14)

So the remaining target is to bound $\mathcal{R}$.

We first denote $\bm{v}_{i}=\hat{\bm{U}}_{r}^{\top}{\mathbf{x}}_{i}$, so
$\bm{v}_{i}\in\mathbb{R}^{r}$ and $\bm{v}_{i}$ are jointly independent
standard normal random variables. $\mathcal{L}_{e}^{i}$ is always $L$
Lipschitz in $\theta^{\top}\bm{v}_{i}$, the Rademacher complexity can be upper
bounded by

$\displaystyle\mathcal{R}\leq\tilde{\mathcal{R}}:=\frac{L}{n}{\bm{E}}_{\epsilon_{i}\in{\mathscr{U}}}\sup_{\|\theta\|\leq
a}\sum_{i=1}^{n}\epsilon_{i}\theta^{\top}\bm{v}_{i}.$ (A.15)

We first refer to the following lemma.

######  Lemma A.10.

[29] Let $c>0$, $X$ follow $\chi_{r}^{2}$ distribution, then

$\displaystyle{\bm{P}}(X-r\geq 2\sqrt{cr\log n}+2c\log n)\leq n^{-c}.$

For a constant $c>1$, via union bound we have that
$\max{\|\bm{v}_{i}\|^{2}}\leq r+2\sqrt{cr\log n}+2c\log n$ for all $i=1,..,n$
with probability $1-n^{-c+1}$. We use $\max{\|\bm{v}_{i}\|}\lesssim
c(\sqrt{r}+\log(n))$ for simplicity.

Conditioned on this event, we apply the Rademacher complexity for linear model
that

$\displaystyle\tilde{\mathcal{R}}$
$\displaystyle\leq\frac{L\max\|\theta\|\cdot\max\|\bm{v}_{i}\|}{\sqrt{n}}$
(A.16) $\displaystyle\leq\frac{caL(\sqrt{r}+\log(n))}{\sqrt{n}}.$ (A.17)

Combining with (A.14) and Theorem A.7 we get the bound in Theorem A.8. We can
also bound $M$ in (A.13).

Finally we will use Lemma A.11 to bound $M$.

######  Lemma A.11.

Let $M$ be defined as in (A.13). With probability at least $1-n^{-c+1}$, we
have $M<caL(\sqrt{r}+\log(n))$.

Let $\bm{v}_{i}$ be replaced by $\hat{\bm{U}}_{r}^{\top}{\mathbf{x}}_{i}$ in
Lemma A.10, then this directly results from Lemma A.10. Lemma A.11 bounds $M$,
thus bounds $K$ (which is $L$ Lipschitz in $M$) in Lemma A.9. After we insert
(A.17) together into Lemma A.9, we can get the result in Theorem 3.5. ∎