summaries: This paper gives a new empirical approach for learning schemes for compressing high-dimensional neural representations into binary codes over a small number of dimensions. Given labeled examples and a fixed neural architecture with d-dimensional output, they give a two-phase algorithm for learning weights for the network, a low-dimensional projector to a k-dimensional subspace of R^d, and a binary "codebook" matrix B(C) mapping the k-dimensional subspace to R^L, where L is the number of classes. The goal is to do this for k as close to log_2(L) as possible while mostly preserving test accuracy.  Concretely, the embedding g maps any input x to the Boolean vector given by the entrywise sign of the k-dimensional projection of the network's output under x, and B(C) maps any such g(x) to an L-dimensional vector corresponding to the scores of the different classes. In the first phase of the algorithm, they simply run ERM to simultaneously find some weights, projector, and codebook, using a standard heuristic to get around the fact that B(C) is discrete-valued. In the second phase, they train the weights and projector further by essentially encouraging the embedding to align with the codebook.   The distinguishing feature of this approach is that the codebook and embedding are learning in conjunction rather than separately. Empirically over ImageNet-1K, they found that under two natural decoding schemes, the resulting classifiers beat a number of baseline approaches that separately constructed a codebook and then learned an embedding. Additionally, the accuracy is only ~3% less than the standard ResNet50 baseline.  As other applications, they showed that for image retrieval, the learnt embedding can be used as a hash function, outperforming HashNet and GreedyHash. They also gave an application to out-of-distribution detection which is comparable to certain baselines but notably does not need samples from the out-of-distribution domain.

summaries: This work proposes a two-phase method for learning low-dimensional binary codes via the standard classification task without side-information. Specifically, binary codes for classes are learned via a surrogate classification task in the first phase. On top of that, instance codes are learned using the Error-Correcting Output Codes approach.

summaries: This paper studies the problem of learning binary vector representations of instances and classes. We pick a small dimension k (the paper uses k=20) and aim to learn a k-dimensional binary vector for each input and each label. Compressing the data into small-dimensional binary codes like this is challenging, but provides many benefits in terms of the space usage (the representations are very small) and the time to do lookups and find nearby neighbors.  The paper presents a new method called LLC which simultaneously finds codewords for both inputs and labels without using any side-information. They claim (and I have no reason to doubt this) that this is the first time a method for this has been designed. LLC consists of two phases:  In the first phase, the LLC method learns a codebook (low-dimensional bianry code for each label) by using the popular Straight-Through Estimator technique to do empirical risk minimization.   In the second phase, the ECOC framework is used to classify the inputs according to this codebook. The algorithm treats each of the k bits of the code completely separately, and hence solves k disjoint binary classification problems instead of one multi-class (with L or 2^k classes) problem. This gives an additive 2% improvement to accuracy over just solving the optimization problem to classify all k bits together, since out of the box optimization finds fairly suboptimal solutions when trying to classify a length k vector all at once. (In other words, the second phase uses a heuristic where sepaartely learning each of the k bits works better than learning all k at once for the current optimization software which is well-suited to doing binary classification.)  The resulting classification accuracy seems quite good: 68.82% of inputs are assigned exactly the same binary code as their label, and 74.57% are assigned a binary code which is closer to the code of their label than any other label.  The result of this binary code classification can now be used in a number of applications, including: - the binary codebook can be naturally used to make a taxonomy visualization for the labels.  - the system can be used for efficient (in terms of representation size and running time of retrieval) multi-class classification. - out-of-distribution detection can be done by seeing whether an input is mapped to the same codeword as any label. (I'm confused about how effective this can be when the original inputs are only correctly mapped to the codeword of their label 69% of the time.)

summaries: Low-dimensional binary codes are important for a variety of large-scale ml tasks, especially retrieval. This paper proposed a method called LLC for learning semantially meaningful low-dimensional biary codes. Compare to the existing literature, LLC can learn both class and instance codes together without side-information:  (1) couple the learning process of both feature and class embedding and capture the sematic structure better (2) naturally benefits downstream tasks like OOD.

summaries: This work propose a method for learning low-dimensional binary codes for instance and classes. It is appealing in classification with large scale number of classes. The method is claimed super-efficient in learning and able to ensure nearly optimal classification accuracy. The learnt class code discovers some intuitive taxonomy over subset of classes selected from ImageNet. The method is applicable in image retrieval and out-of-distribution detection.

abstractText: Learning binary representations of instances and classes is a classical problem with several high potential applications. In modern settings, the compression of high-dimensional neural representations to low-dimensional binary codes is a challenging task and often require large bit-codes to be accurate. In this work, we propose a novel method for Learning Low-dimensional binary Codes (LLC) for instances as well as classes. Our method does not require any side-information, like annotated attributes or label meta-data, and learns extremely low-dimensional binary codes (≈ 20 bits for ImageNet-1K). The learnt codes are super-efficient while still ensuring nearly optimal classification accuracy for ResNet50 on ImageNet-1K. We demonstrate that the learnt codes capture intrinsically important features in the data, by discovering an intuitive taxonomy over classes. We further quantitatively measure the quality of our codes by applying it to the efficient image retrieval as well as out-of-distribution (OOD) detection problems. For ImageNet-100 retrieval problem, our learnt binary codes outperform 16 bit HashNet using only 10 bits and also are as accurate as 10 dimensional real representations. Finally, our learnt binary codes can perform OOD detection, out-of-the-box, as accurately as a baseline that needs ≈ 3000 samples to tune its threshold, while we require none. Code is open-sourced at https://github.com/RAIVNLab/LLC.

authors:
Z. Akata
F. Perronnin
Z. Harchaoui
C. Schmid

title: Label-embedding for image classification

venue: IEEE transactions on pattern analysis and machine intelligence, 38(7):1425–1438

authors:
Z. Akata
S. Reed
D. Walter
H. Lee
B. Schiele

title: Evaluation of output embeddings for fine-grained image classification

venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2927–2936

authors:
E.L. Allwein
R.E. Schapire
Y. Singer

title: Reducing multiclass to binary: A unifying approach for margin classifiers

venue: Journal of machine learning research, 1(Dec):113–141

title: Learning error-correcting representations for multi-class problems

venue: PhD thesis, Universitat de Barcelona,

authors:
S. Bengio
J. Weston
D. Grangier

title: Label embedding trees for large multi-class tasks

venue: Proceedings of the 23rd International Conference on Neural Information Processing Systems- Volume 1, pages 163–171

authors:
Y. Bengio
N. Léonard
A. Courville

title: Estimating or propagating gradients through stochastic neurons for conditional computation

venue: arXiv preprint arXiv:1308.3432

title: K-d trees for semidynamic point sets

venue: Proceedings of the sixth annual symposium on Computational geometry, pages 187–197

authors:
K. Bhatia
H. Jain
P. Kar
M. Varma
P. Jain

title: Sparse local embeddings for extreme multi-label classification

venue: NIPS, volume 29, pages 730–738

authors:
Z. Cao
M. Long
J. Wang
P.S. Yu

title: Hashnet: Deep learning to hash by continuation

venue: Proceedings of the IEEE international conference on computer vision, pages 5608–5617

authors:
Z. Cao
M. Long
J. Wang

title: and P

venue: S. Yu. Hashnet: Deep learning to hash by continuation

authors:
M.A. Carreira-Perpinán
R. Raziperchikolaei

title: Hashing with binary autoencoders

venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 557– 566

authors:
A. Choromanska
K. Choromanski
M. Bojarski
T. Jebara
S. Kumar
Y. LeCun

title: Binary embeddings with structured hashed projections

venue: International Conference on Machine Learning, pages 344–353. PMLR

authors:
M. Cissé
N. Usunier
T. Artieres
P. Gallinari

title: Robust bloom filters for large multilabel classification tasks

venue: Advances in Neural Information Processing Systems 26, pages 1851– 1859

authors:
K. Crammer
Y. Singer

title: On the algorithmic implementation of multiclass kernel-based vector machines

venue: Journal of machine learning research, 2(Dec):265–292

authors:
K. Dahiya
D. Saini
A. Mittal
A. Shaw
K. Dave
A. Soni
H. Jain
S. Agarwal
M. Varma

title: Deepxml: A deep extreme multi-label learning framework applied to short text documents

venue: Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 31–39

authors:
M. Datar
N. Immorlica
P. Indyk
V.S. Mirrokni

title: Locality-sensitive hashing scheme based on p-stable distributions

venue: Proceedings of the twentieth annual symposium on Computational geometry, pages 253–262

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee

authors:
J. Deng
A.C. Berg
L. Fei-Fei

title: Hierarchical semantic indexing for large scale image retrieval

venue: CVPR 2011, pages 785–792. IEEE

authors:
T.G. Dietterich
G. Bakiri

title: Solving multiclass learning problems via error-correcting output codes

venue: Journal of artificial intelligence research, 2:263–286

authors:
S. Escalera
O. Pujol
P. Radeva

title: Error-correcting ouput codes library

venue: The Journal of Machine Learning Research, 11:661–664

authors:
A. Farhadi
I. Endres
D. Hoiem
D. Forsyth

title: Describing objects by their attributes

venue: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 1778–1785. IEEE

authors:
V. Ferrari
A. Zisserman

title: Learning visual attributes

venue: Advances in neural information processing systems, 20:433–440

authors:
Y. Gong
S. Lazebnik
A. Gordo
F. Perronnin

title: Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval

venue: IEEE transactions on pattern analysis and machine intelligence, 35(12):2916–2929

authors:
C. Guo
A. Mousavi
X. Wu
D. Holtmann-Rice
S. Kale
S.J. Reddi
S. Kumar

title: Breaking the glass ceiling for embedding-based classifiers for large output spaces

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770– 778

authors:
D. Hendrycks
K. Gimpel

title: A baseline for detecting misclassified and out-of-distribution examples in neural networks

venue: arXiv preprint arXiv:1610.02136

authors:
A.G. Howard
M. Zhu
B. Chen
D. Kalenichenko
W. Wang
T. Weyand
M. Andreetto
H. Adam

title: Mobilenets: Efficient convolutional neural networks for mobile vision applications

venue: arXiv preprint arXiv:1704.04861

authors:
D. Hsu
S.M. Kakade
J. Langford
T. Zhang

title: Multi-label prediction via compressed sensing

venue: arXiv preprint arXiv:0902.1284

authors:
I. Hubara
M. Courbariaux
D. Soudry
R. El-Yaniv
Y. Bengio

title: Binarized neural networks

venue: Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 4114–4122

authors:
H. Jain
V. Balasubramanian
B. Chunduri
M. Varma

title: Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches

venue: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 528–536

authors:
A. Krizhevsky
I. Sutskever
G.E. Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Advances in neural information processing systems, 25:1097–1105

authors:
B. Kulis
T. Darrell

title: Learning to hash with binary reconstructive embeddings

venue: NIPS, volume 22, pages 1042–1050. Citeseer

authors:
B. Kulis
K. Grauman

title: Kernelized locality-sensitive hashing for scalable image search

venue: 2009 IEEE 12th international conference on computer vision, pages 2130–2137. IEEE

authors:
B. Kulis
P. Jain
K. Grauman

title: Fast similarity search for learned metrics

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12):2143–2157

authors:
A. Kusupati
V. Ramanujan
R. Somani
M. Wortsman
P. Jain
S. Kakade
A. Farhadi

title: Soft threshold weight reparameterization for learnable sparsity

venue: International Conference on Machine Learning, pages 5544–5555. PMLR

authors:
C.H. Lampert
H. Nickisch
S. Harmeling

title: Learning to detect unseen object classes by between-class attribute transfer

venue: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 951–958. IEEE

title: Attribute-based classification for zero-shot visual object categorization

venue: IEEE transactions on pattern analysis and machine intelligence, 36(3):453–465

authors:
H. Liu
R. Wang
S. Shan
X. Chen

title: Deep supervised hashing for fast image retrieval

venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2064–2072

authors:
X. Luo
C. Chen
H. Zhong
H. Zhang
M. Deng
J. Huang
X. Hua

title: A survey on deep hashing methods

venue: arXiv preprint arXiv:2003.03369

authors:
Y.A. Malkov
D.A. Yashunin

title: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs

venue: IEEE transactions on pattern analysis and machine intelligence, 42(4):824–836

title: Wordnet: a lexical database for english

venue: Communications of the ACM, 38(11): 39–41

authors:
F. Murtagh
P. Contreras

title: Algorithms for hierarchical clustering: an overview

venue: Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1):86–97

authors:
M. Norouzi
D.J. Fleet
R.R. Salakhutdinov

title: Hamming distance metric learning

venue: Advances in neural information processing systems, pages 1061–1069

authors:
M. Norouzi
T. Mikolov
S. Bengio
Y. Singer
J. Shlens
A. Frome
G.S. Corrado
J. Dean

title: Zero-shot learning by convex combination of semantic embeddings

venue: arXiv preprint arXiv:1312.5650

authors:
A. Paszke
S. Gross
F. Massa
A. Lerer
J. Bradbury
G. Chanan
T. Killeen
Z. Lin
N. Gimelshein
L. Antiga

title: et al

venue: Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024–8035

authors:
Y. Prabhu
A. Kusupati
N. Gupta
M. Varma

title: Extreme regression for dynamic search advertising

venue: Proceedings of the 13th International Conference on Web Search and Data Mining, pages 456–464

authors:
M. Rastegari
A. Farhadi
D. Forsyth

title: Attribute discovery via predictable discriminative binary codes

venue: European Conference on Computer Vision, pages 876–889. Springer

authors:
M. Rastegari
V. Ordonez
J. Redmon
A. Farhadi

title: Xnor-net: Imagenet classification using binary convolutional neural networks

venue: European conference on computer vision, pages 525–542. Springer

authors:
O. Russakovsky
J. Deng
H. Su
J. Krause
S. Satheesh
S. Ma
Z. Huang
A. Karpathy
A. Khosla
M. Bernstein

title: et al

venue: Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211–252

authors:
R. Salakhutdinov
G. Hinton

title: Learning a nonlinear embedding by preserving class neighbourhood structure

venue: Artificial Intelligence and Statistics, pages 412–419. PMLR

title: Semantic hashing

venue: International Journal of Approximate Reasoning, 50(7):969–978

authors:
F. Shen
Y. Xu
L. Liu
Y. Yang
Z. Huang
H.T. Shen

title: Unsupervised deep hashing with similarity-adaptive and discrete optimization

venue: IEEE transactions on pattern analysis and machine intelligence, 40(12):3034–3044

authors:
S. Su
C. Zhang
K. Han
Y. Tian

title: Greedy hash: Towards fast optimization for accurate hash coding in cnn

venue: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 806–815

title: Extreme classification

venue: Communications of the ACM, 62(11):44–45

authors:
M. Wallingford
A. Kusupati
K. Alizadeh-Vahid
A. Walsman
A. Kembhavi

title: and A

venue: Farhadi. Are we overfitting to experimental setups in recognition? arXiv preprint arXiv:2007.02519

authors:
J. Wang
W. Liu
S. Kumar
S.-F. Chang

title: Learning to hash for indexing big data—a survey

venue: Proceedings of the IEEE, 104(1):34–57

authors:
Y. Weiss
A. Torralba
R. Fergus

title: et al

venue: Spectral hashing. In Advances in Neural Information Processing Systems

authors:
J. Weston
S. Bengio
N. Usunier

title: Wsabie: Scaling up to large vocabulary image annotation

venue: Twenty-Second International Joint Conference on Artificial Intelligence

authors:
T. Weyand
A. Araujo
B. Cao
J. Sim

title: Google landmarks dataset v2-a large-scale benchmark for instance-level recognition and retrieval

venue: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2575–2584

authors:
M. Wortsman
A. Farhadi
M. Rastegari

title: Discovering neural wirings

venue: arXiv preprint arXiv:1906.00586

authors:
H.-F. Yu
P. Jain
P. Kar
I. Dhillon

title: Large-scale multi-label learning with missing labels

venue: International conference on machine learning, pages 593–601. PMLR

authors:
X. Yuan
L. Ren
J. Lu
J. Zhou

title: Relaxation-free deep hashing via policy gradient

venue: Proceedings of the European Conference on Computer Vision (ECCV), pages 134–150

title: A survey on deep hashing for image retrieval

venue: arXiv preprint arXiv:2006.05627

authors:
Y. Zhang
J. Schneider

title: Multi-label output codes using canonical correlation analysis

venue: Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 873–882. JMLR Workshop and Conference Proceedings

authors:
B. Zhou
A. Lapedriza
J. Xiao
A. Torralba
A. Oliva

venue: Advances in Neural Information Processing Systems

heading: 1 Introduction

text:
Embedding data in low-dimensional binary space is a long-standing machine learning problem [56]. The problem has received a lot of interest in the computer vision (CV) domain, where the goal is to find binary codes that capture the key semantics of the image, like, objects present in the image or interpretable attributes. Section 2 covers the literature on learning binary codes and their applications.
In addition to learning semantically meaningful representations of the instances, low-dimensional binary codes allow efficiency in a variety of large-scale machine learning (ML) applications. Lowdimensional codes are crucial in extreme classification with millions of classes [8, 30, 15] and also critical in efficient large-scale retrieval settings [38, 16, 59].
Compressing information into binary codes is challenging due to its highly non-smooth nature while requiring the preservation of relevant information in an instance/class. This might explain the lack of good classification accuracy for existing classification-based embedding techniques [28, 13]. To address that, traditional methods often relied on side-information like attributes to construct class codes and then use that to learn the instance codes [18, 1].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Learning binary embeddings can be posed in a variety of formulations like pairwise optimization [34] or unsupervised learning [11, 50], in this work we focus on learning binary codes using a given labeled multi-class dataset, e.g., ImageNet-1K. This allows us to couple the representation (code) learning of both instances and classes thus enabling us to capture the underlying semantic structure efficiently to assist in downstream tasks like classification, retrieval etc.
We propose LLC, a method to learn both class and instance codes via the standard classification task and its setup without any side-information. Our Learning Low-dimensional binary Codes (LLC) technique, formulates the embedding (code) learning problem as that of learning a low-dimensional binary embedding of a standard deep neural “backbone”. Instead of directly training for the lowdimensional binary instance codes, we propose a two-phase approach. In the first phase, LLC learns low-dimensional (k-bit) binary codes for classes that capture semantic information through a surrogate classification task. Then in the second phase, LLC uses these learnt class codes as an efficient alternative to learning instance codes in sub-linear cost (in the number of classes, L) using the Error-Correcting Output Codes (ECOC) approach [19]. This two-phase pipeline helps in the effective distillation of required semantic similarity between instances through the learnt class codes. For example, on ImageNet-1K with ResNet50, LLC is able to learn tight 20-bit codes that can be used for efficient classification and achieve 74.5% accuracy compared to the standard baseline 77% on ImageNet-1K (Section 4.1). Furthermore, we observe that the learnt 20-bit class codes capture intuitive taxonomy over classes (Figure 1) while the instance codes retain the distilled class similarity information useful in efficient retrieval and OOD detection.
Retrieval. To further study, the effectiveness of our learnt binary codes, we apply them to hashingbased efficient retrieval, where the goal is to retrieve a large number of similar instances with the same class label in top retrieved samples. Deep supervised hashing is a widely studied problem with several recent results [9, 53] which are designed specifically for the learnt hashing-based retrieval. Interestingly, our learnt instance codes through the LLC routine provide strikingly better performance while not being learnt explicitly for hashing. For eg., using AlexNet, with just 32-bit codes we are can provide 5.4% more accurate retrieval than HashNet’s 64-bit codes on ImageNet-100 (Section 4.2).
OOD Detection. We similarly apply LLC based learnt binary codes to detect OOD instances [26]. We adopt a simple approach based on our binary codes: if an instance is not within a Hamming distance of 1 to any class codes, we classify it as OOD. That is, we do not fine-tune our OOD detector for the new domain, which is critical in practical settings. In contrast, baseline techniques for OOD detection require a few samples (eg., ≈ 3000 for ImageNet-750) from the OOD domain to fine-tune thresholds, while we require no samples yet reaching similar OOD detection (Section 4.3).
In this work, we make the following key contributions:
• LLC method to learn semantically-rich low-dimensional binary codes for both classes & instances. • Show that the learnt codes enable accurate & efficient classification: ImageNet-1K with 20-bits. • Apply LLC to image retrieval task, and demonstrate that it comfortably outperforms the instance
code learning methods for hashing-based retrieval on ImageNet-100. • Finally, use codes from LLC for strong & sample efficient OOD detection in practical settings.

heading: 2 Related Work

text:
Binary class codes were originally aimed at sub-linear training and prediction for multi-class classification. The Error-Correcting Output Codes (ECOC) framework [19, 3, 20] reformulated multi-class classification as multi-label classification using k-bit codes per class (codebook). The learning of optimal codebook is NP-complete [14] which lead to use of random codebooks [28, 13] in traditional ML. However, there were a few codebook learning [5, 64, 58, 4] and construction schemes using side-information from other modalities [1]. The lack of a strong learnable feature extractor often deterred the gains these codebooks provide for the classification and effective learning of instance codes. Attribute annotations can also help in constructing class codes [2]. These binary codes are either explicitly annotated [21] or discovered [47, 22]. Attributed-based learning also ties into leveraging the class codes for zero/few-shot learning [36, 37, 1, 44] expecting some form of interpretability.
Most methods that use class codes as supervision can produce instance codes [19]. However, the standalone literature of instance codes comes from requirements in large-scale application like retrieval (hashing). In the past, most hashing techniques that created instance codes were based on
random projections [16, 13, 12], semantics [51, 18] or learnt through metric learning [34, 33, 43, 32], clustering [57, 50] and quantization [23]. Deep learning further helped in learning more accurate hashing functions to generate instance codes either in an unsupervised [11, 52] or supervised [38, 9, 53, 62] fashion. We refer to [39, 63, 56] for a more thorough review on deep hashing methods.
Finally, embedding-based classification [13, 61, 8, 24] enables joint low-dimensional representation learning for both classes and instances with an eye on sub-linear training and prediction costs. After distilling the key ideas from the literature, we aim to a) learn semantically rich low-dimensional representations for both classes and instances together, b) have these representations in the binary space, and c) do this with minimal dependence on side-information or metadata.
LLC, to the best of our knowledge - for the first time, jointly learns low-dimensional binary codes for both classes and instances using a surrogate classification task, without any side-information (Section 3). The learnt class codes capture intrinsic information at the semantic level that helps in discovering an intuitive taxonomy over classes (Figure 1). The learnt class codes then anchor the instance code learning which results in tight and accurate low-dimensional instance codes further used in retrieval (Section 4.2). Finally, both the learnt class and instance codes power extremely efficient yet accurate classification (Section 4.1) and out-of-distribution detection (Section 4.3).

heading: 3 Learning Low-dimensional Binary Codes

