publication . Preprint . Article . 2017

Learn-and-Adapt Stochastic Dual Gradients for Network Resource Allocation

Tianyi Chen; Qing Ling; Georgios B. Giannakis;
Open Access English
  • Published: 05 Mar 2017
Abstract
Network resource allocation shows revived popularity in the era of data deluge and information explosion. Existing stochastic optimization approaches fall short in attaining a desirable cost-delay tradeoff. Recognizing the central role of Lagrange multipliers in a network resource allocation, a novel learn-and-adapt stochastic dual gradient (LA-SDG) method is developed in this paper to learn the sample-optimal Lagrange multiplier from historical data, and accordingly adapt the upcoming resource allocation strategy. Remarkably, an LA-SDG method only requires just an extra sample (gradient) evaluation relative to the celebrated stochastic dual gradient method. LA-...
Persistent Identifiers
Subjects
free text keywords: Computer Science - Systems and Control, Computer Science - Distributed, Parallel, and Cluster Computing, Control and Systems Engineering, Signal Processing, Computer Networks and Communications, Control and Optimization, Resource allocation, Computer science, Stochastic optimization, Information explosion, Stochastic approximation, Cloud computing, business.industry, business, Lagrange multiplier, symbols.namesake, symbols, Resource management, Mathematical optimization, Gradient method
Related Organizations
33 references, page 1 of 3

[1] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Automat. Contr., vol. 37, no. 12, pp. 1936-1948, Dec. 1992.

[2] S. H. Low and D. E. Lapsley, “Optimization flow control-I: basic algorithm and convergence,” IEEE/ACM Trans. Networking, vol. 7, no. 6, pp. 861-874, Dec. 1999.

[3] L. Georgiadis, M. Neely, and L. Tassiulas, “Resource allocation and crosslayer control in wireless networks,” Found. and Trends in Networking, vol. 1, pp. 1-144, 2006.

[4] M. J. Neely, “Stochastic network optimization with application to communication and queueing systems,” Synthesis Lectures on Communication Networks, vol. 3, no. 1, pp. 1-211, 2010.

[5] T. Chen, X. Wang, and G. B. Giannakis, “Cooling-aware energy and workload management in data centers via stochastic optimization,” IEEE J. Sel. Topics Signal Process., vol. 10, no. 2, pp. 402-415, Mar. 2016.

[6] T. Chen, Y. Zhang, X. Wang, and G. B. Giannakis, “Robust workload and energy management for sustainable data centers,” IEEE J. Sel. Areas Commun., vol. 34, no. 3, pp. 651-664, Mar. 2016.

[7] J. Gregoire, X. Qian, E. Frazzoli, A. de La Fortelle, and T. Wongpiromsarn, “Capacity-aware backpressure traffic signal control,” IEEE Trans. Control of Network Systems, vol. 2, no. 2, pp. 164-173, June 2015.

[8] S. Sun, M. Dong, and B. Liang, “Distributed real-time power balancing in renewable-integrated power grids with storage and flexible loads,” IEEE Trans. Smart Grid, 2016, to appear.

[9] A. Beck, A. Nedic, A. Ozdaglar, and M. Teboulle, “An O(1=k) gradient method for network resource allocation problems,” IEEE Trans. Control of Network Systems, vol. 1, no. 1, pp. 64-73, Mar. 2014.

[10] J. Liu, A. Eryilmaz, N. B. Shroff, and E. S. Bentley, “Heavy-ball: A new approach to tame delay and convergence in wireless network optimization,” in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2016.

[11] E. Wei, A. Ozdaglar, and A. Jadbabaie, “A distributed Newton method for network utility maximization-I: Algorithm,” IEEE Trans. Automat. Contr., vol. 58, no. 9, pp. 2162-2175, Sep. 2013. [OpenAIRE]

[12] M. Zargham, A. Ribeiro, and A. Jadbabaie, “Accelerated backpressure algorithm,” arXiv preprint:1302.1475, Feb. 2013. [OpenAIRE]

[13] K. Yuan, B. Ying, and A. H. Sayed, “On the influence of momentum acceleration on online learning,” arXiv preprint:1603.04136, Mar. 2016.

[14] L. Huang and M. J. Neely, “Delay reduction via Lagrange multipliers in stochastic network optimization,” IEEE Trans. Automat. Contr., vol. 56, no. 4, pp. 842-857, Apr. 2011.

[15] L. Huang, X. Liu, and X. Hao, “The power of online learning in stochastic network optimization,” in Proc. ACM SIGMETRICS, vol. 42, no. 1, New York, NY, Jun. 2014, pp. 153-165.

