A variety of modern data analysis problems, ranging from finance to job scheduling, can be considered as online resource allocation (ORA) problems. A key consideration in such ORA problems is some notion of risk, and suitable ways to alleviate risk. In several settings, the risk is structured so that groups of assets, such as stocks, are exposed to similar risks. In this paper, we present a formulation for online resource allocation with structured diversification (ORASD) as a constrained online convex optimization problem. The key novel component of our formulation is a constraint on the L(∞1) group norm of the resource allocation vector, which ensures that no single group gets a large share of the resource and, unlike L(1, p)norms used for overlapping group Lasso, does not impose sparsity structures over groups. We instantiate the problem in the context of portfolio selection, propose an efficient ADMM algorithm, and illustrate the effectiveness of the formulation through extensive experiments on two benchmark datasets.
|Original language||English (US)|
|Title of host publication||SIAM International Conference on Data Mining 2015, SDM 2015|
|Editors||Suresh Venkatasubramanian, Jieping Ye|
|Publisher||Society for Industrial and Applied Mathematics Publications|
|Number of pages||9|
|State||Published - 2015|
|Event||SIAM International Conference on Data Mining 2015, SDM 2015 - Vancouver, Canada|
Duration: Apr 30 2015 → May 2 2015
|Name||SIAM International Conference on Data Mining 2015, SDM 2015|
|Other||SIAM International Conference on Data Mining 2015, SDM 2015|
|Period||4/30/15 → 5/2/15|
Bibliographical noteFunding Information:
Acknowledgements: The research was supported in part by NSF grants IIS-1447566, IIS-1422557, CCF-1451986, CNS-1314560, IIS-0953274, IIS-1029711, and by NASA grant NNX12AQ39A. AB also acknowledges support from IBM and Yahoo. The authors would also like to thank Maria Gini for her helpful feedback.