Review for NeurIPS paper: A Simple and Efficient Smoothing Method for Faster Optimization and Local Exploration

Summary and Contributions: This paper describes a way to smooth functions that interpolates between the Moreau envelope and the "randomized sampling" smoothing which approximates a function f with fRS(x) E_z[f(x gamma z)] where is a standard Gaussian and gamma is a smoothing parameter. Such an approach is useful because many optimization methods only apply to smooth functions, but can be extended to nonsmooth functions with controlled error by using such smoothings. The key claimed drawback with random sampling is that it introduces an approximation error for a given level of smoothing that is dimension-dependent (on the order of sqrt(d)). The key claimed drawback with the Moreau envelope is that it is difficult to compute (as it involves solving an optimization problem). The proposed interpolation essentially replaces the minimization problem in the Moreau envelope with a "soft" approximation.