PaperlayerView exact revision on arXiv

Source-linked AI summary

On-Device Machine Learning: An Algorithms and Learning Theory Perspective

Sauptik Dhar, Junyao Guo, Jiayi Liu, Samarth Tripathi, Unmesh Kurup, Mohak Shah

arXiv:1911.00623v2cs.LGcs.DCstat.ML

TL;DR

On-device learning is motivated by cloud-based privacy, security, and latency constraints, alongside growing interest in device-side training. This survey reformulates on-device learning as resource-constrained learning over compute and memory, synthesizes algorithms and theory, and identifies research needs.

  • Problem

    Cloud-based training exposes user data to transmission and storage risks and can impose untenable latency for real-time model updates.

  • Method

    The survey reformulates on-device learning as resource-constrained learning with compute and memory as the relevant resources.

  • Results

    The survey summarizes the state of the art and identifies areas needing further algorithmic and theoretical research and development.

  • Takeaways & Limitations

    Resource-constrained learning provides a device-agnostic basis for comparing tools, techniques, and algorithms from diverse research areas.

  • Takeaways & Limitations

    Traditional learning theories primarily analyze estimation error guarantees and do not directly address how resource constraints affect generalization.

Abstract

from arXiv · show

The predominant paradigm for using machine learning models on a device is to train a model in the cloud and perform inference using the trained model on the device. However, with increasing number of smart devices and improved hardware, there is interest in performing model training on the device. Given this surge in interest, a comprehensive survey of the field from a device-agnostic perspective sets the stage for both understanding the state-of-the-art and for identifying open challenges and future avenues of research. However, on-device learning is an expansive field with connections to a large number of related topics in AI and machine learning (including online learning, model adaptation, one/few-shot learning, etc.). Hence, covering such a large number of topics in a single survey is impractical. This survey finds a middle ground by reformulating the problem of on-device learning as resource constrained learning where the resources are compute and memory. This reformulation allows tools, techniques, and algorithms from a wide variety of research areas to be compared equitably. In addition to summarizing the state-of-the-art, the survey also identifies a number of challenges and next steps for both the algorithmic and theoretical aspects of on-device learning.

1 INTRODUCTION

On-device learning addresses cloud-based systems’ privacy, personalization, and latency drawbacks by moving model development onto resource-constrained devices. This survey focuses on algorithmic and theoretical approaches, organizing them around compute and memory constraints.

  • Motivation: Cloud-based learning exposes transmitted and stored user data to privacy and security risks.Data is transferred to and stored in the cloud, creating opportunities for interception or unauthorized access.
  • Motivation: Aggregated cloud-trained models are typically less personalized because individual models are often cost prohibitive.Distributed approaches such as federated learning generally improve a global model rather than fully tailoring one to each consumer.
  • Motivation: Cloud-based training adds communication latency, making local model updates necessary for scenarios requiring rapid responses.The paper identifies connected vehicles and autonomous driving as examples where long delays become untenable.
  • Resource-constrained setting: Edge devices are defined by constrained compute, memory, and energy resources that cannot be easily increased or decreased.The constraints arise from form-factor or cost considerations; cloud systems and upgradeable workstations are excluded.
  • Improvement levels: Improving on-device training can involve hardware, libraries, algorithms, or theory, with this survey covering the latter algorithmic and theoretical levels.Hardware and libraries provide lower-level interfaces, while algorithms and theory address resource efficiency more abstractly.
  • Survey scope: The survey analyzes on-device learning at the algorithms and learning-theory levels, emphasizing hardware-independent approaches for single devices.Its framework reformulates efficiency using compute and memory, enabling comparison of machine-learning techniques and identifying future research challenges.

2 RESOURCE CONSTRAINTS IN ON-DEVICE LEARNING

