PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithmic progress in computer vision

Ege Erdil, Tamay Besiroglu

arXiv:2212.05153v4cs.CVcs.LG

TL;DR

The paper asks how much ImageNet classification progress reflects scaling compute and data versus algorithmic improvements. It models performance and uses Shapley values to attribute progress across these sources. It finds algorithms contribute roughly as much as compute scaling, with compute-augmenting advances predominating and estimated to halve compute requirements about every nine months.

  • Problem

    The contribution of scaling compute and data versus algorithmic and architectural improvements to machine-learning progress remains debated.

    Source: §1 · p. 1

  • Method

    The paper models ImageNet performance using neural-scaling-law guidance and applies Shapley values to attribute improvements across algorithms, compute, and data.

    Source: §1 · p. 2, §5.2 · p. 5

  • Results

    Algorithmic and hardware improvements contribute roughly equally to computer-vision performance, and compute-augmenting innovations are the main driver of algorithmic progress, halving compute requirements about every nine months.

    Source: §6 · pp. 7–8, §5.4 · p. 7

  • Takeaways & Limitations

    For the computer-vision models studied, algorithmic advances mainly improve compute efficiency rather than expand effective data budgets.

    Source: §5.1 · p. 5, §6 · p. 8

    Because the model is nonlinear, parameter estimates favoring compute augmentation do not alone establish that it is the primary performance mechanism.

    Source: §5.3 · p. 6

Abstract

from arXiv · show

We investigate algorithmic progress in image classification on ImageNet, perhaps the most well-known test bed for computer vision. We estimate a model, informed by work on neural scaling laws, and infer a decomposition of progress into the scaling of compute, data, and algorithms. Using Shapley values to attribute performance improvements, we find that algorithmic improvements have been roughly as important as the scaling of compute for progress computer vision. Our estimates indicate that algorithmic innovations mostly take the form of compute-augmenting algorithmic advances (which enable researchers to get better performance from less compute), not data-augmenting algorithmic advances. We find that compute-augmenting algorithmic advances are made at a pace more than twice as fast as the rate usually associated with Moore's law. In particular, we estimate that compute-augmenting innovations halve compute requirements every nine months (95\% confidence interval: 4 to 25 months).

1 Introduction

The paper addresses debate over how much computer-vision progress comes from scaling compute and datasets versus algorithmic and architectural improvements. It decomposes progress on ImageNet and examines algorithmic advances, including estimates that they double effective compute roughly every nine months.

1 Introduction

  • The paper frames its analysis against debate over the contributions of scaling compute and datasets versus improvements to algorithms and architectures.Prior work re-implemented 15 popular models and reported a 44-fold compute reduction to reach AlexNet performance [Krizhevsky, Sutskever, and Hinton 2012].Source: §1 · pp. 1–2
  • Algorithmic improvements double effective compute available for training image-classification models roughly every nine months, according to model predictions.The figure cautions that its predictions may extrapolate beyond the model’s domain of validity.Source: Figure 1 · p. 1
  • Related studies across computing problems report variable algorithmic progress, often comparable to or greater than hardware progress.Evidence includes studies of algorithm families, scientific computing, optimization solvers, SAT solvers, and chess engines.Source: §1 · p. 2
  • The paper decomposes ImageNet progress into algorithmic advances and compute and data scaling, then distinguishes compute- from data-augmenting algorithms.It also estimates how much less compute is needed over time to reach a given performance level.Source: §1 · p. 2

2 Estimating the extent of algorithmic advances

Measuring algorithmic progress in machine learning is difficult because estimates based on a single benchmark threshold can vary with the chosen threshold. The paper motivates evaluating models at the scales used in their original implementations, where scaling behavior and low-resource performance can differ.

2 Estimating the extent of algorithmic advances

  • A fixed-performance approach measures how much compute newer architectures need to match an earlier model’s benchmark result.Prior work found the compute needed to match AlexNet’s top-5 ImageNet classification error halved every 16 months.Source: §2 · p. 2
  • Estimates of algorithmic progress can vary by around a factor of ten depending on whether an easy or difficult benchmark threshold is selected.Easy thresholds can make algorithmic improvements appear less significant, while hard thresholds can make them explain nearly all observed gains.Source: §2 · pp. 2–3
  • Algorithmic gains may depend on scale: some improve performance regardless of execution scale, while others adapt to new hardware.A miniature Vision Transformer at compute parity with LeCun et al.’s 1989 convolutional network failed to achieve good performance; the paper therefore considers implementations at scales reported in the original publications.Source: §2 · p. 3

