论文标题
用于最大化单面$σ$ -Smooth功能的并行算法
Parallel algorithms for maximizing one-sided $σ$-smooth function
论文作者
论文摘要
在本文中，我们研究了最大化单调的单面$σ$ -smooth（$ oss $ for Short）函数$ f（x）$的问题，但要遵守凸polytope。这个问题首先由Mehrdad等人提出。 \ cite {gss2021}以表征某些集合功能的多线性扩展。与Mehrdad等人的串行算法不同，名称启动了连续的贪婪算法。 \ cite {gss2021}，我们建议使用此问题的第一个并行算法（简称JSPG）gump-start Parallel Greedy（JSPG）算法。 JSPG算法的近似值被证明为$（（1-e^{ - \ lesg（\fracα{\fracα{α+1} \ right） n/ε^{2}））$自适应回合，并消耗$ O（n \ log n/ε^{2}）$查询。 t} f（x，y）$。$ f $是关于随机变量$ y $的随机功能，而$ y $是从概率分布$ t $的$ y $的实现，我们设计了随机版本，我们设计了随机版本。 -e^{ - \ left（\fracα{α+1} \ right）^{2σ}} - ε）opt-o（κ^{1/2}）$，在这里$κ= \ frac {\ frac {\ max \ max \ frac {\ max \ frac f（x_ {0}） - d_ {o} \ |^{2}，16σ^{2}+2l^{2} d^{2} {2}}} {（t+9）^{2/3}} $与Preset参数$σ，l，d $和time $ t $有关。
In this paper, we study the problem of maximizing a monotone normalized one-sided $σ$-smooth ($OSS$ for short) function $F(x)$, subject to a convex polytope. This problem was first introduced by Mehrdad et al. \cite{GSS2021} to characterize the multilinear extension of some set functions. Different with the serial algorithm with name Jump-Start Continuous Greedy Algorithm by Mehrdad et al. \cite{GSS2021}, we propose Jump-Start Parallel Greedy (JSPG for short) algorithm, the first parallel algorithm, for this problem. The approximation ratio of JSPG algorithm is proved to be $((1-e^{-\left(\fracα{α+1}\right)^{2σ}}) ε)$ for any any number $α\in(0,1]$ and $ε>0$. We also prove that our JSPG algorithm runs in $(O(\log n/ε^{2}))$ adaptive rounds and consumes $O(n \log n/ε^{2})$ queries. In addition, we study the stochastic version of maximizing monotone normalized $OSS$ function, in which the objective function $F(x)$ is defined as $F(x)=\mathbb{E}_{y\sim T}f(x,y)$. Here $f$ is a stochastic function with respect to the random variable $Y$, and $y$ is the realization of $Y$ drawn from a probability distribution $T$. For this stochastic version, we design Stochastic Parallel-Greedy (SPG) algorithm, which achieves a result of $F(x)\geq(1 -e^{-\left(\fracα{α+1}\right)^{2σ}}-ε)OPT-O(κ^{1/2})$, with the same time complexity of JSPG algorithm. Here $κ=\frac{\max \{5\|\nabla F(x_{0})-d_{o}\|^{2}, 16σ^{2}+2L^{2}D^{2}\}}{(t+9)^{2/3}}$ is related to the preset parameters $σ, L, D$ and time $t$.