On-device learning must balance model accuracy with constrained compute, memory, energy, and response-time resources. These constraints affect how applications are measured, designed, and optimized on edge hardware.

  • Processing speed: Response time is measured through throughput and latency, with latency emphasized for time-critical applications.Throughput measures processed input rate, whereas latency measures the interval from one input to its response; the survey uses runtime as an abstract proxy for both.
  • Scope: Communication latency affects processing speed but is outside this survey’s scope because it is associated with distributed or decentralized edge learning.The survey focuses on resource constraints for single-device learning rather than communication among system components.
  • Memory: Limited device memory makes lightweight models essential because training stores parameters and auxiliary variables.Even ResNet-50 can require megabytes of memory, motivating model designs tailored to edge constraints.
  • Memory: Memory access can bottleneck throughput and increase energy consumption during model execution.A single MAC requires three memory reads and one write, which may access slower off-chip memory and cause orders-of-magnitude higher energy use.
  • Power consumption: Power consumption depends on computation volume and application context, so system power alone is unsuitable for evaluating edge machine-learning workloads.Energy-efficient solutions can extend battery life and reduce maintenance costs, while energy estimates commonly use surrogates based on memory and runtime.
  • Resource characterization: Hardware diversity creates a broad range of resource constraints that must be incorporated into model, algorithm, and theoretical design.The survey characterizes edge learning across varied hardware specifications and emphasizes understanding those constraints before designing systems.

3 ALGORITHMS FOR ON-DEVICE LEARNING

This section surveys task-agnostic algorithms and analysis techniques for on-device learning under compute and memory constraints. It compares resource footprints, profiling, modeling, lightweight architectures, and metrics across traditional ML and DNNs.

  • Task-agnostic approaches: Resource-efficient techniques adapt traditional ML algorithms and deep learning models to constrained devices across classification, detection, regression, segmentation, and super-resolution.The survey presents these approaches task-agnostically and expects them to generalize across tasks.
  • Resource analysis: Resource analysis combines asymptotic complexity with hardware-agnostic metrics such as parameter counts and FLOPs/MACs, although these metrics may poorly predict actual performance.The section compares computational and space complexity for traditional algorithms and DNNs using both analysis styles.
  • Traditional machine learning: Most traditional algorithms have model sizes linear in input dimension and fast inference, but some require matrix inversion or eigen-decomposition near O(n^3).kNN is an exception because inference requires distance calculations against all training samples; platform support for complex matrix operations must be considered.
  • Open evaluation gaps: On-device learning lacks sufficient studies jointly analyzing algorithm accuracy, complexity, and their tradeoffs, limiting empirical understanding of traditional and DNN approaches.The survey also notes limited focus on RNNs and traditional methods because of structural complexity, heterogeneity, and missing benchmarking datasets.
  • Deep neural networks: DNN training is especially resource intensive because memory must hold weights, activations, gradients, data batches, and workspace, often requiring hundreds of MBs or GBs.The resulting models are difficult to deploy on constrained devices, motivating smaller and more compact architectures.
  • Resource profiling: Deployment profiling measures resource requirements accurately, but large-scale DNN training benchmarks on edge devices remain infeasible and traditional-ML profiling is comparatively sparse.Reported traditional-ML studies often compare inference time or energy without profiling memory footprint.
  • Resource modeling: DNN resource-estimation models commonly use features such as FLOPs, activation size, matrix size, kernel size, and layer configuration, yet most achieve relative errors of 20%–30%.The survey notes that these models are platform- and framework-dependent, and that FLOPs or MACs alone provide limited insight.

3.2 Resource Efficient Training

Resource-efficient training adapts models, optimization, and data representations to operate within constrained compute and memory budgets. The survey emphasizes lightweight architectures, model simplification, quantization, and training-routine changes as complementary algorithmic strategies.

  • Resource-constrained training: Resource-constrained training targets the model, optimization process, and dataset, using complexity reduction, optimization changes, and data reduction as primary approaches.These sources of resource use motivate distinct but complementary algorithmic adaptations.
  • Traditional algorithms: Decision-tree pruning and shallow sparse tree learners reduce memory requirements, with some learners requiring only a few kilobytes.Pruning is also used to reduce over-fitting caused by large tree structures.
  • Reducing model complexity: Lightweight CNN architectures reduce model size and computation while retaining fairly good accuracy compared with larger CNNs.The survey notes limited comparable work on lightweight DNN architectures beyond CNNs.
  • Reducing model complexity: Neural architecture search explores accuracy–energy/runtime tradeoffs and can generate models suited to platforms with different resource constraints.The survey identifies MnasNet as a representative NAS-generated model and contrasts it with manually designed networks.
  • Architecture evolution: Figure 3 tracks CNN evolution using ImageNet top-1 accuracy and FLOPS, with FLOPS represented by ball size and publication availability determining time.The plotted models exceed 60% top-1 ImageNet accuracy and show a transition toward NAS-generated architectures.
  • Reducing model complexity: Pruning, sparse structures, and quantization reduce DNN complexity by removing structure or using lower-precision representations.Quantized training may require modifications to account for quantization error.
  • Optimization routines: Efficient optimization routines aim to reduce training time, while quantization-aware modifications address instability caused by quantization error.The survey distinguishes convergence improvements from explicit treatment of other resource constraints.

