Scalable and Sustainable Deep Learning via Randomized Hashing

1. INTRODUCTION

• Large networks create costly distributed-training synchronization and conflicting updates, while their matrix multiplications also consume substantial energy on low-power devices.The introduction identifies synchronization as a scalability hurdle and reducing computation as important for longer mobile-device battery life.Source: §1 · pp. 1–2
• Earlier adaptive-dropout and winner-take-all methods select neurons using brute-force activation computation, so they offer no computational savings over standard back-propagation.The paper presents sub-linear randomized hashing as a way to choose sparse active neurons while reducing computation.Source: §1 · p. 2
• Hashing-based indexing selects highly activated neurons without computing every activation, using sparse active sets and sparse gradient updates.The approach combines randomized hashing with adaptive dropout; sparse updates are suited to asynchronous and parallel training.Source: §1 · p. 2

1.1 Our Contributions

• On several deep learning benchmarks, the approach outperforms standard algorithms including vanilla dropout at high sparsity, and matches adaptive dropout and winner-take-all using only 5% computation; average accuracy is within 1% of the original model.Source: §1 · p. 2, §1.1 · p. 2
• The method reduces multiplications in both training and inference, and its sparse updates support asynchronous training with near-linear speedup as processors increase.The contributions describe asynchronous training without accuracy compromise.Source: §1.1 · p. 2

Reduced precision

• A separate line of work reduces floating-point multiplications through stochastic weight quantization and bit-shift-based back-propagation; the paper describes reduced precision as orthogonal.The stated approach can be integrated with other approaches.Source: §2 · p. 2

Low-rank methods

• Low-rank methods reduce parameter storage, but their dense updates are poorly suited to asynchronous parallel training; this work instead uses random sparse activations.The cited low-rank approach reduces the memory footprint, while the paper positions sparse activations as more amenable to parallelization.Source: §2 · pp. 2–3

Dropout methods

• Dropout randomly removes nodes, while adaptive dropout samples by activation and winner-take-all keeps the largest k% activations, but all require full activation computation.The paper says these methods therefore target generalization rather than reducing computation.Source: §2 · p. 3

Hashing-based selection

• The proposed approach reformulates sparse high-activation node selection as approximate query processing and uses sub-linear randomized hashing instead of computing every node’s inner product.The stated distinction from adaptive dropout and winner-take-all is how the active set is found.Source: §2 · p. 3

Hashed Nets

• Hashed Nets reduce memory by tying weights that share hash values, whereas this paper targets computational cost rather than network size.The paper describes the two approaches as complementary.Source: §2 · p. 3

Low-rank structure

• For rank r much smaller than m and n, factoring W as UV reduces storage and multiplication time from O(mn) to O(mr + rn).The factorization can be represented as an equivalent network with an intermediate layer of r nodes.Source: §3 · p. 3

Limits of low-rank updates

• The equivalent low-rank network still requires dense gradient updates, which are not ideally suited to data parallelism or asynchronous training.The paper contrasts these updates with its sparse approach.Source: §3 · p. 3

Input-dependent sparsity

• Unlike permanent weight sparsification, the proposed method uses every node weight but selects weights for different inputs, producing random sparse activations.The paper presents this sparsity as a way to reduce computation and support asynchronous SGD.Source: §3 · p. 3

4.1 Artificial Neural Networks

• A neural-network layer transforms the previous layer’s output with weights and bias, applies an activation function, and is trained using SGD with layerwise back-propagation.Momentum and Adagrad are described as variants that modify parameter updates or learning rates.Source: §4.1 · p. 3

4.2 Adaptive Dropout

• Adaptive dropout samples neurons according to a monotonic function of their activations, while winner-take-all retains only the top k% activations.Both approaches are presented as sparse-activation techniques.Source: §4.2 · p. 4

4.3 Locality-Sensitive Hashing (LSH)

• Locality-sensitive hashing maps similar items to the same bucket with higher probability, enabling approximate nearest-neighbor search.A hash function maps a vector to an integer key, and equal keys constitute a collision.Source: §4.3 · p. 4

Sub-linear Search with (K, L) LSH Algorithm

• The (K, L) LSH procedure stores data points in L hash tables and queries by probing one bucket per table rather than scanning the full collection.The cited discussion describes the method as provably sub-linear with suitable parameters and near-constant-time in practice.Source: Sub-linear Search with (K, L) LSH… · p. 4

Hashing Inner Products

• Maximum inner-product search requires an asymmetric transformation before it can be handled as standard nearest-neighbor search with LSH.The paper assumes access to an efficient data structure that can be queried for large inner products.Source: Hashing Inner Products · p. 4

Multi-Probe LSH

• Multi-probe LSH queries nearby buckets in each hash table, reducing the number of tables needed compared with probing only one bucket.The cited approach generates additional bucket addresses by slightly perturbing the original address.Source: Multi-Probe LSH · p. 5

5.1 Intuition

• Hashing replaces Winner-Take-All’s O(n log n) active-set search with sub-linear search for nodes with large activations.For input x, selecting active nodes is framed as maximum inner-product search over the nodes’ weight vectors.Source: §5.1 · p. 5

5.2 Equivalence with Adaptive Dropouts

• LSH samples nodes with probability monotonic in their activation, making this an efficient form of adaptive dropout.The (K, L) hash scheme samples with probability proportional to 1 − (1 − p^K)^L, where p is collision probability.Source: §5.2 · p. 5

5.3 Hashing Based Back-Propagation

• Each layer’s hash tables retrieve an active set; forward and back-propagation update only those nodes, and modified weights are rehashed.Hash tables are built from layer weights, and the active set is reused for gradient computation and parameter updates.Source: §5.3 · p. 6

5.4 Efficient Query and Updates

• Sparse buckets support efficient queries and weight updates; the method stores references to weight vectors rather than duplicating them.With sparse buckets, array insertion is O(1) and deletion is O(b), where b is bucket size.Source: §5.4 · pp. 6–7

5.5 Overall Cost

• 5% is the reported low-end computation cost, with total work proportional to the active-set size.For a 1,000-node layer, the authors report updating around 10–50 nodes; their experiments use K = 6 and L = 5.Source: §5.5 · p. 7

5.6 Bonus: SparseUpdatescanbeParallelized

• Random, sparse active sets are expected to overlap little, reducing update conflicts; the authors report near-linear scaling with more processors without hurting convergence.The argument assumes sufficient randomness in the data vectors.Source: §5.6 · p. 7

Evaluation questions

• The evaluation asks how much computation can be reduced without affecting vanilla-network accuracy and how adaptive sampling compares with random node sampling.It also asks how approximate hashing compares in accuracy with adaptive dropout and Winner-Take-All.Source: §6 · p. 7
• The authors ask whether parallel SGD changes convergence, whether dense parallel updates hurt performance, and how training time changes with processor count.Source: §6 · p. 7

Compared methods

• The comparison includes standard neural networks, vanilla dropout, adaptive dropout, Winner-Take-All, and randomized hashing.The standard network is fully connected; the other listed methods select or disable hidden-layer nodes using their respective strategies.Source: §6 · p. 7

Datasets

• MNIST8M, CONVEX, and RECTANGLES use 28×28 images represented as 784-dimensional feature vectors.MNIST8M classifies handwritten digits; CONVEX detects a convex region, while RECTANGLES distinguishes tall from wide rectangles.Source: §6.1 · pp. 7–8

Dataset sizes

• Figure 3 is identified as reporting dataset training and test sizes.Source: Figure 3 · p. 8

Datasets

• NORB contains images of 50 toys in five categories under varying lighting and camera angles, resized into 2,048-dimensional feature vectors.Each example is a 96×96 stereo pair resized to 32×32 before the pair is concatenated.Source: §6.1 · p. 8

6.2.1 Experimental Setting

• Experiments used ReLU networks on a six-core CPU, with randomized hashing configured to K = 6 bits and L = 5 tables.The active-node count was capped to control computation; learning rates were selected by grid search.Source: §6.2.1 · p. 8

6.2.2 Effect of computation levels

• The x-axis in Figures 4 and 5 is the average active-node percentage; standard neural-network accuracy is shown as a dashed black baseline.Each hidden layer has 1,000 nodes; most comparison methods compute all activations before zeroing selected nodes, unlike LSH and vanilla dropout.Source: §6.2.2 · p. 8
• LSH gave the best overall accuracy with the fewest active nodes, and the plots were consistent across datasets and network depths.As active nodes fell from 90% to 5%, LSH had the smallest performance drop and less volatility.Source: §6.2.2 · p. 8
• Adaptive Dropout diverged below 25% active nodes, so results are unavailable for its 5% and 10% settings.The reported experiments used α = 1.0 and β values of −1.5, −1.0, 0, 1.0, and 3.5.Source: §6.2.2 · p. 8
• The authors report that LSH performs well at low computation levels, while method performance stabilizes as computation approaches 100%.They connect fewer operations with reduced processor energy use and heat production.Source: §6.2.2 · p. 8

6.3.1 Experimental Setting

• The experiments used concurrent ASGD with momentum and adagrad on a 56-core Intel Xeon ES-2697 machine with 256 GB of memory.Models used ReLU activations and learning rates between 10^-2 and 10^-3.Source: §6.3.1 · p. 8

6.3.3 ASGD PerformanceComparisonwithStandard Neural Network

• With 56-core ASGD, LSH outperforms the standard network on all experimental datasets, while parallel vanilla SGD converges more slowly and performs especially poorly on Convex.Dense updates can overwrite one another, affecting the four datasets differently.Source: §6.3.3 · p. 9

6.3.2 Results with different numbers of processors

• With 5% LSH, convergence on all four datasets is indistinguishable between 1-core and 56-core ASGD updates.The experiments report similar convergence rates and accuracy regardless of processor count.Source: §6.3.3 · p. 9, §6.3.2 · p. 9

6.3.3 ASGD PerformanceComparisonwithStandard Neural Network

• Adding processors produces a near-perfect decrease in LSH-5% wall-clock time per epoch, consistent with fewer gradient overwrites.Too many overwrites may require atomic updates, adding overhead and hurting parallelism.Source: §6.3.3 · p. 9
• 50,254 to 1,637 seconds per epoch on MNIST8M yields about a 31x speedup with 56 processors, without affecting convergence.The reported times are for the 1-core and 56-core implementations, respectively.Source: §6.3.3 · p. 9
• Scaling flattens on Convex and Rectangles because their smaller training sets offer less parallel work, especially with 56 processors.The paper reports no such behavior on MNIST8M, which has around 8 million training examples.Source: §6.3.3 · pp. 9–10

• Approximate query processing can identify an active parameter set without the parameter-scale search normally required, while approximate sets add random noise that may aid generalization.The discussion links sparse, random updates to a lower likelihood of overwriting one another.Source: §7 · p. 10
• Recasting the learning problem as approximate query processing draws on decades of systems and database research for scalability across distributed systems.The paper presents deep-network scaling as one concrete demonstration of this integration.Source: §7 · p. 10

• The approach performs better than other methods using only 5% of the nodes executed in a standard network, and the authors project longer mobile-device battery life while maintaining performance.The conclusion also reports near-linear scaling with asynchronous SGD across multiple processors.Source: §8 · p. 10
• Future work is to optimize the approach for mobile processors, including Nvidia Tegra, Qualcomm Snapdragon, and Myriad 2 VPU architectures.The authors plan to leverage differences among these platforms for greater efficiency.Source: §8 · p. 10
• Figure 6 evaluates LSH-5% convergence across 1, 8, and 56 threads on four datasets, using only 5% of standard-network computation.Source: Figure 6 · p. 11