text:
The goal is to learn a binary embedding (code) function g : X → {−1, 1}k where X is the input domain and k is the dimensionality of the code. We focus on learning embeddings using a labelled multi-class data [28]. That is, suppose we are given a labelled dataset D = {(x1, y1), . . . , (xn, yn)} where xi ∈ X is an input point and yi ∈ [L] is the label of xi for all i ∈ [n]. Then, the goal is to learn an instance embedding function g : X → {+1,−1}k and class embeddings hq ∈ {+1,−1}k for all q ∈ [L] such that g(xi) = hyi and g(xi) = g(xj) if and only if yi = yj . Intuitively, for large-scale datasets, g(x) and hq should capture key semantic information to provide accurate classification, thus allowing their use in application domains like retrieval or OOD detection. Note that while we present our technique for learning embeddings using multi-class datasets, it applies more generally to multi-labeled datasets as well.
Instance and Class Code Parameterization. For learning such embedding function, we assume access to a deep neural architecture F ( · ; θF ) : X → Rd that maps the input x ∈ X to a d-dimensional real-valued representation. θF is a learnable parameterization of the network; we drop θF from F wherever the meaning is clear from the context. For example, ResNet50 is one such network that encodes 224× 224 RGB images into d = 2048 dimensions. Now, given a network F and x ∈ X , we formulate embedding function of x and the corresponding multiclass prediction scores ŷ ∈ ZL as:
g(x) := B (P · F (x; θF )) , ŷ := B(C) · g(x) , (1)
where P ∈ Rk×d maps F (x) into k-dimensions and B(a) = sign(a) ∈ {+1,−1} is the standard binarization/sign operator applied elementwise (with the assumption sign(0) = +1). Finally, C ∈ RL×k, and ŷ = B(C) · g(x) represents the scores of each class for an input x. Note that for a class ` ∈ [L], B(C`) (where C` represents the `-th row of C) is the learnt binary class embedding (code) of class ` ∈ [L], and g(x) = B(P · F (x; θF )) is the learnt instance embedding (code) of instance x. Note that (1) is a general purpose formulation for the problem of learning class and instance codes.
3.1 The LLC Method
Phase 1: Codebook Learning – B(C). Given labelled examples D, we use standard empirical risk minimization to learn a multi-class classifier, i.e., we solve
min C,P,θF ∑ (xi,yi)∈D L (B(C) · (P · F (xi; θF )) ; yi) , (2)
where L : RL × [L]→ R+ is the standard multi-class softmax cross-entropy loss function. This is a standard optimization problem that can be solved using standard gradient descent methods or other
sub-gradient based optimizers. However, one challenge is that B(C) is a binary matrix and B is a binary function, so the gradients are 0 almost everywhere. Instead, we use the Straight-Through Estimator (STE) [6] technique popular in binary neural networks domain [48], to optimize for C through the binarization. Intuitively, STE uses binarization/sign function in the forward pass, but in the backpropagation phase, it allows the gradients to flow straight-through as if it were real-valued. The codebook, B(C) refers to the collection of k-bit class codes learnt in this process.
For ImageNet-1K, we learnt unique binary codes, B(C`), for every class ` ∈ [L] of the 1000 classes using only 20-bits, only twice the information-theoretic limit. As with the class representations from a linear classifier, these class codes do capture intrinsically important features that help in discovering intuitive taxonomy over classes (Section 3.2) among various applications (Section 4).
Phase 2: Instance Code Learning – B(P · F (x; θF )). Several existing techniques model C and P in different ways to learn an embedding function similar to (1). However, these methods often try to only learn instance codes and have challenges in maintaining high accuracy [9, 11] in a variety of applications because optimization problem (2) is challenging and might lead to significantly sub-optimal classification error. For example, for ImageNet-1K classification with ResNet50, the accuracy for our trained model (20-bits) at this stage is 72.5% compared to the standard 77%.
To remedy this, we further optimize our embeddings using the ECOC framework [19] for multi-class classification, which essentially transforms the multi-class problem into a multi-label problem, which in turn is k independent binary classification problems. That is, we use the k-bit codes learnt for each class as the supervision to further train F ( · ; θF ) and P:
min θF ,P ∑ (xi,yi)∈D k∑ j=1 BCE (σ(Pj · F (xi; θF )) ; (B(Cyi,j) + 1) /2) , (3)
where σ is the sigmoid/logistic function, BCE is the binary cross-entropy loss between the j-th bit of instance xi’s embedding, and the j-th bit extracted from the class embedding of it’s label yi (the function z 7→ (z + 1)/2 is used to map {+1,−1} to {1, 0} to make it a simple binary classification problem per each bit). We use gradient based optimization to learn θF and P. As mentioned earlier, ECOC framework allows us to correct errors in classification. For example, with just 20 bits on ImageNet-1K dataset, the method now achieves 74.5% accuracy with ResNet50 backbone.
The advantage of this two-phase pipeline where we start with a codebook learning for classes is that the cost of learning instances codes reduces to a bottleneck of k-dims ( L) instead of the usual L . Furthermore, these learnt low-dimensional binary codes for both classes and instances help in large-scale applications via efficient classification and retrieval (see Section 4). Note that, unlike attribute-based methods [37], we do not require additional meta-data, but learn binary codes by only using the standard classification task. This also circumvents the potential instabilities of pairwise optimization in instance binary code learning which often leads to poor class codes due to codebook collapse. At the end of LLC routine, we have learnt the instance codes, B(P · F (x; θF )), and class codes, B(C) to be used for downstream applications. Algorithm 1 presents LLC in full.
Algorithm 1 The LLC Method Input: D, F and B Output: C, P and θF
1: Codebook Learning – B(C): Solve (2) using ERM and STE to get C, P and θF -
C,P, θF ← argmin C,P,θF ∑ (xi,yi)∈D L (B(C) · (P · F (xi; θF )) ; yi) .
2: Instance Code Learning – B(P · F (x; θf )): Further optimize P and θF by solving (3) using ECOC framework and ERM by fixing C -
θF , P ← argmin θF ,P ∑ (xi,yi)∈D k∑ j=1 BCE (σ(Pj · F (xi; θF )) ; (B(Cyi,j) + 1) /2) .
Overall, we present a simple yet scalable method to learn low-dimensional (exact) binary codes for both classes and instances which in turn could power multi-class classification with sub-linear costs (in terms of L) and efficient retrieval for large-scale applications. Using our method, we can consistently learn unique low-dimensional binary codes for all 1000 classes in ImageNet-1K using only 20-bits (which is twice the information-theoretic limit of dlog2(1000)e). Next, we discuss the learnt codebook’s intrinsic information about the classes and their structure.

heading: 3.2 Discovered Taxonomy and Visualizations

text:
After learning the 20-bit binary codebook for 1000 classes of ImageNet-1K, we used the class representation from B(C) of the first 50 classes to discover an intuitive taxonomy through agglomerative clustering [42]. Figure 1 shows the discovered hierarchy. This hierarchy effectively separates birds from amphibians; frogs and chickens are on extremes of the taxonomy and brings species with shared similarities closer (lizards & crocodiles; marine life). While the taxonomy is not perfect, the 20-bits do capture enough important information that can be used downstream.
Figure 2 shows the pair-wise inner-product heat maps for all the 1000 classes using 20-bits and 2048-dimensional real representation; the comparison reveals that 20-bits indeed highlights the same substructures as the higher dimensional real-valued embeddings. Appendix D has a more detailed discussion about quantitatively evaluating the discovered hierarchy and more visualizations.

heading: 4 Applications

text:
In this section, we discuss three applications of the learnt low-dimensional binary codes: 1) efficient multi-class classification (Section 4.1), 2) efficient retrieval (Section 4.2), and 3) out-of-the-box
out-of-distribution (OOD) detection (Section 4.3). We also present ablation studies on codebook learning, feature separability and classification (Section 4.4).

heading: 4.1 Efficient Multi-class Classification

text: Recall that the proposed LLC algorithm outputs a) the learnt class codes (codebook), B(C) and b) an encoder that produces instance codes, B(P · F (x; θF )) for x. We define a class codebook as a collection of L binary vectors, one for each class in the dataset, that can then be used for classification of a test instance x. We can use several “decoding" routines to classify an instance x, given its encoding and the learnt codebook. Below we discuss two decoding schemes that are diametrically opposite in terms of the inference cost. Also, note that the standard linear classification with real-valued representation and classifiers scale as O(L) in terms of computational complexity and model size.

heading: 4.1.1 Decoding Schemes

text:
Exact Decoding (ED). Exact Decoding scheme expects the Hamming distance between the generated instance code, B(PF (x; θF )), and the ground truth class code, B(Ci) to be exactly 0. That is, we can hash the class codes in a table, and then ED requires only a O(1) hash-table lookup for a given instance. Consequently, the inference time for ED is nearly independent of L. Naturally, the decoding scheme is highly stringent and would misclassify an instance if the instance binary code and the ground truth code do not match in even a single bit. Surprisingly, this highly efficient decoding scheme still provides non-trivial accuracy (see Table 1 and Section 4.1.2).
Minimum Hamming Decoding (MHD). Minimum Hamming Decoding is akin to the Maximum Dot Product used by standard linear classifiers. For an instance code, we evaluate the Hamming distance with all the L class codes and output the class with the least Hamming distance. Note that the Hamming distance over binary codes can be computed using XOR operations that are implemented significantly more efficiently than the floating-point operations [48]. Even though, technically, computational complexity and model size of MHD scales as O(L) but the real-world implementations should be an order of magnitude faster than standard classifiers. In fact, for large number of classes L, the efficiency of MHD can be further improved by using approximate nearest neighbour search [16, 7, 40]. Appendix A has the mathematical presentation of the decoding schemes.
See Section 5 for more discussion on potential decoding schemes. Also see Section 4.4 for ablation studies about the two decoding schemes along with feature separability (linear vs Hamming).

heading: 4.1.2 Empirical Evaluation

text:
ImageNet-1K [49] is a widely used image classification dataset with 1000 hierarchical classes. Our classification experiments use ResNet50 [25] and are trained using the ∼1.3M training images. Images were transformed & augmented with standard procedures [35, 60]. All the implementations were in PyTorch [45] and experimented on a machine with 4 NVIDIA Titan X (Pascal) GPUs.
When applied to ImageNet-1K, the first phase of LLC, learnt a 20-bit codebook with 1000 unique class codes, i.e., every class has its own distinct binary code. We warm start the second phase of LLC by the learnt ResNet50 backbone along with the 20 dimensional projection layer. See Appendix C for the hyperparameter values and other training details.
A key feature of LLC is that it jointly learns both the class codebook as well as instance codes. Several existing techniques decouple this learning process where the codebook is constructed separately and is then used to train the instance codes [28, 14, 3, 20, 1, 58]. We evaluate the advantage of the joint learning approach of LLC by comparing its performance against three strong baselines: i) Random codebook of 20-bits, ii) 20-bit CCA codebook [1, 58, 64] & iii) 20-bit SVD codebook. Previous works [28, 14, 3] argued that random codebooks are competitive to the ones constructed using side-information. 20-bit CCA and SVD codebooks aim to capture the hierarchy that is amiss in the random codebook. The 20-bit SVD codebook is built using the SVD of 2048 dimensional linear classifiers (for each class) in the pre-trained ResNet50, and binarizing it. 20-bit CCA codebook is the binarized version of the transformed label embedding projected on to 20 components learnt using CCA between 2048 dimensional representations of 50K samples from the ImageNet train set and
their one-hot label embeddings. Despite being able to capture the hierarchy information, both 20-bit CCA/SVD codebooks suffer from clashes reducing their overall effectiveness.
Next, using the baselines codebooks and the corresponding learnt instance codes, we compute class predictions for each test instance using the Exact Decoding (ED) & Minimum Hamming Decoding (MHD) schemes mentioned in the previous section. We evaluate all the methods using top-1 accuracy on the ImageNet-1K validation set. Baseline ResNet50 architecture represents the maximum accuracy we can hope to achieve using binarized instance+class codes. Note that this baseline classifier requires O(L) computation over 16-bit real numbers, and achieves Top-1 accuracy of 77%.
Table 1 compares the accuracy of LLC (with 20-bit codebook) against baseline codebooks mentioned above. Note that MHD with LLC codebook is 74.5% accurate, i.e., despite using only 20-dimensional binary representation it is only about 2.5% less accurate than standard ResNet50 that uses 2048 dimensional real-valued representation. Furthermore, we observe that compared to standard codebooks like SVD, our jointly learnt codebook is 5% more accurate.
Interestingly, Exact Decoding (ED) – which is O(1) inference scheme – with LLC codebook is nearly as accurate as the SVD codebook with MHD scheme and is about 12% more accurate than the CCA codebook with ED scheme. Naturally, codebook length/dimensionality plays a critical role in classification accuracy; see Section 4.4 for a detailed ablative study on this aspect. Finally, the gains in efficiency should be even more compelling for problems with millions of classes [54].

heading: 4.2 Efficient Retrieval

text:
The goal in retrieval is to find instances from a database that are most similar to a given query. Traditional retrieval approaches, use a fixed metric to retrieve "similar points", with data structures like LSH for efficient retrieval. Recent progress in Deep Supervised Hashing (DSH) [38] offer significantly more compelling solutions by learning the hashing function itself. That is, DSH aims to learn binary codes for each instance s.t. a pair of instances are embedded closely iff they belong to the same class, and then learns the hashing function end-to-end using a small train set.
As LLC also learns instance codes to reflect class membership, we can directly use our learnt encoder as a hashing function for given instances. For each query, the most relevant samples from the database are retrieved based on the minimum Hamming distance. Similar to the decoding schemes in classification, the retrieval can be optimized using approximate nearest neighbor search. Finally, the efficiency gains provided by using bits instead of real numbers should enable deployment of LLC based retrieval for efficient high recall portions of retrieval pipelines.

heading: 4.2.1 Empirical Evaluation

text:
Following DSH literature, we evaluate hashing-based image retrieval on ImageNet-100, a benchmark dataset created by Cao et al. [9]. ImageNet-100 has 100 classes randomly sampled from ImageNet-1K. All the validation images of these classes are used as query images, all the training images (∼ 1300 per class) of these 100 classes are used as database images. Finally, 130 samples per class from the database are used as the training set for learning binary codes or hashing functions.
We compare against HashNet [9] and Greedy Hash [53] for image retrieval using learnt instance codes. HashNet learns the bit representations of instances using a pairwise optimization with positive and negative instance pairs. HashNet is a representative baseline for an alternative way of learning binary instance codes compared to LLC. On the other hand, Greedy Hash learns only the instance codes using straight-through-estimator via the classification task. Note that LLC learns both class
codes as well as instance codes differentiating it from Greedy Hash style methods. Learnt instance codes are a byproduct of efficient classification as opposed to baselines that optimize for them.
We use the Mean Average Precision (MAP@1000) metric for evaluation. The MAP@1000 calculation code of HashNet [9] is erroneous and has propagated to several papers in the literature. We use the corrected version, hence the accuracy numbers are different from the original paper. Please see Appendix B for the corrected version, the changes required along with an example and a brief discussion. We used the publicly available pre-trained HashNet models [10] and Greedy Hash [53] code to recompute the MAP@1000.
Following HashNet [9], we use AlexNet [31] as the backbone and warm-start it with a pre-trained model on ImageNet-1K. We add a projection layer to the backbone and learn the instance and class codes. We also report retrieval numbers with ResNet50 [25] and compare LLC based retrieval numbers to learnt real-valued representations. Please see Appendix C for the training details and hyperparameters of efficient retrieval pipelines.
Table 3 shows the performance (evaluated using MAP@1000) for HashNet, Greedy Hash, and LLC across various code lengths. LLC outperforms HashNet across all code lengths (16 – 64) by at least 4.79% on MAP@1000. LLC is also better than Greedy Hash across all the bit lengths. LLC also outperforms 16-bit HashNet by 2% & 15% using only 10 & 16 bits respectively. Finally, 32-bit LLC comfortably outperforms both 48 & 64-bit HashNet showcasing the effectiveness of our learnt tight bit codes. Note that LLC, learning both instance and class codes, is effective in retrieval even though it was designed for classification.
We repeat the retrieval experiments with ResNet50. Table 4 shows the MAP@1000 for LLC with 10 and 64 bits along with the same dimensional real-valued representations. The 10-bit LLC is only 2% lower than 10 dimensional real-valued representation even though theoretically, the cost associated with 10-bit LLC based retrieval is about 256× less than 10 dimensional real representations. The 64 bit and 10 bit LLC outperforms 10 and 8 dimensional real-valued representations respectively at a much cheaper retrieval cost, at least by an order of magnitude. More discussion about the use of binary codes for retrieval at a large scale can be found in Section 5. Finally, 10-bit LLC with ResNet50 outperforms the best performing AlexNet based models for the same task, suggesting ResNet50 is a more appropriate architecture for benchmarking DSH literature.

heading: 4.3 Out-of-Distribution (OOD) Detection

text:
For a multi-class classifier, detecting an OOD sample is very important for robustness [26] and sequential learning [55]. Multi-class classifiers are augmented with OOD detection capability by setting a threshold on heuristics like maximum logit which is tuned using a validation set.
We focus on the scenario where the ratio of in-distribution to out-of-distribution samples in the validation set is not representative of the deployment. This throws off the methods that try to maximize metrics, F1, using a validation set. Our learnt class codebook from LLC comes with over-provisioning (for ease of optimization) resulting in unassigned codes. These unassigned codes can be treated as OOD out-of-the-box with no tuning whatsoever. That is, we classify an instance as OOD if its instance code does not match exactly with the code of a class in our learnt codebook.
Appendix E discusses the OOD detection experiments on ImageNet-750 [55] & MIT Places [65]. At a high level, LLC based out-of-the-box OOD detection (with a learnt 20-bit codebook on ImageNet-1K) achieves nearly the same OOD detection accuracy as a baseline [26] that tries to maximize F1 using a validation set. We would like to stress that while such a method needs ≈ 3000 points in the validation set, our method requires no samples, which is critical in several practical settings.

heading: 4.4 Ablation Studies

text:
Classification Accuracy vs Number of Bits. Table 2 shows the trade-off in classification accuracy with the variation in the length of the learnt codebook for ImageNet-1K. LLC learns a 15-bit codebook with only 990 unique codes leading to a loss of accuracy due to code collapse in both ED and MHD schemes (1.62% & 3.54% compared to 20-bit codebook respectively). An interesting observation is that the ED accuracy gradually goes down after 20-bits while the MHD accuracy keeps on increasing. The phenomenon of increasing accuracy with MHD is probably due to the increase in the capacity of both instance and class codes. However, the decrease in ED accuracy after 20-bits can be explained through the hardness in exactly predicting every bit in the instance code to match the ground truth class code. Our classification model with 20-bits on average gets 19.2 bits correct but the model with 30-bits only gets 28.5 bits right. This increase in uncertainty coupled with the stringent ED scheme leads to a slight dip in accuracy as the code length increases. However, this also provides us with a path for more accurate decoding schemes while being efficient as discussed in Section 5.
Classification Accuracy vs Faster Codebook Learning. Codebook learning phase of LLC is expensive, this motivated us to speed up codebook learning at a minimal loss in accuracy. One way is to warm-start the codebook using the ones built with SVD/CCA (see Section 4.1). While these codebooks suffer from code collapse, with further training, they start to learn 1000 unique codes quickly. Using these final codebooks gets to a comparable (1% drop) accuracy as the 20-bit learnt LLC codebook but at a relatively cheaper training. Another option is to use only a portion of the data and a much smaller network to learn the codebook. We sampled 50K training images and use a MobileNetV1 [27] (which has about 6× less parameters and compute than ResNet50) to learn a 20-bit codebook which gets to ED and MHD accuracy of 66.62% & 72.55% which is only 2% lower than the end-to-end learnt codebook but at a fraction of the training cost (3 hrs vs 2 days).
Linear vs Hamming Separability. Fitting a deep neural network to the learnt codebook for classification results in warping of the feature space considerably. The final classification space is a hypercube with the vertices being apart by Hamming distance of 1. To verify linear separability, we take the learnt, frozen ResNet50 trained for the 20-bit classification problem and fit a linear classifier on top of the 2048 dimensional features. Linear classifier quickly reaches a top-1 accuracy of 75.51%.
The opposite does not seem to be true. We extract and freeze the backbone of a pre-trained ResNet50 and train a projection layer to fit the 20-bit learnt codebook. This gets to top-1 accuracy of only about 21% with the ED scheme. However, we also observed that unfreezing and finetuning the last 3 layers of the backbone recovers the top-1 ED accuracy to roughly 68%.
These experiments show 1) Hamming separability inherently enables linear separability, 2) Linear separability does not imply Hamming separability & 3) with enough overparameterization, linearly separable space can be warped to support Hamming separability. Hamming separability automatically provides linear separability with increased accuracy of ∼ 1% over the MHD scheme which allows for an option for using a more powerful yet simple classifier, in case of accuracy requirements.
Independent vs Nested Codebook Learning. Consider a scenario with varied computational budgets for classification. We could either train independent k-bit models (eg., k = 20, 25, 30) and use them according to the budget, or we could learn a single nested codebook-based model that can be readily adapted to any of these settings. While training a codebook of larger bit length like k = 30, we can ensure that the first m-bits, m < k, also form a codebook at minimal additional cost. We were able to stably train a 30-bit codebook and also extract 20, 25-bit codebooks from it all of which are as accurate as independently trained codebooks. These nested codebooks have the potential to be used based on the computational resource availability for efficient classification without having to retrain.

heading: 5 Discussion and Conclusions

text:
We designed LLC to learn low-dimensional binary codes for instances as well as classes, and utilized them in applications like efficient classification, retrieval, OOD detection. A key finding is that combining class code learning with ECOC framework to learn instance code leads to a stable training system that can accurately capture the semantics of the class data despite just 20-dimensional code. Traditionally, methods like HashNet, KLSH [33] attempt to learn hashing function using pairwise
loss functions by embedding instances such that points from the same class are embedded closely and points from different classes are far. But such formulations are hard to optimize, due to the risk of embedding collapse. We observe that LLC by using instance-wise formulation can train stably with significantly higher performance. Another fascinating observation is that while architectures like ResNet50 have large intermediate (2048 dimensional real) representations, they can be compressed to just 20 bits without significant loss in accuracy! Even though quantization [48] literature demonstrates strong compression of representations, we believe such stark compression has been elusive so far and is worth further exploration from the efficient inference viewpoint.
Limitations. Our visualization (see Figure 4 in Appendix D) indicates that each bit does not correspond to some easily interpretable attributes, unlike DBC [47]. We believe incorporating priors with weak supervision as well as cross-modal learning could help LLC get past this limitation.
ED and MHD schemes are on two ends of the computation vs accuracy spectrum and do not transition smoothly. Designing decoding schemes that can compromise between these two extreme decoding schemes might be able to address this limitation.
Strong encoders are needed to warp the feature space to ensure Hamming separability. For example, using a 20-bit learnt codebook with ED scheme, ResNet50 gets to 68.8% top-1 accuracy whereas MobileNetV1 can only reach 53.23%. This also ties into the argument that classification is a tradeoff between encoder and decoder costs. Making decoders efficient and cheap, puts the burden on encoding the information in the right way and higher expressivity often helps in that cause.
Future Work. There are several exciting directions that we would like to explore. In principle, LLC can easily incorporate side-information when needed with simple additional losses during training. The additional regularization losses can also help in incorporating natural constraints on the codebook [14, 3] or can enable attribute-based class codes for interpretablity [21, 22, 37] making them exciting directions to explore. LLC algorithm can also be used to encode instances of multiple modalities like audio, visual, language to the same learnt low-dimensional binary space. This might help in effective cross-modal supervision along with retrieval among various other applications.
Potential in Large-Scale Applications. While our focus was on designing low-dimensional accurate binary codes, several studies [48, 29] have shown that efficiency afforded by bit-wise computation over floating-point computation can lead to almost an order of magnitude speed-up. Furthermore, as the number of classes increases, the learning of class codebooks helps in training representations in sublinear costs [13] along with sublinear inference (in L). We expect LLC algorithm to have its efficiency benefits outweigh the accuracy drop for large multi-class/multi-label problems, like objection recognition using ImageNet-22K [17], document tagging [54, 46] and instance classification [59]. The efficiency aspect of the binary codes has not been fully explored in this paper as the main computational bottleneck for ImageNet-1K classification is the deep neural network featurizer.
Lastly, LLC based efficient retrieval can be used for the initial high-recall shortlisting of a search pipeline, which is followed by high precision models operating on more expressive yet expensive embeddings. We leave practical demonstration of such a system at web-scale for future work.

heading: Acknowledgments

text: We are grateful to Tapan Chugh, Kunal Dahiya, Max Horton, Sewoong Oh, Mohammad Rastegari, Ludwig Schmidt and members of RAIVN Lab for helpful discussions and feedback. AK would also like to thank Soumen Chakrabarti and Manik Varma for sowing the seeds of this idea in his initial research days. Sham Kakade acknowledges funding from NSF Awards CCF-1703574. Ali Farhadi acknowledges funding from the NSF awards IIS 1652052, IIS 1703166, DARPA N66001-19-2-4031, W911NF-15-1-0543 and gifts from Allen Institute for Artificial Intelligence.

title: LLC: Accurate, Multi-purpose Learnt Low-dimensional Binary Codes


summaries: 1. The paper proposes GDWS with an error optimization strategy to replace regular convolution for enhancing both throughput (FPS) and adversarila robustness. 2. Experimental results on CIFAR-10, SVHN, and ImageNet validate that the replacing a CNN's regular conv with GDWS can achieve significantly higher FPS and preserve adversarial robustness.

summaries: The paper proposes a post-training transformation of a pre-trained 2D convolutional layer into a general depth-wise separable convolution operation. The optimization primarily focuses on minimizing error and limiting computation complexity. The paper claims to achieve a higher robustness (i.e., defend adversarial input attack) and higher frame per second than existing methods.

summaries: This paper proposed a method named  Generalized Depthwise-Separable (GDWS) to improve the throughput on real-life hardware while simultaneously preserving robustness. The advantage of GDWS is that does not need any additional training.  This paper has demonstrated the effectiveness of GDWS via extensive experiments on CIFAR-10, SVHN, and ImageNet datasets.

summaries: The paper proposes a generalization of depthwise-separable convolutions (called GDWS) where each channel can have multiple depthwise filters (instead of just one) that are subsequently combined using a pointwise convolution. Two algorithms are proposed to minimize the error/complexity of mapping general convolutions to GDWS as a post-processing step after training. Results show small degradation on natural and robust accuracy while increasing the FPS substantially.

summaries: The authors propose Generalized Depthwise-Separable (GDWS) convolutions for processing images for the purpose of getting high throughput in efficiency and robustness. This is carried out by introducing channel distribution vectors in the standard 2D CNNs. The efficiency is managed by means of the singular value decomposition of the matrix in the convolutional operations after vectorizations. Experiments show that the method provides similar results for some benchmark data.

abstractText: Despite their tremendous successes, convolutional neural networks (CNNs) incur high computational/storage costs and are vulnerable to adversarial perturbations. Recent works on robust model compression address these challenges by combining model compression techniques with adversarial training. But these methods are unable to improve throughput (frames-per-second) on real-life hardware while simultaneously preserving robustness to adversarial perturbations. To overcome this problem, we propose the method of Generalized Depthwise-Separable (GDWS) convolution – an efficient, universal, post-training approximation of a standard 2D convolution. GDWS dramatically improves the throughput of a standard pre-trained network on real-life hardware while preserving its robustness. Lastly, GDWS is scalable to large problem sizes since it operates on pre-trained models and doesn’t require any additional training. We establish the optimality of GDWS as a 2D convolution approximator and present exact algorithms for constructing optimal GDWS convolutions under complexity and error constraints. We demonstrate the effectiveness of GDWS via extensive experiments on CIFAR-10, SVHN, and ImageNet datasets. Our code can be found at https://github.com/hsndbk4/ GDWS.

authors:
Gabriel Bender
Pieter-Jan Kindermans
Barret Zoph
Vijay Vasudevan
Quoc Le

title: Understanding and simplifying one-shot architecture search

venue: In International Conference on Machine Learning,

authors:
Jungwook Choi
Zhuo Wang
Swagath Venkataramani
Pierce I-Jen Chuang
Vijayalakshmi Srinivasan
Kailash Gopalakrishnan

title: PACT: Parameterized clipping activation for quantized neural networks

venue: arXiv preprint arXiv:1805.06085,

authors:
Hassan Dbouk
Hetul Sanghvi
Mahesh Mehendale
Naresh Shanbhag

title: DBQ: A differentiable branch quantizer for lightweight deep neural networks

venue: In European Conference on Computer Vision,

title: Fast R-CNN

venue: In Proceedings of the IEEE International Conference on Computer Vision (ICCV),

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Shupeng Gui
Haotao Wang
Chen Yu
Haichuan Yang
Zhangyang Wang
Ji Liu

title: Model compression with adversarial robustness: A unified optimization framework

venue: Advances in Neural Information Processing Systems,

authors:
Minghao Guo
Yuzhe Yang
Rui Xu
Ziwei Liu
Dahua Lin

title: When nas meets robustness: In search of robust architectures against adversarial attacks

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Yiwen Guo
Anbang Yao
Yurong Chen

title: Dynamic network surgery for efficient DNNs

venue: In Advances in Neural Information Processing Systems (NIPS),

authors:
Song Han
Xingyu Liu
Huizi Mao
Jing Pu
Ardavan Pedram
Mark A Horowitz
William J Dally

title: EIE: Efficient inference engine on compressed deep neural network

venue: ACM SIGARCH Computer Architecture News,

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Andrew G Howard
Menglong Zhu
Bo Chen
Dmitry Kalenichenko
Weijun Wang
Tobias Weyand
Marco Andreetto
Hartwig Adam

title: Mobilenets: Efficient convolutional neural networks for mobile vision applications

venue: arXiv preprint arXiv:1704.04861,

authors:
Gao Huang
Shichen Liu
Laurens Van der Maaten
Kilian Q Weinberger

title: Condensenet: An efficient densenet using learned group convolutions

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Itay Hubara
Matthieu Courbariaux
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Binarized neural networks

venue: In Advances in neural information processing systems,

authors:
Forrest N Iandola
Song Han
Matthew W Moskewicz
Khalid Ashraf
William J Dally
Kurt Keutzer

title: Squeezenet: Alexnet-level accuracy with 50x fewer parameters and < 0.5 MB model size

venue: arXiv preprint arXiv:1602.07360,

authors:
Andrew Ilyas
Shibani Santurkar
Logan Engstrom
Brandon Tran
Aleksander Madry

title: Adversarial examples are not bugs, they are features

venue: Advances in neural information processing systems,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Ji Lin
Chuang Gan
Song Han

title: Defensive quantization: When efficiency meets robustness

venue: In International Conference on Learning Representations,

authors:
Hanxiao Liu
Karen Simonyan
Yiming Yang

title: DARTS: Differentiable architecture search

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

authors:
Pratyush Maini
Eric Wong
Zico Kolter

title: Adversarial robustness against the union of multiple perturbation models

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

venue: NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in PyTorch

venue: In NIPS Autodiff Workshop,

authors:
Vivek Ramanujan
Mitchell Wortsman
Aniruddha Kembhavi
Ali Farhadi
Mohammad Rastegari

title: What’s hidden in a randomly weighted neural network

authors:
Mohammad Rastegari
Vicente Ordonez
Joseph Redmon
Ali Farhadi

title: XNOR-net: Imagenet classification using binary convolutional neural networks

authors:
Esteban Real
Alok Aggarwal
Yanping Huang
Quoc V Le

title: Regularized evolution for image classifier architecture search

venue: In Proceedings of the AAAI conference on artificial intelligence,

authors:
Leslie Rice
Eric Wong
Zico Kolter

title: Overfitting in adversarially robust deep learning

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International journal of computer vision,

authors:
Charbel Sakr
Yongjune Kim
Naresh Shanbhag

title: Analytical guarantees on numerical precision of deep neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Charbel Sakr
Naresh Shanbhag

title: An analytical method to determine minimum per-layer precision of deep neural networks

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Mark Sandler
Andrew Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Mobilenetv2: Inverted residuals and linear bottlenecks

authors:
Lukas Schott
Jonas Rauber
Matthias Bethge
Wieland Brendel

title: Towards the first adversarially robust neural network model on MNIST

authors:
Vikash Sehwag
Shiqi Wang
Prateek Mittal
Suman Jana

title: HYDRA: Pruning adversarially robust neural networks

venue: Advances in Neural Information Processing Systems (NeurIPS),

authors:
Sanchari Sen
Balaraman Ravindran
Anand Raghunathan

title: EMPIR: Ensembles of mixed precision deep networks for increased robustness against adversarial attacks

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199,

authors:
Mingxing Tan
Quoc Le

title: Efficientnet: Rethinking model scaling for convolutional neural networks

authors:
Florian Tramèr
Dan Boneh

title: Adversarial training and robustness for multiple perturbations

venue: In Conference on Neural Information Processing Systems (NeurIPS),

authors:
Florian Tramèr
Nicholas Carlini
Wieland Brendel
Aleksander Madry

title: On adaptive attacks to adversarial example defenses

authors:
Tien-Ju Yang
Yu-Hsin Chen
Vivienne Sze

title: Designing energy-efficient convolutional neural networks using energy-aware pruning

authors:
Shaokai Ye
Kaidi Xu
Sijia Liu
Hao Cheng
Jan-Henrik Lambrechts
Huan Zhang
Aojun Zhou
Kaisheng Ma
Yanzhi Wang
Xue Lin

title: Adversarial robustness vs. model compression, or both

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks

venue: arXiv preprint arXiv:1605.07146,

authors:
Dongqing Zhang
Jiaolong Yang
Dongqiangzi Ye
Gang Hua

title: LQ-nets: Learned quantization for highly accurate and compact deep neural networks

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Hongyang Zhang
Yaodong Yu
Jiantao Jiao
Eric Xing
Laurent El Ghaoui
Michael Jordan

title: Theoretically principled trade-off between robustness and accuracy

authors:
Tianyun Zhang
Shaokai Ye
Kaiqi Zhang
Jian Tang
Wujie Wen
Makan Fardad
Yanzhi Wang

title: A systematic DNN weight pruning framework using alternating direction method of multipliers

authors:
Xiangyu Zhang
Xinyu Zhou
Mengxiao Lin
Jian Sun

title: Shufflenet: An extremely efficient convolutional neural network for mobile devices

authors:
Barret Zoph
Vijay Vasudevan
Jonathon Shlens
Quoc V Le

title: Learning transferable architectures for scalable image recognition

heading: 1 Introduction

text:
Nearly a decade of research after the release of AlexNet [18] in 2012, convolutional neural networks (CNNs) have unequivocally established themselves as the de facto classification algorithm for various machine learning tasks [11, 38, 4]. The tremendous success of CNNs is often attributed to their unrivaled ability to extract correlations from large volumes of data, allowing them to surpass human level accuracy on some tasks such as image classification [11].
Today, the deployment of CNNs in safety-critical Edge applications is hindered due to their high computational costs [11, 30, 31] and their vulnerability to adversarial samples [37, 5, 16]. Traditionally, those two problems have been addressed in isolation. Recently, very few bodies of works [19, 35, 42, 6, 34, 7] have addressed the daunting task of designing both efficient and robust CNNs. A majority of these methods focus on model compression, i.e. reducing the storage requirements of CNNs. None have demonstrated their real-time benefits in hardware. For instance, Fig. 1a shows recent robust pruning works HYDRA [34] and ADMM [42] achieve high compression ratios (up to 97×) but either fail to achieve high throughput measured in frames-per-second (FPS) or compromise significantly on robustness. Furthermore, the overreliance of current robust complexity reduction techniques on adversarial training (AT) [45, 21] increases their training time significantly (Fig. 1b). This prohibits their application to complex ImageNet scale problems with stronger attack models, such as union of norm-bounded perturbations [22]. Thus, there is critical need for methods to
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
design deep nets that are both adversarially robust and achieve high throughput when mapped to real hardware.
To address this need, we propose Generalized Depthwise-Separable (GDWS) convolutions, a universal post-training approximation of a standard 2D convolution that dramatically improves the real hardware FPS of pre-trained networks (Fig. 1a) while preserving their robust accuracy. Interestingly, we find GDWS applied to un-pruned robust networks simultaneously achieves higher FPS and higher robustness than robust pruned models obtained from current methods. This in spite of GDWS’s compression ratio being smaller than those obtained from robust pruning methods. Furthermore, GDWS easily scales to large problem sizes since it operates on pre-trained models and doesn’t require any additional training.
Our contributions:
1. We propose GDWS, a novel convolutional structure that can be seamlessly mapped onto off-the-shelf hardware and accelerate pre-trained CNNs significantly while maintaining robust accuracy.
2. We show that the error-optimal and complexity-optimal GDWS approximations of any pre-trained standard 2D convolution can be obtained via greedy polynomial time algorithms, thus eliminating the need for any expensive training.
3. We apply GDWS to a variety of networks on CIFAR-10, SVHN, and ImageNet to simultaneously achieve higher robustness and higher FPS than existing robust complexity reduction techniques, while incurring no extra training cost.
4. We demonstrate the versatility of GDWS by using it to design efficient CNNs that are robust to union of (`∞, `2, `1) perturbation models. To the best of our knowledge, this is the first work that proposes efficient and robust networks to the union of norm-bounded perturbation models.

