Timezone: »

A Simple and Efficient Smoothing Method for Faster Optimization and Local Exploration
Kevin Scaman · Ludovic DOS SANTOS · Merwan Barlier · Igor Colin

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1143
This work proposes a novel smoothing method, called Bend, Mix and Release (BMR), that extends two well-known smooth approximations of the convex optimization literature: randomized smoothing and the Moreau envelope. The BMR smoothing method allows to trade-off between the computational simplicity of randomized smoothing (RS) and the approximation efficiency of the Moreau envelope (ME). More specifically, we show that BMR achieves up to a $\sqrt{d}$ multiplicative improvement compared to the approximation error of RS, where $d$ is the dimension of the search space, while being less computation intensive than the ME. For non-convex objectives, BMR also has the desirable property to widen local minima, allowing optimization methods to reach small cracks and crevices of extremely irregular and non-convex functions, while being well-suited to a distributed setting. This novel smoothing method is then used to improve first-order non-smooth optimization (both convex and non-convex) by allowing for a local exploration of the search space. More specifically, our analysis sheds light on the similarities between evolution strategies and BMR, creating a link between exploration strategies of zeroth-order methods and the regularity of first-order optimization problems. Finally, we evidence the impact of BMR through synthetic experiments.

Author Information

Kevin Scaman (Huawei Noah's Ark Lab)
Ludovic DOS SANTOS (Huawei)
Merwan Barlier (Huawei Technologies)
Igor Colin (Huawei)

More from the Same Authors