Fast Gradient-Free Optimization in Distributed Multi-User MIMO Systems

Olivier Bilenne, Panayotis Mertikopoulos, Elena Veronica BelmegaarXiv 2020 · arXiv · OpenReview

Abstract

In this paper, we develop a gradient-free optimization methodology for efficient resource allocation in Gaussian MIMO multiple access channels. Our approach combines two main ingredients: (i) an entropic semidefinite optimization based on matrix exponential learning (MXL); and (ii) a one-shot gradient estimator which achieves low variance through the reuse of past information. This novel algorithm, which we call gradient-free MXL algorithm with callbacks (MXL0$^{+}$), retains the convergence speed of gradient-based methods while requiring minimal feedback per iteration—a single scalar. In more detail, in a MIMO multiple access channel with $K$ users and $M$ transmit antennas per user, the MXL0$^{+}$ algorithm achieves $\epsilon$-optimality within $\text{poly}(K,M)/\epsilon^2$ iterations (on average and with high probability), even when implemented in a fully distributed, asynchronous manner. For cross-validation, we also perform a series of numerical experiments in medium- to large-scale MIMO networks under realistic channel conditions. Throughout our experiments, the performance of MXL0$^{+}$ matches—and sometimes exceeds—that of gradient-based MXL methods, all the while operating with a vastly reduced communication overhead. In view of these findings, the MXL0$^{+}$ algorithm appears to be uniquely suited for distributed massive MIMO systems where gradient calculations can become prohibitively expensive.

The Challenge: Overhead in Massive MIMO

In multi-user MIMO (Multiple-Input Multiple-Output) systems, transmitters must optimize their signal covariance matrices to maximize throughput. Traditional approaches like Iterative Water-Filling (IWF) or Weighted MMSE require "full matrix feedback." This means every user needs perfect knowledge of their channel matrices and the aggregate interference at the receiver.

As we move toward "Massive MIMO" (hundreds of antennas), this requirement becomes a bottleneck. Transmitting dense $N \times N$ matrices back to users consumes massive bandwidth and is highly sensitive to noise and asynchronicity. The fundamental challenge addressed here is: Can we optimize these complex systems using only "zeroth-order" feedback—a simple scalar representing the achieved throughput—without sacrificing convergence speed?

Comparison of resource allocation algorithms highlighting feedback requirements and convergence speeds.

Methodology: From MXL to MXL0+

The proposed solution is built on Matrix Exponential Learning (MXL), a mirror-descent-like framework that ensures transmit power constraints are met without costly projections. The authors introduce three iterations of the algorithm to bridge the gap between blind and full-information methods:

  1. MXL0 (The Baseline): Uses a standard SPSA (Simultaneous Perturbation Stochastic Approximation) gradient estimator. It perturbs the signal in a random direction and measures the resulting throughput. However, this suffers from high variance and a slow convergence rate of $O(1/\epsilon^4)$.
  2. MXL0+ (The Innovation): This version introduces a "callback" mechanism. By subtracting the throughput from the previous iteration from the current measurement, the variance of the SPSA estimator is significantly reduced. This allows MXL0+ to achieve a convergence rate of $O(1/\epsilon^2)$, matching first-order gradient-based methods while maintaining scalar feedback.
  3. AMXL0+: An asynchronous version designed for fully distributed systems where users update their settings at different rates.
The MXL0+ algorithm routine, showcasing the variance-reducing callback mechanism in step 4.

Key Insights and Results

Variance Reduction via Callbacks

The "aha moment" of this research is that the error in a one-shot gradient estimator is dominated by the magnitude of the function itself. By using the previous throughput as a baseline (the "callback"), the estimator focuses only on the change in throughput, which is much less noisy. This theoretical breakthrough allows for the communication efficiency of zeroth-order methods (1 scalar vs. $N^2$ matrix elements) without the usual performance penalty.

Scale-Free Behavior and Efficiency

The convergence rate of MXL0+ does not depend on the number of receive antennas ($N$). This makes it "scale-free" and uniquely suited for massive MIMO where $N$ is very large. Furthermore, because the SPSA estimator is sparse, MXL0+ actually has a lower per-iteration computational cost than Water-Filling methods as the number of antennas grows, as it avoids frequent large-scale matrix inversions.

Numerical Performance

In simulations using the COST 2100 Channel Model (60 users, 128 receive antennas), MXL0+ demonstrated remarkable efficiency:

  • Convergence Speed: MXL0+ closed the optimality gap significantly faster than the standard MXL0, reaching thresholds in fewer than 100 iterations that required $10^5$ iterations for the baseline.
  • Robustness: Unlike Water-Filling methods, which can collapse under "pilot contamination," MXL0+ remained stable because it relies on realized throughput rather than estimated channel states.
  • Overhead Reduction: For a 128-antenna system, traditional MXL requires ~65 KB of feedback per frame. MXL0+ reduces this to a single 16-bit scalar.

Conclusion

MXL0+ represents a significant step forward for distributed resource allocation. By bridging the gap between zeroth-order and first-order optimization, it provides a robust, low-overhead solution for the massive MIMO systems of the future. While currently optimized for concave sum-rate functions, future work may extend this "callback" methodology to non-convex interference channels and broader energy efficiency maximization problems.

Summary updated

Abstract

In this paper, we develop a gradient-free optimization methodology for efficient resource allocation in Gaussian MIMO multiple access channels. Our approach combines two main ingredients: (i) an entropic semidefinite optimization based on matrix exponential learning (MXL); and (ii) a one-shot gradient estimator which achieves low variance through the reuse of past information. This novel algorithm, which we call gradient-free MXL algorithm with callbacks (MXL0$^{+}$), retains the convergence speed of gradient-based methods while requiring minimal feedback per iteration$-$a single scalar. In more detail, in a MIMO multiple access channel with $K$ users and $M$ transmit antennas per user, the MXL0$^{+}$ algorithm achieves $\epsilon$-optimality within $\text{poly}(K,M)/\epsilon^2$ iterations (on average and with high probability), even when implemented in a fully distributed, asynchronous manner. For cross-validation, we also perform a series of numerical experiments in medium- to large-scale MIMO networks under realistic channel conditions. Throughout our experiments, the performance of MXL0$^{+}$ matches$-$and sometimes exceeds$-$that of gradient-based MXL methods, all the while operating with a vastly reduced communication overhead. In view of these findings, the MXL0$^{+}$ algorithm appears to be uniquely suited for distributed massive MIMO systems where gradient calculations can become prohibitively expensive.
BibTeX
@misc{bilenne2020fast,
  author = {Olivier Bilenne and Panayotis Mertikopoulos and Elena Veronica Belmega},
  title = {{Fast Gradient-Free Optimization in Distributed Multi-User MIMO Systems}},
  year = {2020},
  eprint = {2006.05445},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.05445},
}
Figure