• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Zhang, H. (Zhang, H..) | Xu, D. (Xu, D..) | Gai, L. (Gai, L..) | Zhang, Z. (Zhang, Z..)

Indexed by:

EI Scopus SCIE

Abstract:

The online optimization model was first introduced in the research of machine learning problems (Zinkevich, Proceedings of ICML, 928–936, 2003). It is a powerful framework that combines the principles of optimization with the challenges of online decision-making. The present research mainly consider the case that the reveal objective functions are convex or submodular. In this paper, we focus on the online maximization problem under a special objective function Φ(x):[0,1]n→R+ which satisfies the inequality 12⟨uT∇2Φ(x),u⟩≤σ·‖u‖1‖x‖1⟨u,∇Φ(x)⟩ for any x,u∈[0,1]n,x≠0. This objective function is named as one sided σ-smooth (OSS) function. We achieve two conclusions here. Firstly, under the assumption that the gradient function of OSS function is L-smooth, we propose an (1-exp((θ-1)(θ/(1+θ))2σ))- approximation algorithm with O(T) regret upper bound, where T is the number of rounds in the online algorithm and θ,σ∈R+ are parameters. Secondly, if the gradient function of OSS function has no L-smoothness, we provide an 1+((θ+1)/θ)4σ-1-approximation projected gradient algorithm, and prove that the regret upper bound of the algorithm is O(T). We think that this research can provide different ideas for online non-convex and non-submodular learning. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.

Keyword:

L-smooth Gradient algorithm Online optimization

Author Community:

  • [ 1 ] [Zhang H.]School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, 100049, China
  • [ 2 ] [Xu D.]Institute of Operations Research and Information Engineering, Beijing University of Technology, Beijing, 100124, China
  • [ 3 ] [Gai L.]Business School, School of Intelligent Emergency Management, University of Shanghai for Science and Technology, Shanghai, 200093, China
  • [ 4 ] [Zhang Z.]Institute of Operations Research and Information Engineering, Beijing University of Technology, Beijing, 100124, China

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Source :

Journal of Combinatorial Optimization

ISSN: 1382-6905

Year: 2024

Issue: 5

Volume: 47

1 . 0 0 0

JCR@2022

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 9

Affiliated Colleges:

Online/Total:372/10590645
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.