Parallelized maximization of nonmonotone one-sided σ-smooth function. (January 2023) - Zhang, Hongxiang; Xu, Dachuan; Zhang, Yapu; Zhang, Zhenning
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: