PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Optimal Resource Allocations in Wireless Systems

Mark Eisen, Clark Zhang, Luiz F. O. Chamon, Daniel D. Lee, Alejandro Ribeiro

arXiv:1807.08088v3cs.LGcs.NIstat.ML

TL;DR

The paper addresses optimal wireless resource allocation as a functional optimization problem with stochastic constraints and learning-like structure. It uses Lagrangian duality with near-universal DNN parameterizations and a model-free primal-dual training method. The resulting approach achieves bounded suboptimality, precise optimality for arbitrarily large DNNs, and near-optimal performance in simulations.

  • Problem

    Wireless resource allocation involves functional optimization with non-convex stochastic constraints and limited model knowledge, making direct solution challenging.

  • Method

    The paper trains a DNN resource allocation policy in the dual domain using a model-free primal-dual method with sampled gradient estimates.

  • Results

    Near-universal parameterizations yield duality gaps of O(ϵ) for approximation error O(ϵ), while arbitrarily large DNNs achieve precise optimality with respect to the original problem.

  • Takeaways & Limitations

    Lagrangian duality, model-free training, and DNN parameterization provide a practical means of learning wireless resource allocation policies with near-optimality.

Abstract

from arXiv · show

This paper considers the design of optimal resource allocation policies in wireless communication systems which are generically modeled as a functional optimization problem with stochastic constraints. These optimization problems have the structure of a learning problem in which the statistical loss appears as a constraint, motivating the development of learning methodologies to attempt their solution. To handle stochastic constraints, training is undertaken in the dual domain. It is shown that this can be done with small loss of optimality when using near-universal learning parameterizations. In particular, since deep neural networks (DNN) are near-universal their use is advocated and explored. DNNs are trained here with a model-free primal-dual method that simultaneously learns a DNN parametrization of the resource allocation policy and optimizes the primal and dual variables. Numerical simulations demonstrate the strong performance of the proposed approach on a number of common wireless resource allocation problems.

I. INTRODUCTION

Wireless resource allocation is a functional optimization problem over fading states, with stochastic constraints that give it the structure of statistical learning. The paper develops dual-domain, model-free DNN learning methods and shows near-optimality for near-universal parameterizations.

  • Problem setting: Wireless design allocates resources across fading states to optimize long-term system properties rather than instantaneous performance.The formulation covers power allocation, frequency division multiplexing, beamforming, and random access.
  • Problem setting: High dimensionality and unavailable training data make direct or supervised solutions difficult for generic resource allocation problems.The allocation policy is a function over a dense set of channel realizations, while acquiring optimal labeled allocations can be a bottleneck.
  • Learning formulation: Parametrizing the allocation function converts wireless optimization into a learning problem in which statistical loss appears as a constraint.This motivates learning directly from sampled observations without requiring labeled training data.
  • Dual-domain method: Dual-domain training combines constraints into a weighted objective and has a duality gap of O(ϵ) when the parametrization approximates arbitrary functions with error O(ϵ).The result establishes small loss of optimality for near-universal learning representations.
  • Training method: The paper introduces a model-free primal-dual method that estimates gradients by sampling model functions and wireless channels, including policy gradients.Because the problem is non-convex, the method converges to a stationary point of the KKT conditions rather than necessarily the global optimum.
  • DNN approach and evaluation: Deep neural networks are advocated as universal parameterizations, and simulations show near-optimal performance across common wireless resource allocation problems.The proposed approach combines Lagrangian duality, model-free training, and DNN policy parameterization.

II. OPTIMAL RESOURCE ALLOCATION IN WIRELESS COMMUNICATION SYSTEMS

Wireless resource allocation optimizes long-term performance by choosing instantaneous allocations across fading states under ergodic and set constraints. The framework covers power, interference, scheduling, and channel-access decisions.

  • The formulation chooses an instantaneous allocation p(h) to optimize utilities of ergodic performance averages under constraints.The allocation function is bounded and belongs to a feasible set, while the average performance lies in a specified set.
  • The model allows nonconvex instantaneous performance functions and nonconvex allocation sets, reflecting practical wireless systems.Utilities are assumed concave and the average-performance set convex, but the instantaneous mapping and allocation set need not be.
  • Examples: Point-to-point fading channels illustrate the framework through average rate maximization subject to average power constraints.The example uses c(p(h); h) = log(1 + hp(h)), with average rate and average power as ergodic quantities.
  • Examples: Multiple-access interference allocation optimizes long-term terminal rates while enforcing individual average-power constraints.The formulation supports both continuous power allocation and binary terminal activation.
  • Examples: Time-division multiple access adds binary scheduling variables and restricts each fading realization to at most one active terminal.This formulation allocates both transmission power and channel access without an interference term.

