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

Author:

Lian, Yuefang (Lian, Yuefang.) | Du, Donglei (Du, Donglei.) | Wang, Xiao (Wang, Xiao.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhou, Yang (Zhou, Yang.)

Indexed by:

EI Scopus SCIE

Abstract:

Stochastic optimization has experienced significant growth in recent decades, with the increasing prevalence of variance reduction techniques in stochastic optimization algorithms to enhance computational efficiency. In this paper, we introduce two projection-free stochastic approximation algorithms for maximizing diminishing return (DR) submodular functions over convex constraints, building upon the Stochastic Path Integrated Differential EstimatoR (SPIDER) and its variants. Firstly, we present a SPIDER Continuous Greedy (SPIDER-CG) algorithm for the monotone case that guarantees a (1- e(-1))OPT- epsilon approximation after O(epsilon(-1)) iterations and O(epsilon(-2)) stochastic gradient computations under the mean-squared smoothness assumption. For the non-monotone case, we develop a SPIDER Frank-Wolfe (SPIDER-FW) algorithm that guarantees a 1/4 (1- minx (x is an element of C)||x||(infinity))OPT- epsilon approximation withO(epsilon(-1)) iterations and O(epsilon (-2)) stochastic gradient estimates. To address the practical challenge associated with a large number of samples per iteration, we introduce a modified gradient estimator based on SPIDER, leading to a Hybrid SPIDER-FW (Hybrid SPIDER-CG) algorithm, which achieves the same approximation guarantee as SPIDER-FW (SPIDER-CG) algorithm with only O(1) samples per iteration. Numerical experiments on both simulated and real data demonstrate the efficiency of the proposed methods.

Keyword:

Frank-Wolfe algorithm DR-Submodular Gradient estimator Variance reduction Stochastic algorithm

Author Community:

  • [ 1 ] [Lian, Yuefang]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 9Y2, Canada
  • [ 4 ] [Lian, Yuefang]Peng Cheng Lab, Shenzhen 518066, Peoples R China
  • [ 5 ] [Wang, Xiao]Peng Cheng Lab, Shenzhen 518066, Peoples R China
  • [ 6 ] [Zhou, Yang]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Shandong, Peoples R China

Reprint Author's Address:

  • [Zhou, Yang]Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Shandong, Peoples R China;;

Show more details

Related Keywords:

Source :

ALGORITHMICA

ISSN: 0178-4617

Year: 2023

Issue: 5

Volume: 86

Page: 1335-1364

1 . 1 0 0

JCR@2022

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:986/10607231
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.