{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T14:19:02Z","timestamp":1790000342043,"version":"4.0.1"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["AWD1004532"],"award-info":[{"award-number":["AWD1004532"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>In several online prediction problems of recent interest the comparison class is composed of matrices. For example, in the online max-cut problem, the comparison class is matrices which represent cuts of a given graph, and in online gambling the comparison class is matrices which represent permutations over $n$ teams. Another important example is online collaborative filtering, in which a widely used comparison class is the set of matrices with a small trace norm. In this paper we isolate a property of matrices, which we call $(\\beta,\\tau)$-decomposability, and derive an efficient online learning algorithm that enjoys a regret bound of $\\tilde{O}(\\sqrt{\\beta\\,\\tau\\,T})$ for all problems in which the comparison class is composed of $(\\beta,\\tau)$-decomposable matrices. By analyzing the decomposability of cut matrices, low trace-norm matrices, and triangular matrices, we derive near-optimal regret bounds for online max-cut, online collaborative filtering, and online gambling. In particular, this resolves (in the affirmative) an open problem posed by Abernethy [ Proceedings of the 23 rd Annual Conference on Learning Theory (COLT 2010), pp. 318--319] and Kleinberg, Niculescu-Mizil, and Sharma [ Machine Learning, 80 (2010), pp. 245--272]. Finally, we derive lower bounds for the three problems and show that our upper bounds are optimal up to logarithmic factors. In particular, our lower bound for the online collaborative filtering problem resolves another open problem posed by Shamir and Srebro [ Proceedings of the 24 th Annual Conference on Learning Theory (COLT 1011), pp. 661--678].<\/jats:p>","DOI":"10.1137\/120895731","type":"journal-article","created":{"date-parts":[[2017,4,18]],"date-time":"2017-04-18T11:19:27Z","timestamp":1492514367000},"page":"744-773","source":"Crossref","is-referenced-by-count":4,"title":["Near-Optimal Algorithms for Online Matrix Prediction"],"prefix":"10.1137","volume":"46","author":[{"given":"Elad","family":"Hazan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satyen","family":"Kale","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shai","family":"Shalev-Shwartz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,4,18]]},"reference":[{"key":"atypb1","unstructured":"J. Abernethy,\n                      Can we learn to gamble efficiently?\n                      , in Proceedings of the 23rd Annual Conference on Learning Theory (COLT 2010), 2010, pp. 318-319."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Kale,\n                      A combinatorial, primal-dual approach to semidefinite programs\n                      , in Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), 2007, pp. 227-236.","DOI":"10.1145\/1250790.1250823"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi and G. Lugosi,\n                      Prediction, Learning, and Games\n                      , Cambridge University Press, Cambridge, UK, 2006.","DOI":"10.1017\/CBO9780511546921"},{"key":"atypb6","unstructured":"N. Cesa-Bianchi and O. Shamir,\n                      Efficient online learning via randomized rounding\n                      , in Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS), 2011, pp. 343-351."},{"key":"atypb7","unstructured":"F. R. K. Chung,\n                      Spectral Graph Theory\n                      , American Mathematical Society, Providence, RI, 1997."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.137.B1127"},{"key":"atypb9","first-page":"427","volume":"70","author":"Haagerup U.","year":"1982","journal-title":"Stud. Math."},{"key":"atypb10","unstructured":"E. Hazan, S. Kale, and S. Shalev-Shwartz,\n                      Near-optimal algorithms for online matrix prediction\n                      , in Proceedings of the 25th Conference on Learning Theory (COLT 2012), 2012, 38."},{"key":"atypb11","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, Cambridge, UK, 1990."},{"key":"atypb12","first-page":"1865","volume":"13","author":"Kakade S. M.","year":"2012","journal-title":"J. Machine Learning Res."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"V. Kanade and T. Steinke,\n                      Learning hurdles for sleeping experts\n                      , in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), 2012, pp. 11-18.","DOI":"10.1145\/2090236.2090238"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. J. Kearns and U. V. Vazirani,\n                      An Introduction to Computational Learning Theory\n                      , MIT Press, Cambridge, MA, 1994.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5178-7"},{"key":"atypb17","unstructured":"J. Lee, B. Recht, R. Salakhutdinov, N. Srebro, and J. A. Tropp,\n                      Practical large-scale optimization for max-norm regularization\n                      , in Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS), 2010, pp. 1297-1305."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M. A. Nielsen and I. L. Chuang,\n                      Quantum Computation and Quantum Information\n                      , Cambridge University Press, Cambridge, UK, 2011.","DOI":"10.1017\/CBO9780511976667"},{"key":"atypb20","unstructured":"R. Salakhutdinov and N. Srebro,\n                      Collaborative filtering in a non-uniform world: Learning with the weighted trace norm\n                      , in Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS), 2010, pp. 2056-2064."},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Shalev-Shwartz and S. Ben-David,\n                      Understanding Machine Learning\n                      , Cambridge University Press, Cambridge, UK, 2014.","DOI":"10.1017\/CBO9781107298019"},{"key":"atypb22","unstructured":"O. Shamir and S. Shalev-Shwartz,\n                      Collaborative filtering with the trace norm: Learning, bounding, and transducing\n                      , in Proceedings of the 24th Annual Conference on Learning Theory (COLT), 2011, pp. 661-678."},{"key":"atypb23","unstructured":"O. Shamir and N. Srebro,\n                      Sample complexity of trace-norm?\n                      , talk at the 24th Annual Conference on Learning Theory (COLT), 2011."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1063\/1.1704727"},{"key":"atypb25","first-page":"995","volume":"6","author":"Tsuda K.","year":"2006","journal-title":"J. Machine Learning Res."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120895731","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:21:14Z","timestamp":1787340074000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120895731"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/120895731"],"URL":"https:\/\/doi.org\/10.1137\/120895731","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}