  Several large-scale machine learning tasks, such as data summarization, can
be approached by maximizing functions that satisfy submodularity. These
optimization problems often involve complex side constraints, imposed by the
underlying application. In this paper, we develop an algorithm with
poly-logarithmic adaptivity for non-monotone submodular maximization under
general side constraints. The adaptive complexity of a problem is the minimal
number of sequential rounds required to achieve the objective.
  Our algorithm is suitable to maximize a non-monotone submodular function
under a $p$-system side constraint, and it achieves a $(p +
O(\sqrt{p}))$-approximation for this problem, after only poly-logarithmic
adaptive rounds and polynomial queries to the valuation oracle function.
Furthermore, our algorithm achieves a $(p + O(1))$-approximation when the given
side constraint is a $p$-extendible system.
  This algorithm yields an exponential speed-up, with respect to the
adaptivity, over any other known constant-factor approximation algorithm for
this problem. It also competes with previous known results in terms of the
query complexity. We perform various experiments on various real-world
applications. We find that, in comparison with commonly used heuristics, our
algorithm performs better on these instances.