3.3 Resource Efficient Inference

Resource-efficient inference compresses or adapts models to reduce deployment cost, while broader algorithm-development challenges concern measurement, platform variability, and coverage beyond CNNs. Dynamic methods respond to changing inputs and resource budgets, but practical comparison remains difficult across systems.

  • Model compression: Static compression techniques reduce DNN model size while retaining most predictive capacity, but compressed models cannot adapt their complexity to changing resources or inputs.Examples include pruning, vector quantization, distillation, hashing, projection, and binarization.
  • Adaptive inference: Adaptive inference scales computation to inputs, using approaches such as early termination and cascaded processing when simple samples need less computation.The cited motivation is that difficult inputs may require more complex models than easy inputs.
  • Challenges: Resource characterization varies substantially with platform, framework, and computing library, making it difficult to select algorithms that fit specific budgets.The survey highlights framework-dependent CNN memory footprints and differing memory-optimization mechanisms.
  • Challenges: Hardware-agnostic measures such as parameter counts and FLOPs rarely reflect realistic platform performance or guarantee that training fits the resource budget.The survey calls for practical, commensurable, and interpretable metrics covering accuracy and multiple resource constraints.
  • Challenges: Research focuses mainly on DNNs, especially CNNs, while RNNs and traditional methods remain less studied despite their relevance to devices with megabytes or kilobytes of memory.The survey also identifies small-data learning as a challenge for reducing training-data memory requirements.
  • Dynamic resource budgets: Runtime model selection can choose among nested models with different accuracy–latency tradeoffs while satisfying user-defined requirements and a device memory limit.The described deployment uses a greedy heuristic for multiple applications.

4 THEORETICAL CONSIDERATIONS FOR ON-DEVICE LEARNING

The survey connects resource-constrained algorithm design to computational learning theory. It categorizes the theoretical foundations of existing approaches and formalizes resource-constrained learning as an extension of traditional learning formulations.

  • Theoretical foundations: Theoretical considerations examine the computational learning theory underlying algorithms for on-device learning.The survey positions this analysis after its categorization of resource-constrained algorithms.
  • Theoretical foundations: Traditional machine learning theory supports inference methods and several resource-efficient training approaches, including low-footprint learning, model-complexity reduction, data compression, and modified optimization.The survey presents traditional theory as one underlying category rather than the only theoretical basis.
  • Survey organization: The survey provides a brief review of traditional theories to introduce notation and situate later resource-constrained formulations.The review is included despite the abundance of existing literature on traditional learning theories.
  • Formalization: Section 4.1 formalizes both traditional and resource-constrained learning problems before the survey details their theoretical connections.The formalization provides the stated basis for analyzing algorithms under resource constraints.

4.1 Formalization of the Learning problem

The survey begins with a supervised inductive learning formulation and then extends it to resource-constrained machine learning. It uses a data-generating distribution over inputs and labels as the basis for this formalization.

  • 4.1 Formalization of the Learning problem: The section first formalizes traditional machine learning before extending the formulation to novel algorithms under resource constraints.This ordering establishes the conventional problem before introducing the constrained setting.
  • 4.1 Formalization of the Learning problem: The formalization focuses on supervised problems under an inductive learning setting.Transductive, semi-supervised, and universum settings are identified as possible extensions but are outside this focus.
  • 4.1 Formalization of the Learning problem: The section’s progression from conventional supervised learning to resource-constrained learning supplies the framework for later theoretical analysis.This progression is stated as the section’s formalization plan.
  • 4.1 Formalization of the Learning problem: In the supervised formulation, labels follow an underlying process y = д(x), with y in Y and x in a data domain X contained in R^d.The label-generating process is characterized by a data-generating distribution D.
  • 4.1 Formalization of the Learning problem: The input–label relationship is modeled through a data-generating distribution that governs the supervised learning problem.This distributional characterization provides the basis for the displayed formalization.
  • 4.1 Formalization of the Learning problem: The formalization treats x as belonging to the data domain X, which is represented as a subset of R^d.The passage explicitly assigns x to the input domain and y to the label space.

