This paper proves an impossibility result for stochastic
network utility maximization for multiuser wireless systems,
including multiaccess and broadcast systems. Every time slot an
access point observes the current channel states and opportunistically
selects a vector of transmission rates. Channel state vectors
are assumed to be independent and identically distributed with
an unknown probability distribution. The goal is to learn to make
decisions over time that maximize a concave utility function of
the running time average transmission rate of each user. Recently
it was shown that a stochastic FrankWolfe algorithm converges
to utilityoptimality with an error of O(log(T)/T ), where T is
the time the algorithm has been running. An existing
O(1/T ) converse is known. The current paper improves the converse
to O(log(T)/T), which matches the known achievability result.
The proof uses a reduction from the opportunistic scheduling
problem to a Bernoulli estimation problem. Along the way, it
refines a result on Bernoulli estimation.
more »
« less
This content will become publicly available on October 13, 2024
Network utility maximization with unknown utility functions: A distributed, datadriven bilevel optimization approach
Fair resource allocation is one of the most important topics in communication networks. Existing solutions almost exclusively assume each user utility function is known and concave. This paper seeks to answer the following question: how to allocate resources when utility functions are unknown, even to the users? This answer has become increasingly important in the nextgeneration AIaware communication networks where the user utilities are complex and their closedforms are hard to obtain. In this paper, we provide a new solution using a distributed and datadriven bilevel optimization approach, where the lower level is a distributed network utility maximization (NUM) algorithm with concave surrogate utility functions, and the upper level is a datadriven learning algorithm to find the best surrogate utility functions that maximize the sum of true network utility. The proposed algorithm learns from data samples (utility values or gradient values) to autotune the surrogate utility functions to maximize the true network utility, so works for unknown utility functions. For the general network, we establish the nonasymptotic convergence rate of the proposed algorithm with nonconcave utility functions. The simulations validate our theoretical results and demonstrate the great effectiveness of the proposed method in a realworld network.
more »
« less
 Award ID(s):
 2326592
 NSFPAR ID:
 10505577
 Publisher / Repository:
 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
 Date Published:
 Format(s):
 Medium: X
 Location:
 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
 Sponsoring Org:
 National Science Foundation
More Like this


Learning network topology from partial knowledge of its connectivity is an important objective in practical scenarios of communication networks and socialmedia networks. Representing such networks as connected graphs, exploring and recovering connectivity information between network nodes can help visualize the network topology and improve network utility. This work considers the use of simple hop distance measurement obtained from a fraction of anchor/source nodes to reconstruct the node connectivity relationship for large scale networks of unknown connection topology. Our proposed approach consists of two steps. We first develop a treebased search strategy to determine constraints on unknown network edges based on the hop count measurements. We then derive the logical distance between nodes based on principal component analysis (PCA) of the measurement matrix and propose a binary hypothesis test for each unknown edge. The proposed algorithm can effectively improve both the accuracy of connectivity detection and the successful delivery rate in data routing applications.more » « less

null (Ed.)Modern Public Safety Networks (PSNs) are assisted by Unmanned Aerial Vehicles (UAVs) to provide a resilient communication paradigm during catastrophic events. In this context, we propose a distributed usercentric riskaware resource management framework in UAVassisted PSNs supported by both a static UAV and a mobile UAV. The mobile UAV is entitled to a larger portion of the available spectrum due to its capability and flexibility to reposition itself, and therefore establish better communication channel conditions to the users, compared to the static UAV. However, the potential overexploitation of the mobile UAVbased communication by the users may lead to the mobile UAV’s failure to serve the users due to the increased levels of interference, consequently introducing risk in the user decisions. To capture this uncertainty, we follow the principles of Prospect Theory and design a user’s prospecttheoretic utility function that reflects user’s riskaware behavior regarding its transmission power investment to the static and/or mobile UAVbased communication option. A noncooperative game among the users is formulated, where each user determines its power investment strategy to the two available communication choices in order to maximize its expected prospecttheoretic utility. The existence and uniqueness of a Pure Nash Equilibrium (PNE) is proven and the convergence of the users’ strategies to it is shown. An iterative distributed and lowcomplexity algorithm is introduced to determine the PNE. The performance of the proposed usercentric riskaware resource management framework in terms of users’ achievable data rate and spectrum utilization, is achieved via modeling and simulation. Furthermore, its superiority and benefits are demonstrated, by comparing its performance against other existing approaches with regards to UAV selection and spectrum utilization.more » « less

This paper considers the fundamental convergence time for opportunistic scheduling over timevarying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within ε of optimality, for any desired ε > 0, with convergence and adaptation times of O(1/ε^2). This paper shows that if the utility function is concave and smooth, then O(log(1/ε)/ε) convergence time is possible via an existing stochastic variation on the FrankWolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/ε), provided the algorithm has no a priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic FrankWolfe with a fixed step size yields improved O(1/ε^2) adaptation time, but convergence time increases to O(1/ε^2), similar to existing driftpluspenalty based algorithms. This raises important open questions regarding optimal adaptation.more » « less

This paper considers the fundamental convergence time for opportunistic scheduling over timevarying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within ε of optimality, for any desired ε > 0, with convergence and adaptation times of O(1/ε^2). This paper shows that if the utility function is concave and smooth, then O(log(1/ε)/ε) convergence time is possible via an existing stochastic variation on the FrankWolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/ε), provided the algorithm has no a priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic FrankWolfe with a fixed step size yields improved O(1/ε^2) adaptation time, but convergence time increases to O(1/ε^2), similar to existing driftpluspenalty based algorithms. This raises important open questions regarding optimal adaptation.more » « less