[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Strongly adaptive online learning over partial intervals

  • Research Paper
  • Published:
Science China Information Sciences Aims and scope Submit manuscript

Abstract

To cope with changing environments, strongly adaptive algorithms that almost enjoy the optimal performance on every time interval have been proposed for online learning. However, the best regret bound of existing algorithms on each time interval with length τ is \(O\left( {\sqrt {\tau \log \,T} } \right)\), and their complexities are increasing with a factor of O(log T), where T is the time horizon. In real-world applications, T could go to infinity, which means that even these logarithmic factors are unacceptable. In this paper, we propose to remove the logarithmic factors of existing algorithms by utilizing prior information of environments. Specifically, we assume a lower bound τ1 and an upper bound τ2 on how long the environment changes are given, and only focus on the performance over time intervals with length in [τ1, τ2]. Then, we propose a new algorithm with a refined set of intervals that can reduce the complexity and a simple weighting method that can cooperate with our interval set. Theoretical analysis reveals that the regret bound of our algorithm on any focused interval is optimal up to a constant factor. Both the regret bound and the computational cost per iteration are independent of T. Experimental results show that our algorithm outperforms the state-of-the-art algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Cesa-Bianchi N, Freund Y, Haussler D, et al. How to use expert advice. J ACM, 1997, 44: 427–485

    Article  MathSciNet  MATH  Google Scholar 

  2. Zinkevich M. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning, Washington, 2003. 928–936

  3. Zhang L J. Online learning in changing environments. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, Online, 2020. 5178–5182

  4. Daniely A, Gonen A, Shalev-Shwartz S. Strongly adaptive online learning. In: Proceedings of the 32nd International Conference on Machine Learning, Lille, 2015. 1405–1411

  5. Jun K-S, Orabona F, Wright S, et al. Improved strongly adaptive online learning using coin betting. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Fort Lauderdale, 2017. 943–951

  6. Auer P, Cesa-Bianchi N, Gentile C. Adaptive and self-confident on-line learning algorithms. J Comput Syst Sci, 2002, 64: 48–75

    Article  MathSciNet  MATH  Google Scholar 

  7. Shalev-Shwartz S. Online learning: theory, algorithms, and applications. Dissertation for Ph.D. Degree. Jerusalem: The Hebrew University of Jerusalem, 2007

    MATH  Google Scholar 

  8. Hazan E, Agarwal A, Kale S. Logarithmic regret algorithms for online convex optimization. Mach Learn, 2007, 69: 169–192

    Article  MATH  Google Scholar 

  9. Duchi J, Hazan E, Singer Y. Adaptive subgradient methods for online learning and stochastic optimization. J Mach Learn Res, 2011, 12: 2121–2159

    MathSciNet  MATH  Google Scholar 

  10. Hazan E, Kale S. Projection-free online learning. In: Proceedings of the 29th International Conference on Machine Learning, Edinburgh, 2012. 1843–1850

  11. Zhang L J, Jin R, Chen C, et al. Efficient online learning for large-scale sparse kernel logistic regression. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto, 2012. 1219–1225

  12. Zhang L J, Yi J F, Jin R, et al. Online kernel learning with a near optimal sparsity bound. In: Proceedings of the 30th International Conference on Machine Learning, Atlanta, 2013. 621–629

  13. Oiwa H, Matsushima S, Nakagawa H. Feature-aware regularization for sparse online learning. Sci China Inf Sci, 2014, 57: 052104

    Article  MathSciNet  MATH  Google Scholar 

  14. Wan Y Y, Wei N, Zhang L J. Efficient adaptive online learning via frequent directions. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. Stockholm, 2018. 2748–2754

  15. Wang Y H, Lin P, Hong Y G. Distributed regression estimation with incomplete data in multi-agent networks. Sci China Inf Sci, 2018, 61: 092202

    Article  MathSciNet  Google Scholar 

  16. Wan Y Y, Tu W W, Zhang L J. Projection-free distributed online convex optimization with \(O\left( {\sqrt T } \right)\) communication complexity. In: Proceedings of the 37th International Conference on Machine Learning, Online, 2020. 9818–9828

  17. Wan Y Y, Zhang L J. Projection-free online learning over strongly convex sets. 2020. ArXiv:2010.08177

  18. Hou B J, Zhang L J, Zhou Z H. Learning with feature evolvable streams. In: Proceedings of Advances in Neural Information Processing Systems 30, Long Beach, 2017. 1416–1426

  19. Wang C Y, Xie L, Wang W, et al. Moving tag detection via physical layer analysis for large-scale RFID systems. In: Proceedings of the 35th Annual IEEE International Conference on Computer Communications, Calcutta, 2016. 1–9

  20. Wells W D, Gubar G. Life cycle concept in marketing research. J Marketing Res, 1966, 3: 355–363

    Article  Google Scholar 

  21. Yang J W, Yu Y, Zhang X P. Life-stage modeling by customer-manifold embedding. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, Melbourne, 2017. 3259–3265

  22. Bojanic D C. The impact of age and family life experiences on Mexican visitor shopping expenditures. Tourism Manage, 2011, 32: 406–414

    Article  Google Scholar 

  23. Hazan E. Introduction to online convex optimization. FNT Optim, 2015, 2: 157–325

    Article  Google Scholar 

  24. Shalev-Shwartz S. Online learning and online convex optimization. FNT Mach Learn, 2011, 4: 107–194

    Article  MATH  Google Scholar 

  25. Cesa-Bianchi N, Orabona F. Online learning algorithms. Annu Rev Stat Appl, 2020, 8: 1–26

    MathSciNet  Google Scholar 

  26. Hazan E, Seshadhri C. Adaptive algorithms for online decision problems. Electron Colloq Comput Complex, 2007, 14: 88

    Google Scholar 

  27. Abernethy J D, Bartlett P L, Rakhlin A, et al. Optimal stragies and minimax lower bounds for online convex games. In: Proceedings of the 21st Annual Conference on Learning Theory, Helsinki, 2008. 415–424

  28. Arora S, Hazan E, Kale S. The multiplicative weights update method: a meta-algorithm and applications. Theor Comput, 2012, 8: 121–164

    Article  MathSciNet  MATH  Google Scholar 

  29. Freund Y, Schapire R E, Singer Y, et al. Using and combining predictors that specialize. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, El Paso, 1997. 334–343

  30. Orabona F, Pal D. Coin betting and parameter-free online learning. In: Proceedings of Advances in Neural Information Processing Systems 29, Barcelona, 2016. 577–585

  31. Zhang L J, Liu T Y, Zhou Z H. Adaptive regret of convex and smooth functions. In: Proceedings of the 36th International Conference on Machine Learning, Long Beach, 2019. 7414–7423

  32. Luo H P, Schapire R E. Achieving all with no parameters: AdaNormalHedge. In: Proceedings of the 28th Conference on Learning Theory, Paris, 2015. 1286–1304

  33. Orabona F, Pál D. Scale-free online learning. Theor Comput Sci, 2018, 716: 50–69

    Article  MathSciNet  MATH  Google Scholar 

  34. Wang G H, Zhao D K, Zhang L J. Minimizing adaptive regret with one gradient per iteration. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, Stockholm, 2018. 2762–2768

  35. van Erven T, Koolen W M. MetaGrad: multiple learning rates in online learning. In: Proceedings of Advances in Neural Information Processing Systems 29, Barcelona, 2016. 3666–3674

  36. Zhang L J, Yang T B, Jin R, et al. Dynamic regret of strongly adaptive methods. In: Proceedings of the 35th International Conference on Machine Learning, Stockholm, 2018. 5877–5886

  37. Zhang L J, Wang G H, Tu W W, et al. Dual adaptivity: a universal algorithm for minimizing the adaptive regret of convex functions. 2019. ArXiv:1906.10851

  38. Zhang L J, Lu S Y, Yang T B. Minimizing dynamic regret and adaptive regret simultaneously. In: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, Palermo, 2020. 309–319

  39. Srebro N, Sridharan K, Tewari A. Smoothness, low-noise and fast rates. In: Proceedings of Advances in Neural Information Processing Systems 23, Vancouver, 2010. 2199–2207

  40. Gaillard P, Stoltz G, van Erven T. A second-order bound with excess losses. In: Proceedings of the 27th Annual Conference on Learning Theory, Barcelona, 2014. 176–196

  41. Luo H P, Schapire R E. A drifting-games analysis for online learning and applications to boosting. In: Proceedings of Advances in Neural Information Processing Systems 27, Montreal, 2014. 1368–1376

  42. Chang C C, Lin C J. LIBSVM: a library for support vector machines. ACM Trans Intell Syst Technol, 2011, 2: 1–27

    Article  Google Scholar 

Download references

Acknowledgements

This work was partially supported by National Natural Science Foundation of China (Grant No. 61976112), Natural Science Foundation of Jiangsu Province (Grant No. BK20200064), and Open Research Projects of Zhejiang Lab (Grant No. 2021KB0AB02).

Author information

Authors and Affiliations

  1. National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China

    Yuanyu Wan & Lijun Zhang

  2. 4 Paradigm Inc., Beijing, 100085, China

    Wei-Wei Tu

Authors
  1. Yuanyu Wan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei-Wei Tu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lijun Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lijun Zhang.

Additional information

Supporting information

Appendixes A–G. The supporting information is available online at info.scichina.com and link.springer.com. The supporting materials are published as submitted, without typesetting or editing. The responsibility for scientific accuracy and content remains entirely with the authors.

Electronic supplementary material

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wan, Y., Tu, WW. & Zhang, L. Strongly adaptive online learning over partial intervals. Sci. China Inf. Sci. 65, 202101 (2022). https://doi.org/10.1007/s11432-020-3273-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11432-020-3273-9

Keywords

Search

Navigation