pith. sign in

arxiv: 1907.08774 · v1 · pith:SW6WXX5Mnew · submitted 2019-07-20 · 💻 cs.IT · math.IT· math.OC

Optimal Design of Queuing Systems via Compositional Stochastic Programming

Srujan Teja Thomdapu , Ketan Rajawat This is my paper

Pith reviewed 2026-05-24 18:54 UTC · model grok-4.3

classification 💻 cs.IT math.ITmath.OC
keywords queuing systemsstochastic optimizationcompositional gradient descentstochastic programmingiteration complexityconstrained optimizationqueuing design
0
0 comments X

The pith

Queuing design problems reduce to compositional stochastic programs solved by a tracking-based constrained gradient algorithm.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that many queuing system designs, which balance infrastructure costs against quality-of-service metrics, can be expressed as stochastic optimization problems even when arrival and departure processes have completely unknown distributions. These problems take a compositional form in which both the objective and the constraints are nonlinear functions of expectations. A constrained stochastic compositional gradient descent method that maintains a tracking sequence for the inner expectations is introduced to solve the resulting programs. The non-asymptotic convergence rate of the algorithm is characterized explicitly through iteration complexity bounds. Numerical experiments confirm that the method produces feasible designs without requiring the unbiased-gradient assumption of classical stochastic approximation.

Core claim

Many queuing design problems can be formulated as stochastic optimization problems where the objective and constraint are non-linear functions of expectations. A constrained stochastic compositional gradient descent algorithm utilizing a tracking step is proposed whose non-asymptotic performance is characterized via iteration complexity.

What carries the argument

Constrained stochastic compositional gradient descent algorithm that maintains a tracking sequence for the inner expected-value functions.

If this is right

  • Queuing systems can be designed optimally without requiring parametric assumptions on arrival or departure processes.
  • The algorithm supplies explicit non-asymptotic iteration bounds that replace the usual asymptotic convergence statements.
  • Designs remain feasible with respect to quality-of-service and physical constraints even when the exogenous processes are completely unknown.
  • Numerical validation shows that the tracking step enables practical solution of problems previously handled only by simplified models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same compositional structure appears in many resource-allocation tasks outside queuing, suggesting the algorithm could be reused for admission control or power allocation.
  • Because the method works with streaming samples, it could be embedded inside online controllers that continuously adjust queue parameters as traffic statistics drift.
  • The iteration-complexity analysis opens the possibility of deriving sample-complexity results when the tracking step is itself approximated by finite memory.

Load-bearing premise

Queuing design problems with arbitrary unknown exogenous processes can be cast as compositional stochastic programs whose objective and constraints are non-linear functions of expectations.

What would settle it

A concrete queuing design problem whose optimal objective or feasible set cannot be written as a nonlinear function of expectations, or an empirical run in which the algorithm requires far more iterations than the derived complexity bound predicts.

Figures

Figures reproduced from arXiv: 1907.08774 by Ketan Rajawat, Srujan Teja Thomdapu.

