{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,4]],"date-time":"2025-10-04T12:25:26Z","timestamp":1759580726853,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T00:00:00Z","timestamp":1528848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2018,6,13]]},"abstract":"<jats:p>In many online learning paradigms, convexity plays a central role in the derivation and analysis of online learning algorithms. The results, however, fail to be extended to the non-convex settings, while non-convexity is necessitated by a large number of recent applications. The Online Non-Convex Learning (\u00f8nco) problem generalizes the classic Online Convex Optimization (\u00f8co) framework by relaxing the convexity assumption on the cost function (to a Lipschitz continuous function) and the decision set. The state-of-the-art result for the \u00f8nco demonstrates that the classic online exponential weighting algorithm attains a sublinear regret of $O(\\sqrtT\u0142og T )$. The regret lower bound for the \u00f8co, however, is $\u00d8mega(\\sqrtT )$, and to the best of our knowledge, there is no result in the context of the \u00f8nco problem achieving the same bound. This paper proposes the Online Recursive Weighting (\\rw) algorithm with regret of $O(\\sqrtT )$, matching the tight regret lower bound for the \u00f8co problem, and fills the regret gap between the state-of-the-art results in the online convex and non-convex optimization problems.<\/jats:p>","DOI":"10.1145\/3224420","type":"journal-article","created":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T18:21:15Z","timestamp":1528914075000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["An Optimal Algorithm for Online Non-Convex Learning"],"prefix":"10.1145","volume":"2","author":[{"given":"Lin","family":"Yang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}]},{"given":"Lei","family":"Deng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}]},{"given":"Mohammad H.","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"Johns Hopkins University, Baltimore, USA"}]},{"given":"Cheng","family":"Tan","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong , Hong Kong"}]},{"given":"Wing Shing","family":"Wong","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong , Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"263","volume-title":"COLT","author":"Abernethy J.","year":"2008"},{"key":"e_1_2_1_2_1","first-page":"28","volume-title":"COLT","author":"Agarwal A.","year":"2010"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012992237273"},{"key":"e_1_2_1_4_1","article-title":"Distributed online convex optimization on time-varying directed graphs","author":"Akbari M.","year":"2015","journal-title":"IEEE Transactions on Control of Network Systems"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"D. Ardia K. Boudt P. Carl K. M. Mullen and B. Peterson. Differential evolution (deoptim) for non-convex portfolio optimization. 2010.  D. Ardia K. Boudt P. Carl K. M. Mullen and B. Peterson. Differential evolution (deoptim) for non-convex portfolio optimization. 2010.","DOI":"10.32614\/RJ-2011-005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.016"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258179"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745852"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9965.1991.tb00002.x"},{"key":"e_1_2_1_11_1","first-page":"2926","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Dekel O.","year":"2015"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.109"},{"key":"e_1_2_1_13_1","first-page":"385","volume-title":"Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA)","author":"Flaxman A.","year":"2005"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646943.712093"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961200"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010844028087"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2009.02.037"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_2_1_19_1","unstructured":"E. Hazan and S. Kale. Online submodular minimization. Journal of Machine Learning Research 13(Oct):2903--2922 2012.   E. Hazan and S. Kale. Online submodular minimization. Journal of Machine Learning Research 13(Oct):2903--2922 2012."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670328"},{"key":"e_1_2_1_21_1","first-page":"784","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Hazan E.","year":"2014"},{"key":"e_1_2_1_22_1","unstructured":"E. Hazan and Y. Li. An optimal algorithm for bandit convex optimization. arXiv preprint arXiv:1603.04350.  E. Hazan and Y. Li. An optimal algorithm for bandit convex optimization. arXiv preprint arXiv:1603.04350."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2525928"},{"key":"e_1_2_1_24_1","first-page":"761","volume-title":"Advances in neural information processing systems","author":"Jain P.","year":"2009"},{"key":"e_1_2_1_25_1","unstructured":"A. Kalai and S. Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research 3(Nov):423-- 440 2002.   A. Kalai and S. Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research 3(Nov):423-- 440 2002."},{"key":"e_1_2_1_26_1","first-page":"287","volume-title":"Advances in neural information processing systems (NIPS)","author":"Kivinen J.","year":"1998"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873669"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374475"},{"key":"e_1_2_1_29_1","unstructured":"R. Kleinberg A. Slivkins and E. Upfal. Bandits and experts in metric spaces. arXiv preprint arXiv:1312.1277 2013.  R. Kleinberg A. Slivkins and E. Upfal. Bandits and experts in metric spaces. arXiv preprint arXiv:1312.1277 2013."},{"key":"e_1_2_1_30_1","first-page":"697","volume-title":"Advances in Neural Information Processing Systems","author":"Kleinberg R. D.","year":"2005"},{"key":"e_1_2_1_31_1","first-page":"824","volume-title":"the 32nd International Conference on Machine Learning (ICML-15)","author":"Krichene W.","year":"2015"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.21314\/JOR.2002.057"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2650563"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154490"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888305.1888326"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007697429651"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.20"},{"key":"e_1_2_1_39_1","first-page":"449","volume-title":"Proceedings of the 29th International Conference on Machine Learning (ICML-12)","author":"Rakhlin A.","year":"2012"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics pages 400--407 1951.  H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics pages 400--407 1951.","DOI":"10.1214\/aoms\/1177729586"},{"key":"e_1_2_1_41_1","first-page":"636","volume-title":"AISTATS","author":"Saha A.","year":"2011"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277813"},{"key":"e_1_2_1_43_1","article-title":"Distributed online optimization in dynamic environments using mirror descent","author":"Shahrampour S.","year":"2017","journal-title":"IEEE Transactions on Automatic Control"},{"key":"e_1_2_1_44_1","first-page":"71","volume-title":"International Conference on Machine Learning","author":"Shamir O.","year":"2013"},{"key":"e_1_2_1_45_1","article-title":"Stochastic online shortest path routing: The value of feedback","author":"Talebi M. S.","year":"2017","journal-title":"IEEE Transactions on Automatic Control"},{"key":"e_1_2_1_46_1","first-page":"49","volume-title":"Computational Intelligence for Financial Engineering, 2000.(CIFEr) Proceedings of the IEEE\/IAFE\/INFORMS 2000 Conference on","author":"Uryasev S.","year":"2000"},{"key":"e_1_2_1_47_1","first-page":"109","volume-title":"International Conference on Machine Learning (ICML)","author":"Wauthier F.","year":"2013"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"W. Wong and C. Sung. Robust convergence of low-data rate-distributed controllers. IEEE transactions on automatic control 49(1):82--87 2004.  W. Wong and C. Sung. Robust convergence of low-data rate-distributed controllers. IEEE transactions on automatic control 49(1):82--87 2004.","DOI":"10.1109\/TAC.2003.821418"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti736"},{"key":"e_1_2_1_50_1","first-page":"3158","volume-title":"AAAI","author":"Zhang L.","year":"2015"},{"key":"e_1_2_1_51_1","first-page":"928","volume-title":"Proceedings of the 20th International Conference on Machine Learning (ICML)","author":"Zinkevich M.","year":"2003"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3224420","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3224420","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:06Z","timestamp":1750210746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3224420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,13]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,13]]}},"alternative-id":["10.1145\/3224420"],"URL":"https:\/\/doi.org\/10.1145\/3224420","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2018,6,13]]},"assertion":[{"value":"2018-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}