Network Resource Allocation via Stochastic Subgradient Descent: Convergence Rate
Amrit Singh Bedi Ketan Rajawat

	
	
	

	
Network Resource Allocation via Stochastic Subgradient Descent: Convergence Rate	
    Amrit S. Bedi, Student Member, IEEE and Ketan Rajawat, Member, IEEE Manuscript submitted December 30, 2023. This work was supported by the Indo-French Centre for the Promotion of Advanced Research-CEFIPRA. The authors are with the Department of Electrical Engineering, IIT Kanpur, Kanpur (UP), India 208016 (email: ).

    
==================================================================================================================================================================================================================================================================================================================================


		This paper considers a general stochastic resource allocation problem that arises widely in wireless networks, cognitive radio, networks, smart-grid communications, and cross-layer design. The problem formulation involves expectations with respect to a collection of random variables with unknown distributions, representing exogenous quantities such as channel gain, user density, or spectrum occupancy. We consider the constant step-size stochastic dual subgradient descent (SDSD) method that has been widely used for online resource allocation in networks. The problem is solved in dual domain which results in a primal resource allocation subproblem at each time instant. The goal here is to characterize the non-asymptotic behavior of such stochastic resource allocations in an almost sure sense.
		 It is well known that with a step size of ϵ, SDSD converges to an 𝒪(ϵ)-sized neighborhood of the optimum. In practice however, there exists a trade-off between the rate of convergence and the choice of ϵ. This paper establishes a convergence rate result for the SDSD algorithm that precisely characterizes this trade-off. Towards this end, a novel stochastic bound on the gap between the objective function and the optimum is developed. The asymptotic behavior of the stochastic term is characterized in an almost sure sense, thereby generalizing the existing results for the stochastic subgradient methods. For the stochastic resource allocation problem at hand, the result explicates the rate with which the allocated resources become near-optimal. As an application, the power and user-allocation problem in device-to-device networks is formulated and solved using the SDSD algorithm. Further intuition on the rate results is obtained from the verification of the regularity conditions and accompanying simulation results. 
	
		

	
	
		

		Stochastic subgradient, constant step-size, stochastic resource allocation, D2D communication.
	
	

	

§ INTRODUCTION

	Resource allocation is a fundamental problem in economic theory that finds application in the design of wireless communication protocols <cit.>, smart grid systems <cit.>, and scheduling algorithms <cit.>. From an optimization perspective, the goal is to find the optimal allocation variables such as transmit power, bandwidth, operational schedule, or facility locations, so as to maximize the user satisfaction, minimize the cost, and satisfy all system constraints. The stochastic resource allocation problem arises in scenarios where the optimization problem includes random parameters with unknown distributions <cit.>. For such problems, the goal is to find an allocation policy that is feasible and optimal, on average <cit.> or with high probability <cit.>.  Since the policy variable may be infinite dimensional , the problem is more tractable in the dual domain due to finite number of constraints, an aspect exploited by a number of algorithms; see e.g., <cit.> and references therein.
	
	This paper focuses on the so-called online algorithms, where the allocation must occur every time the random parameter is realized and revealed. For each realization, the resource allocation adheres to the operational or “box” constraints, while the overall allocation policy is only asymptotically feasible and optimal. The dual problem may then be solved using the stochastic subgradient descent method, whose asymptotic behavior is well-known <cit.>. Further justification for solving the problem in the dual domain was provided in <cit.>, where it was shown that such stochastic problems have zero duality gap under some mild conditions. The asymptotic feasibility and optimality of the allocated resources via primal averaging was also established in <cit.>. In a similar vein, the relationship between the stochastic and 'averaged' dual iterates for the power and subcarrier allocation problem in OFDM was established in <cit.>. 
	
	In resource allocation problems, it is possible for the environmental variables to change abruptly. This motivates the use of constant step sizes in stochastic algorithms, that obviate the need to restart the iterations whenever such a change occurs <cit.>. With a constant step size of  however, it is well known that the stochastic iterates converge only to an O()-sized neighborhood of the optimum <cit.>. On the other hand, making  arbitrarily small is also impractical, since it results in a slow convergence rate <cit.>. The aforementioned trade-off between the rate of convergence and the asymptotic performance of the constant step-size stochastic dual subgradient descent (SDSD) algorithm is an important aspect that has not been studied explicitly.
	
The goal of this paper is to rigorously characterize the convergence rate of the SDSD algorithm in an almost sure sense. 	
		The key contribution of the paper is the development of stochastic bounds on the iterates produced by SDSD method,
		that explicate the role played by  in ‘forgetting’ the initial conditions, and coming close to the optimum. To this end, the iterations are divided into epochs of duration 1/ϵ, and the optimality gap is analyzed for both fixed and arbitrarily small ϵ. The main result of the paper is that the stochastic component of this gap goes to zero almost surely, either as the number of epochs go to infinity with fixed ϵ > 0, or as ϵ itself goes to zero. The bounds developed here specialize to the known asymptotic results, and are generally applicable to any problem solved via the SDSD method. To the best of our knowledge, these are also the first such convergence rate results for the constant step size SDSD algorithm. Corresponding results for the diminishing step size stochastic subgradient exist, but cannot be readily extended to the present case <cit.>. Likewise, the analysis in <cit.> can be extended to yield rate results that hold on average, but does not yield almost sure bounds. The analysis in the present work makes use of the strong law of large numbers directly, and is completely different from that in <cit.>.
	
	
	
	
	As the second contribution, it is shown that the convergence rate results are readily applicable to the stochastic resource allocation problem of interest here. To further demonstrate the usefulness of the bounds, the paper details a contemporary application that uses mobile caching for improving service via device-to-device (D2D) communication <cit.>. To this end, we consider the D2D edge caching framework where willing users offer data connectivity to highly mobile users experiencing spotty coverage. 
The problem is well-motivated for vehicular users who may download data from other users residing near the highway. 
	 The corresponding resource allocation problem is shown to satisfy the required regularity conditions, thereby demonstrating the flexibility afforded by the SDSD algorithm.
	
	This paper is organized as follows. Sec. <ref> lists some of the related work in this area, providing context to the current work.  Sec. <ref> starts with detailing the D2D edge caching problem and formulates the general network resource allocation problem. Sec. <ref> discusses the various solution methodologies in the literature, including the stochastic subgradient descent (SSD) framework. Sec. <ref> provides the main results of the paper, stating the convergence rate results for both primal and dual problems. Sec. <ref> further develops the D2D examples introduced in Sec. <ref>, and verifies the different conditions required for the convergence results to hold. Simulation results on D2D example are provided in Sec. <ref> and Sec. <ref> concludes the paper.
	
The notation used here is as follows. Boldface letters denote column vectors, for which the inequalities and equalities are defined component-wise. The set of all real numbers is denoted by , and likewise the sets of non-negative reals, positive reals, and K-dimensional real vectors are denoted by _+, _++, and ^K, respectively. Time indices are denoted by the subscripts t and τ. For a vector , []_i denotes its i-th entry,  denotes its ℓ_2 norm, _p denotes its p-th norm, for p ∈_+, and ^T denotes the transposed row vector. The expectation operator is denoted by · and the inner product is denoted by ·,·. Finally, [c]^a_b = min(max{c,b},a) and [c]_+:=[c]_0^∞. 
	

	

 §.§ Related work

	Stochastic approximation algorithms have a long history, going back to the prototypical adaptive filtering algorithms by Robbins and Monro <cit.> and Widrow and Stearns <cit.>, and have been studied extensively in the context of least mean square (LMS) and recursive least-squares (RLS) algorithms <cit.>. Stochastic gradient and subgradient methods have since been applied to neural networks <cit.>, parameter tracking <cit.>, large-scale machine learning <cit.>, and resource allocation problems <cit.>. Convergence of these algorithms is well known for various choices of the step-size parameter <cit.>. Convergence rate of the stochastic subgradient descent algorithm has been established for diminishing step size rules via non-asymptotic analysis <cit.>. However, not much is known about the convergence rate of the constant step-size counterpart, except for the fact that it exhibits linear convergence when far from the optimum, if the objective function is strongly convex <cit.>. The rate analysis presented here fills this gap for a  class of convex problems that satisfy certain regularity conditions; see Sec. <ref>.
	
	The use of dual subgradient algorithms for deterministic resource allocation was first popularized in <cit.>. Recovery of near-optimum allocations via primal averaging was proposed in <cit.>, and the result was extended to stochastic resource allocation problems in <cit.>. The  corresponding convergence rate analysis for primal recovery was provided in <cit.>, which also serves as a starting point for the analysis presented here. Note however that the extension of the rate results to stochastic problems is not trivial, and does not follow immediately from the result in <cit.>. The specific assumptions required to develop the bounds in this paper are inspired from those used in the context of stochastic approximation and averaging <cit.>.
	
	From a broader perspective, the work in this paper is also related to the backpressure algorithm, first proposed in the context of stochastic network optimization <cit.>. As shown in <cit.>, the dual subgradient algorithm when applied to deterministic resource allocation problems, may also be viewed as the so-called drift-plus-penalty algorithm. The analysis in <cit.> however does not translate to convergence rate results for the SDSD algorithm.
	
	The wireless caching framework utilizing D2D communications was first proposed in <cit.>, where the fundamental limits were analyzed. The system model described here builds upon the basic framework of <cit.> by formulating the problem within the resource allocation fabric, and adding some implementation details. The results presented here may also be applied to other stochastic resource allocation formulations, such as those in broadcast power allocation<cit.>,  OFDM <cit.>, beamforming <cit.>, cognitive radio networks <cit.>, network utility maximization <cit.>, demand-response in the smart grid <cit.>, smart grid powerded green communications <cit.> and energy harvesting <cit.>.





§ PROBLEM FORMULATION

This section formulates the general stochastic network resource allocation problem. We begin with detailing a D2D caching example that is used to motivate the general problem.	

	
	

 §.§ Motivation: D2D Mobile Caching

	 The D2D framework enables direct communication between nearby user equipments (UE), enabling greater spectrum utilization, higher energy efficiency, and increased overall throughput. The technology also allows unique solutions to connectivity problems that arise at the network edge or as a result of cellular congestion at overcrowded events. As an example,  the D2D architecture proposed in <cit.> considers caching of popular content on mobile devices with excess storage. The content files are then available for download over a D2D link, allowing users to reach higher data rates, avoid congestion, and overcome coverage issues. By directly involving the smartphone equipped users into the process of content distribution, such an edge-caching solution not only cuts down the hardware provisioning costs but also promises better user experience. 
	 
	 This example builds upon the mobile caching framework proposed in <cit.>. Specifically, the mobile user equipment (MoUE) seeks to download a large file or stream media for a sufficiently long duration, while maintaining a reasonable download rate or quality of experience. Let ℳ = {1, …, M} be the set of mobile caches in the network and at time t, the requested chunk be available at ℳ_t ⊂ℳ unique mobile caches (devices) that are at close proximity to the user. The potential download rate R_i(p_t^i, γ_t^i) depends on the power allocation p_t^i at the i-th mobile cache, as well as on the channel gain γ_t^i of the D2D links. The downloads also incur a cost c_t^i∈_++ per unit of transmit power p_t^i for slot t. The costs could be in form of incentives provided to the mobile caches by the content delivery network (CDN) company, and/or directly charged to the MoUE in form of an “enhanced coverage” fee. At each time t, the MoUE selects a cache i_t to download from, and obtains an average throughput of r over time. Finally, the user satisfaction for the achieved average throughput r is quantified through the concave utility function U(r). Fig. <ref> depicts an example scenario, where a MoUE connects to different UEs in order to download cached data, that would otherwise be available only from the base stations. 
	 
	 
	 
	 The resulting stochastic resource allocation problem is formulated as
	 

	  
	 	
    max_r,{p^i}     U(r) - ∑_i∈ℳ_t c_t^ip_t^i
    s. t.     r≤∑_i∈ℳ_tR_i(p_t^i,γ_t^i)
       {p^i}_i∈ℳ∈,   r_min≤ r ≤ r_max

	 
	 where the expectations are with respect to the random variables _t :=(ℳ_t, {c^i_t}_i∈ℳ_t, {γ^i_t}_i∈ℳ_t). The optimization variables consist of the power allocation function p^i and the rate variable r. The formulation of  (<ref>) follows the classical “utility minus penalty” maximization format common to network resource allocation problems <cit.>. The set of functions  is such that only one out of {p_t^i}_i∈ℳ is non-zero for each t (cf. Sec. <ref>). Consequently, the summations in (<ref>) and (<ref>)  consist of only one term for each t. The set  also specifies the maximum and minimum values of p_t^i for each t. Finally, the constraint in (<ref>) ensures that the power allocated per-time slot is sufficient to satisfy the average rate requirement.
	 
	 The specific form of the rate function depends on the wireless technology used by the users. For instance, under slow fading scenarios, the power allocation and user selection can occur every coherence interval. Since channel state information can be acquired easily, the users may employ adaptive modulation and coding in order to achieve a rate close to the ergodic capacity. Specifically, for the mobile device i, the potential transmission rate is of the form R_i(p_t^i,γ_t^i) : = Wlog_2 (1 + p_t^iγ_t^i/α) where W is the bandwidth of the channel and α includes the effect of noise and interference as well as other impairments, such as the use of finite block length codes and imperfect channel state information at the transmitter.
	 
	 More realistically, under fast fading scenarios, the power allocation must occur over intervals that are significantly longer than the coherence time. In this case, it is more reasonable to consider the average rate over several coherence intervals as R_i(p_t^i,γ_t^i):= Wlog_2(1+p_t^iγ_t^ih_i/α) where h_i is the small-scale fading gain <cit.>. In this case, the power allocation and user selection occur only on the basis of the average channel gain γ_t^i, which changes slowly. It is remarked that the system model considered here allows other forms of the rate function as well. 
	 

	

 §.§ Stochastic Resource Allocation

	This section considers the more general stochastic resource allocation problem where the formulation involves expectations with respect to a collection of q random variables with unknown distributions, denoted by ∈^q. Of particular interest are the problems arising in the context of wireless communications and networks, where  captures the state of the system, and the  formulation takes the form <cit.> 


    (^⋆, ^⋆)    =  f_0() 
    s. t.    (̆) + (̌,_)≥ 0, 
       ∈𝒳, ∈.

The optimization variables in  comprise of the resource allocation variable ∈^d and the policy functions :^q →^p. The objective function f_0: ^d → is a concave function, while the set  𝒳 is compact and convex. The vector-valued constraint function is defined as (̆):=[u_1() ⋯ u_K()]^T, where {u_i():^d →}_i=1^K are concave functions.  In contrast, no such restriction is placed on the vector-valued function :̌^q ×^p →^K and the compact set of functions . The rate analysis in Sec. <ref> however does require the overall problem to satisfy certain regularity properties, such as Slater's constraint qualification and differentiability of the subgradient error; see (A1)-(A4). 

It can be seen that the D2D edge caching problem in (<ref>) is a special case of (<ref>)-(<ref>). Introducing a scalar variable z ∈, it is possible to write (<ref>) equivalently as
	  
	 	
    max_r,{p^i}     U(r) +z  
    
    s. t.      -z-∑_i∈ℳ_t c_t^ip_t^i≥ 0
        -r+∑_i∈ℳ_tR_i(p_t^i,γ_t^i)≥ 0
       {p^i}_i∈ℳ∈,   r_min≤ r ≤ r_max

	   
Comparing (<ref>) with (<ref>)-(<ref>), we see that = [r, z]^T and _t :=(ℳ_t, {c^i_t}_i∈ℳ_t, {γ^i_t}_i∈ℳ_t). Likewise the forms of vector functions $̆ and$̌ can be readily inferred. 
	
Since the distribution of  is also not known in advance, it is generally not possible to solve  in an offline manner. The goal here is to solve  in an online fashion by observing the realizations of the independent identically distributed (i.i.d.) process {_t}_t∈_0, where _0 is the set of non-negative integers. For most problems of interest, such a framework also entails online allocation of resources for each time t. To this end, the class of algorithms considered here will output the sequence of vector pairs {_t, _t} for each t, for the purpose of allocating resources. For the sake of brevity, we will subsequently denote policy function _t:= __t and _t(,_t):=(̆) + (̌_t,__t), so that (<ref>) can equivalently be written as _t(,_t)≥ 0. Here, it is understood that the expectation is with respect to the random vector _t. Having introduced the problem at hand, we detail an example formulation in the context of D2D mobile caching.
	

	

	

