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

Author:

Zhang, Hongxiang (Zhang, Hongxiang.) | Xu, Dachuan (Xu, Dachuan.) | Gai, Ling (Gai, Ling.) | Zhang, Zhenning (Zhang, Zhenning.)

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 Phi(x) : [0,1](n) -> R+ which satisfies the inequality 1/2 < u(T) del(2)Phi(x), u > <= sigma center dot ||u||(1)/||x||(1) < u, del Phi(x)> for any x, u is an element of[0, 1](n), x not equal 0. This objective function is named as one sided sigma-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((theta - 1)(theta/(1+theta))(2 sigma)))- approximation algorithm with O(root T) regret upper bound, where T is the number of rounds in the online algorithm and theta, sigma is an element of R+ are parameters. Secondly, if the gradient function of OSS function has no L-smoothness, we provide an (1 + ((theta + 1)/theta)(4 sigma))(-1)-approximation projected gradient algorithm, and prove that the regret upper bound of the algorithm is O(root T). We think that this research can provide different ideas for online non-convex and non-submodular learning.

Keyword:

L-smooth Online optimization Gradient algorithm

Author Community:

  • [ 1 ] [Zhang, Hongxiang]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Inst Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 3 ] [Zhang, Zhenning]Beijing Univ Technol, Inst Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 4 ] [Gai, Ling]Univ Shanghai Sci & Technol, Business Sch, Sch Intelligent Emergency Management, Shanghai 200093, Peoples R China

Reprint Author's Address:

  • [Gai, Ling]Univ Shanghai Sci & Technol, Business Sch, Sch Intelligent Emergency Management, Shanghai 200093, Peoples R China;;

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: 0

Affiliated Colleges:

Online/Total:2119/10900208
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.