A. Learning formulations

Wireless allocation is posed as a learning problem because the policy is functional, channel statistics and system functions may be unknown, and direct optimization is computationally difficult. Parametrization and dual-domain training address these obstacles.

  • Direct optimization is difficult because the allocation variable is a function over fading states and the ergodic constraint is nonconvex.Discretizing n channel dimensions into d values yields md^n allocation variables.
  • A further challenge is that instantaneous performance, objective utilities, and constraint utilities may be unavailable or inaccurate.Uncertain radio-environment measurements can produce discrepancies between predicted and realized performance.
  • Learning introduces a parametrization p(h) = φ(h, θ), replacing functional optimization with optimization over parameters and ergodic variables.The resulting problem has q + u variables but may lose optimality if the parametrization cannot represent suitable policies.
  • Near-universal parameterizations can approximate any feasible allocation function within a stated accuracy; DNNs are highlighted as a universal approximation class.RBFNs and RKHSs are also identified as universal parameterization families.
  • Training over observed channel realizations can bypass estimating the channel distribution and system functions, but constrained learning requires dual-domain operation.The paper introduces a model-free primal-dual method after showing that near-universal parametrizations preserve near-optimality.

III. LAGRANGIAN DUAL PROBLEM

The Lagrangian dual reformulates the parameterized constrained allocation problem as an unconstrained learning objective by penalizing constraint violations. Dual optimization then searches for multipliers minimizing the resulting dual function.

  • The parameterized problem optimizes both allocation parameters θ and ergodic variables x under convex and nonconvex constraints.Nonnegative multipliers λ and µ are introduced for the constraints.
  • The Lagrangian combines objective and constraint values as averages weighted by their respective multipliers.The dual function maximizes this Lagrangian over x ∈ X and θ ∈ Θ.
  • The Lagrangian acts as a penalized version of the primal problem, replacing explicit constraint enforcement with violation penalties.The resulting optimization is unconstrained apart from the set restrictions on θ and x, making it analogous to conventional learning objectives.
  • For nonnegative multipliers, the dual function upper-bounds the parameterized primal optimum, motivating minimization over the multipliers.The paper separately addresses the duality gap and the method for finding optimal multipliers.

A. Suboptimality of the dual problem

Although the parameterized problem is nonconvex, near-universal parameterizations yield a dual value close to the original primal optimum under explicit regularity assumptions. The gap scales with approximation error and problem sensitivity.

  • The original unparameterized problem has zero duality gap, whereas the parameterized problem requires bounding the duality/parametrization gap.The relevant difference is between D*φ and P* for the original problem.
  • Theorem 1 establishes bounds on the parameterized dual value when φ is ϵ-universal and Assumptions 1–4 hold.The assumptions include nonatomic fading distributions, Slater feasibility, monotone objective utility, and an expectation-wise Lipschitz performance function.
  • The bound becomes more favorable when constraints have sufficient slack and more sensitive when constraints are difficult to satisfy.Small slack can increase the bound through the associated feasibility terms.
  • Near-universal parametrizations make the dual value no worse than an O(ϵ) bias relative to the original primal optimum.These bounds justify using the parametrized dual function as a proxy for the unparameterized allocation problem.
  • The duality gap satisfies a bound involving the approximation error ϵ, Lipschitz constant L, and optimal multiplier norm ∥λ*∥_1.The approximation error is translated into performance-function error through L, while the multiplier norm captures sensitivity to perturbations.

B. Primal-Dual learning

The paper uses primal-dual optimization to train resource-allocation policies by updating primal and dual variables of the Lagrangian. Direct implementation requires explicit knowledge of system functions and the channel distribution.

  • B. Primal-Dual learning: The primal-dual method jointly updates primal variables θ and x and dual variables λ and µ toward stationary KKT points.Primal updates ascend the Lagrangian, while dual updates descend and project onto the positive orthant.
  • B. Primal-Dual learning: Direct gradient updates require knowledge of g0, g, f, and the wireless channel distribution m(h).The paper treats this model-based method as a baseline for developing a model-free alternative.

IV. MODEL-FREE LEARNING

