Generalizing Stochastic Smoothing for Differentiation and Gradient Estimation

Authors: Felix Petersen, Christian Borgelt, Aashwin Ananda Mishra, Stefano Ermon
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords: differentiable, sorting, rendering, ranking, variance reduction, continuous, cryo-et, differentiable simulator, shortest-path, stochastic relaxation

Abstract:
We deal with the problem of gradient estimation for stochastic differentiable relaxations of algorithms, operators, simulators, and other non-differentiable functions. Stochastic smoothing conventionally perturbs the input of a non-differentiable function with a differentiable density distribution with full support, smoothing it and enabling gradient estimation. Our theory starts at first principles to derive stochastic smoothing with reduced assumptions, without requiring a differentiable density nor full support, and presenting a general framework for relaxation and gradient estimation of non-differentiable black-box functions $f:\mathbb{R}^n\to\mathbb{R}^m$. We develop variance reduction for gradient estimation from 3 orthogonal perspectives. Empirically, we benchmark 6 distributions and up to 24 variance reduction strategies for differentiable sorting and ranking, differentiable shortest-paths on graphs, differentiable rendering for pose estimation, as well as differentiable cryo-electron tomography simulations.

Decision: reject
Reviewer scores: 3, 8, 3, 6

Reviews and discussion:
<thread>
creation date:
1729772917205

thread_type:
official_review

<thread_object>
creator: reviewer_rmt6

<content>
summary:
The work addresses gradient estimation for stochastic differentiable relaxations of non-differentiable functions. The developed theory does not require a differentiable density or full support as it was in prior works.

strengths:
The work contains rigorous theorem statements and proofs. The work contains extensive empirical results.

weaknesses:
The work considers the problem of estimating the gradient of the relaxation of the algorithm or of the loss function. In Section 2.3 the authors formalize the algorithm smoothing and the objective smoothing. It seems that the paper does not provide the theoretical convergence analysis of the backbone stochastic optimization algorithms, but only introduces the techniques of smoothing and variance reduction and then tests the theoretical findings in practice.

questions:
Is it possible to demonstrate the advantage of your smoothing approach over the previous works in theory, not only in practice, in some way? For instance, by incorporating the proposed gradient estimator into the SGD or Adam optimizer and providing a better convergence result? 

There exist many general variance reduction techniques in the field of optimization (in such algorithms as SVRG, L-SVRG, Page, SAGA, Variance Reduced Adam, SPIDER etc.). Do the proposed variance reduction techniques generalize the techniques from the optimization field or orthogonal to them? Can they be combined together?

Smoothing should introduce some bias to the estimator. There are some works on the analysis of SGD with biased estimators [1, 2]. They both consider smoothing techniques. Does the proposed smoothing technique fit into the frameworks of assumptions in these papers?

[1] Ahmad Ajalloeian, Sebastian U. Stich, On the Convergence of SGD with Biased Gradients
[2] Yury Demidovich, Grigory Malinovsky, Igor Sokolov, Peter Richtárik, A Guide Through the Zoo of Biased SGD
</content>
</thread_object>

</thread>
<thread>
creation date:
1730516350159

thread_type:
official_review

<thread_object>
creator: reviewer_fxvh

<content>
summary:
The authors study stochastic gradients, with applications in stochastic smoothing and variance reduction of gradient estimation. 

I recommend rejection of this paper because I feel there is a lack of novelty and impact for machine learning.

I present a more detailed summary of the paper along with my criticisms under the weakness section.

strengths:
The experiments in Section 4 seem quite interesting, particularly the use of smoothing for relaxing discrete functions to continuous functions.

weaknesses:
The goals of the paper are somewhat diverse, so I will go over each result and state my criticisms.

1. In Lemma 3, the authors present a result for smoothing an objective $f$ using a distribution $\mu$ that is possibly non-differentiable. However, the non-differentiable set for $\mu$ is assumed to be $0$-measure. In any learning application I can think of, there seems to be no meaningful difference between "differentiable" and "almost everywhere differentiable". For instance, one can always convolve $\mu$ with a tiny Gaussian, of variance less than machine precision, and immediately get a differentiable density, while not affecting the outcome in any meaningful way. There are also no quantitative analysis which indicate that choosing a non-differentiable $\mu$ would offer any advantages. 
2. Theorem 7 discusses smoothing with an additional rescaling matrix involved. The result appears unsurprising, and the proof appears to use just calculus. I think the authors want to apply this to finding a optimal rescaling matrix $\mathbf{L}$, but the consequences of Theorem 7 are never discussed.
3. The authors discuss numerous variance reduction techniques in Section 2.1, but there is no attempt at any quantitative and theoretical comparison of these approaches. The authors did include some simple synthetic experiments, but it is questionable how well the observations will generalize to realistic scenarios.
4. In Section 2.3, the authors discuss smoothing of the algorithm vs the objective. I am not convinced by the setup of $\ell(h(y))$ where $\ell$ is the loss, $h$ is an algorithm, and $y$ is the model output. 
5. In Section 4, the authors present a series of experiments that compare the effectiveness of different distributions and different variance reduction techniques. I am not sure how well the conclusions here generalize.

questions:
1. Can the authors comment on how their theoretical or experimental results might be applicable for discrete-to-continuous relaxations? Particularly, how would quantities such as lipschitz smoothness, convexity, or general ease of optimization be affected by different choices of distributions?

2. Can the authors comment on the run-time of their algorithms compared to the baselines in Section 4?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714399961

thread_type:
official_review

<thread_object>
creator: reviewer_n4mm

<content>
summary:
This paper presents improved results on gradient estimation by stochastic smoothing. In particular, the density function is assumed to be absolutely continuous as opposed to being differentiable. The authors discuss three ways to reduce variance of the estimated gradients. Finally, the paper presents application of this smoothing on various problem where gradients of non-differentiable functions are required.

This paper builds on existing ideas, but it does present some strong and comprehensive results that are both insightful.

strengths:
The paper is very well written, with ideas clearly conveyed. Mathematical descriptions are precise.

I like the fact that multiple density functions are considered and discussed.

The discussion on variance reduction is insightful.

Many different applications are presented. And at the end, some recommendations are made about the "optimal" densities, as well as on the sampling methods.

weaknesses:
None.

questions:
Can this method be applied to problems where the $ L^1 $ loss is minimized?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730967370524

thread_type:
official_review

<thread_object>
creator: reviewer_nbyq

<content>
summary:
This work presents methods for stochastic smoothing of non-differentiable functions, motivated by applications where there is the need to optimize non-differentiable functions. Some experiments are provided.

strengths:
.

weaknesses:
The novelty is insufficient. The idea of smoothing using Gaussian perturbations is a well-established technique in 0-th order optimization or non-smooth optimization. The authors present further general smoothing conditions, requiring that the density function be absolutely continuous, but these derivations are mostly standard exercises in mathematical analysis. The variance reduction techniques are also not novel. Overall, my view is that there is very little theoretical novelty.

The authors provide applications and experiments, but I do not think they are strong enough to warrant publication on the basis of the experiments.

questions:
.
</content>
</thread_object>

</thread>


Metareview:
metareview:
While the paper aims to address interesting problems, several reviewers have found its theoretical contribution, in light of the existing literature, to be rather minimal, with its impact on machine learning deemed questionable. It has been noted that the theoretical derivations are at times trivial, and the results occasionally lack meaningful applications. Furthermore, the numerical examples fall short of being convincing and fail to complement the shortcomings of the theoretical results.