  We consider non-monotone DR-submodular function maximization, where
DR-submodularity (diminishing return submodularity) is an extension of
submodularity for functions over the integer lattice based on the concept of
the diminishing return property. Maximizing non-monotone DR-submodular
functions has many applications in machine learning that cannot be captured by
submodular set functions. In this paper, we present a
$\frac{1}{2+\epsilon}$-approximation algorithm with a running time of roughly
$O(\frac{n}{\epsilon}\log^2 B)$, where $n$ is the size of the ground set, $B$
is the maximum value of a coordinate, and $\epsilon > 0$ is a parameter. The
approximation ratio is almost tight and the dependency of running time on $B$
is exponentially smaller than the naive greedy algorithm. Experiments on
synthetic and real-world datasets demonstrate that our algorithm outputs almost
the best solution compared to other baseline algorithms, whereas its running
time is several orders of magnitude faster.
