Multi-task nonconvex optimization with total budget constraint: A distributed algorithm using Monte Carlo estimates

Mengdi Wang, Yunjian Xu, Yuntao Gu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Multi-task optimization is common in machine learning, filtering, communication and network problems. We focus on the nonconvex separable problem where the objective is the sum of N individual utility functions subject to a total budget constraint. By leveraging the Lagrangian dual decomposition, the dual ascent method naturally applies and can be implemented distributively. For stochastic versions of multi-task problems, we propose a simulation-based dual ascent algorithm. According to a classical result from convex geometry, the average-per-task duality gap between the primal and dual problems is bounded by O(1=N). This suggests that the nonconvex multi-task problem is getting "convexified" as the number of tasks increases. As a result, the proposed distributed dual algorithm recovers the optimal solution of the nonconvex problem with very small error.

Original languageEnglish (US)
Title of host publication2014 19th International Conference on Digital Signal Processing, DSP 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages793-796
Number of pages4
ISBN (Electronic)9781479946129
DOIs
StatePublished - Jan 1 2014
Event2014 19th International Conference on Digital Signal Processing, DSP 2014 - Hong Kong, Hong Kong
Duration: Aug 20 2014Aug 23 2014

Publication series

NameInternational Conference on Digital Signal Processing, DSP
Volume2014-January

Other

Other2014 19th International Conference on Digital Signal Processing, DSP 2014
CountryHong Kong
CityHong Kong
Period8/20/148/23/14

All Science Journal Classification (ASJC) codes

  • Signal Processing

Keywords

  • Distributed algorithms
  • Dual decomposition
  • Duality gap
  • Monte Carlo
  • Multi-task learning
  • Nonconvex optimization
  • Simulation

Fingerprint Dive into the research topics of 'Multi-task nonconvex optimization with total budget constraint: A distributed algorithm using Monte Carlo estimates'. Together they form a unique fingerprint.

  • Cite this

    Wang, M., Xu, Y., & Gu, Y. (2014). Multi-task nonconvex optimization with total budget constraint: A distributed algorithm using Monte Carlo estimates. In 2014 19th International Conference on Digital Signal Processing, DSP 2014 (pp. 793-796). [6900773] (International Conference on Digital Signal Processing, DSP; Vol. 2014-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDSP.2014.6900773