heading: 2 Background and Related Work

text:
The problem of designing efficient and robust CNNs, though crucial for safety-critical Edge applications, is not yet well understood. Very few recent works have addressed this problem [19, 35, 42, 6, 34, 7]. We cluster prior works into the following categories:
Quantization Reducing the complexity of CNNs via model quantization in the absence of any adversary is a well studied problem in the deep learning literature [30, 31, 2, 44, 14, 26, 3]. The role of quantization on adversarial robustness was studied in Defensive Quantization (DQ) [19] where it was observed that conventional post-training fixed-point quantization makes networks more vulnerable to adversarial perturbations than their full-precision counterparts. EMPIR [35] also leverages extreme model quantization (up to 2-bits) to build an ensemble of efficient and robust networks. However, [40] broke EMPIR by constructing attacks that fully leverage the model structure, i.e., adaptive attacks. In contrast, GDWS is an orthogonal complexity reduction technique that preserves the base model’s adversarial robustness and can be applied in conjunction with model quantization.
Pruning The goal of pruning is to compress neural networks by zeroing out unimportant weights [10, 8, 46, 41]. The structured pruning method in [42] combines the alternating direction method of multipliers (ADMM) [46] for parameter pruning within the AT framework [21] to design pruned and robust networks. The flexibility of ADMM enables it to achieve a high FPS on Jetson (as seen in Fig. 1a) but suffers from a significant drop in robustness. ATMC [6] augments the ADMM framework [42] with model quantization and matrix factorization to further boost the compression ratio. On the other hand, unstructured pruning methods such as HYDRA [34] prunes models via important score optimization [25]. However, HYDRA’s high pruning ratios (> 90%) doesn’t translate into real-time FPS improvements on off-the-shelf hardware and often requires custom hardware design to fully leverage their capabilities [9]. GDWS is complementary to unstructured pruning methods, e.g., when applied to HYDRA, GDWS boosts the achievable FPS and achieves much higher robustness at iso-FPS when compared to structured (filter) pruning ADMM.
Neural Architecture Search Resource-efficient CNNs can be designed by exploiting design intuitions such as depthwise separable (DWS) convolutions [12, 32, 13, 47, 15, 38]. While neural architecture search (NAS) [48, 27] automates the process, it requires massive compute resources, e.g., thousands of GPU hours for a single network. Differentiable NAS [20] and one-shot NAS [1] drastically reduce the cost of this search. In [7], a one-shot NAS framework [1] is combined with the AT framework [21] to search for robust network architectures, called RobNets. RobNets achieve slightly higher robustness than existing networks with less storage requirements. In this work, we show that applying GDWS to existing architectures, e.g., WideResNet-28-4, achieves significantly higher FPS than RobNet, at iso-robustness and model size.

