PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Task Allocation for Mobile Edge Learning

Umair Mohammad, Sameh Sorour

arXiv:1811.03748v2cs.DCcs.LGcs.NI

TL;DR

The paper addresses adaptive task allocation for distributed learning on wireless edge nodes with heterogeneous computing and communication capacities under a fixed cycle-time budget. It formulates an NP-hard integer problem, relaxes it, and develops bound-based and suggest-and-improve solutions. Simulations show substantially more local updates and faster accuracy gains than equal task allocation.

Abstract

from arXiv · show

This paper aims to establish a new optimization paradigm for implementing realistic distributed learning algorithms, with performance guarantees, on wireless edge nodes with heterogeneous computing and communication capacities. We will refer to this new paradigm as `Mobile Edge Learning (MEL)'. The problem of dynamic task allocation for MEL is considered in this paper with the aim to maximize the learning accuracy, while guaranteeing that the total times of data distribution/aggregation over heterogeneous channels, and local computing iterations at the heterogeneous nodes, are bounded by a preset duration. The problem is first formulated as a quadratically-constrained integer linear problem. Being an NP-hard problem, the paper relaxes it into a non-convex problem over real variables. We thus proposed two solutions based on deriving analytical upper bounds of the optimal solution of this relaxed problem using Lagrangian analysis and KKT conditions, and the use of suggest-and-improve starting from equal batch allocation, respectively. The merits of these proposed solutions are exhibited by comparing their performances to both numerical approaches and the equal task allocation approach.

I. INTRODUCTION

The paper introduces Mobile Edge Learning for distributed learning across heterogeneous wireless edge nodes, where adaptive allocation must improve accuracy under bounded communication and computation time. It motivates this setting through distributed learning's local training and global aggregation cycles.

I. INTRODUCTION

  • Existing distributed-learning studies largely assume wired or homogeneous environments, leaving the effects of heterogeneous learner and link capacities on task allocation insufficiently investigated.Prior work optimized learning cycles but overlooked heterogeneous computing and communication capacities.Source: §I · p. 1
  • MEL targets distributed learning over heterogeneous wireless edge nodes while maximizing local iterations and respecting a preset global-cycle duration.The duration covers data distribution, local processing, and parameter aggregation.Source: §I · p. 2

A. Distributed Learning Preliminaries

  • Distributed learning cycles between local training on learners' batches and orchestrator aggregation of updated parameters.The framework supports distributed datasets and task parallelization, with the latter additionally requiring batch transfer from the orchestrator.Source: A. Distributed Learning Preliminaries · p. 2
  • In synchronous MEL, each global update cycle includes batch and parameter transmission, τ local updates, learner-to-orchestrator responses, and one aggregation after all learners respond.The global cycle clock excludes the global update process itself.Source: A. Distributed Learning Preliminaries · p. 2

B. Transition to MEL

The MEL timing model decomposes each learner's global-cycle workload into wireless transmission, local computation, and response transmission. These components depend on batch size, model size, processor frequency, and heterogeneous channel conditions.

B. Transition to MEL

  • Transmission times depend on the bits in allocated batches and parameter matrices, wireless bandwidth, channel gains, transmit power, and precision settings.The model distinguishes batch-related and constant model-related parameter sizes.Source: B. Transition to MEL · pp. 2–3
  • Each learner receives its batch and global model, performs τ local updates, and returns its updated parameter matrix to the orchestrator.The process repeats after global aggregation and redistribution of a new batch and global model.Source: B. Transition to MEL · p. 3
  • The local computation workload depends on assigned samples and model complexity, with per-iteration computations determined by batch size and C_m.The model also accounts for learner processor frequency.Source: B. Transition to MEL · p. 3
  • The total learner time t_k sums sending, computation, and return processes and must satisfy t_k ≤ T for every learner.For distributed datasets, the initial batch-transfer term is omitted.Source: B. Transition to MEL · p. 3

III. PROBLEM FORMULATION

The paper optimizes batch sizes and local iterations to maximize learning progress within per-learner timing limits. The resulting integer problem has quadratic constraints and is NP-hard, motivating relaxation.

III. PROBLEM FORMULATION

  • The optimization maximizes local iterations τ by selecting integer batch sizes d_k while enforcing t_k ≤ T for every learner.Increasing local iterations is used as the accuracy objective for the MEL cycle.Source: §III · p. 3
  • Because learner time is quadratic in τ and d_k, the formulation is an integer linear program with quadratic and linear constraints.The constraints also enforce total batch size, non-negativity, and integrality.Source: §III · pp. 3–4
  • The ILPQC is NP-hard, so the paper relaxes its integer constraints to obtain a simpler problem.The relaxed problem is non-convex, preventing direct analytical derivation of its optimum.Source: §III · pp. 3–4

A. Problem Relaxation

The integer-constrained allocation problem is relaxed to real variables, yielding a linear program with quadratic constraints that remains non-convex. The paper therefore uses numerical solvers or analytical bounds rather than an exact analytical optimum.

A. Problem Relaxation

  • Relaxing the integer constraints produces a linear program with quadratic constraints over real variables.Source: A. Problem Relaxation · p. 4
  • The same problem type and solution approach apply to both scenarios, with different C1_k expressions for distributed datasets and task parallelization.Source: A. Problem Relaxation · p. 4
  • The relaxed problem remains non-convex because its quadratic-constraint matrices are not positive semi-definite.Source: A. Problem Relaxation · p. 4
  • Because the relaxed problem is non-convex, exact optimal variables cannot be derived analytically, but KKT conditions can provide upper bounds.Source: A. Problem Relaxation · p. 4

B. Upper Bounds using KKT conditions

The paper formulates the relaxed problem’s Lagrangian and applies KKT conditions to derive upper bounds on its optimal variables. In simulations, these bounds were already feasible and directly produced the relaxed optimum for τ.

B. Upper Bounds using KKT conditions

V. SIMULATION RESULTS

The simulation section evaluates UB-Analytical in realistic mobile edge learning environments. Its performance is compared with equal task allocation and an OPTI-based numerical solution to the relaxed problem.

V. SIMULATION RESULTS

  • UB-Analytical is tested in simulated mobile edge learning scenarios representing realistic edge-node environments.Source: §V · p. 4
  • Table I lists the simulation parameters used for the evaluation.Source: Table I · p. 5
  • The evaluation compares UB-Analytical with equal task allocation and the OPTI-based numerical solution to the relaxed problem.Source: §V · p. 5

A. Simulation Environment, Dataset, and Learning Model

The simulations model heterogeneous edge nodes in a 50 m-radius area, combining conventional computing devices with micro-controllers and 802.11-type wireless links.

A. Simulation Environment, Dataset, and Learning Model

B. Number of Local Updates

The adaptive scheme increases feasible local updates under heterogeneous edge settings and reaches target learning accuracy in fewer cycles than equal task allocation, while matching numerical optimization in simulated cases.

VI. CONCLUSION

  • UB-Analytical and OPTI-numerical achieve identical local-update performance across all simulated node counts and global update clocks.The conclusion reports that the analytical solution matched numerical solvers across the simulated MNIST scenarios.Source: B. Number of Local Updates · p. 5, §VI · p. 6

B. Number of Local Updates

  • 6 versus 1 local updates for 20 nodes at T = 30s, a 600% gain over ETA; at K = 10 and T = 60s, adaptive allocation achieves 7 versus 3 updates, a 233% gain.The optimized scheme can also match ETA's accuracy level in half the time or with half the number of nodes.Source: B. Number of Local Updates · p. 5, Figure 1 · p. 5

C. Learning Accuracy

  • At K = 20 and T = 12s, adaptive allocation reaches 96.67% accuracy in 4 cycles versus 7 for ETA, a reduction of about 43%.At K = 10 and T = 30s, it crosses 97% in 5 updates versus 9 for ETA, reducing time by about 56%.Source: Figure 2 · p. 5, C. Learning Accuracy · p. 6

APPENDIX A PROOF OF THEOREM 1

The proof derives batch-allocation relations from KKT conditions, converts their summed form into a rational equation in τ, and identifies a feasible root as an upper bound for the relaxed problem.

APPENDIX A PROOF OF THEOREM 1

  • KKT conditions impose batch-size bounds, with equality for users whose corresponding multiplier λ_k is nonzero.Source: Appendix A · p. 7
  • If the problem is feasible, the allocated batch sizes sum to the total dataset size d; otherwise, the orchestrator must offload the entire task to edge or cloud servers.Source: Appendix A · p. 7
  • Summing the batch-bound equalities yields a partial-fraction expansion that becomes a rational function of τ equal to d.The expanded numerator and denominator have degrees K − 1 and K, respectively.Source: Appendix A · p. 7
  • Solving the resulting polynomial gives a feasible τ*; because the relaxed problem is non-convex, this feasible root constitutes an upper bound on its solution.The poles are −b_k, while τ = −b_k is excluded by the τ ≥ 0 constraint.Source: Appendix A · p. 7

Related papers

Loading 1811.03748v2…