3 Empirical approach

The empirical approach uses neural scaling laws to estimate how compute, data, and algorithm quality relate to ImageNet performance. Its model represents effective compute and data as time-varying budgets and incorporates regularization to address weak identification of data-scaling parameters.

3 Empirical approach

  • The empirical approach aims to align with neural scaling laws, distinguish compute- from data-bottleneck effects of algorithms, and account for model fit.It estimates performance relationships using models presented at scales reported in the relevant publications.Source: §3.1 · p. 3, §3 · p. 3

3.1 Empirical model

  • The model predicts top-1 ImageNet accuracy from effective compute and data budgets through a product of sigmoid terms with an error term.Effective budgets are logarithmic functions of year and the model’s compute or data; time-varying coefficients capture changes in how efficiently each is used.Source: §3.1 · pp. 3–4
  • Predictions may be unreliable when compute or data lie far outside the observed range, including meaningless cases where data greatly exceeds compute.The authors note that processing images requires at least on the order of one floating-point operation per image.Source: §3.1 · p. 4
  • The model uses priors and maximum a posteriori estimation because the relatively small dataset leaves data-scaling parameters poorly identified without regularization.Pure maximum-likelihood bootstrap estimates put data-scaling parameters at unrealistic values in about 5% of simulated datasets.Source: §3.1 · p. 4

4 Dataset

The dataset extends an existing collection of ImageNet-1k computer-vision models and estimates training compute when papers do not report it. It excludes re-implementations and neural-architecture-search models for stated reliability and scaling-behavior concerns.

4 Dataset

  • The dataset extends Thompson et al.’s collection to 124 computer-vision models tested on ImageNet-1k.When training compute is unreported, it is estimated from architecture, dataset size, and epochs using a previously described procedure.Source: §4 · p. 4
  • The dataset excludes prior-model re-implementations and neural-architecture-search models.Re-implementation performance was considered unreliable and potentially affected by software improvements; architecture-search models were excluded because their scaling behavior may differ from other models.Source: §4 · p. 4

5 Results

The results attribute ImageNet progress to compute scaling and algorithmic innovation using Shapley values, with algorithmic improvements roughly as important as compute overall. The estimates point mainly to compute-augmenting innovation, while the model’s nonlinearity qualifies what budget changes alone imply about performance.

5.1 Empirical estimates

  • αYear is positive and significant at 5%, indicating that models use compute more effectively over time; βYear is smaller and not significant.The estimates indicate no discernible net effect of algorithmic improvements on expanding effective data budgets.Source: §5.1 · p. 5, Table 1 · p. 5

5.2 Progress has mostly been due to compute and algorithms

  • Algorithmic innovation accounts for 24.9% to 70.6% of performance gains across model transitions, and is roughly as important as compute scaling overall.Algorithmic progress was more crucial in early years, while compute scaling was more important in later years.Source: Table 2 · p. 6, §5.2 · p. 6

5.3 Most algorithmic progress involves improved compute efficiency

  • Algorithmic innovation expands effective compute budgets by 100.96% per year (95% CI: 24.60% to 215.18%) and effective data budgets by 37.64% (95% CI: -46.95% to 134.46%).The authors characterize the main effect as compute-augmenting, but caution that the nonlinear model means budget estimates alone do not establish the primary performance mechanism.Source: §5.3 · p. 6
  • Compute-augmenting innovations explain four to 11 times more variation in performance than data-augmenting innovations.The relative multiple is reported as 11-fold for AlexNet to ResNet50 and roughly 7x for AlexNet to ViT-e.Source: §5.3 · p. 6

5.4 Algorithmic progress doubles effective compute budgets roughly every nine months

  • Algorithmic improvements double effective compute in a mean of 8.95 months (95% CI: 3.55 to 25.40 months).The doubling time is calculated from the model coefficients and bootstrapped estimates.Source: §5.4 · p. 7

6 Conclusion

The paper decomposes ImageNet computer-vision progress into compute, data, and algorithmic contributions, finding algorithms and hardware contributed roughly equally. Compute-augmenting innovations were the main form of algorithmic progress in the models considered and reduced compute requirements at an estimated faster pace than earlier work suggested.

6 Conclusion

  • Algorithms and hardware contributed roughly equally to performance improvements in computer vision.The estimate uses marginal expected contributions from different sources of progress.Source: §6 · p. 7
  • Compute-augmenting advances were the main driver of algorithmic improvements in the computer-vision models considered.These innovations enable researchers to achieve better performance with less compute.Source: §6 · p. 8
  • Nine months is the estimated time for compute-augmenting innovations to halve compute requirements, faster than the previously reported 16 months.The paper says this pace is likely faster than past work found.Source: §6 · p. 8