§ SOLUTION VIA DUAL DESCENT

	This section details the SDSD algorithm for solving  in an online fashion. To this end, the basic assumptions are first stated (Sec. <ref>), followed by the SDSD algorithm (Sec. <ref>), and a discussion of the known results (Sec. <ref>). 
	

	

 §.§ Basic assumptions

	The following assumptions are commonly utilized by different dual algorithms proposed in the literature. None of these assumptions are too restrictive, and they can be easily verified  for most resource allocation problems of interest. 
	
	
		
  A1.  Non-atomic probability density function:  The random variable _t has a non-atomic probability density function (pdf). 
		
  A2.  Slater's condition:  There exists strictly feasible (,), i.e., (,_t)> 0. 
		
  A3.  Bounded subgradients:  The function (·,·) takes bounded values, i.e., there exists a constant G < ∞ such that  _t(·,·)≤ G for all t∈ℕ_0. 
	
	
	In (A1), for _t to have a non-atomic pdf, it should not have any point masses or delta functions. Note that this requirement is not restrictive for a number of applications arising in wireless communications; see e.g. <cit.>. The Slater's condition is also not restrictive, since a strictly feasible resource allocation can often be found for most real-world problems; see Sec. <ref>, <cit.> for examples. Finally, the bound in (A3) also holds for most resource allocation problems where  the functions (·,·) represent natural quantities such as instantaneous rate (cf. (<ref>)), indicator function for channel outage <cit.>, or household power consumption <cit.>. Having introduced the basic assumptions, we are ready to state the SDSD algorithm. 
	

	

 §.§ The stochastic dual subgradient algorithm

	Towards solving , consider the more tractable dual formulation, which has a finite number of optimization variables. Introducing a dual variable ∈^K_+ corresponding to the constraint (<ref>), the Lagrangian is given by
	

	
    L(,,)= f_0() + ,(,_t)
 
	where the constraints in (<ref>) are kept implicit. The dual function is obtained by maximizing L(,,) subject to (<ref>), that is, 
		

	
    g() = max_∈, ∈L(,,).

	Finally, the dual problem of  is given by
		

	
    𝖣 = min_≥ 0     g().

	In general, since  may be non-convex, it holds that 𝖣≥𝖯. It was shown in <cit.>
	
	however, that under (A1)-(A3), it holds that 𝖯 = 𝖣. The proof utilizes the Lyapunov convexity theorem, and holds even if at least one element of _t has an absolutely continuous cumulative distribution function (cdf) <cit.>. It is remarked that Lyapunov convexity has previously yielded similar results in control theory <cit.>, economics <cit.>, and wireless communications <cit.>. 
	
	The result on zero duality gap legitimizes the dual descent approach, since the dual problem is always convex, and the resultant dual solution can be used for primal recovery. To this end, similar problems in various contexts have been solved via the classical dual descent algorithm <cit.>, wherein the primal updates utilize various sampling techniques.
	
This paper considers the ergodic stochastic optimization (ESO) algorithm proposed in <cit.> for a similar problem[The ESO algorithm is a stochastic dual subgradient descent algorithm applied to a resource allocation problem in <cit.>.]. Applied to , the ESO algorithm starts with an arbitrary _0, and utilizes the following iterations for t ∈ℕ_0,



	
    (_t(),_t())    = _∈, ∈Π_t f_0() + ,(,)
    _t+1   = [ - ϵ(_t(),_t())]_+.


Here, Π_t :={__t∈^p | ∈} is the set of all legitimate values of the vector __t and  denotes all feasible vectors _t(). The ESO algorithm is motivated from the fact that for any ∈^K_+, (_t(),_t()) is a stochastic subgradient of the dual function g(). Consequently, the updates in (<ref>) amount to solving (<ref>) via the SSD algorithm with a constant step-size. The use of a constant step size is motivated from classical short memory adaptive algorithms such as the least mean squares algorithm. As stated earlier, the constant step-size algorithms can even handle abrupt changes in the problem parameters, without being restarted.
	
	This paper considers the projected variant of the SSD algorithm for dual updates. Specifically, the updates in (<ref>) are projected on to a compact set ℒ⊂_+^K, and take the following form
	
    _t+1   = 𝒫_ℒ( - ϵ(_t(),_t()))

	where for any ∈^K, 
	
  
	
    [𝒫_ℒ()]_i =  0     []_i < 0 
    λ_max    []_i > λ_max
    λ_i     0 ≤ []_i ≤λ_max

	for 1≤ i≤ K. In other words, large values of []_i are truncated to λ_max, where λ_max≫_∞. Such a modification is already applicable to any practical implementation of the SSD algorithm, where _t is not allowed to take arbitrarily large values. Since  is not known in advance, a bound on _∞ is derived in Appendix <ref> using (A2). Consequently, the following rule can be used for choosing λ_max in practice: 
	

	
    λ_max≫1/χ(,)(g() - f_0()) ≥(g() - f_0())/G
 
		where ∈^K_+, (, ) is a strictly feasible solution to  (cf. (A2)), G is the subgradient bound (cf. A3) and χ(,) := min_1≤ k≤ K[(,_t)]_k. In general, the quantity χ(,) may be calculated empirically. However, for many problems of interest, a bound on λ_max may arise naturally (cf. Sec. VI). The projected SSD proposed in (<ref>) ensures that the iterates _t stay bounded for all t ∈ℕ_0. The boundedness condition is required for carrying out the rate analysis in Sec. <ref>.
		
	

	

 §.§ Known results

	The asymptotic properties of the SDSD algorithm with constant step-size are well-known <cit.>. Asymptotic convergence results for the ESO algorithm, applied to slightly different resource allocation problem, were established in <cit.>. The results in <cit.> can readily be extended to  solved via projected SDSD, and take following form:
	
		
    lim_t→∞1/t∑_τ=0^t-1_τ(_τ(_τ),_τ(_τ)) ≥ 0	   a. s.
       lim_t→∞ f(_t) ≥𝖯-(ϵG̅^̅2̅/2)    a. s.

	
	where the running average _t is defined as 
	


_t = 1/t∑_τ=0^t-1_τ(_τ)


	and G̅^̅2̅ is the bound on (_t(_t), _t(_t))^2. An important feature of the stochastic algorithm is that the primal updates in (<ref>) can be used for allocating resources in real-time. Further, such allocations will be asymptotically feasible and near-optimal for almost every realization of the random process {_t}_t∈_0. 
	



§ CONVERGENCE RATE RESULTS

This section develops various results regarding the rate of convergence of the SDSD algorithm. In contrast to the asymptotic results in (<ref>), the goal here is to quantify the rate at which the allocations specified by (<ref>) become optimal. Such results are of practical significance to the protocol designers, since they can be used to estimate the number of iterations required for the primal and dual objectives to be near-optimal. In the case of the constant step-size SDSD, the convergence rate also depends on the step-size parameter ϵ. For instance, it is well-known that the choice ϵ→ 0, motivated from the result in (<ref>), leads to slow convergence in all constant step-size (sub-)gradient descent algorithms. The results presented here provide a precise characterization of the trade-off between ϵ and the convergence rate for the SDSD algorithm.
	
As in <cit.>, the results in this section make use of the strong law of large numbers, and thus hold for almost every realization of the i.i.d. process {_t}_t∈_0. It is emphasized that the analysis presented here is quite different from the standard convergence analysis carried out for SSD algorithm and its variants <cit.>. It is also different from the non-asymptotic analysis for the case of diminishing step-size SSD algorithms, that only applies to ensemble averages <cit.>. Furthermore, the rate results presented in <cit.> apply only to the unconstrained stochastic subgradient algorithm, and cannot be extended to constrained problems (cf. ) or to the projected subgradient algorithm (cf. (<ref>)).
	
The results are first developed for the general SSD algorithm (Sec. <ref>), and subsequently specialized to the resource allocation problem at hand (Sec. <ref>). 




 §.§ Convergence rate for the SSD algorithm

This section considers the generic optimization problem 



    ^⋆   = min_∈Λ g()

where Λ⊂^K is a closed, compact, and convex set, and max_∈Λ-^⋆≤Λ_max < ∞. Similar to (<ref>), the optimum function value is denoted by 𝖣 = g(^⋆). Given ∈Λ, let  () ∈∂ g() be a subgradient of g(). Similar to , let ():=__t() for all t∈_0 be the corresponding stochastic subgradients that depend on the i.i.d. process {_t}_t∈_0 and satisfy () = () for any ∈Λ. For instance, in the simplest case, the stochastic gradient could be of the form ()=()+ζ_t, where ζ_t is a zero mean i.i.d. random variable. The optimization problem (<ref>) is solved via the projected SSD algorithm. 

    _t+1   =  - ϵ()

where · denotes the projection operation. The algorithm is initialized with an arbitrary _0 ∈Λ such that B_0:=_0-^⋆ < ∞. Next, we make certain assumptions specific to (<ref>). To this end, define the stochastic error _t():= _t()-(), and observe that for any ∈Λ, the sequence {_t()} is also i.i.d.
	
	 
		
  A3^'.  Bounded subgradients:  There exists constant G < ∞ such that _t()≤ G for all ∈Λ. 
		
  A4.  Continuously differentiable error:  The error function _t() is continuously differentiable on Λ, and the gradient with respect to  satisfies ∇__t() < G_e < ∞. 
	
		
	The requirement for bounded subgradient in (A3^') is analogous to that in (A3) for . Here, (A3^') is stated separately because the problem in (<ref>) is more general than the dual of (<ref>)-(<ref>). In practice, applying the results of this section to (<ref>) entails substituting _t(λ)=_t((),_t(), which makes (A3') the same as (A3). The error function _t() may not always be continuous or differentiable for the problem at hand, and the same must be verified explicitly. It is emphasized that (A4) need only be checked for _t() and not for _t(), which is still allowed to be non-differentiable; see Sec. <ref>.
		
		As an example, consider the class of problems where the convex objective function takes the form g() =ℓ_t() + r(), where ℓ_t() is a twice-differentiable loss function that depends on the `data index' t, and r() is a possibly non-differentiable regularizer. For such problems, the error function becomes _t() = ∇_ℓ_t() -∇_ℓ_t(), which is clearly differentiable. Further, the `loss-plus-regularizer' problem structure is quite general, and includes well-known formulations such as LASSO <cit.> and nuclear norm regularized matrix least squares <cit.>. Specifically, given regressands {y_t} and regressors {_t}, the objective function in the LASSO formulation takes the form ∑_t (y_t -_t,) +_1 and thus adheres to (A4). The first result is regarding the objective function values obtained from (<ref>), and holds for all T.
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		

 
	Under (A1)-(A4) and for T = n/ϵ, the minimum dual function value is bounded as 
	
    min_0≤τ≤ T-1 g (_τ) ≤1/T∑_τ = 0^T-1 g(_τ)    ≤𝖣 + B_0/2n + ϵ G^2/2 + C_T(n,ϵ)

	where the random variable C_T(n,ϵ) holds for ζ > 0, 
	
		
    ϵ^ζ-1/2 C_T(n,ϵ) → 0 a.s. as ϵ→ 0  for fixed n < ∞
       n^1/2-ζ C_T(n,ϵ) → 0  a.s. as  n →∞ for fixed ϵ > 0 . 
       ℙ(C_t(n,ϵ) > ν^ζ-1/2) < Aexp(-ν^2ζ)

	
	where ν :=max{1/ϵ,n} and A < ∞ is a constant that does not depend on n or ϵ. 

		
		
		
















			
			
			
			
		It is remarked that since g(·) is convex, the bound in (<ref>) also holds for g(_t), where _t : = 1/t∑_τ = 0^t-1_τ is the running average of the iterates. Theorem 1 characterizes the manner in which the minimum objective function value approaches 𝖣 for large t. Of the three terms in this optimality gap, the first one depends on the initialization and decays as Ø(1/n). The second term depends on the subgradient bound, and decays linearly with the step-size ϵ. Finally, the third term is random, and decays almost surely as Ø((ϵ/n)^1/2-ζ) for any ζ >0 (cf. (<ref>)). Alternatively, the probability of the third term being non-zero decays exponentially as either n →∞ or ϵ→ 0 (cf. (<ref>)). Indeed, for a given run of (<ref>) with a fixed ϵ, the probability of the third term being non-negligible starts to decrease only beyond n > 1/ϵ or equivalently, T > 1/ϵ^2. 
			
			Further intuition on the convergence rate can be obtained by considering the two cases in  (<ref>). When ϵ > 0 is fixed, it can be seen that the asymptotic results in <cit.> follow directly from Theorem <ref> as n →∞. That is, while the initial condition is “forgotten” for t ≫ 1/ϵ, the optimality gap does not necessarily approach zero, but is eventually bounded by ϵ G^2/2. At the same time, the fluctuations due to the stochastic term subside exponentially fast; see (<ref>). 
			
			On the other extreme, consider the case when n is kept fixed, while the algorithm is run for different values of ϵ. For the scenarios when ϵ is arbitrarily small, the asymptotic optimality gap is clearly negligible. However, for such small step-sizes, the algorithm takes a long time to forget the initial conditions, since the first term decays only as Ø(1/ϵ t). Consequently, for all runs when ϵ is taken to be small, the algorithm will appear to converge slowly. Likewise, the probability of the stochastic term being non-negligible starts to decrease exponentially only for T > 1/ϵ^2 (cf. (<ref>)). It is remarked that such a trade-off also applies to the classical subgradient method <cit.>, and the result in Theorem 1 can be viewed as its stochastic counterpart. It is remarked that the results in <cit.> can be readily obtained by taking expectation on both sides of (<ref>) since we have that C_t(n,ϵ)=0. Observe further that unlike the results in <cit.> that hold on an average, the almost sure results in (<ref>) cannot be specified in terms of problem parameters alone. Indeed, while it holds that C_t(n,) ≤ 2G^2(Λ_max+1), such a bound is not very useful in the present case, as compared to the stronger convergence rate result in (<ref>).
			
Finally, it is remarked that it may be possible to minimize the bound in (<ref>) to the extent possible, by fixing T and choosing a corresponding step size. In the present case, given T, the bound is the smallest when ϵ = 1/√(T) which yields the following result

    min_0≤τ≤ T-1 g (_τ) ≤1/T∑_τ = 0^T-1g(_τ)    ≤𝖣 + 𝒪(1/√(T))  + C_T

where the random variable C_T = 𝒪(T^-1/4) almost surely. The result in Theorem 1 may therefore be seen as the generalization of the results in <cit.> that have also reported an 𝒪(T^-1/2) bound on average but have not analyzed the almost sure behavior. It is emphasized however that in practice, minimizing the bound may not necessarily translate to an improved convergence rate. Moreover, the number of iterations T for which the algorithm runs may not necessarily be known in advance, e.g., in target tracking applications. Instead, it may be simpler to specify a fixed value of ϵ, and continue to run the algorithm till the contribution of the 𝒪(1/n) term becomes tolerably small. 
			 
		Before proceeding with the proof of Theorem <ref>, an intermediate lemma establishing rate results on various time-averages is provided. The proof of Theorem <ref> will subsequently utilize these results by expressing the optimality gap in (<ref>) in terms of these time-averages. 
			
			 
				Let :={t_1, t_2, …, t_} be a set of natural numbers such that t_i ≠ t_j. Then for any T ≥ and , ' ∈Λ, it holds under (A3^')-(A4) that
				
					
    1/T∑_t ∈_t()   ≤ L^1_T()
    1/T∑_t ∈_t() - _t(')   ≤ L^2_T()-'

				
			where, for a given ζ > 0,  the random variables {L^i_T()}_i=1,2 satisfy 
				 
					
    T^1/2-ζL^i_T()    → 0    a.s. as  T →∞
    ℙ(L^i_T() > T^ζ-1/2)    < A_i exp(-T^2ζ)

				
				where the constant A_i < ∞ does not depend on T. 
			
				
				 Observe that the i.i.d. process {_t()}_t ∈ is zero-mean and satisfies
						

						
    _t()≤_t() + ()≤ 2G

						where the last inequality holds from (A4). Therefore, it follows from the strong law of large numbers that for any T ≥, 
					
					1/T∑_t∈_t() →0
					
						almost surely as T →∞. It can also be seen that the same holds for L_T^1() := 1/T∑_t∈_t(). The rate results in (<ref>) hold as consequences of the strong law of large numbers for i.i.d. sequences with bounded moments; see <cit.> for (<ref>). Finally, (<ref>), follows from the Bernstein inequality  applied to i.i.d. zero-mean and bounded random vectors {e_t()} <cit.>.
					
				Denote the j-th entry of _t() by e^j_t() for 1 ≤ j ≤ K. From (A3^')-(A4), we have that e^j_t() is bounded and continuously differentiable on Λ. Consider arbitrary ≠'∈Λ, and observe that since Λ is convex, it holds for any β∈ [0,1] that _β:=β+ (1-β)' ∈Λ. It is now possible to use the mean-value theorem, which guarantees that there exists some β_j ∈ [0,1], such that
				

				
    e^j_t() - e^j_t(') = ⟨∇ e^j_t(_β_j), -' ⟩.

				Here, ∇^j_t(_β_j) is an i.i.d. random variable that is also zero-mean, since for continuously differentiable and bounded functions  (cf. (A4)), we have that ∇^j_t(_β_j) = ∇e^j_t(_β_j) = 0. Taking summation in (<ref>) and stacking the K components, it follows for any T ≥, that
				
    1/T∑_t∈_t() - _t(') = _T(,')(-')

				where the K × K matrix _T(,') is defined as [_T(,')]_jk : = 1/T∑_t∈[∇ e^j_t(_β_j)]_k, where the subscript is used to denote the k-th element of vector ∇ e^j_t(_β_j). Applying the Cauchy-Schwarz inequality to (<ref>), we obtain
			
				1/T∑_t∈_t() - _t(')≤_T(,')-'.
			
				From the strong law of large numbers, we have that [_T(,')]_jk→ 0 almost surely as T →∞ for all 1≤ j,k≤ K. It can be seen that the same also holds for L^2_T():=_T(,'). Finally, the rate results in (<ref>) follow from <cit.>^2 and the Bernstein inequality  applied to i.i.d. zero-mean and bounded random variables {[∇ e_t^j(_β_j)]_k} <cit.>. 
				
				
				The proof of Theorem <ref> follows in two steps: the derivation of the overall form required in (<ref>), presented next; and the analysis of the random term C_t(n,ϵ) deferred to Appendix <ref>.
				
				
			[Proof of Theorem <ref>]
				In order to derive the bound in (<ref>), recall that since g() is convex, we have that,
				

				
    g()    ≤ g() + (), -     t   ∈ℕ_0.

				Letting g_t := g(), it follows from the non-expansive property of · that
				

				
    δ_t+1   := _t+1-^2 =  - μ()-^2 
       ≤- - μ()^2 =  -^2 - 2μ(),- + μ^2()^2 
       ≤δ_t - 2μ(),- + μ^2G^2- 2μ()- (),-
       ≤δ_t - 2μ(g_t-𝖣) -  2μ()-(),-+ μ^2G^2

				where (<ref>) follows from (A3') and (<ref>) follows from (<ref>). Rearranging  (<ref>) yields
				
    2μ(g_t-𝖣) ≤   (δ_t -δ_t+1)  -  2μ()-(),  -+ μ^2G^2

				Taking sum over τ = 0, 1, …, t-1 and noting that B_0=δ_0 and that μ t ≥ n, yields 
				
    1/t∑_τ = 0^t-1g_τ   ≤𝖣+δ_0 -δ_t/2μ t-1/ t∑_τ = 0^t-1_τ(_τ)-(_τ),_τ-+μ G^2/2≤𝖣 +B_0/2n+μ G^2/2+ C_t(n,ϵ)

				where the last inequality follows since δ_t≥ 0 and the stochastic term in (<ref>) is defined as 
				
    C_t(n,ϵ) := 1/ t∑_τ = 0^t-1_τ(_τ)-(_τ),_τ-.

				Since (<ref>) is of the same form as required in (<ref>), it remains to show that C_t(n,ϵ) converges in the sense of (<ref>)-(<ref>). The convergence analysis for C_t(n,ϵ) makes use of the bounds developed in Lemma <ref> and is deferred to Appendix <ref>. 
			
					
				It is remarked that the results in Theorem <ref> can likely be generalized to the case when Λ is not necessarily compact. Such a generalization is likely possible because the strong law of large numbers, as well as the rate results in <cit.> and <cit.>
				
				only require the random process to have bounded moments. Nevertheless, the requirement that _t-≤Λ_max < ∞ is not too restrictive, and greatly simplifies the analysis.
				

					

 §.§ Convergence rate for the SDSD algorithm

					In order to apply the results developed in Sec. <ref> to the dual problem (<ref>), observe that the stochastic subgradient of g() for any ∈^K_+ is given by 
					
    ()    = (_t(),_t()) 
    _t()    := _∈ f_0() + ,(̆)
    _t()    := _∈Π_t,(̌_t,).

					With () as defined in (<ref>), the projected SSD updates take the same form as (<ref>), with Λ_max = 2√(K)λ_max. Further the bound required in (A3^') follows from (A3). Therefore, Theorem <ref> applies as is to the dual objective function under (A3) and (A4). 
					
					For the resource allocation problem however, the behavior of the primal objective function is more important. The subsequent theorem characterizes the primal near-optimality when the running average of {_t(_t)} is used for allocating resources. For the purpose of rate analysis, time is divided into epochs of duration 1/ϵ each, and the result is expressed in terms of ϵ and n.
				
	
 
	Under (A1)-(A4),		and for n/ϵ≤ t < (n+1)/ϵ, the average primal objective function is near optimal in the following sense: 
	
    f_0(_t) ≥1/t∑_τ = 0^t-1f_0(_t) ≥𝖯 - R_0/2n - ϵ G^2/2 - C'_t(n,ϵ)

	where R_0:=_0^2, _t = 1/t∑_τ = 0^t-1_τ, and the random variable C'_t(n,ϵ) is such that for ζ > 0, 
	
		
    ϵ^ζ-1/2C'_t(n,ϵ)→ 0    a.s. as ϵ→ 0  for fixed n < ∞
       n^1/2-ζC'_t(n,ϵ)→ 0     a.s. as  n →∞ for fixed ϵ > 0 
       ℙ(C_t(n,ϵ) > ν^ζ-1/2) < Aexp(-ν^2ζ)

	
	where ν :=max{1/ϵ,n} and A < ∞ is a constant that does not depend on n or ϵ.

						
					The term  C'_t(n,ϵ) in Theorem <ref> is very similar to C_t(n,ϵ) in Theorem <ref>, and therefore decays at the same rate. It follows from Theorem <ref> that the resource allocation yielded by the projected   SDSD algorithm is near optimal since the average primal objective value is close to 𝖯. Similar to (<ref>), the bound in (<ref>) also holds for max_0 ≤τ≤ t-1 f_0(_τ), as well as for f_0(_t). Further, the optimality gap in (<ref>) is also similar to the one in (<ref>), and therefore decays at the same rate. For details, see the discussion after the statement of Theorem <ref>. 
						
					In order to prove Theorem <ref>, the specific form of the bound in (<ref>) is first established. The rest of the proof is much the same as before, and results from Lemma <ref> are again used to derive the bounds on C'_t(n,ϵ) as in the proof of Theorem <ref>.
						
						
					[Proof of Theorem <ref>]
						Recall that the subgradient of g() is given by () = (_t(), _t()), so that g()=f_0(()) + ,(). Since f_0 is concave, the following inequalities hold:
						
    f_0(_t)    ≥1/t∑_τ = 0^t-1 f_0(_τ)= 1/t∑_τ = 0^t-1(f_0(_τ) + _τ,(_τ)) - 1/t∑_τ = 0^t-1_τ,(_τ)
        = 1/t∑_τ = 0^t-1 g(_τ) - 1/t∑_τ = 0^t-1_τ,(_τ)≥ g() - 1/t∑_τ = 0^t-1_τ,(_τ).

						Next, the second term in (<ref>) can be bounded as 
						
    _t+1^2    =  - μ()^2 ≤ - μ()^2 
       ≤^2 - 2μ,()+μ^2()^2 -2μ()-(),
    ⇒ 2μ,()   ≤_t^2 - _t+1^2 + μ^2G^2 -  2μ()-(),

						where, (<ref>) follows from the non-expansiveness property of the projection operator and from the fact that 0∈Λ (_t+1=_t+1-0), and (<ref>) follows from (A3). Taking sum over τ = 0, 1, …, t-1 and dividing by 2ϵ t yields
						
    1/t∑_τ = 0^t-1_τ,(_τ)   ≤_0^2/2μ t-_t+1^2/2μ t  + μ G^2/2 -  1/t∑_τ = 0^t-1_τ(_τ)-(_τ),≤_0/2n + ϵ G^2/2 + C'_t(n,ϵ)

						where, 
						
					C'_t(n,ϵ) := 1/ t∑_τ = 0^t-1_τ(_τ)-(_τ),_τ.
					
						The bound in (<ref>) follows by plugging back (<ref>) into (<ref>). The analysis for C'_t(n,ϵ) is much the same as in the proof of Theorem <ref>. The only difference for this case is that the iterate bound becomes _t≤√(K)λ_max from (<ref>). Consequently, after rearranging various terms in C'_t(n,ϵ) and using the triangle inequality in (<ref>), (<ref>), and (<ref>), all occurrences of Λ_max get replaced with √(K)λ_max. Since this is equivalent to redefining the constant Λ_max appropriately, the required rate results continue to hold. 
					

							

§ APPLICATION TO D2D COMMUNICATIONS

							This section details some implementation aspects of the SDSD algorithm in the context of D2D communication problem considered in this paper under slow and fast fading scenarios. The Assumptions (A1)-(A4) are also verified for the problems at hand so as to ensure that Theorems 1 and 2 hold. 
							
							Before proceeding, the SDSD algorithm for the general form of the D2D problem (<ref>) is detailed. Specifically, the Lagrangian is given by 
							
    L(r,{p^i}_i∈ℳ,λ)=U(r)-   ∑_i∈ℳ_tc_t^i p^i_t+λ∑_i∈ℳ_tR_i(p^i_t,γ^i_t)-r
which yields the following stochastic algorithm. Since the Lagrangian is separable in r and p^i_t, starting with arbitrary λ_0, the primal iterates at time slot t become:
							
    r_t(λ_t)    ∈_r_min≤ r≤ r_max  U(r)-λ_t r
    {p_t^i(λ_t)}_i∈ℳ_t   ∈_{p^i}_i∈ℳ_t∈Π_t∑_i∈ℳ_t[λ_t R_i(p^i,γ^i_t)-c_t^ip^i].

							At the end of each time slot, the dual variable is updated as
							
    λ_t+1=λ_t-ϵ[∑_i∈ℳ_t R_i(p^i_t(λ_t),γ^i_t)-r_t(λ_t)]

							Recall that the set of functions 𝒫 is such that only one user, denoted by 
							

							
    i_t:=max_i∈ℳ_t p^i_t(λ_t),
 is allocated non-zero power at time slot t. Therefore, the dual variable is updated as
			

							
    λ_t+1   =λ_t-ϵ[R_i_t(p^i_t_t(λ_t),γ^i_t_t)-r_t(λ_t)]

							The full algorithm is summarized in Algorithm <ref>. 
							 							
							The rate analysis developed in Sec. <ref> applies to the present problem under the following assumptions.
							
								
  B1.  Continuous random variables:  The random variables _t = (ℳ_t, {c^i_t}_i∈ℳ_t, {γ^i_t}_i∈ℳ_t) are i.i.d., have continuous cdfs, and finite supports, i.e., ℳ_t⊂ℳ, γ_t^i ∈ [γ_min, γ_max], and c^i_t ∈ [c_min , c_max] for each i∈ℳ_t.
								
  B2.  Power constraints: The set 𝒫 := {:^3M→^M |_∈Π_}, where for any _t, we have that Π__t := Π_t={_t∈^M| p_t^j = 0  j ∉ℳ_t, _t_0 = 1, p^i_t_tc_t^i_t∈ [C_min, C_max] },
								where i_t := max_i∈ℳ_t p^i_t and p^i_t = [_t]_i. 
								
  B3.  High SNR:  It is assumed that γ^i_t ≫ 1 for all i∈ℳ_t. 
							
							
							The finite support of the random quantities is again motivated from practical considerations. The set 𝒫 also includes limits on the maximum affordable cost C_max and the minimum operational cost or minimum allowable transaction amount C_min. A maximum power constraint of the form p^i_t ≤ P_max may also be included within 𝒫. However, for the present application, it is assumed that the caches are not energy constrained, so that P_max≫ C_max/c^i_t for all i∈ℳ_t. In other words, the user's cost constraint is much more stringent than the cache's energy constraint. Finally, the high SNR assumption is justified if there are always enough mobile caches available at all slots. In a typical setting, the MoUE may “see” hundreds of advertisements from potential mobile cache servers, but may choose to consider only tens of users with which control messages may be exchanged easily. Next, the discussion for slow and fast fading cases will be carried out.							
							

 §.§ Slow Fading

							Recall that under slow fading, since power allocation occurs every coherence interval, we have for high SNR (cf. (B3)), that R_i(p_t^i(λ_t),γ_t^i) :≈ Wlog_2 (p_t^i(λ_t)γ_t^i/α). The primal iterate in (<ref>) can be found in two steps. First the optimum transmit power for all potential users is determined, i.e., for each i∈ℳ_t, 

							
    p̂_t^i(λ_t)    =_p^i λ_t  Wlog_2 (p^iγ_t^i/α)-c_t^ip^i 
       s. t.     C_min≤ c_t^ip^i≤ C_max
       = [Wλ_t/c_t^i]_C_min/c_t^i^C_max/c_t^i

							The winning user is the one that maximizes the objective function, i.e., 
							
    i_t    =_i∈ℳ_t  [λ_t R_i(p̂^i_t,γ^i_t)-c_t^ip̂^i_t]= _i∈ℳ_tγ^i_t/c^i_t

							where the expression in (<ref>) derived in Appendix <ref>. An implication of (<ref>) is that the random variable i_t is i.i.d. Finally, it holds that p^j_t = p̂^i_t_t(λ_t) for j = i_t and zero otherwise. Similarly,  r_t is calculated as
							
						r_t(λ_t) =[1/λ_t]_r_min^r_max
						
							resulting in the dual update
							
    λ_t+1=λ_t-ϵ[Wlog_2(p^i_t_t(λ_t)γ^i_t_t/α)-r_t(λ_t)].

							
							An additional assumption regarding the parameter values is made in the slow fading case:
							
							B4.   Strict feasibility:  The problem parameters satisfy r_min < max_i log_2(C_maxγ_t^i/c^i_t). 
							
							The strict feasibility condition is required for ensuring the existence of a Slater point. Since it holds that γ_t^i/c^i_t ≥γ_min/c_max, it is possible to satisfy (B4) by keeping r_min sufficiently small and/or if γ_min is sufficiently large. 
							
							Having stated the algorithm and all required assumptions, the following Lemma summarizes the main result of this subsection. 							
							 
								Under (B1)-(B4), the iterates obtained from (<ref>)-(<ref>) adhere to the rate bounds stated in Theorems 1 and 2.
							
							
								For the results in Theorem 1 and 2 to apply, it suffices to verify that assumptions (A1)-(A4) are satisfied under the slow fading case. The random variable _t has a non-atomic pdf since the channel gains γ^i_t have a continuous cdf, thus confirming (A1); see also <cit.>. The Slater's condition is met by choosing r̃ = r_min and p̃^i_t_t = C_max/c_t^i_t where i_t is given in (<ref>) and zero for all j ≠ i_t. For such a choice, it holds from (B4) that r̃ < log_2(p̃^i_t_tγ^i_t_t), which is the required condition for strict feasibility. For a given λ, the subgradient function is given by 
								
    f_t(λ)    = Wlog_2(p^i_t_t(λ)γ^i_t_t/α)-r_t(λ)

								where i_t and p^i_t_t are evaluated as in (<ref>) and (<ref>). A 
								bound on the subgradient (cf. (A3)) may therefore be found as
f_t(λ)≤ Wlog_2(C_maxγ_max/α c_min) + r_max =: G. Next, in order to verify (A4), the expression for the stochastic subgradient error e_t(λ):=f_t(λ)-f_t(λ) is first derived. Recalling that i_t = _i γ^i_t/c^i_t, consider the following three cases, 
								
									
  * When λ < C_min/W, it holds that p^i_t_t = C_min/c^i_t_t, implying that
									
    e_t(λ)    = W log_2(C_minγ^i_t_t/α c^i_t_t) - [1/λ]_r_min^r_max - W log_2(C_minγ^i_t_t/α c^i_t_t) - [1/λ]_r_min^r_max
       = W log_2(γ^i_t_t/c^i_t_t) - W log_2(γ^i_t_t/c^i_t_t).
 where the expectations are with respect to _t. 
									
  * When C_min/W ≤λ≤ C_max/W, it holds that p^i_t_t = Wλγ^i_t_t/c^i_t_t, implying that
									
    e_t(λ)    = W log_2(Wλγ^i_t_t/c^i_t_t) - [1/λ]_r_min^r_max- W log_2(Wλγ^i_t_t/c^i_t_t) - [1/λ]_r_min^r_max
       = W log_2(γ^i_t_t/c^i_t_t) - W log_2(γ^i_t_t/c^i_t_t).
 
									
  * Similarly, when λ > C_max/W, it holds that p^i_t_t = C_max/c^i_t_t, implying that
									
    e_t(λ)    = W log_2(γ^i_t_t/c^i_t_t) - W log_2(γ^i_t_t/c^i_t_t).
 
								
								Therefore, the subgradient error is a zero-mean random variable that does not depend on λ, and is therefore trivially continuously differentiable in λ. 
							
							

							

 §.§ Fast Fading

							In the more realistic fast fading case, the power allocation and downloads occur over several coherence intervals.  Under the high SNR assumption, the rate becomes , R_i(p^i_t,γ^i_t) ≈ Wlog_2(p_t^iγ_t^i/α)+Wψ_i where ψ_i = log_2(h_i) for a given user i <cit.>. As in the slow fading case, the primal iterates are again found in two steps. First, the power allocation for a potential user i is found,
							
    p̂_t^i(λ_t)    = [Wλ_t/c_t^i]_C_min/c_t^i^C_max/c_t^i.

							It is shown in Appendix <ref> that the winning user for the fast fading case can be written as
							
    i_t    = _i∈ℳ_tlog_2(γ^i_t/c^i_t) + ψ_i.

							Finally, since r_t(λ_t) = max{min{1/λ_t, r_max},r_min} as before, the dual update is given by
							
    λ_t+1=λ_t-ϵ[Wlog_2(p^i_t_t(λ_t)γ^i_t_t/α) + Wψ_i_t-r_t(λ_t)].

							In order to apply the rate bounds in Theorems 1 and 2, we again assume (B1)-(B3), and make the following assumption analogous to (B4). 
							
							B5.   Strict feasibility:  The problem parameters satisfy r_min < max_i {log_2(C_maxγ_t^i/c^i_t) + ψ_i}. 
							
							As in the slow fading case, (B5) allows us to obtain a Slater point, as required by (A2). The following Lemma summarizes the result for the fast fading case. 
							
							 
								Under (B1)-(B3) and (B5), the iterates obtained from (<ref>)-(<ref>) adhere to the rate bounds stated in Theorems 1 and 2. 
							
							
								The 
								As in Lemma <ref>, it suffices to verify assumptions (A1)-(A4). The random variable _t has a non-atomic pdf as remarked earlier. Similarly, it can be verified that the Slater point is given by r̃ = r_min and p̃^i_t_t = C_max/c_t^i_t where i_t is as given in (<ref>), and zero for all j ≠ i_t. The subgradient bound required in (A3) now becomes, f_t(λ)≤ Wlog_2(C_maxγ_max/α c_min) + Wψ_max + r_max =: G where ψ_max := max_iψ_i. Finally, in order to verify (A4), we proceed as in the proof of Lemma <ref> and derive an expression for the subgradient error e_t(λ):=f_t(λ)-f_t(λ). Since expression for the allocated power is the same for the two cases, it can be seen that for the fast fading case as well e_t(λ) = W log_2(γ^i_t_t/c^i_t_t) - W log_2(γ^i_t_t/c^i_t_t) where i_t is found as in (<ref>). Since e_t(λ) does not depend on λ, (A4) also holds trivially in the fast fading scenario.  
							
								
								

							

§ NUMERICAL TESTS

							This section describes the numerical tests on the D2D example discussed in Sec. <ref>. The convergence rate of the SDSD algorithm is studied for the fast fading scenario depicted in Fig. 2. For the simulations, we consider M=25 operational UEs. At each time slot, the MoUE receives advertisements from a random subset ℳ_t of 5 to 25 UEs. Without loss of generality, downloading from the i-th UE incurs a cost of c^i_t = i per unit of transmit power. The lower and upper limits for each transaction are set as C_min= 1 and C_max= 25, respectively. The average channel gains γ^i_t are assumed to be Rayleigh distributed with γ_min=0.1 and γ_max=65, and for simplicity, the parameters α, and ψ_i are all set to unity. In order to keep the numbers realistic, we set W=1 MHz. Finally, in order to ensure Slater's condition, we set r_min = 0.2 and r_max = 10. In realistic scenarios, since the optimal rate is expected to be greater than r_min, it follows from the definition of r_t(λ_t) in Sec.V-A  that λ^⋆ > 1/r_min. Therefore it is safe to take  λ_max≫ 1/r_min.
						
							
							



















						
						
					
						







							Fig. <ref> shows the evolution of the utility function calculated using running averages  r̅_t := 1/t∑_τ = 0^t-1 r_τ of the allocated rate with iterations. As expected from Theorem <ref>, the utility function converges to a value that is closer to the optimal when ϵ is small. Similarly, Fig. <ref> shows the evolution of the dual objective function, which again converges to a point closer to the optimal when ϵ is small. Observe from the results that for ϵ = 0.1, the oscillations continue even as number of iterations go to infinity, as implied by Theorem <ref>. These oscillations are allowed due to the presence of an Ø() term on the right-hand side of (17), and are well-documented for the constant step size stochastic subgradient type algorithms <cit.>. 
						
							
							The convergence rate result of Theorem <ref> is further illustrated in Fig. <ref>(a) and Fig. <ref>(b), where the deterministic terms in (<ref>) are not included. The stochastic term C_t(n,ϵ) is calculated from (<ref>) and plotted against both ϵ and n. It can be seen from both plots that C_t(n,ϵ) → 0 as either n →∞ or ϵ→ 0, as claimed in Theorem <ref>. 
							
							

							
Having studied the convergence properties of the SDSD algorithm, we now focus on some of the nuances of the edge-caching formulation in (<ref>). To begin with, the performance of the proposed scheme is compared against that obtained from two naive algorithms: random and opportunistic. The maximum transmit power for the three cases is scaled so as to ensure equal aggregate power consumption. As the name suggests, an MoUE following the random scheme selects an available UE randomly and without paying any attention to the channel or the cost of the UE. The data is transmitted at the maximum power so as to ensure the maximum rate. As evident from Table <ref>, such a scheme is able to obtain a higher download rate but also at a significantly higher cost. In contrast, the opportunistic scheme advocates a parsimonious approach wherein the MoUE always selects an available UE with the lowest cost. Subsequently, the UE transmits with the maximum power but ultimately achieves a lower aggregate download rate, due to suboptimal channel conditions.

Fig. <ref> provides results from the perspective of the UEs and is generated by running the same algorithm for 1000 independent identically distributed MoUEs. In particular, if an MoUE follows the optimal policy determined by (<ref>), the UEs may be interested in knowing a reasonable price value. As expected, it is clear from Fig. <ref>, that the UEs that charge more are selected less often have lower data usage. Consequently, the aggregate revenue of the UEs with the lowest charges is also the highest. More interestingly however, such high-priced UEs have a very high revenue per Mb of data served. The intuition here is that UEs with high costs are only selected when their channel gains are proportionally higher than the others. Therefore, all transmissions to such UEs occur at higher rates and correspondingly lower power. In summary, by operating only under favorable channel conditions, the high-priced UEs extract a greater revenue for every bit that they serve. Note however that the revenue appears to saturate, and increases very slowly for very high prices. 						
										
								
								
									
									
									
						








							


								

§ CONCLUSIONS

							This paper considers a general stochastic resource allocation problem and solved using constant step-size stochastic subgradient descent algorithm in an online manner. A stochastic bound on the gap between the objective function and the optimum is developed and analyzed in an almost sure sense,
							generalizing the existing results. The bounds characterize the precise manner in which the optimality gap behaves for fixed and arbitrarily small step-sizes. The convergence rate analysis is also extended to a class of stochastic resource allocation problems that utilize stochastic dual subgradient descent (SDSD) iterations. Existing results on near-optimality of the primal average objective function are again generalized for convergence rate analysis. As an example, a resource allocation problem is formulated in the context of mobile caching in device-to-device communications, and solved via SDSD. The regularity conditions required for the rate analysis are verified, and numerical tests are provided, further substantiating the convergence rate results. 
							

							

§ A BOUND ON _∞
 
						From (A2), there exists some ∈𝒳 and ∈, such that (, _t) > 0, where recall that _t:=__t for all t∈_0 and the expectation is with respect to _t. Given ∈^K_+, define the sublevel set _:={∈^K_+| g()≤ g()}, and observe that for any ∈_, it holds that
						
    g()    ≥ g()=max_∈, ∈ f_0() + ,(,_t)≥ f_0() + ,(,_t).

						Rearranging the expression in (<ref>), we obtain 
						
    ∑_k=1^K[]_k[(,_t)]_k   ≤ g()-f_0()
    							⇒_∞≤∑_k=1^K[]_k≤g()-f_0()/χ(,)

						where χ(,):=min_1≤ k≤ K[(,_t)]_k. Observe that _={∈^K_+| g() ≤𝖣}, so that it follows from (<ref>) that

						
    _∞≤𝖣-f_0()/χ(,)

						Finally, since g() ≥𝖣 for all ∈^K_+, the bound in (<ref>) can be relaxed to yield (<ref>).
							



§ ASYMPTOTIC PROPERTIES OF C_T
 

In order to study the convergence rate of C_T, the time is divided into epochs of duration 1/ϵ, so that there exists some n≥0 that satisfies n/ϵ≤ T < (n+1)/ϵ. Since n:= ⌊ϵ t ⌋, where ⌊·⌋ denotes the floor operation, is an arbitrary number, such a split allows the value of t to be increased by keeping either n or ϵ fixed, and varying the other. It is therefore possible to separately study the effects of choosing larger n or smaller ϵ values. For instance, if ϵ = 0.1, the time is divided into epochs of duration 10 iterations each. Hence, the zeroth epoch consists of iterations 0 ≤ t ≤ 9,  the first epoch consists of iterations 10 ≤ t < 19, and so on. With such a split, the classical asymptotic analysis for t →∞ is equivalent to fixing ϵ and letting n →∞. Additionally, the proposed split allows us to study the case when n is fixed, but the algorithm is run with different values of ϵ.							
							
								This proof is devoted to the analysis of  C_t(n,ϵ), and relies on rearranging the terms in (<ref>) so that the results in developed in Lemma <ref> can be applied. The proof is divided into two parts, one for each mode of convergence in (<ref>).
								
								Fixed n < ∞ and μ→ 0:
								For this case, C_t(n,ϵ) is split into summands corresponding to each epoch till time t, that is,

								
    C_t(n,ϵ) = 1/μ t∑_m=0^n C^m(μ)   where,     C^m(μ) :=  μ∑_τ = ℓ_m^u_m_τ(_τ)-(_τ),_τ-.

								The limits in the summation are defined as ℓ_m := m/μ and u_m := (m+1)/μ-1 for m < n while u_n:=t-1. Next, define for all ∈Λ and ℓ_m  ≤τ≤ u_m 
								
    z_τ() = μ∑_ι = ℓ_m^τ_ι() - (),-.

								Substituting (<ref>) in (<ref>), we obtain 
								
    C^m(μ) = z_u_m(_u_m+1) - ∑_τ = ℓ_m^u_m(z_τ(_τ+1) - z_τ(_τ)).

								Such a split allows us to use (<ref>) in order to bound the magnitude of each term separately. Specifically, letting _m := {ℓ_m ,ℓ_m+1, …, u_m}, 
								
    z_u_m(_u_m+1)   = μ∑_ι = ℓ_m^u_m_ι(_u_m+1) - (_u_m+1),_u_m+1-
       ≤μ∑_ι = ℓ_m^u_m(_ι(_u_m+1) - (_u_m+1))_u_m+1-≤ L^1_1/μ(_m)Λ_max.

								Similarly, denoting '_τ := {ℓ_m,ℓ_m+1, …, τ} for all ℓ_m ≤τ≤ u_m, it holds from using triangle inequality and (<ref>), that
								
    z_τ(_τ+1)-z_τ(_τ)=ϵ|∑_ι  = ℓ_m^τ_ι(_τ + 1) - (_τ+1),_τ+1--  _ι(_τ) - (_τ),_τ-| 
    								
       ≤ϵ|∑_ι  = ℓ_m^τ⟨_ι(_τ + 1) -(_τ+1) -_ι(_τ) +(_τ), (_τ+1-)⟩|  + μ∑_ι = ℓ_m^τ_ι(_τ) - (_τ),_τ+1 - _τ
       ≤ϵ∑_ι  = ℓ_m^τ_ι(_τ + 1) -(_τ+1) -_ι(_τ)+(_τ)_τ+1-+ϵ∑_ι = ℓ_m^τ(_ι(_τ) - (_τ))_τ+1 - _τ
       ≤(L^2_1/ϵ('_τ)Λ_max + L^1_1/ϵ('_τ))_τ+1-_τ≤ϵ(L^2_1/ϵ('_τ)Λ_max + L^1_1/ϵ('_τ))G

								where the (<ref>) uses the non-expansive property of the projection operator · and the boundedness of the stochastic subgradients (cf. (A3^')). Substituting (<ref>) and (<ref>) into the expression for C^m(ϵ) yields the following bound
								
    C^m(ϵ)   ≤ L^1_1/μ(_m)Λ_max + ϵ G∑_τ = ℓ_m^u_m L^2_1/ϵ('_τ)Λ_max + L^1_1/ϵ('_τ) 
       ≤ L^1_1/μ(_m)Λ_max  + Gsup_ℓ_m ≤τ≤ u_m (L^2_1/ϵ('_τ)Λ_max + L^1_1/ϵ('_τ)) .

								Finally, the bound for C_t(n,ϵ) becomes
								
    C_t(n,ϵ)    ≤1/n∑_m=0^nC^m(ϵ)≤sup_0≤  m ≤ nC^m(ϵ)
       ≤sup_0≤ m ≤ n L^1_1/ϵ(_m)Λ_max+ Gsup_0≤τ < t (L^2_1/ϵ('_τ)Λ_max + L^1_1/ϵ('_τ))
		
								Therefore, the rate result from Lemma <ref> implies that 
								
    ϵ^ζ-1/2C_t(n,ϵ)    ≤Λ_maxsup_0≤ m ≤ nϵ^ζ-1/2L^1_1/ϵ(_m)+ Gsup_0≤τ < t (ϵ^ζ-1/2L^2_1/ϵ('_τ)Λ_max + ϵ^ζ-1/2L^1_1/ϵ('_τ))
	
								which goes to zero almost surely as ϵ→ 0, yielding the bound in (<ref>). Likewise, let A_1m < ∞ be the constant associated with the bounds for Λ_maxL_1/ϵ^1(_m), as necessitated by Lemma <ref>. Then, using the union bound, it follows that
									
    ℙ(sup_0≤ m ≤ n L_1/ϵ^1(_m) > ϵ^1/2-ζ)    ≤∑_m=0^n A_1mexp(-ϵ^-2ζ) ≤ A_1exp(-ϵ^-2ζ)

									where A_1 := ∑_m A_1m. Along the same lines, the result in Lemma <ref> and the subsequent use of the union bound imply that there exist a constant A_2 < ∞ such that the probability of the second term in (<ref>) exceeds ϵ^1/2-ζ is bounded by A_1exp(-ϵ^-2ζ). Combining the two bounds, and again using union bound, we have that 
									
    ℙ(C_t(n,ϵ) > ϵ^1/2-ζ) ≤ A_3exp(-ϵ^-2ζ)
 
									where A_3 = A_1+A_2.
								
								Fixed ϵ > 0 and n →∞:  
								In this case, C_t(n,ϵ) must now be split into two terms as follows,
								
    C_t(n,ϵ)≤ϵC(n) + D(n)/n

								where,
								
								
    C(n)    :=  ∑_τ = ℓ_m^n/μ-1_τ(_τ)-(_τ),_τ-
       = ∑_τ = 0^1/μ-11/n∑_m=0^n-1_m/μ + τ(_m/μ + τ)-(_m/μ+τ),_m/μ+τ-
    D(n)    := μ∑_τ = n/μ^t-1_τ(_τ)-(_τ),_τ-.

								For this analysis, it is assumed without loss of generality that 1/ϵ is an integer. That way, the subscripts m/ϵ+ τ are also integers and the floor operation is not required. Given ϵ, note that D(n) is a sum of a fixed number of bounded random variables, so that D(n)/n → 0 surely as n →∞.
								In order to bound C(n), define for all ∈Λ and 0  ≤τ≤ 1/μ-1, 
								
    z_τ() = ∑_ι = 0^τ1/n∑_m=0^n-1_m/ϵ+τ() - (),-.

								Then, it follows that
								
    C(n) = z_n/μ-1(_n/μ) - ∑_τ = 0^1/μ-1(z_τ(_τ+1) - z_τ(_τ)).

								It is now possible to bound each term in (<ref>) separately. Defining ^τ:={m/μ + τ}_m=0^n-1, and using (<ref>), it follows that
								
    z_n/μ-1(_n/μ)   = ∑_τ = 0^1/μ-11/n∑_m=0^n-1_m/μ+τ(_n/μ) - (_n/μ),_n/μ-
       ≤∑_τ = 0^1/μ-11/n∑_m=0^n-1(_m/μ+τ(_n/μ) - (_n/μ))_n/μ-
       ≤Λ_max∑_τ = 0^1/μ-1L^1_n(^τ).

								Proceeding similarly,
								
    z_τ(_τ+1)-z_τ(_τ)   =∑_ι = 0^τ|1/n∑_m  = 0^n-1_m/μ+ι(_τ + 1) - (_τ+1),_τ+1- -  _m/μ+ι(_τ) - (_τ),_τ-|
       ≤∑_ι = 0^τ||1/n∑_m  = 0^n-1  (_m/μ+ι(_τ + 1) - (_τ+1)  - _m/μ+ι(_τ) + (_τ))||_τ+1-
         +∑_ι = 0^τ1/n∑_m = 0^n-1(_m/μ+ι(_τ) - (_τ))_τ+1 - _τ
       ≤∑_ι = 0^τ(L^2_n(^ι)Λ_max + L^1_n(^ι))_τ+1-_τ
       ≤ϵ G ∑_ι = 0^τ(L^2_n(^ι)Λ_max + L^1_n(^ι)).

								Finally,  substituting (<ref>) and (<ref>) into the expression for C(n), and noting that 1/ϵ is a fixed number, the following bound is obtained
								
    ϵC(n)   ≤Λ_maxϵ∑_τ = 0^1/μ-1L^1_n(^τ) + ϵ^2∑_τ = 0^1/ϵ-1 G ∑_ι = 0^τ(L^2_n(^ι)Λ_max + L^1_n(^ι))

								
    ≤Λ_maxsup_0≤τ < 1/ϵ L^2_n(^τ)+ Gsup_0≤τ < 1/ϵsup_0≤ι≤τ(L^2_n(^ι)Λ_max  + L^1_n(^ι))

								which goes to zero almost surely as n →∞, implying that C_t(n,ϵ) → 0 almost surely as n →∞. Both the rate results can again be inferred as in the previous case. Indeed, similar to (<ref>), given ζ>0, there exist A_4<∞ such that ℙ(C_t(n,ϵ) > n^ζ-1/2) ≤ A_4exp(-n^2ζ). Combining with (<ref>), the probability bounds can be written as
								
    ℙ(C_t(n,ϵ) > ϵ^1/2-ζ) ≤ Aexp(-ϵ^-2ζ)  and  ℙ(C_t(n,ϵ) > n^ζ-1/2) ≤ Aexp(-n^2ζ)

								where A = max{A_3,A_4}. The required result follows by choosing ν = max{1/ϵ,n} in (<ref>).  
							
							
							

							

§ DERIVATION OF (<REF>) AND (<REF>)
 
							Consider first the slow fading case, where the winning user is given by
							

							
    i_t   =_i∈ℳ_tλ_t (Wlog_2(p̂^i_tγ^i_t/α))-c_t^ip̂^i_t

							where p̂^i_t is given by (<ref>). Thus, the objective function in (<ref>) for a given λ can be written as
							
    T^i_t(λ)=λ Wlog_2(C_minγ^i_t/c^i_t)-C_min,    λ≤C_min/W
    λ Wlog_2(C_maxγ^i_t/c^i_t)-C_max,    if λ≥C_max/W
    λ Wlog_2(λ W/αγ^i_t/c^i_t)-λ W,    otherwise.

							Since log_2 is monotonic function, observe in (<ref>) that in all three cases, T^i_t(λ) depends monotonically on γ^i_t/c^i_t for all λ > 0. This allows us to conclude that i_t = _i∈ℳ_t T^i_t(λ)  = _i∈ℳ_tγ^i_t/c^i_t	which is the required identity in (<ref>).							
							Similarly for the fast fading case, the objective function for the winning user in (<ref>) is given by
							
    T^i_t(λ)=λ Wlog_2(C_minγ^i_t/c^i_t) +λ Wψ_i-C_min,    if λ≤C_min/W
    λ Wlog_2(C_maxγ^i_t/c^i_t) + λ Wψ_i-C_max,    if λ≥C_max/W
    λ Wlog_2(λ W/αγ^i_t/c^i_t) + λ Wψ_i-λ W,    otherwise
which, for λ > 0, again depends monotonically on log_2(γ^i_t/c^i_t) + ψ_i. The expression in (<ref>) therefore follows.
							

							IEEEtran 
							
							

















							
						