Definition 1. Inductive Learning

Inductive learning estimates a hypothesis from a hypothesis class that approximates the data-generating process by minimizing expected loss. Common instances include binary classification and regression, with methodology defining the hypothesis class.

  • Inductive learning estimates a hypothesis ĥ : X → Y from a hypothesis class H to approximate the data-generating process.
  • The learning objective is to minimize expected loss under the data-generating distribution.
  • Binary classification uses 0/1 loss, with Y = {−1, +1} and O = {0, 1}.
  • Regression with additive Gaussian noise uses least-square loss over real-valued outputs.
  • Domain knowledge and solution methodology determine the hypothesis class, such as unconstrained or L1-constrained linear models.
  • Resource-constrained learning adds compute and memory requirements beyond minimizing true risk.

Definition 2. Resource Constrained Machine Learning

Resource-constrained machine learning minimizes true risk while requiring resource constraints during inference or training. These constraints can apply to the final model or to the model-building algorithm.

  • Resource-constrained learning simultaneously minimizes true risk and satisfies a predefined resource constraint.
  • During inference, the constraint applies to the estimated model ĥ through C(ĥ).
  • During training, the constraint applies to the algorithm output C(A(S)), where A maps training data to a hypothesis.
  • The key distinction from traditional inductive learning is constraining either the final model or the training algorithm.

4.2 Learning theories

Traditional learning theory analyzes model quality through approximation and estimation error, with PAC learning providing probabilistic guarantees and ERM offering a common algorithmic framework.

  • Traditional theories decompose prediction error into approximation error and estimation error.
  • PAC learning guarantees error tolerance ϵ with probability 1 − δ when the sample size meets a polynomial requirement.
  • Efficient PAC learning additionally requires the algorithm’s computation complexity to be polynomially bounded.
  • The survey focuses mainly on sample complexity and generalization bounds for binary classification while noting extensions to other tasks.
  • Empirical Risk Minimization algorithms return the hypothesis minimizing empirical risk on the training set.
  • ERM analysis relies on uniform convergence, which bounds |R_S(h) − R(h)| uniformly over h ∈ H.

Definition 4. Canonical Forms

Canonical learning-theory forms organize generalization, sample complexity, algorithmic computation, and resource-constrained learnability. The survey highlights approaches that explicitly analyze memory, observation, and computation alongside statistical requirements.

  • Definition 4. Canonical Forms: Generalization bounds relate true risk to empirical risk for a hypothesis class, training set, and chosen ϵ and δ.
  • Definition 4. Canonical Forms: Sample complexity follows from uniform convergence and depends on how hypothesis-class complexity is measured.
  • Definition 4. Canonical Forms: Canonical complexity measures include growth functions, covering numbers, Gaussian complexity, and maximum discrepancy.
  • Definition 4. Canonical Forms: PAC theory compares algorithmic efficiency using machine-independent big-O computation complexity, despite runtime depending on the machine.The passage contrasts binary sort O(n^2) with merge sort O(nlogn).
  • Definition 4. Canonical Forms: Traditional theories treat sample complexity and resource complexity such as computation, memory, bandwidth, and power as disjunctive.
  • 4.2.2 Resource-Constrained Learning Theories.: Restricted focus of attention limits observed features and analyzes the resulting interplay between memory and sample complexity.
  • 4.2.2 Resource-Constrained Learning Theories.: Streaming statistical-query protocols characterize learnability under space constraints for finite hypothesis classes and extend to infinite classes through ε-covers.
  • 4.2.2 Resource-Constrained Learning Theories.: Hypothesis graphs, branching programs, and mini-batch protocols connect bounded-memory learnability to graph mixing, matrix norms, or O(T(b + n_td)) space.The cited approaches include neural-network unlearnability results, singular-value bounds, and iterative estimation settings.

4.3 Challenges in Resource-Efficient Theoretical Research

