{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:29:25Z","timestamp":1767338965105},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"German Federal Ministry for Economic Affairs and Climate Action","award":["01MK20002C"],"award-info":[{"award-number":["01MK20002C"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper proposes a new family of algorithms for the online optimisation of composite objectives. The algorithms can be interpreted as the combination of the exponentiated gradient and <jats:italic>p<\/jats:italic>-norm algorithm. Combined with algorithmic ideas of adaptivity and optimism, the proposed algorithms achieve a sequence-dependent regret upper bound, matching the best-known bounds for sparse target decision variables. Furthermore, the algorithms have efficient implementations for popular composite objectives and constraints and can be converted to stochastic optimisation algorithms with the optimal accelerated rate for smooth objectives.<\/jats:p>","DOI":"10.1007\/s10994-022-06229-1","type":"journal-article","created":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T21:17:27Z","timestamp":1661203047000},"page":"4719-4764","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimistic optimisation of composite objective with exponentiated update"],"prefix":"10.1007","volume":"111","author":[{"given":"Weijia","family":"Shao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fikret","family":"Sivrikaya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sahin","family":"Albayrak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,22]]},"reference":[{"key":"6229_CR1","unstructured":"Alacaoglu, A., Malitsky, Y., Mertikopoulos, P., & Cevher, V. (2020). A new regret analysis for Adam-type algorithms. In International conference on machine learning (pp. 202\u2013210)."},{"key":"6229_CR2","unstructured":"Allen-Zhu, Z., & Orecchia, L. (2017). Linear coupling: An ultimate unification of gradient and mirror descent. In 8th Innovations in theoretical computer science conference (ITCS 2017)."},{"key":"6229_CR3","unstructured":"Anava, O., Hazan, E., Mannor, S., & Shamir, O. (2013). Online learning for time series prediction. In Conference on learning theory (pp. 172\u2013184)."},{"issue":"1","key":"6229_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., & Kale, S. (2012). The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(1), 121\u2013164.","journal-title":"Theory of Computing"},{"key":"6229_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-007-2247-7","volume-title":"Convexity and optimization in banach spaces","author":"V Barbu","year":"2012","unstructured":"Barbu, V., & Precupanu, T. (2012). Convexity and optimization in banach spaces. Berlin: Springer."},{"issue":"1","key":"6229_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., & Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1), 183\u2013202.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"6229_CR7","volume-title":"Matrix analysis","author":"R Bhatia","year":"2013","unstructured":"Bhatia, R. (2013). Matrix analysis (Vol. 169). Berlin: Springer."},{"key":"6229_CR8","doi-asserted-by":"publisher","unstructured":"Cancela, B., Bol\u00f3n-Canedo, V., & Alonso-Betanzos, A. (2021). A delayed elastic-net approach for performing adversarial attacks. In 2020 25th International conference on pattern recognition (ICPR) (pp. 378\u2013384). https:\/\/doi.org\/10.1109\/ICPR48806.2021.9413170.","DOI":"10.1109\/ICPR48806.2021.9413170"},{"key":"6229_CR9","doi-asserted-by":"crossref","unstructured":"Carlini, N., & Wagner, D. (2017). Towards evaluating the robustness of neural networks. In 2017 IEEE symposium on security and privacy (SP) (pp. 39\u201357).","DOI":"10.1109\/SP.2017.49"},{"issue":"9","key":"6229_CR10","doi-asserted-by":"publisher","first-page":"2050","DOI":"10.1109\/TIT.2004.833339","volume":"50","author":"N Cesa-Bianchi","year":"2004","unstructured":"Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9), 2050\u20132057.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"6229_CR11","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1109\/TIT.2007.911292","volume":"54","author":"N Cesa-Bianchi","year":"2008","unstructured":"Cesa-Bianchi, N., & Gentile, C. (2008). Improved risk tail bounds for on-line algorithms. IEEE Transactions on Information Theory, 54(1), 386\u2013390.","journal-title":"IEEE Transactions on Information Theory"},{"key":"6229_CR12","doi-asserted-by":"crossref","unstructured":"Chen, P.-Y., Sharma, Y., Zhang, H., Yi, J., & Hsieh, C.-J. (2018). Ead: Elastic-net attacks to deep neural networks via adversarial examples. In Thirty-second AAAI conference on artificial intelligence.","DOI":"10.1609\/aaai.v32i1.11302"},{"key":"6229_CR13","volume-title":"Advances in neural information processing systems","author":"X Chen","year":"2019","unstructured":"Chen, X., Liu, S., Xu, K., Li, X., Lin, X., Hong, M., & Cox, D. (2019). Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d\u2019Alch\u00e9-Buc, E. Fox, & R. Garnett (Eds.), Advances in neural information processing systems (Vol. 32). Berlin: Curran Associates, Inc."},{"key":"6229_CR14","unstructured":"Cutkosky, A. (2019). Anytime online-to-batch, optimism and acceleration. In International conference on machine learning (pp. 1446\u20131454)."},{"key":"6229_CR15","unstructured":"Cutkosky, A., & Boahen, K. (2017a). Online learning without prior information. In Conference on learning theory (pp. 643\u2013677)."},{"key":"6229_CR16","volume-title":"Advances in neural information processing systems","author":"A Cutkosky","year":"2016","unstructured":"Cutkosky, A., & Boahen, K. A. (2016). Online convex optimization with unconstrained domains and losses. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, & R. Garnett (Eds.), Advances in neural information processing systems (Vol. 29). Berlin: Curran Associates, Inc."},{"key":"6229_CR17","volume-title":"Advances in neural information processing systems","author":"A Cutkosky","year":"2017","unstructured":"Cutkosky, A., & Boahen, K. A. (2017b). Stochastic and adversarial online learning without hyperparameters. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, & R. Garnett (Eds.), Advances in neural information processing systems (Vol. 30). Berlin: Curran Associates, Inc."},{"key":"6229_CR18","volume-title":"Advances in neural information processing systems","author":"A Dhurandhar","year":"2018","unstructured":"Dhurandhar, A., Chen, P.-Y., Luss, R., Tu, C.-C., Ting, P., Shanmugam, K., & Das, P. (2018). Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, & R. Garnett (Eds.), Advances in neural information processing systems.  (Vol. 31). Berlin: Curran Associates Inc."},{"key":"6229_CR19","first-page":"2121","volume":"12","author":"J Duchi","year":"2011","unstructured":"Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12, 2121\u20132159.","journal-title":"Journal of Machine Learning Research"},{"issue":"5","key":"6229_CR20","doi-asserted-by":"publisher","first-page":"2788","DOI":"10.1109\/TIT.2015.2409256","volume":"61","author":"JC Duchi","year":"2015","unstructured":"Duchi, J. C., Jordan, M. I., Wainwright, M. J., & Wibisono, A. (2015). Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5), 2788\u20132806.","journal-title":"IEEE Transactions on Information Theory"},{"key":"6229_CR21","unstructured":"Duchi, J. C., Shalev-Shwartz, S., Singer, Y., & Tewari, A. (2010). Composite objective mirror descent. In A. T. Kalai & M. Mohri (Eds.), COLT 2010\u2014The 23rd conference on learning theory, Haifa, Israel, June 27\u201329, 2010 (pp. 14\u201326). Omnipress."},{"issue":"3","key":"6229_CR22","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1026319107706","volume":"53","author":"C Gentile","year":"2003","unstructured":"Gentile, C. (2003). The robustness of the p-norm algorithms. Machine Learning, 53(3), 265\u2013299.","journal-title":"Machine Learning"},{"key":"6229_CR23","unstructured":"Ghai, U., Hazan, E., & Singer, Y. (2020). Exponentiated gradient meets gradient descent. In Algorithmic learning theory (pp. 386\u2013407)."},{"key":"6229_CR24","doi-asserted-by":"publisher","unstructured":"He, K., Zhang, X., Ren, S., & Sun, J. (2016). Deep residual learning for image recognition. In 2016 IEEE conference on computer vision and pattern recognition (CVPR) (pp. 770-778). https:\/\/doi.org\/10.1109\/CVPR.2016.90.","DOI":"10.1109\/CVPR.2016.90"},{"key":"6229_CR25","first-page":"40","volume":"1","author":"P Joulani","year":"2017","unstructured":"Joulani, P., Gy\u00f6rgy, A., & Szepesv\u00e1ri, C. (2017). A modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, and variational bounds. Journal of Machine Learning Research, 1, 40.","journal-title":"Journal of Machine Learning Research"},{"key":"6229_CR26","unstructured":"Joulani, P., Raj, A., Gyorgy, A., & Szepesv\u00e1ri, C. (2020). A simpler approach to accelerated optimization: Iterative averaging meets optimism. In International conference on machine learning (pp. 4984\u20134993)."},{"issue":"1","key":"6229_CR27","first-page":"1865","volume":"13","author":"SM Kakade","year":"2012","unstructured":"Kakade, S. M., Shalev-Shwartz, S., & Tewari, A. (2012). Regularization techniques for learning with matrices. The Journal of Machine Learning Research, 13(1), 1865\u20131890.","journal-title":"The Journal of Machine Learning Research"},{"key":"6229_CR28","first-page":"6260","volume-title":"Advances in neural information processing systems","author":"A Kavis","year":"2019","unstructured":"Kavis, A., Levy, K. Y., Bach, F., & Cevher, V. (2019). Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d\u2019Alch\u00e9-Buc, E. Fox, & R. Garnett (Eds.), Advances in neural information processing systems (pp. 6260\u20136269). Berlin: Curran Associates Inc."},{"key":"6229_CR29","unstructured":"Kempka, M., Kotlowski, W., & Warmuth, M. K. (2019). Adaptive scale-invariant online algorithms for learning linear models. In International conference on machine learning (pp. 3321\u20133330)."},{"issue":"1","key":"6229_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.2612","volume":"132","author":"J Kivinen","year":"1997","unstructured":"Kivinen, J., & Warmuth, M. K. (1997). Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1), 1\u201363.","journal-title":"Information and Computation"},{"key":"6229_CR31","unstructured":"Krizhevsky, A. (2009). Learning multiple layers of features from tiny images. Master\u2019s thesis, University of Tront."},{"key":"6229_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-order and stochastic optimization methods for machine learning","author":"G Lan","year":"2020","unstructured":"Lan, G. (2020). First-order and stochastic optimization methods for machine learning. Berlin: Springer."},{"key":"6229_CR33","first-page":"6500","volume-title":"Advances in neural information processing systems","author":"YK Levy","year":"2018","unstructured":"Levy, Y. K., Yurtsever, A., & Cevher, V. (2018). Online adaptive methods, universality and acceleration. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, & R. Garnett (Eds.), Advances in neural information processing systems (pp. 6500\u20136509). Berlin: Curran Associates Inc."},{"issue":"1","key":"6229_CR34","first-page":"173","volume":"2","author":"AS Lewis","year":"1995","unstructured":"Lewis, A. S. (1995). The convex analysis of unitarily invariant matrix functions. Journal of Convex Analysis, 2(1), 173\u2013183.","journal-title":"Journal of Convex Analysis"},{"key":"6229_CR35","unstructured":"Li, X., & Orabona, F. (2019). On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd international conference on artificial intelligence and statistics (pp. 983\u2013992)."},{"issue":"2","key":"6229_CR36","first-page":"646","volume":"24","author":"C Lu","year":"2014","unstructured":"Lu, C., Lin, Z., & Yan, S. (2014). Smoothed low rank and sparse matrix recovery by iteratively reweighted least squares minimization. IEEE Transactions on Image Processing, 24(2), 646\u2013654.","journal-title":"IEEE Transactions on Image Processing"},{"key":"6229_CR37","unstructured":"McMahan, H. B., & Streeter, M. J. (2010). Adaptive bound optimization for online convex optimization. In A. T. Kalai & M. Mohri (Eds.), COLT 2010\u2014The 23rd conference on learning theory, Haifa, Israel, June 27\u201329, 2010 (pp. 244\u2013256). Omnipress."},{"key":"6229_CR38","volume-title":"Introductory lectures on convex optimization: A basic course","author":"Y Nesterov","year":"2003","unstructured":"Nesterov, Y. (2003). Introductory lectures on convex optimization: A basic course (Vol. 87). Berlin: Springer."},{"key":"6229_CR39","unstructured":"Orabona, F. (2013). Dimension-free exponentiated gradient. In NIPS (pp. 1806\u20131814)."},{"issue":"3","key":"6229_CR40","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10994-014-5474-8","volume":"99","author":"F Orabona","year":"2015","unstructured":"Orabona, F., Crammer, K., & Cesa-Bianchi, N. (2015). A generalized online mirror descent with applications to classification and regression. Machine Learning, 99(3), 411\u2013435.","journal-title":"Machine Learning"},{"key":"6229_CR41","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.tcs.2017.11.021","volume":"716","author":"F Orabona","year":"2018","unstructured":"Orabona, F., & P\u00e1l, D. (2018). Scale-free online learning. Theoretical Computer Science, 716, 50\u201369.","journal-title":"Theoretical Computer Science"},{"key":"6229_CR42","doi-asserted-by":"crossref","unstructured":"Ribeiro, M. T., Singh, S., Guestrin, C. (2016). \u201cWhy should I trust you?\u201d Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining (pp. 1135\u20131144).","DOI":"10.1145\/2939672.2939778"},{"issue":"3","key":"6229_CR43","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1109\/TSC.2014.2365795","volume":"9","author":"L Song","year":"2014","unstructured":"Song, L., Tekin, C., & Van Der Schaar, M. (2014). Online learning in large-scale contextual recommender systems. IEEE Transactions on Services Computing, 9(3), 433\u2013445.","journal-title":"IEEE Transactions on Services Computing"},{"key":"6229_CR44","unstructured":"Steinhardt, J., & Liang, P. (2014). Adaptivity and optimism: An improved exponentiated gradient algorithm. In International conference on machine learning (pp. 1593\u20131601)."},{"key":"6229_CR45","doi-asserted-by":"crossref","unstructured":"Warmuth, M. K. (2007). Winnowing subspaces. In Proceedings of the 24th international conference on machine learning (pp. 999\u20131006).","DOI":"10.1145\/1273496.1273622"},{"issue":"10","key":"6229_CR46","doi-asserted-by":"publisher","first-page":"1545","DOI":"10.1109\/LSP.2018.2867724","volume":"25","author":"C Xie","year":"2018","unstructured":"Xie, C., Bijral, A., & Ferres, J. L. (2018). Nonstop: A nonstationary online prediction method for time series. IEEE Signal Processing Letters, 25(10), 1545\u20131549.","journal-title":"IEEE Signal Processing Letters"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06229-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06229-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06229-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T22:25:49Z","timestamp":1669760749000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06229-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,22]]},"references-count":46,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["6229"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06229-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,22]]},"assertion":[{"value":"3 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2022","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing\nOpen Access funding information has been added in the Funding Note.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest or competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}