Figure 1
Figure 1. Figure 1: System model for Examples 1-4 algorithms do not cater to problems of the form in (P). Nevertheless, such problems are com￾monplace in queuing systems where the delay is generally a non-linear function of expectation with unknown distributions. B. Design of queuing systems In this section, we describe various queuing design examples that adhere to the formulation in (P). As a simple example, consider a firs… view at source ↗
Figure 2
Figure 2. Figure 2: Evolution of the objective function and the constrai [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Evolution of the objective function and the constrai [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Evolution of the objective function of Example 3 (out [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Evolution of the objective function of Example 4 (effe [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: minimum eigenvalue of the Hessian of (72) with K = 5, an [PITH_FULL_IMAGE:figures/full_fig_p031_6.png] view at source ↗
read the original abstract

Well-designed queuing systems form the backbone of modern communications, distributed computing, and content delivery architectures. Designs balancing infrastructure costs and user experience indices require tools from teletraffic theory and operations research. A standard approach to designing such systems involves formulating optimization problems that strive to maximize the pertinent utility functions while adhering to quality-of-service and other physical constraints. In many cases, formulating such problems necessitates making simplistic assumptions on arrival and departure processes to keep the problem simple. This work puts forth a stochastic optimization framework for designing queuing systems where the exogenous processes may have arbitrary and unknown distributions. We show that many such queuing design problems can generally be formulated as stochastic optimization problems where the objective and constraint are non-linear functions of expectations. The compositional structure obviates the use of classical stochastic approximation approaches where the stochastic gradients are often required to be unbiased. To this end, a constrained stochastic compositional gradient descent algorithm is proposed that utilizes a tracking step for the expected value functions. The non-asymptotic performance of the proposed algorithm is characterized via its iteration complexity. Numerical tests allow us to validate the theoretical results and demonstrate the efficacy of the proposed algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that many queuing design problems with arbitrary unknown exogenous processes can be cast as constrained compositional stochastic programs (objective and constraints as nonlinear functions of expectations), proposes a constrained stochastic compositional gradient descent algorithm that uses a tracking step for the inner expectations, derives non-asymptotic iteration complexity bounds for the algorithm, and validates the approach with numerical experiments.

Significance. If the modeling step and the complexity analysis hold under standard smoothness, bounded-variance and Lipschitz assumptions, the work supplies a general-purpose stochastic-optimization tool for queuing design that avoids restrictive distributional assumptions (e.g., Poisson arrivals) while furnishing explicit non-asymptotic guarantees; this would be a useful addition to the teletraffic and stochastic-optimization literature.

minor comments (1)
  1. The abstract supplies no equations, sample complexity expressions, or numerical results; a one-sentence statement of the leading-order complexity bound would help readers gauge the contribution immediately.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review and for recognizing the potential utility of our compositional stochastic programming framework for queuing system design under arbitrary exogenous processes. The report provides a concise summary of the contribution but lists no specific major comments. We therefore have no individual points to rebut or revise at this stage. Should the referee have additional questions or concerns, we are happy to address them in a revised version.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The visible abstract and problem framing formulate queuing design as compositional stochastic programs (objective/constraint as non-linear functions of expectations) and propose a tracking-based constrained SCGD algorithm whose non-asymptotic iteration complexity is characterized under standard smoothness/Lipschitz/bounded-variance assumptions. No equations, derivations, or self-citations are exhibited that reduce any central claim to a tautology, fitted parameter renamed as prediction, or load-bearing self-reference. The modeling step and complexity analysis remain independent of the target result and rely on externally verifiable stochastic-optimization primitives, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; typical stochastic optimization parameters such as step sizes are implied but unspecified.

pith-pipeline@v0.9.0 · 5727 in / 1026 out tokens · 21347 ms · 2026-05-24T18:54:33.575165+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

  1. [1]

    SLA-oriented r esource provisioning for cloud computing: challenges, architecture, and solutions,

    R. Buyya, S. K. Garg, and R. N. Calheiros, “SLA-oriented r esource provisioning for cloud computing: challenges, architecture, and solutions,” in Proc. of the IEEE SC2 , Dec. 2011

    work page 2011

  2. [2]

    Provisioning for large scale cloud computing services,

    Y . Tan, Y . Lu, and C. H. Xia, “Provisioning for large scale cloud computing services,” ACM Sigmetrics Perf. Eval. Review , vol. 40, no. 1, pp. 407–408, 2012

    work page 2012

  3. [3]

    An adaptive learning approach for ef ficient resource provisioning in cloud services,

    Y . Tan and C. H. Xia, “An adaptive learning approach for ef ficient resource provisioning in cloud services,” ACM Sigmetrics Perf. Eval. Review , vol. 42, no. 4, pp. 3–11, 2015

    work page 2015

  4. [4]

    Stidham Jr, Optimal Design of Queueing Systems

    S. Stidham Jr, Optimal Design of Queueing Systems . Chapman and Hall/CRC, 2009

    work page 2009

  5. [5]

    D. P . Bertsekas, R. G. Gallager, and P . Humblet, Data Networks . Prentice-Hall International New Jersey, 1992, vol. 2

    work page 1992

  6. [6]

    Average SNR and ergodic capac ity analysis for opportunistic DF-relaying with outage ove r rayleigh fading channels,

    S. Lee, M. Han, and D. Hong, “Average SNR and ergodic capac ity analysis for opportunistic DF-relaying with outage ove r rayleigh fading channels,” IEEE Trans. Wireless Commun. , vol. 8, no. 6, pp. 2807–2812, 2009

    work page 2009

  7. [7]

    Effective bandwidth in hig h-speed digital networks,

    C.-S. Chang and J. A. Thomas, “Effective bandwidth in hig h-speed digital networks,” IEEE J. Sel. Areas Commun. , vol. 13, no. 6, pp. 1091–1100, 1995

    work page 1995

  8. [8]

    Squeezin g the most out of atm,

    G. L. Choudhury, D. M. Lucantoni, and W. Whitt, “Squeezin g the most out of atm,” IEEE Trans. Commun. , vol. 44, no. 2, pp. 203–217, 1996

    work page 1996

  9. [9]

    Effective capacity: a wireless link mo del for support of quality of service,

    D. Wu and R. Negi, “Effective capacity: a wireless link mo del for support of quality of service,” IEEE Trans. Wireless Commun., vol. 2, no. 4, pp. 630–643, 2003

    work page 2003

  10. [10]

    Capacity with explicit delay guarantees for generic sour ces over correlated rayleigh channel,

    B. Soret, M. C. Aguayo-Torres, and J. T. Entrambasaguas , “Capacity with explicit delay guarantees for generic sour ces over correlated rayleigh channel,” IEEE Trans. Wireless Commun. , vol. 9, no. 6, pp. 1901–1911, 2010

    work page 1901

  11. [11]

    Statistic al guarantee optimization for age of information for the D/G /1 queue,

    J. P . Champati, H. Al-Zubaidy, and J. Gross, “Statistic al guarantee optimization for age of information for the D/G /1 queue,” in Proc. of the IEEE Infocom W orkshops , Apr. 2018, pp. 130–135

    work page 2018

  12. [12]

    Benveniste, M

    A. Benveniste, M. M´ etivier, and P . Priouret, Adaptive Algorithms and Stochastic Approximations . Springer Science & Business Media, 2012, vol. 22

    work page 2012

  13. [13]

    D. P . Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods . Prentice hall Englewood Cliffs, NJ, 1989, vol. 23

    work page 1989

  14. [14]

    V . S. Borkar, Stochastic Approximation: A Dynamical Systems Viewpoint . Cambridge Univ. Press, 2008

    work page 2008

  15. [15]

    Stochastic composition al gradient descent: algorithms for minimizing compositio ns of expected-value functions,

    M. Wang, E. X. Fang, and H. Liu, “Stochastic composition al gradient descent: algorithms for minimizing compositio ns of expected-value functions,” Mathematical Programming, vol. 161, no. 1-2, pp. 419–449, 2017

    work page 2017

  16. [16]

    Finite-sum composition op timization via variance reduced gradient descent,

    X. Lian, M. Wang, and J. Liu, “Finite-sum composition op timization via variance reduced gradient descent,” in Proc. of the Artificial Intel. and Stats. , Apr. 2017, pp. 1159–1167

    work page 2017

  17. [17]

    Accelerating stochastic c omposition optimization,

    M. Wang, J. Liu, and E. Fang, “Accelerating stochastic c omposition optimization,” in Proc. of NIPS , Dec. 2016, pp. 1714–1722

    work page 2016

  18. [18]

    A stochastic compositional gradien t method using markov samples,

    M. Wang and J. Liu, “A stochastic compositional gradien t method using markov samples,” in Proc. of the IEEE WSC , Dec. 2016, pp. 702–713

    work page 2016

  19. [19]

    Multilevel stochastic gradient methods for nested composition optimization,

    S. Yang, M. Wang, and E. X. Fang, “Multilevel stochastic gradient methods for nested composition optimization,” SIAM J. on Optim. , vol. 29, no. 1, pp. 616–659, 2019

    work page 2019

  20. [20]

    Controlling the t he bias-variance tradeoff via coherent risk for robust lear ning with kernels,

    A. Koppel, A. S. Bedi, and K. Rajawat, “Controlling the t he bias-variance tradeoff via coherent risk for robust lear ning with kernels,” in Proc. of the ACC , May 2019

    work page 2019

  21. [21]

    Y . M. Ermoliev and R.-B. Wets, Numerical Techniques for Stochastic Optimization . Springer-V erlag, 1988

    work page 1988

  22. [22]

    Resource allocation for wi reless multiuser OFDM networks,

    X. Wang and G. B. Giannakis, “Resource allocation for wi reless multiuser OFDM networks,” IEEE Trans. Inf. Theory , vol. 57, no. 7, pp. 4359–4372, 2011

    work page 2011

  23. [23]

    Ergodic stochastic optimization algorit hms for wireless communication and networking,

    A. Ribeiro, “Ergodic stochastic optimization algorit hms for wireless communication and networking,” IEEE Trans. Signal Process., vol. 58, no. 12, pp. 6369–6386, 2010

    work page 2010

  24. [24]

    Asynchronous incremental st ochastic dual descent algorithm for network resource alloc ation,

    A. S. Bedi and K. Rajawat, “Asynchronous incremental st ochastic dual descent algorithm for network resource alloc ation,” IEEE Trans. Signal Process. , vol. 66, no. 9, pp. 2229–2244, 2018

    work page 2018

  25. [25]

    Stochastic averaging for constrained optimization with application to online resource allocation,

    T. Chen, A. Mokhtari, X. Wang, A. Ribeiro, and G. B. Giann akis, “Stochastic averaging for constrained optimization with application to online resource allocation,” IEEE Trans. Signal Process. , vol. 65, no. 12, pp. 3078–3093, 2017

    work page 2017

  26. [26]

    Asynchronous sad dle point algorithm for stochastic optimization in heterog eneous networks,

    A. S. Bedi, A. Koppel, and K. Rajawat, “Asynchronous sad dle point algorithm for stochastic optimization in heterog eneous networks,” IEEE Trans. Signal Process. , vol. 67, no. 7, pp. 1742–1757, 2019

    work page 2019

  27. [27]

    Two-scale stochastic control for integrated multipoint communication systems with renewables,

    X. Wang, X. Chen, T. Chen, L. Huang, and G. B. Giannakis, “ Two-scale stochastic control for integrated multipoint communication systems with renewables,” IEEE Trans. Smart Grid , vol. 9, no. 3, pp. 1822–1834, 2016

    work page 2016

  28. [28]

    Learning and management for internet of things: Accounting for adaptivity and scalability,

    T. Chen, S. Barbarossa, X. Wang, G. B. Giannakis, and Z.- L. Zhang, “Learning and management for internet of things: Accounting for adaptivity and scalability,” in Proc. of the IEEE , 2019

    work page 2019

  29. [29]

    Automa ted function placement and online optimization of network functions virtualization,

    X. Chen, W. Ni, I. B. Collings, X. Wang, and S. Xu, “Automa ted function placement and online optimization of network functions virtualization,” IEEE Trans. Commun. , vol. 67, no. 2, pp. 1225–1237, 2018

    work page 2018

  30. [30]

    Stability properties of constrained qu eueing systems and scheduling policies for maximum through put in multihop radio networks,

    L. Tassiulas, “Stability properties of constrained qu eueing systems and scheduling policies for maximum through put in multihop radio networks,” IEEE Trans. Autom. Control , vol. 31, no. 12, 1992

    work page 1992

  31. [31]

    Dynamic server alloca tion to parallel queues with randomly varying connectivity ,

    L. Tassiulas and A. Ephremides, “Dynamic server alloca tion to parallel queues with randomly varying connectivity ,” IEEE Trans. Inf. Theory , vol. 39, no. 2, pp. 466–478, 1993

    work page 1993

  32. [32]

    Stability of queueing networks and scheduling policies,

    P . Kumar and S. P . Meyn, “Stability of queueing networks and scheduling policies,” IEEE Trans. Autom. Control , vol. 40, no. 2, pp. 251–260, 1995

    work page 1995

  33. [33]

    Achieving 100% throughput in an input-queued switch,

    N. McKeown, A. Mekkittikul, V . Anantharam, and J. Walra nd, “Achieving 100% throughput in an input-queued switch,” IEEE Trans. Commun. , vol. 47, no. 8, pp. 1260–1267, 1999

    work page 1999

  34. [34]

    Optimal backpressure rou ting for wireless networks with multi-receiver diversity,

    M. J. Neely and R. Urgaonkar, “Optimal backpressure rou ting for wireless networks with multi-receiver diversity, ” Ad Hoc Networks, vol. 7, no. 5, pp. 862–881, 2009

    work page 2009

  35. [35]

    Low-complexity distr ibuted scheduling algorithms for wireless networks,

    A. Gupta, X. Lin, and R. Srikant, “Low-complexity distr ibuted scheduling algorithms for wireless networks,” IEEE/ACM Trans. Netw., vol. 17, no. 6, pp. 1846–1859, 2009

    work page 2009

  36. [36]

    On combini ng shortest-path and back-pressure routing over multihop w ireless networks,

    L. Ying, S. Shakkottai, A. Reddy, and S. Liu, “On combini ng shortest-path and back-pressure routing over multihop w ireless networks,” IEEE/ACM Trans. Netw. , vol. 19, no. 3, pp. 841–854, 2011

    work page 2011

  37. [37]

    Stochastic first-and zeroth-ord er methods for nonconvex stochastic programming,

    S. Ghadimi and G. Lan, “Stochastic first-and zeroth-ord er methods for nonconvex stochastic programming,” SIAM J. on Optim., vol. 23, no. 4, pp. 2341–2368, 2013

    work page 2013

  38. [38]

    Stochastic gradient descent with b iased but consistent gradient estimators,

    J. Chen and R. Luss, “Stochastic gradient descent with b iased but consistent gradient estimators,” arXiv preprint arXiv:1807.11880, 2018

    work page arXiv 2018

  39. [39]

    Subgradient methods for sad dle-point problems,

    A. Nedi´ c and A. Ozdaglar, “Subgradient methods for sad dle-point problems,” J. of Opt. Theory and Applications. , vol. 142, no. 1, pp. 205–228, 2009

    work page 2009

  40. [40]

    A saddle poin t algorithm for networked online convex optimization,

    A. Koppel, F. Y . Jakubiec, and A. Ribeiro, “A saddle poin t algorithm for networked online convex optimization,” IEEE Trans. Signal Process. , vol. 63, no. 19, pp. 5149–5164, 2015

    work page 2015

  41. [41]

    Beyond consensus and synchrony in decentralized online optimization using saddle point method,

    A. S. Bedi, A. Koppel, and K. Rajawat, “Beyond consensus and synchrony in decentralized online optimization using saddle point method,” in Proc. of the IEEE Asilomar , 2017, pp. 293–297

    work page 2017

  42. [42]

    Geometric programming for communication s ystems,

    M. Chiang, “Geometric programming for communication s ystems,” F ound. and Trends in Comm. and Inf. Theory , vol. 2, no. 1–2, pp. 1–154, 2005

    work page 2005

  43. [43]

    Throughput maximization f or ARQ-like systems in fading channels with coding and queuing delay constraints,

    N. Ahmed and R. G. Baraniuk, “Throughput maximization f or ARQ-like systems in fading channels with coding and queuing delay constraints,” in Proc. of the IEEE Asilomar , vol. 2, Nov. 2004, pp. 1463–1467

    work page 2004