Resource-efficient theoretical research faces gaps in learnability guarantees, comprehensive resource analysis, empirical validation, model selection, and framework comparison.

  • Open theoretical challenges: Most theories analyze when hypothesis classes become unlearnable under resource constraints rather than developing algorithms that guarantee learnability.A few frameworks guide resource-efficient algorithm design, but their assumptions exclude many hypothesis classes.
  • Open theoretical challenges: Existing analyses usually isolate one aspect of space complexity instead of jointly analyzing an algorithm’s overall space and computation complexity.Examples include per-sample space and intermediate-state representation complexity.
  • Open theoretical challenges: Most theoretical frameworks provide limited empirical analysis, and their asymptotic expressions do not yet clearly translate into practical behavior.The practical interpretation of mathematical resource bounds remains an open problem.
  • Open theoretical challenges: Current theories generally lack resource-constrained procedures for hyperparameter optimization, model selection, and correctness guarantees for the selected model.The missing capability concerns selecting an optimal model while respecting resource constraints.
  • Open theoretical challenges: A systematic comparison among the resource-constrained learning frameworks summarized in Table 10 is still missing.The survey identifies framework comparison as a separate unresolved challenge.

5 DISCUSSION

The discussion organizes on-device learning around resource-aware algorithms and theories, then identifies hardware-aware modeling, broader algorithm coverage, dynamic budgets, and stronger empirical grounding as research needs.

  • Algorithm Research: Algorithm research designs models under limited resources using software-centric surrogates based on asymptotic analysis, profiling, or resource modeling.These surrogates approximate hardware constraints for computational model design.
  • Algorithm Research: Current algorithmic approaches include lightweight algorithms, reduced model complexity, modified optimization routines, data compression, and new data-observation protocols.These approaches constrain model, computation, data, or observation resources in different ways.
  • Algorithm Research: New data-observation protocols are guided by resource-constrained learning theory and can support algorithms for a wider range of learning problems and loss functions.The framework changes traditional batch or online observation assumptions while modeling the interaction between resources and model quality.
  • Research challenges: Algorithm design needs better software-centric characterization of hardware constraints because optimal designs depend on the device’s computational model and available resources.The survey also highlights applicability to broader algorithm classes and dynamic resource budgeting.
  • Theory Research: Traditional learning theories do not directly capture the interplay between resource constraints and generalization or error guarantees.They often constrain the hypothesis class first and then optimize within that class.
  • Theory Research: Resource-constrained theories provide learning guarantees under device limits and generic algorithm-design frameworks, but few algorithms currently use them.Applying these theories to complete machine-learning pipelines, including hyperparameter optimization, remains underdeveloped.
  • Research challenges: The discussion frames adoption challenges as spanning algorithmic resource optimization, software-centric measurement, and broader research and development needs.The section positions these issues within the broader transition from cloud-based to edge learning.
  • Research challenges: Traditional machine learning methods and low-sample-complexity algorithms deserve more attention because deep architectures can be unsuitable for devices with very limited memory and compute.Dynamic resource budgets also require algorithms that incorporate accuracy-latency trade-offs as application priorities change.

6 CONCLUSION

The survey narrows on-device learning to an algorithms-and-theory perspective by reformulating it as resource-constrained learning, then identifies unresolved algorithmic and theoretical challenges.

  • Scope and framing: The survey addresses growing interest in on-device training by focusing on algorithms and learning theory rather than systems-level hardware and library effects.It studies learning on single devices while noting extension to distributed settings through communication-latency constraints.
  • Scope and framing: Reformulating on-device learning as resource-constrained learning provides a basis for identifying areas requiring further research and development.The resource perspective supports a device-agnostic treatment of the field.
  • Algorithmic challenges: Current algorithmic work mainly uses lightweight algorithms or modifies existing algorithms to reduce resource utilization.The survey identifies decoupling algorithms from hardware, resource-aware metrics, broader low-sample-complexity methods, dynamic budgets, and improved profiling as needs.
  • Theoretical challenges: Resource-constrained learning theory currently emphasizes un-learnability and memory complexity rather than learnability guarantees, estimation error, and compute requirements.The survey presents these as the natural next directions for theoretical research.
Loading 1911.00623v2…