{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:12:29Z","timestamp":1740809549714,"version":"3.38.0"},"reference-count":28,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2025,3,1]]},"DOI":"10.1587\/transinf.2024fcp0006","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T22:12:19Z","timestamp":1720649539000},"page":"221-228","source":"Crossref","is-referenced-by-count":0,"title":["Online Combinatorial Linear Optimization via a Frank-Wolfe-Based Metarounding Algorithm"],"prefix":"10.1587","volume":"E108.D","author":[{"given":"Ryotaro","family":"MITSUBOSHI","sequence":"first","affiliation":[{"name":"Department of Informatics, Kyushu University"},{"name":"RIKEN AIP"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kohei","family":"HATANO","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University"},{"name":"RIKEN AIP"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eiji","family":"TAKIMOTO","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","unstructured":"[2] M.K. Warmuth and D. Kuzmin, \u201cRandomized Online PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension,\u201d Journal of Machine Learning Research, vol.9, pp.2287-2320, 2008."},{"key":"2","unstructured":"[3] A. Gy\u00f6rgy, T. Linder, G. Lugosi, and G. Ottucs\u00e1k, \u201cThe On-Line Shortest Path Problem Under Partial Monitoring,\u201d Journal of Machine Learning Research, vol.8, pp.2369-2403, 2007."},{"key":"3","doi-asserted-by":"publisher","unstructured":"[4] N. Cesa-Bianchi and G. Lugosi, \u201cCombinatorial Bandits,\u201d Journal of Computer and System Sciences, vol.78, no.5, pp.1404-1422, 2012. 10.1016\/j.jcss.2012.01.001","DOI":"10.1016\/j.jcss.2012.01.001"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[5] J.G. Propp and D.B. Wilson, \u201cHow to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph,\u201d Journal of Algorithms, vol.27, no.2, pp.170-217, May 1998. 10.1006\/jagm.1997.0917","DOI":"10.1006\/jagm.1997.0917"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[6] S. Yasutake, K. Hatano, S. Kijima, E. Takimoto, and M. Takeda, \u201cOnline Linear Optimization over Permutations,\u201d Proc. 22nd International Symposium on Algorithms and Computation (ISAAC 2011), vol.7074 of LNCS, pp.534-543, 2011. 10.1007\/978-3-642-25591-5_55","DOI":"10.1007\/978-3-642-25591-5_55"},{"key":"6","unstructured":"[7] S. Yasutake, K. Hatano, E. Takimoto, and M. Takeda, \u201cOnline Rank Aggregation,\u201d NIPS 2011 Workshop on Computational Trade-offs in Statistical Learning (COST), 2011."},{"key":"7","doi-asserted-by":"publisher","unstructured":"[8] S.M. Kakade, A.T. Kalai, and K. Ligett, \u201cPlaying games with approximation algorithms,\u201d SIAM Journal on Computing, vol.39, no.3, pp.1088-1106, 2009. 10.1137\/070701704","DOI":"10.1137\/070701704"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[9] D. Garber, \u201cEfficient Online Linear Optimization with Approximation Algorithms,\u201d Math. Oper. Res., vol.46, no.1, pp.204-220, 2021. 10.1287\/moor.2020.1053","DOI":"10.1287\/moor.2020.1053"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[10] T. Fujita, K. Hatano, and E. Takimoto, \u201cCombinatorial Online Prediction via Metarounding,\u201d Proc. 24th Annual Conference on Algorithmic Learning Theory (ALT 2013), vol.8139 of LNCS, pp.68-82, 2013. 10.1007\/978-3-642-40935-6_6","DOI":"10.1007\/978-3-642-40935-6_6"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[11] R.D. Carr and S.S. Vempala, \u201cRandomized metarounding,\u201d Random Struct. Algorithms, vol.20, no.3, pp.343-352, 2002. 10.1002\/rsa.10033","DOI":"10.1002\/rsa.10033"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[12] A. Srinivasan, \u201cImproved approximations of packing and covering problems,\u201d Proc. Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC \u201995, Association for Computing Machinery, pp.268-276, 1995. 10.1145\/225058.225138","DOI":"10.1145\/225058.225138"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[13] M.X. Goemans and D.P. Williamson, \u201cNew 3\/4-Approximation Algorithms for the Maximum Satisfiability Problem,\u201d SIAM J. Discret. Math., vol.7, no.4, pp.656-666, 1994. 10.1137\/s0895480192243516","DOI":"10.1137\/S0895480192243516"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[14] M. Frank and P. Wolfe, \u201cAn algorithm for quadratic programming,\u201d Naval Research Logistics Quarterly, vol.3, no.1-2, pp.95-110, 1956. 10.1002\/nav.3800030109","DOI":"10.1002\/nav.3800030109"},{"key":"14","unstructured":"[15] M. Jaggi, \u201cRevisiting frank-wolfe: Projection-free sparse convex optimization,\u201d Proc. 30th International Conference on Machine Learning, ICML 2013, vol.28 of JMLR Workshop and Conference Proceedings, pp.427-435, JMLR.org, 2013."},{"key":"15","doi-asserted-by":"crossref","unstructured":"[16] M.K. Warmuth, K.A. Glocer, and S.V.N. Vishwanathan, \u201cEntropy Regularized LPBoost,\u201d Proc. 19th International Conference on Algorithmic Learning Theory (ALT\u201908), vol.5254, pp.256-271, Springer, 2008. 10.1007\/978-3-540-87987-9_23","DOI":"10.1007\/978-3-540-87987-9_23"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[18] S. Shalev-Shwartz and Y. Singer, \u201cOn the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithms,\u201d Mach. Learn., vol.80, no.2-3, pp.141-163, 2010. 10.1007\/s10994-010-5173-z","DOI":"10.1007\/s10994-010-5173-z"},{"key":"17","unstructured":"[19] M.K. Warmuth, K. Glocer, and G. R\u00e4tsch, \u201cBoosting Algorithms for Maximizing the Soft Margin,\u201d Advances in Neural Information Processing Systems 20 (NIPS 2007), pp.1585-1592, 2007."},{"key":"18","doi-asserted-by":"publisher","unstructured":"[20] J.H. Friedman, \u201cGreedy function approximation: A gradient boosting machine.,\u201d The Annals of Statistics, vol.29, no.5, pp.1189-1232, 2001. 10.1214\/aos\/1013203451","DOI":"10.1214\/aos\/1013203451"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[21] T. Chen and C. Guestrin, \u201cXgboost: A scalable tree boosting system,\u201d Proc. 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201916, pp.785-794, Association for Computing Machinery, 2016. 10.1145\/2939672.2939785","DOI":"10.1145\/2939672.2939785"},{"key":"20","unstructured":"[22] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T. Liu, \u201cLightGBM: A Highly Efficient Gradient Boosting Decision Tree,\u201d Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp.3146-3154, 2017."},{"key":"21","doi-asserted-by":"crossref","unstructured":"[23] P. Bartlett, Y. Freund, W.S. Lee, and R.E. Schapire, \u201cBoosting the margin: a new explanation for the effectiveness of voting methods,\u201d The Annals of Statistics, vol.26, no.5, pp.1651-1686, 1998. 10.1214\/aos\/1024691352","DOI":"10.1214\/aos\/1024691352"},{"key":"22","unstructured":"[24] F. Pedregosa, G. N\u00e9giar, A. Askari, and M. Jaggi, \u201cLinearly Convergent Frank-Wolfe without Line-Search,\u201d The 23rd International Conference on Artificial Intelligence and Statistics, (AISTATS 2020), Proc. Machine Learning Research, PMLR, 2020."},{"key":"23","unstructured":"[25] K. Tsuji, K. Tanaka, and S. Pokutta, \u201cPairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding,\u201d International Conference on Machine Learning, (ICML 2022), vol.162 of Proc. Machine Learning Research, 2022."},{"key":"24","doi-asserted-by":"publisher","unstructured":"[26] A. Demiriz, K.P. Bennett, and J. Shawe-Taylor, \u201cLinear Programming Boosting via Column Generation,\u201d Machine Learning, vol.46, no.1-3, pp.225-254, 2002. 10.1023\/a:1012470815092","DOI":"10.1023\/A:1012470815092"},{"key":"25","doi-asserted-by":"crossref","unstructured":"[27] R. Mitsuboshi, K. Hatano, and E. Takimoto, \u201cBoosting as Frank-Wolfe,\u201d CoRR, vol.abs\/2209.10831, 2022. 10.2139\/ssrn.4505391","DOI":"10.2139\/ssrn.4505391"},{"key":"26","unstructured":"[28] M. Zinkevich, \u201cOnline convex programming and generalized infinitesimal gradient ascent,\u201d Machine Learning, Proc. Twentieth International Conference (ICML 2003), Aug. 21-24, 2003, Washington, DC, USA (T. Fawcett and N. Mishra, eds.), pp.928-936, AAAI Press, 2003."},{"key":"27","doi-asserted-by":"crossref","unstructured":"[29] M.K. Warmuth, J. Liao, and G. R\u00e4tsch, \u201cTotally corrective boosting algorithms that maximize the margin,\u201d Proc. 23rd international conference on Machine learning (ICML \u201906), pp.1001-1008, 2006. 10.1145\/1143844.1143970","DOI":"10.1145\/1143844.1143970"},{"key":"28","unstructured":"[30] E. Hazan, \u201cIntroduction to online convex optimization,\u201d CoRR, vol.abs\/1909.05207, 2019. 10.1561\/9781680831719"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E108.D\/3\/E108.D_2024FCP0006\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T03:33:30Z","timestamp":1740800010000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E108.D\/3\/E108.D_2024FCP0006\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2024fcp0006","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"type":"print","value":"0916-8532"},{"type":"electronic","value":"1745-1361"}],"subject":[],"published":{"date-parts":[[2025,3,1]]},"article-number":"2024FCP0006"}}