Appendix A: Estimating compute

The appendix describes two ways to estimate training compute: counting model operations across training passes, or estimating compute from training time and GPU performance.

Appendix A: Estimating compute

  • Two methods from Sevilla et al. 2022 estimate training compute: operation counts from model architecture and batches, or hardware performance and training time.The appendix presents these as complementary approaches.Source: Appendix A · p. 8

Method 1: Counting operations in the model

  • Training compute is the forward- and backward-pass operations multiplied by the number of training passes.The appendix simplifies this to three times forward-pass FLOPs, epochs, and examples; when example count is unstated, it can be derived from batches per epoch and batch size.Source: Method 1: Counting operations in the… · p. 8

Method 2: GPU time

  • Training-time estimates multiply seconds, core count, peak FLOP/s, and utilization rate to estimate compute.When utilization cannot otherwise be derived, the authors often assume 0.3 as a baseline.Source: Method 2: GPU time · p. 8

Appendix B: Empirical challenges

The authors report estimation challenges from a limited dataset and from fitting nonlinear models with multiple similarly fitting local maxima. Their constant-rate assumption also limits what the data can establish about changes in algorithmic progress over time.

Appendix B: Empirical challenges

  • 2% to 5% of bootstrap estimates prefer another local maximum, producing highly skewed, non-unimodal parameter distributions.Because separated maxima can have similar goodness of fit, Fisher-information standard errors are unreliable; the authors report standard errors and 90% confidence intervals but favor bootstrapping for parameter uncertainty.Source: Appendix B · pp. 8–9
  • The limited, later-year-concentrated dataset makes year-specific efficiency estimates too variable and cannot reliably establish higher-order trends in algorithmic progress.The authors therefore choose a constant rate of algorithmic improvement as a bias-variance trade-off, not as evidence that the historical pace was constant.Source: Appendix B · p. 9

Appendix C: Senstivity of threshold-based estimates

The appendix shows threshold-based halving-time estimates depend on the chosen target, contrasts prediction trends for compute- and data-bottlenecked models, and relates the model’s sigmoid form to standard scaling laws.

Appendix C: Senstivity of threshold-based estimates

  • Halving-time estimates can differ by an order of magnitude between easier AlexNet-level targets and recent-model targets around 87% without additional training data.Table 4 estimates the compute required to train models to a given performance level.Source: Appendix C · p. 9, Table 4 · p. 9

Appendix D: Predictions

  • The model has high prediction uncertainty in some situations because of parameter uncertainty and noise built into the model.Figure 3 illustrates both mean predictions and uncertainty.Source: Appendix D · p. 10, Figure 3 · p. 10
  • Algorithmic improvements help both compute- and data-bottlenecked models, but their impact seems greater for compute-bottlenecked models, where improvement over time is considerably faster.Figure 3 illustrates the models’ mean predictions and uncertainty.Source: Appendix D · p. 10, Figure 3 · p. 10

Appendix E: Relationship with standard scaling laws

  • The model’s performance is a product of two sigmoid terms, whose large-argument approximation makes its similarity to traditional scaling laws apparent (Hoffmann et al. 2022).The model includes year, data, and compute terms.Source: Appendix E · p. 10

Appendix F: Supporting results

The appendix checks the decomposition in log-odds space and finds that its key results do not substantially differ from the linear-space analysis. It also presents Shapley-attribution results and shares of algorithmic progress by augmentation type.

Decompositions in log-odds space

  • The analysis replaces linear distance between predicted performances with distance in log-odds space, a measure suited to values bounded on the unit interval.The section reports Shapley decompositions in log-odds space.Source: Decompositions in log-odds space · p. 10, Table 2 · p. 11
  • Table 2 attributes progress between model pairs to algorithmic progress, compute scaling, and data scaling; “NS” marks no scaling of an input.Numbers may not add to 100 because of rounding.Source: Table 2 · p. 11
  • Table 3 reports the shares of algorithmic progress that are compute-augmenting versus data-augmenting.Source: Table 3 · p. 11
  • The log-odds decomposition results do not substantially differ from the linear-space results, supporting the robustness of the key findings to this analysis choice.The log-odds distance is described as a natural measure for values bounded on the unit interval.Source: Decompositions in log-odds space · pp. 10–11
Loading 2212.05153v4…