Online learning under one sided $$\sigma $$ σ -smooth function

Hongxiang Zhang (), Dachuan Xu (), Ling Gai () and Zhenning Zhang ()
Additional contact information
Hongxiang Zhang: University of Chinese Academy of Sciences
Dachuan Xu: Beijing University of Technology
Ling Gai: University of Shanghai for Science and Technology
Zhenning Zhang: Beijing University of Technology

Journal of Combinatorial Optimization, 2024, vol. 47, issue 5, No 6, 15 pages

Abstract: 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 $$\varPhi (x):[0,1]^n\rightarrow \mathbb {R}_{+}$$ Φ ( x ) : [ 0 , 1 ] n → R + which satisfies the inequality $$\frac{1}{2}\langle u^{T}\nabla ^{2}\varPhi (x),u\rangle \le \sigma \cdot \frac{\Vert u\Vert _{1}}{\Vert x\Vert _{1}}\langle u,\nabla \varPhi (x)\rangle $$ 1 2 ⟨ u T ∇ 2 Φ ( x ) , u ⟩ ≤ σ · ‖ u ‖ 1 ‖ x ‖ 1 ⟨ u , ∇ Φ ( x ) ⟩ for any $$x,u\in [0,1]^n, x\ne 0$$ x , u ∈ [ 0 , 1 ] n , x ≠ 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 }))$$ ( 1 - exp ( ( θ - 1 ) ( θ / ( 1 + θ ) ) 2 σ ) ) - approximation algorithm with $$O(\sqrt{T})$$ O ( T ) regret upper bound, where T is the number of rounds in the online algorithm and $$\theta , \sigma \in \mathbb {R}_{+}$$ θ , σ ∈ R + are parameters. Secondly, if the gradient function of OSS function has no L-smoothness, we provide an $$\left( 1+((\theta +1)/\theta )^{4\sigma }\right) ^{-1}$$ 1 + ( ( θ + 1 ) / θ ) 4 σ - 1 -approximation projected gradient algorithm, and prove that the regret upper bound of the algorithm is $$O(\sqrt{T})$$ O ( T ) . We think that this research can provide different ideas for online non-convex and non-submodular learning.

Keywords: Online optimization; L-smooth; Gradient algorithm; 90C27; 68W25 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01174-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01174-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01174-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().