heading: 3 Generalized Depthwise-Separable Convolutions

text:
In this section, we introduce GDWS convolutions and develop error-optimal and complexity-optimal GDWS approximations of standard 2D convolution. These optimal approximations are then employed to construct GDWS networks from any pre-trained robust CNN built from standard 2D convolutions.
Notation: A (C,K,M) standard 2D convolution operates on an input feature map X ∈ RC×H×W via M filters (also referred to as kernels or output channels) each consisting of C channels each of dimension K ×K to generate an output feature map Y ∈ RM×H′×W ′ . 2D Convolution as Matrix Multiplication: The M filters can be viewed as vectors {wi}Mi=1 ∈ RCK2 obtained by vectorizing the K2 elements within a channel and then across the C channels. The resulting weight matrix W ∈ RM×CK2 is constructed by stacking these filter vectors, i.e., W = [w1|w2|...|wM ]T. From an operational viewpoint, the matrix W can be used to compute the 2D convolution via Matrix Multiplication (MM) with the input matrix X = Ψ(X) ∈ RCK2×H′W ′ :
Y = WX = WΨ(X) (1)
where Ψ is an unrolling operator that generates all H ′W ′ input feature map slices and stacks them in matrix format. The resultant output matrix Y ∈ RM×H′W ′ can be reshaped via the operator Φ to retrieve Y = Φ(Y). The computational complexity of (1) in terms of multiply-accumulate (MAC) operations is given by:
H ′W ′MCK2 (2)
The reshaping operators Φ and Ψ are only for notational convenience and are computation-free.