The model-free approach replaces unavailable analytic gradients with measurements and stochastic gradient estimates, enabling primal-dual updates without explicit system or channel models. Its non-convex optimization has local convergence guarantees, while practical refinements remain future work.

  • IV. MODEL-FREE LEARNING: The algorithm estimates gradients from observed function values using finite differences and random perturbations.Finite-difference estimators use sampled channel states and can be averaged over batches.
  • IV. MODEL-FREE LEARNING: Finite differences can be computationally burdensome for large parameter dimensions and may require repeated observations at an unchanged channel state.Rapidly changing channel states can make the required repeated observations impractical.
  • IV. MODEL-FREE LEARNING: Policy gradients provide an alternative estimator that samples resource allocations rather than high-dimensional parameters when q ≫ m.This approach requires that the policy-density gradient be evaluable.
  • IV. MODEL-FREE LEARNING: The model-free updates replace function and gradient evaluations with observations and estimated gradients, updating both primal and dual variables without explicit model knowledge.Algorithm 1 samples states and perturbations, observes function values, computes estimates, and updates the iterates.
  • IV. MODEL-FREE LEARNING: Because the Lagrangian is non-convex, stochastic primal-dual descent converges only to a local optimum and is not guaranteed to achieve D∗.The paper evaluates practical performance through numerical simulations instead.
  • IV. MODEL-FREE LEARNING: More sophisticated techniques, including entropy regularization, actor-critic methods, and model-based initialization, are left for future work.These techniques are identified as possible improvements but are not explored in detail.

V. DEEP NEURAL NETWORKS

The paper specializes its near-universal parametrization framework to DNNs, describing their architecture and training within constrained primal-dual optimization. Increasing network size supports arbitrarily accurate approximation, while finite-size networks are characterized by approximation-dependent bounds.

  • V. DEEP NEURAL NETWORKS: DNNs are studied as near-universal parameterizations for resource-allocation policies because their function-approximation richness grows with network depth and layer sizes.The theoretical framework considers non-constant continuous activation functions and varying layer dimensions.
  • V. DEEP NEURAL NETWORKS: A fully connected DNN passes inputs through linear layer transformations followed by point-wise activation functions.The illustrated example contains one hidden layer and an output layer.
  • V. DEEP NEURAL NETWORKS: Learning the DNN policy reduces to learning its layer weight functions W1, . . . , WL and computing the policy φ(h, θ).Backpropagation evaluates the required derivatives through the network layers.
  • V. DEEP NEURAL NETWORKS: Unlike supervised DNN training, the method backpropagates through the policy constraint and interleaves parameter updates with primal and dual updates.This avoids requiring a labeled training set of optimal resource allocations.
  • V. DEEP NEURAL NETWORKS: As DNN dimension grows, arbitrarily small function-approximation error yields a null duality gap under the stated assumptions.The result follows from universal function approximation, but arbitrarily large networks may be impractical.

VI. SIMULATION RESULTS

Simulations apply the proposed primal-dual learning method with truncated-Gaussian DNN policies to AWGN and interference-channel resource allocation. In the simple capacity problem, learned policies are feasible and achieve near-optimal performance, while larger networks reduce suboptimality.

  • Simulation setup: The simulations use stochastic truncated-Gaussian policies, REINFORCE-style policy gradients, and primal-dual updates for learning DNN resource-allocation parametrizations.The policy outputs means and standard deviations, while primal and dual variables are updated using batch size 32, exponentially decaying dual steps, and ADAM for DNN parameters.
  • A. Simple AWGN channel: The simple AWGN problem allocates power among dedicated user channels under a total expected power budget to maximize weighted aggregate throughput.Each user’s capacity is modeled as log(1 + SNR_i), with SNR_i = h_ip_i(h_i)/v_i and nonnegative user weights.
  • A. Simple AWGN channel: For m = 20 users and pmax = 20, the DNN primal-dual method converges to roughly the exact solution’s total capacity and satisfies the constraint.The constraint value converges to 0, implying feasibility of the learned policy.
  • Training considerations: Training may require more iterations than the unparameterized solution because the DNN has many parameters and learning is model-free.The paper notes that training is generally performed offline and that prior weights can provide a warm start when model parameters change.
  • A. Simple AWGN channel: The DNN and exact policies can differ in shape or resource assignment while achieving similar overall performance.Across eight representative users, one policy may assign no resources where the other does, yet the achieved performance matches the exact solution.
  • Interference channel: For the interference-channel problem, all channel states are supplied to one MIMO DNN with hidden layers of size 32 and 16.The network outputs means and standard deviations for the users’ truncated-Gaussian policy distributions.
  • A. Simple AWGN channel: Across user counts, fixed-size DNNs achieve the same optimality, while increasing hidden-layer size improves the suboptimality obtained.Figure 5 compares networks with hidden layers of sizes 4 and 2 versus 32 and 16 over 10 randomly initialized simulations, plotting means with one-standard-deviation error bars.

B. Interference channel

The paper applies DNN-based primal-dual learning to challenging interference-channel resource allocation problems with coupled, non-convex capacity constraints. Across experiments, the learned policies are feasible and closely match or outperform model-free heuristics, while truncated Gaussian outputs outperform Gamma outputs.

  • Problem formulation: Coupled resource policies make interference-channel capacity optimization challenging because the capacity function is non-convex and cannot be minimized exactly by existing dual approaches.The DNN primal-dual approach is therefore compared with standard model-free heuristics rather than an analytic optimum.
  • DNN parameterization: The MIMO DNN receives all channel conditions and outputs truncated Gaussian policy-distribution parameters for every user.The architecture uses hidden layers of sizes 32 and 16 to represent power allocations coupled across users.
  • Interference capacity problem (34): For m = 20 users, the DNN policy achieves close performance to WMMSE, outperforms other model-free heuristics, and converges to a feasible solution.Figure 7 reports convergence for both the objective function value and constraint value.
  • Output distributions: The truncated Gaussian output distribution produces stronger performance than the Gamma distribution in the power-allocation problem.The comparison motivates truncated Gaussian outputs because their mean and variance are easier to interpret and learn.
  • Interference capacity problem (35): For m = 5 users, the DNN policy is feasible and almost matches WMMSE in achieved sum-capacity without access to the capacity model.The experiment compares the proposed method with heuristic WMMSE and equal power allocation.

APPENDIX A PROOF OF THEOREM 1

The appendix proves the approximation and optimality bounds underlying the proposed parameterized optimization. It combines null duality gap, perturbation, norm, and continuity arguments under stated regularity assumptions.

  • Suboptimality analysis: The appendix uses the optimal dual value of the original problem to connect the derived inequalities to the suboptimality analysis of D*.The dual value relationship is invoked explicitly when establishing the upper bound.
  • Strong duality: Under Assumptions 1 and 2, the original functional optimization problem has a null duality gap, so P* = D*.This strong-duality result is the foundation for the subsequent bounds.
  • Upper bound: Because the parameterized policy class is a subset of the feasible policy class, its dual objective can be bounded using any solution of the original problem.The proof substitutes the original optimum into the parameterized dual formulation.
  • Lower bound: The lower bound is obtained by constructing an Lε-perturbed version of the original problem and applying a perturbation inequality.The argument uses Hölder’s inequality and continuity to control the perturbation terms.
  • Constraint qualification: Slater’s condition supplies a strictly feasible point, yielding positive slack that enters the bound on the dual variables.The proof selects feasible x′ and p′ with strict inequality in the utility and expectation constraints.

APPENDIX B PROOF OF THEOREM 2

The appendix establishes that sufficiently large DNN classes are universal in probability and therefore satisfy the paper’s ε-universality condition. This supports approximation of measurable resource-allocation policies within the stated assumptions.

  • Universal approximation: A sufficiently large DNN with non-constant continuous activations is dense in probability in the set of measurable functions.For every measurable target policy and positive tolerance, an appropriate network size and parameter vector exist.
  • ε-universality: The full class of DNN parameterizations is ε-universal for every ε > 0.This follows by applying the measurable-function approximation theorem to the paper’s universality definition.
  • Approximation bound: The approximation proof bounds the expected sup-norm error by splitting the channel-state domain into well-approximated and poorly approximated regions.The poorly approximated region is controlled through its probability measure and bounded feasible policies.
  • Approximation bound: The boundedness of feasible policies yields the bound 2Γϵ′ on the contribution from the poorly approximated region.Here Γ is the supremum norm bound over feasible policies and channel states.
  • Implication for optimality: ε-universality makes the dual-value bound hold for all ε > 0, after which continuity arguments complete the connection to optimality.The argument additionally requires a finite Lipschitz constant and addresses boundedness of the optimal dual multipliers.
Loading 1807.08088v3…