Parallelized maximization of nonmonotone one-sided σ-smooth function. (January 2023)

• Record Type: Journal Article
• Authors: Zhang, Hongxiang; Xu, Dachuan; Zhang, Yapu; Zhang, Zhenning
• Is Part Of: Computers & electrical engineering. Volume 105(2023)
• Publication Date: 2023-01
• Subjects: OSS function -- Parallel algorithm -- Down-closed -- Frank Wolfe; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.108478
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: In this paper, we study the problem of maximizing a nonmonotone nonnegative one-sided σ -smooth (OSS) function G ( x ) . For a downwards-closed basis polyhedron constraint, we propose two classes of parallel algorithms under deterministic and random settings. For the deterministic nonmonotone O S S problem, we design the Jump-Start Parallel Frank Wolfe (JSPFW) algorithm and obtain an approximation solution of e − 1 − e − 2 − O ( ϵ ) . The JSPFW algorithm has ( O ( log n / ϵ 2 ) ) adaptive rounds and O ( n log n / ϵ 2 ) queries about function and its gradient value. For the stochastic O S S problem, we design the Stochastic Parallel Frank Wolfe (SPFW) algorithm and get the ( e − 1 − e − 2 ) ( 1 − O ( ϵ ) ) ( 1 − o ( 1 ) ) approximation solution. The SPFW algorithm needs O ( n 2 ) adaptive rounds and consumes O ( n 2 ) queries about gradient function value. Highlights: Parallel algorithm for continuous one sided smooth optimization problem. The expansion research of continuous DR submodular maximization problem. The parallel framework of Frank Wolfe type algorithm. Algorithm is suitable for downwards closed convex constraint. Graphical abstract: