<p>We study the problem of maximizing the difference between a non-monotone submodular function and a modular function. We adopt the convention in the literature and refer to this problem as the non-monotone Regularized Submodular Maximization (RSM) problem. Since the RSM problem is inapproximable, our goal is to design algorithms which are guaranteed to provide the bi-criteria and PASS approximations. For the cardinality-constrained problem, we propose two algorithms: one is based on the maximization of a scaled objective function, and the other one is a refinement of the algorithm given in our previous paper. Our analysis shows that both algorithms have nontrivial approximation bounds. For the matroid-constrained problem, we also design an algorithm based on the scaled function technique. Although its approximation guarantee is weaker than the existing algorithms in the literature, it requires less function evaluations which makes it more practical in applications.</p>