33 references, page 1 of 3
Abstract
Network resource allocation shows revived popularity in the era of data deluge and information explosion. Existing stochastic optimization approaches fall short in attaining a desirable cost-delay tradeoff. Recognizing the central role of Lagrange multipliers in a network resource allocation, a novel learn-and-adapt stochastic dual gradient (LA-SDG) method is developed in this paper to learn the sample-optimal Lagrange multiplier from historical data, and accordingly adapt the upcoming resource allocation strategy. Remarkably, an LA-SDG method only requires just an extra sample (gradient) evaluation relative to the celebrated stochastic dual gradient method. LA-...
Persistent Identifiers
Subjects
free text keywords: Computer Science - Systems and Control, Computer Science - Distributed, Parallel, and Cluster Computing, Control and Systems Engineering, Signal Processing, Computer Networks and Communications, Control and Optimization, Resource allocation, Computer science, Stochastic optimization, Information explosion, Stochastic approximation, Cloud computing, business.industry, business, Lagrange multiplier, symbols.namesake, symbols, Resource management, Mathematical optimization, Gradient method
Related Organizations
33 references, page 1 of 3

[1] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Automat. Contr., vol. 37, no. 12, pp. 1936-1948, Dec. 1992.

[2] S. H. Low and D. E. Lapsley, “Optimization flow control-I: basic algorithm and convergence,” IEEE/ACM Trans. Networking, vol. 7, no. 6, pp. 861-874, Dec. 1999.

[3] L. Georgiadis, M. Neely, and L. Tassiulas, “Resource allocation and crosslayer control in wireless networks,” Found. and Trends in Networking, vol. 1, pp. 1-144, 2006.

[4] M. J. Neely, “Stochastic network optimization with application to communication and queueing systems,” Synthesis Lectures on Communication Networks, vol. 3, no. 1, pp. 1-211, 2010.

[5] T. Chen, X. Wang, and G. B. Giannakis, “Cooling-aware energy and workload management in data centers via stochastic optimization,” IEEE J. Sel. Topics Signal Process., vol. 10, no. 2, pp. 402-415, Mar. 2016.

[6] T. Chen, Y. Zhang, X. Wang, and G. B. Giannakis, “Robust workload and energy management for sustainable data centers,” IEEE J. Sel. Areas Commun., vol. 34, no. 3, pp. 651-664, Mar. 2016.

[7] J. Gregoire, X. Qian, E. Frazzoli, A. de La Fortelle, and T. Wongpiromsarn, “Capacity-aware backpressure traffic signal control,” IEEE Trans. Control of Network Systems, vol. 2, no. 2, pp. 164-173, June 2015.

[8] S. Sun, M. Dong, and B. Liang, “Distributed real-time power balancing in renewable-integrated power grids with storage and flexible loads,” IEEE Trans. Smart Grid, 2016, to appear.

[9] A. Beck, A. Nedic, A. Ozdaglar, and M. Teboulle, “An O(1=k) gradient method for network resource allocation problems,” IEEE Trans. Control of Network Systems, vol. 1, no. 1, pp. 64-73, Mar. 2014.

[10] J. Liu, A. Eryilmaz, N. B. Shroff, and E. S. Bentley, “Heavy-ball: A new approach to tame delay and convergence in wireless network optimization,” in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2016.

[11] E. Wei, A. Ozdaglar, and A. Jadbabaie, “A distributed Newton method for network utility maximization-I: Algorithm,” IEEE Trans. Automat. Contr., vol. 58, no. 9, pp. 2162-2175, Sep. 2013. [OpenAIRE]

[12] M. Zargham, A. Ribeiro, and A. Jadbabaie, “Accelerated backpressure algorithm,” arXiv preprint:1302.1475, Feb. 2013. [OpenAIRE]

[13] K. Yuan, B. Ying, and A. H. Sayed, “On the influence of momentum acceleration on online learning,” arXiv preprint:1603.04136, Mar. 2016.

[14] L. Huang and M. J. Neely, “Delay reduction via Lagrange multipliers in stochastic network optimization,” IEEE Trans. Automat. Contr., vol. 56, no. 4, pp. 842-857, Apr. 2011.

[15] L. Huang, X. Liu, and X. Hao, “The power of online learning in stochastic network optimization,” in Proc. ACM SIGMETRICS, vol. 42, no. 1, New York, NY, Jun. 2014, pp. 153-165.

33 references, page 1 of 3
Any information missing or wrong?Report an Issue