heading: 3.1 GDWS Formulation

text:
Definition: A (C,K,g,M) GDWS convolution is parameterized by the channel distribution vector g ∈ ZC+ in addition to the parameters (C,K,M) of a standard 2D convolution. A GDWS convolution is composed of a (C,K,g) Generalized Depthwise (GDW) convolution and a (G, 1,M) standard pointwise (PW) convolution where G = ∑ gc with c ∈ [C]1.
A (C,K,g) GDW convolutional layer (Fig. 2) operates on an input feature map X ∈ RC×H×W by convolving the cth channel with gc ∈ Z+ depthwiseK×K filters to produce a total ofG intermediate output channels each of size H ′ ×W ′. The (G, 1,M) PW layer operates on the intermediate output feature map by convolving it with M filters of size 1 × 1, thus producing the output feature map Y ∈ RM×H′×W ′ . Relation to DWS: Setting gc = 1 ∀c ∈ [C] reduces the GDWS convolution to the standard DWS convolution popularized by [12]. Thus, GDWS generalizes DWS by allowing for more than one (gc ≥ 1) depthwise filters per channel. This simple generalization relaxes DWS’s highly constrained structure enabling accurate approximations of the 2D convolution. Thus, GDWS when applied to pre-trained models preserves its original behavior and therefore its natural and robust accuracy. Furthermore, GDWS achieves high throughput since it exploits the same hardware features that enable networks with DWS to be implemented efficiently. One might ask: why not use DWS on pre-trained models? Doing so will result in very high approximation errors. In fact, in Section 4.2, we show that applying GDWS to a pre-trained complex network such as ResNet-18 achieves better robust accuracy than MobileNet trained from scratch, while achieving similar FPS.
GDWS Complexity: The total number of MAC operations required by GDWS convolutions is:
H ′W ′ ( C∑ c=1 gc(K 2 +M) ) = H ′W ′G(K2 +M) (3)
Thus, replacing standard 2D convolutions with GDWS convolutions results in a complexity reduction by a factor of G(K
2+M) CK2M .

heading: 3.2 Properties of GDWS Convolutions

text:
We present properties of the GDWS weight matrix W that will be vital for developing the optimal approximation procedures.
Property 1. The weight matrix W ∈ RM×CK2 of a (C,K,g,M) GDWS convolution can be expressed as:
W = WPW D (4)
where WP ∈ RM×G and WD ∈ RG×CK 2
are the weight matrices of the PW and GDW convolutions, respectively.
Property 1 implies that any GDWS convolution has an equivalent 2D convolution whose weight matrix is the product of WP and WD, where WP is a regular convolution weight matrix with K = 1 and WD has the following property:
1we use the notation [C] = {1, 2, ..., C} for brevity.
Property 2. The weight matrix WD ∈ RG×CK 2
of a (C,K,g) GDW convolution has a blockdiagonal structure. Specifically, WD is a concatenation of C sub-matrices where each sub-matrix WD,c ∈ RG×K 2 has at most gc non-zero consecutive rows, starting at row index 1 + ∑c−1 k=1 gk as shown in Fig. 3.
This structure is due to the fact that input channels are convolved independently with at most gc depthwise filters per channel. Finally, let W = [W1|W2|...|WC ] be represented as the concatenation of C sub-matrices, then combining Properties 1 & 2 establishes the following lemma:
Lemma 1. The weight matrix of a (C,K,g,M) GDWS convolution can be expressed as the concatenation of C sub-matrices Wc where rank(Wc) ≤ min(gc,K2) ∀c ∈ [C].
The reason for this is that each sub-matrix Wc can be expressed as the sum of gc rank 1 matrices of size M ×K2. A detailed proof of Lemma 1 can be found in the Appendix. A major implication of Lemma 1 is that any 2D standard convolution is equivalent to a GDWS convolution with gc = K2 ∀c2. Hence, in the rest of this paper we will assume gc ≤ K2 when we approximate 2D convolutions with GDWS.

heading: 3.3 Optimal GDWS Approximation Methods

text:
We wish to approximate a standard 2D convolution with weight matrix W ∈ RM×CK2 with a GDWS convolution with weight matrix Q ∈ RM×CK2 to minimize the weighted approximation error defined as:
e(W,Q,α) = √√√√ C∑ c=1 αc||Wc −Qc||2F (5)
where ||.||F denotes the Frobenius norm of a matrix and α ∈ RC+ is a vector of positive weights. Setting αc = 1 ∀c simplifies (5) to the Frobenius norm of the error matrix W −Q. Furthermore, from (3), one can upper bound the complexity of the GDWS approximation Q via an upper bound on G = ∑ gc where the gc’s are obtained from Lemma 1.
Based on the GDWS properties and Lemma 1, we state the following error-optimal approximation theorem:
Theorem 1. Given a (C,K,M) standard 2D convolution with weight matrix W, the (C,K,g,M) GDWS approximation with weight matrix Ŵ that minimizes the error in (5) subject to ∑ gc = G ≤ γ (for some γ ∈ Z+), can be obtained in polynomial time via Algorithm 1.
That is: Ŵ = arg min
Q: G≤γ e(W,Q,α) (6)
can be solved for any weight error vector α ∈ RC+ in polynomial time. While Theorem 1 shows that the optimal GDWS approximation under a complexity constraint can be solved efficiently, a similar result can be obtained for the reverse setting shown next.
2Typical CNNs satisfy K2 < M , e.g., K = 3 and M ≥ 16
Theorem 2. Given a (C,K,M) standard 2D convolution with weight matrix W, the (C,K,g,M) GDWS approximation with weight matrix Ŵ that minimizes the complexity in (3) subject to e(W,Q,α) ≤ β (for some β ≥ 0), can be constructed in polynomial time via Algorithm 2.
That is:
Ŵ = arg min Q: e(W,Q,α)≤β C∑ c=1 gc (7)
can be solved for any weight error vector α ∈ RC+ in polynomial time. Proofs of Theorems 1 & 2 can be found in the Appendix.
Algorithm 1: (MEGO) Minimum Error Complexity-constrained GDWS Optimal Approximation Input: A (C,K,M) convolution W,
weight error vector α, and constraint γ ∈ Z+.
Output: A (C,K,g,M) GDWS convolution Ŵ, satisfying∑ gc ≤ γ.
1 Compute SVDs of Wc = ∑rc i=1 σi,cui,cv T i,c 2 Initialize g = 0 3 while ∑ gc < γ do 4 c′ = arg maxc αcσ 2 gc+1,c // gc < rc 5 gc′ ← gc′ + 1 6 Compute Ŵc via truncated SVD of Wc
with rank gc: Ŵc = ∑gc i=1 σi,cui,cv T i,c
7 Construct Ŵ = [Ŵ1|...|ŴC ]
Algorithm 2: (LEGO) Least Complex Errorconstrained GDWS Optimal Approximation Input: A (C,K,M) convolution W,
weight error vector α, and constraint β ≥ 0.
Output: A (C,K,g,M) GDWS convolution Ŵ, satisfying e ≤ β.
1 Compute SVDs of Wc = ∑rc i=1 σi,cui,cv T i,c 2 Initialize gc = rc, b = 0, c′ = arg minc αcσ 2 rc,c, h = αc′σ 2 rc′ ,c ′ 3 while b+ h < β do 4 b← b+ h and gc′ ← gc′ − 1 5 c′ = arg minc αcσ 2 gc,c // gc > 1 6 h = αc′σ 2 rc′ ,c ′
7 Compute Ŵc via truncated SVD of Wc with rank gc: Ŵc = ∑gc i=1 σi,cui,cv T i,c 8 Construct Ŵ = [Ŵ1|...|ŴC ]

heading: 3.4 Constructing GDWS Networks

text:
When confronted with a CNN with L convolutional layers, the question arises: How to assign resources (in terms of complexity) amongst the L layers such that the robustness of the CNN is minimally compromised? To answer this question, we compute per-layer weight error vectors αl, such that the computed error in (5) weighs how different sub-matrices affect the final output of the CNN.
Let f : RD → RN be a pre-trained CNN for an N -way classification problem with L convolutional layers parameterizd by weight matrices W(l) ∈ RMl×ClK2l . The CNN f operates on aD-dimensional input vector x to produce a vector z = f(x) of soft outputs or logits. Denote by nx ∈ [N ] the predicted class label associated with x, and define δx,j = zj − znx to be the soft output differences ∀j ∈ [N ] \ {nx}. Inspired by [30, 31], we propose a simple yet effective method for computing the per-layer weight error vectors as follows:
αc,l = 1
MlK2l E  N∑ j=1 j 6=nx ||D(c,l)x,j ||2F 2δ2x,j  ∀l ∈ [L], ∀c ∈ [Cl] (8) where D(c,l)x,j ∈ RMl×K 2 l is the derivative of δx,j w.r.t. the sub-matrix W (l) c . The expectation is taken over the input vector x. Equation (8) can be thought of as the expected noise gain from a particular channel in a particular layer to the network output required to flip its decision. The Appendix provides a detailed rationale underlying (8).
Computation of (8) can be simplified by obtaining an estimate of the mean over a small batch of inputs sampled from the training set and by leveraging software frameworks such as PyTorch
[24] that automatically take care of computing D(c,l)x,j . Algorithm 3 summarizes the steps required to approximate any pre-trained CNN with an equivalent CNN utilizing GDWS convolutions. Unless specified otherwise, all the results in this paper are obtained via Algorithm 3.
Algorithm 3: Constructing GDWS networks Input: CNN f with convolutional layers {W(l)}, {αl} computed via (8), and constraint β ≥ 0. Output: CNN f̂ with GDWS convolutions {Ŵ(l)}
1 f̂ = f // Initialize f̂ 2 for l ∈ {1, ..., L} do 3 Ŵ(l) = LEGO(W(l),αl, β) // solve via Algorithm 2 4 Decompose Ŵ(l) into GDW and PW convolutions via Property 1 and Lemma 1 5 Replace the lth convolution layer in f̂ with GDW and PW convolutions

heading: 4 Experiments

heading: 4.1 Evaluation Setup

text: We measure the throughput in FPS by mapping the networks onto an NVIDIA Jetson Xavier via native PyTorch [24] commands. We experiment with VGG-16 [36], ResNet-183 [11], ResNet-50, and WideResNet-28-4 [43] network architectures, and report both natural accuracy (Anat) and robust accuracy (Arob). Following standard procedure, we report Arob against `∞ bounded perturbations generated via PGD [21] with standard attack strengths: = 8/255 with PGD-100 for both CIFAR-10 [17] and SVHN [23] datasets, and = 4/255 with PGD-50 for the ImageNet [29] dataset. Section 4.3 studies union of multiple perturbation models (`∞, `2, `1). In the absence of publicly released pretrained models, we establish strong baselines using AT [21] following the approach of [28] which utilizes early stopping to avoid robust over-fitting. Details on the training/evaluation setup can be found in the Appendix.

heading: 4.2 Results

text:
Ablation Study: We first show the effectiveness of GDWS on the CIFAR-10 datasets using four network architectures. Table 1 summarizesAnat andArob as well as FPS and model size. It is clear that GDWS networks preserve robustness as bothAnat andArob are always within∼1% of their respective baselines. The striking conclusion is that in spite of GDWS offering modest reductions in model size, it drastically improves the FPS of the base network across diverse architectures. For instance, a ResNet-18 utilizing GDWS convolutions is able to run at 104 FPS compared to the baseline’s 28 FPS (>250% improvement) without additional training and without compromising on robust accuracy. In the Appendix, we explore the benefits of applying GDWS using both Algorithms 1 & 2, provide more detailed results on CIFAR-10 and show that similar gains are observed with SVHN dataset.
3For CIFAR-10 and SVHN, we use the standard pre-activation version of ResNets.
GDWS vs. RobNet: In Table 1, we also compare GDWS networks (obtained from standard networks) with a publicly available pre-trained RobNet model, the robust network architecture designed via the NAS framework in [7]. Note that RobNet utilizes DWS convolutions which precludes the use of GDWS. However, despite the efficiency of DWS convolutions in RobNet, its irregular cell structure leads to extremely poor mapping on the Jetson as seen by its low 5 FPS. For reference, a standard WideResNet-28-4 (WRN-28-4) runs at 17 FPS with similar robustness and model size. Applying GDWS to the WideResNet-28-4 further increases the throughput to 65 FPS which is a 1200% improvement compared to RobNet while maintaining robustness. This further supports our assertion that model compression alone does not lead to enhanced performance on real hardware.
GDWS vs. Lightweight Networks: A natural question that might arise from this work: why not train lightweight networks utilizing DWS convolutions from scratch instead of approximating pre-traind complex networks with GDWS? In Table 2, we compare the performance of GDWS networks (obtained from Table 1) vs. standard lightweight networks: MobileNetV1 [12], MobileNetV2 [32], and ResNet-20 [11], as well as a DWS-version of the standard ResNet18 trained from scratch on the CIFAR-
10 dataset. We find that applying GDWS to a pre-trained complex network such as ResNet-18 achieves better Anat and Arob than all lightweight networks, while achieving DWS-like FPS and requiring no extra training despite offering modest reductions in model size. The only benefit of using lightweight networks is the much smaller model size compared to GDWS networks.
GDWS vs. Structured Pruning: In Table 3, we compare GDWS with the robust structured pruning method ADMM [42] on CIFAR-10, using two networks: VGG-16 and ResNet-18. Due to the lack of publicly available pre-trained models, we use their released code to reproduce both the AT baselines, and the corresponding pruned models at different pruning ratios. The nature of structured pruning allows ADMM pruned networks (p ≥ 50%) to achieve both high compression ratios and significant improvement in FPS over their un-pruned baselines but at the expense of robust-
ness and accuracy. For instance, a ResNet-18 with 75% of its channels pruned results in a massive 7% (4%) drop in Anat (Arob) compared to the baseline even though it achieves a 160% improvement in FPS. In contrast, a post-training application of GDWS to the same ResNet-18 baseline results in a massive 275% improvement in FPS while preserving both Anat and Arob within 1% of their baseline values. Thus, despite achieving modest compression ratios compared to ADMM, GDWS achieves comparable improvements in FPS without compromising robustness.
GDWS vs. Unstructured Pruning: We compare GDWS with HYDRA [34] which is an unstructured robust pruning method, on both CIFAR-10 and ImageNet datasets. We use the publicly released HYDRA models as well as their AT baselines, and apply GDWS to both the un-pruned and pruned models. Table 4 summarizes the robustness and FPS of HYDRA and GDWS networks on CIFAR-10. HYDRA pruned models have arbitrarily sparse weight matrices that cannot be leveraged by off-theshelf hardware platforms immediately. Instead, we rely on the extremely high sparsity (99%) of these matrices to emulate channel pruning whereby channels are discarded only if all filter weights are zero.
This explains why, despite their high compression ratios, HYDRA models do not achieve significant improvements in FPS compared to their baselines.
For instance, a 99% HYDRA pruned WideResNet model achieves a massive∼100× compression ratio and improves the FPS from 17 to 28, but suffers from a large ∼10% drop in both Anat and Arob. In contrast, GDWS applied to the same un-pruned baseline preserves robustness and achieves significantly better throughput of 68 FPS, even though the model size reduction is negligible. Interestingly, we find that applying GDWS directly to HYDRA pruned models results in networks with high compression ratios with no robustness degradation and massive improvements in FPS compared to the pruned baseline. For example, applying GDWS to the same 99% HYDRA pruned WideResNet achieves a ∼20× compression ratio and improves the throughput from 28 FPS to 68 FPS while preserving Anat and Arob of the pruned baseline. This
synergy between HYDRA and GDWS is due to the fact that highly sparse convolution weight matrices are more likely to have low-rank and sparse sub-matrices. This implies that, using Lemma 1, sparse convolutions can be transformed to sparse GDWS versions with negligible approximation error. We explore this synergy in detail in the Appendix. Table 5 shows that GDWS benefits also show up in ImageNet using ResNet-50.

heading: 4.3 Defending against Union of Perturbation Models

text: Recent work has shown that adversarial training with a single perturbation model leads to classifiers vulnerable to the union of (`∞, `2, `1)-bounded perturbations [33, 39, 22]. The method of multi steepest descent (MSD) [22] achieves state-of-the-art union robust accuracy (AUrob) against the union of (`∞, `2, `1)-bounded perturbations. We demonstrate the versatility of GDWS by applying it to a publicly available [22] robust pre(MSD)-trained ResNet-18 model on CIFAR-10. Following the setup in [22], all attacks were run on a subset of the first 1000 test images with 10 random restarts with the following attack configurations: ∞ = 0.03 with PGD-100 , 2 = 0.5 with PGD-500, and 1 = 12 with PGD-100. Table 6 shows that applying GDWS with β = 0.01 to the pre-trained ResNet-18 incurs a negligible (<∼1%) drop in Anat and AUrob while improving the throughput from 28 FPS to 101 FPS (> 250% improvement).

heading: 5 Discussion

text:
We have established that the proposed GDWS convolutions are universal and efficient approximations of standard 2D convolutions that are able to accelerate any pre-trained CNN utilizing standard 2D convolution while preserving its accuracy and robustness. This facilitates the deployment of CNNs in safety critical edge applications where real-time decision making is crucial and robustness cannot be compromised. One limitation of this work is that GDWS alone does not achieve high compression ratios compared to pruning. Combining unstructured pruning with GDWS alleviates this problem to some extent. Furthermore, GDWS cannot be applied to CNNs utilizing DWS convolutions, such as RobNet for instance. An interesting question is to explore the possibility of training GDWS-structured networks from scratch. Another possible direction is fine-tuning post GDWS approximation to recover robustness, which we explore in the Appendix.
In summary, a GDWS approximated network inherits all the properties, e.g., accuracy, robustness, compression and others, of the baseline CNN while significantly enhancing its throughput (FPS) on real hardware. Therefore, the societal impact of GDWS approximated networks are also inherited from those of the baseline CNNs.

heading: Acknowledgments

text: This work was supported by the Center for Brain-Inspired Computing (C-BRIC) and the Artificial Intelligence Hardware (AIHW) program funded by the Semiconductor Research Corporation (SRC) and the Defense Advanced Research Projects Agency (DARPA).

title: Generalized Depthwise-Separable Convolutions for Adversarially Robust and Efficient Neural Networks