TY - GEN
T1 - Online resource allocation with structured diversification
AU - Johnson, Nicholas
AU - Banerjee, Arindam
N1 - Funding 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.
Publisher Copyright:
Copyright © SIAM.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84961876886&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961876886&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974010.67
DO - 10.1137/1.9781611974010.67
M3 - Conference contribution
AN - SCOPUS:84961876886
T3 - SIAM International Conference on Data Mining 2015, SDM 2015
SP - 595
EP - 603
BT - SIAM International Conference on Data Mining 2015, SDM 2015
A2 - Venkatasubramanian, Suresh
A2 - Ye, Jieping
PB - Society for Industrial and Applied Mathematics Publications
T2 - SIAM International Conference on Data Mining 2015, SDM 2015
Y2 - 30 April 2015 through 2 May 2015
ER -