The Flip Side of the Reweighted Coin: Duality of Adaptive Dropout and Regularization
Year: 2022

Abstract:
Among the most successful methods for sparsifying deep (neural) networks are those that adaptively mask the network weights throughout training. By examining this masking, or dropout, in the linear case, we uncover a duality between such adaptive methods and regularization through the so-called “η-trick” that casts both as iteratively reweighted optimizations. We show that any dropout strategy that adapts to the weights in a monotonic way corresponds to an effective subquadratic regularization penalty, and therefore leads to sparse solutions. We obtain the effective penalties for several popular sparsification strategies, which are remarkably similar to classical penalties commonly used in sparse optimization. Considering variational dropout as a case study, we demonstrate similar empirical behavior between the adaptive dropout method and classical methods on the task of deep network sparsification, validating our theory.

heading: 1 Introduction
text: In machine learning, it is often valuable for models to be parsimonious or sparse for a variety of reasons, from memory savings and computational speedups to model interpretability and generalizability. Classically, this is achieved by solving a regularized empirical risk minimization (ERM) problem of the form
minimize w
Lpwq ` λΩpwq, (1)
where L is the data-dependent empirical risk and Ω is a sparsity-inducing regularization penalty. Ideally, Ωpwq is equal to }w}0 :“ # ti : wi ‰ 0u or a function of }w}0 [6], in which case an appropriately chosen λ balances the trade-off between the suboptimality of L and the sparsity of the solution. However, the use of }w}0 directly as a penalty is difficult, as it makes local search impossible, so alternative approaches are necessary for high-dimensional problems. The classical solution to this is to relax the problem using a smooth surrogate Ω that approximates }w}0 [5, 18]. When we know the regularization penalty Ω, we can understand the types of solutions they encourage; however, many popular methods for sparsifying deep (neural) networks do not appear to fit the form (1). For example, variational dropout [27, 32], “`0 regularization” [29], and magnitude pruning [45] are the only methods compared in a recent large-scale study by Gale et al. [15], and all achieve sparsity by adaptively masking or scaling the parameters of the network while optimizing the loss function in w. Although these methods are well-motivated heuristically, it is unclear how to make a principled choice between them aside from treating them as black boxes and comparing their empirical performance. However, if these methods could be cast as solutions to a regularized ERM problem, then we could compare them on the basis of their regularization penalties.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We show that, in fact, these sparsity methods do correspond to regularization penalties Ω, which we can obtain, compute, and compare. As we show in Figure 1, these penalties bear striking resemblance to classical sparsity-inducing penalties such as the LOGSUM [9] penalty and the minimax concave penalty (MCP) [44]. More broadly, we analyze adaptive dropout methods, which apply the dropout technique of Srivastava et al. [35] with adaptive parameters. By considering adaptive dropout in the linear setting, we uncover a duality between adaptive dropout methods and regularized ERM. We make this connection via the “η-trick” [4], a tool with a long history of application in sparse optimization via iteratively reweighted least squares (IRLS) (see the history presented by Daubechies et al. [11]).
We prove that all adaptive dropout methods whose amount of dropout varies monotonically with the magnitudes of the parameters induce an effective subquadratic (and hence sparsity-inducing [5]) penalty Ω. This further supports the experimental evidence that such methods excel at inducing sparsity. We also demonstrate how to use our result to determine the effective penalty for adaptive dropout methods, using as examples the sparsity methods listed above as well as the standout method [3], which has an effective penalty on the layer activations, rather than the parameters, explaining why the standout method sparsifies activations. We then numerically compute the effective penalties1 and plot them together in Figure 1.
We validate our new theory by applying variational dropout on the task of deep network sparsification, and we show that the performance is similar to non-dropout methods based on the same effective penalty. This suggests that not only is considering the effective penalty a sound means for comparing sparsity methods, but also that classical regularized ERM is itself an effective means for inducing sparsity in deep networks and serves as a valuable tool for future work on deep network sparsity.
For theoreticians, this work provides a general framework for obtaining the effective regularization penalty for adaptive dropout algorithms, enabling regularized ERM analysis tools to be applied to these methods. For practitioners, this work enables the application of classical regularization intuition when choosing between sparsifying approaches. For methods developers, this work provides a strong baseline against which new adaptive dropout methods should be compared: the effective penalty Ω.

heading: 2 Background
text: Notation. We denote the extended reals and the non-negative reals by R “ R Y t´8,8u and R` “ r0,8q, respectively. The operator diag p¨q takes a vector and returns a matrix with that vector along the diagonal entries or takes a matrix and returns the same matrix with all non-diagonal entries set to zero. The matrix J denotes a matrix of all ones. We denote element-wise multiplication and exponentiation by d; i.e., ru d vsj “ ujvj and rUdpsij “ Upij . Division of vectors and scalar functions of vectors denote element-wise operations. Order statistics of the magnitudes of
1Our code is available at https://github.com/dlej/adaptive-dropout.
elements in a vector u P Rd are denoted by upjq such that |up1q| ě |up2q| ě . . . |updq|. The function σ : RÑ r0, 1s denotes the sigmoid σptq “ 1{p1` e´tq.

heading: 2.1 Dropout as Tikhonov Regularization
text: We can understand adaptive dropout methods by breaking them down into two components: the regularizing effect of dropout itself and the effect of adaptively updating the dropout-induced regularization. For the former, it is well-known [40, 39, 35, 32] that dropout induces Tikhonov-like regularization for standard binary and Gaussian dropout. The same result holds more broadly given a second moment condition, which we need in order to be able to consider methods like HARDCONCRETE “`0 regularization” [29]. In general, we use the term dropout to refer to methods that mask or scale the weights w by independent “mask” variables s „ MASKpαq with sampling parameters α P r0, 1sd. We emphasize that in this formulation, it is the parameters that are masked, rather than the nodes of a network as in the original formulation of dropout [35], although in linear regression there is no difference. We assume that the masks are unbiased (i.e., that E rsjs “ 1), and that E “ s2j ‰
“ α´1j . Note that with the independence assumption, this implies that Covpsq “ diag pαq´1 ´ I. Both standard unbiased binary dropout, where sj take value α´1j with probability αj and 0 otherwise, as well as Gaussian dropout with sj „ N ` 1, α´1j ´ 1 ˘ , satisfy these assumptions.
Dropout solves the optimization problem
minimize w
Es rLpsdwqs (2)
via stochastic optimization such as gradient descent where each iteration performs a partial optimization of Lps d wq with a random s. It is most insightful to consider when L is the loss for linear regression of target variables y P Rn given data X P Rnˆd:
Lpwq “ 1 2n }y ´Xw}22. (3)
In this case, under our assumptions on s, we recover the known Tikhonov result [e.g., 32]
Es rLpsdwqs “ Lpwq ` 1
2 wJ
ˆ
´ diag pαq´1 ´ I ¯ d 1 n XJX
˙
w. (4)
For simplicity, we assume that the data is standardized, or that diag ` 1 nX JX ˘ “ I, which is inexpensive to satisfy in practice, but our analysis can be extended to the general case. Under this assumption, we see that dropout elicits a diagonal Tikhonov regularization with scale diag pαq´1´ I.

heading: 2.2 The “η-trick”
text: The second component of adaptive dropout is the adaptive update of the dropout-induced regularization. To understand this, we introduce the so-called “η-trick” [4] applied to the regularization penalty in (1). By introducing an auxiliary variable η P H Ď Rd`, we can replace Ωpwq with a dual formulation as a function of η that majorizes Ωpwq and is quadratic in w for fixed η. In other words, we can find a function f : H Ď Rd` Ñ R such that
Ωpwq “ min ηPH
1
2
´ wJdiag pηq´1 w ` fpηq ¯ . (5)
If such a function f exists, then the regularized ERM problem (1) can be rewritten as a joint optimization in w and η of the dual regularized ERM formulation
minimize w,η Lpwq ` λ 2 ´ wJdiag pηq´1 w ` fpηq ¯ . (6)
This joint optimization can be performed, for example, by alternating minimization over w and η. For linear regression problems, this gives rise to the iteratively reweighted least squares (IRLS) algorithm, a popular method for sparse recovery [10, 11]. We note that iteratively reweighted `1 schemes have also held a significant place in sparse optimization [47, 9, 42], but because dropout regularization is quadratic, we limit our consideration to iteratively reweighted `2 (Tikhonov) regularization like (6).
Table 1: Common regularization penalties have dual formulations that are often straightforward to obtain. See
The simplest example of a penalty Ω that fits the form (5) is Ωpwq “ |w|, for which fpηq “ η, and it is used in the IRLS formulation of `1 regularization. More broadly, we can consider the class of functions for which Ω is concave in wd2. These functions are said to be subquadratic, and are known to have a sparsity-inducing effect [5]. In fact, these are the only functions Ω that can fit this form. This is because wd2 ÞÑ ´2Ωpwq is the Legendre–Fenchel (LF) transform of ´ηd´1 ÞÑ fpηq, and thus Ω is concave in wd2. By the Fenchel–Moreau theorem, there is conversely a unique function f satisfying (5) that is convex in ´ηd´1, which can be obtained by the LF transform. That is, Ω and f are dual functions. Additionally, for differentiable penalties, the minimizing η given a fixed w is
pηpwq “ p2∇wd2Ωpwqq d´1 , (7)
which means that if Ωpwq has a closed-form expression, then so does the minimizer pηpwq. The simplicity of this form means that iteratively reweighted Tikhonov regularization is simple to implement for any differentiable penalty, leading to its popularity as a sparse optimization technique.
We enumerate a few penalties along with their dual formulations in Table 1. For separable penalties, we list the scalar function applied to a single element. Where H is restricted, we include it with fpηq. Hard Thresholding. Of particular note is HARDTHRESH, the indicator penalty of level sets of }w}0, which gives rise to the iterative hard thresholding (IHT) algorithm [7]. We remark that to the best of our knowledge, what we show in Table 1 is the first characterization of IHT as an iteratively reweighted `2 solution to a regularized ERM problem, rather than as a heuristic algorithm. This connection is important for understanding the MAGNITUDEPRUNING [45] algorithm in Section 4.4.

heading: 3 Adaptive Dropout as Iteratively Reweighted Stochastic Optimization
text: We can now consider an adaptive dropout algorithm [3, 27, 29], which both optimizes the weights w using dropout and updates the dropout parameters α according to some update rule depending on w. To facilitate our analysis, we can equivalently consider the algorithm to be updating parameters ηj :“ λ ` α´1j ´ 1 ˘´1 , which is a monotonic and invertible function of αj , with
αj “ ηj
ηj ` λ . (8)
An adaptive dropout method could resemble, for example, the following gradient descent strategy with step size parameter ρ given an update function pη : Rd Ñ H:
wt`1 “ wt ´ ρ∇wL ` st dwt ˘ , st „ MASKpαtq, αtj “ pηjpwtq
pηjpwtq ` λ . (9)
The stochastic update of w corresponds to the expected loss Es rLpsdwqs, but we must also characterize the η update. We can make the assumption, which we will justify later, that pηpwq is the minimizer given w of a joint objective function J pw,ηq with a function f such that
J pw,ηq “ Es rLpsdwqs ` λ
2 fpηq. (10)
This brings us to our main result, in which we uncover a duality between the adaptive dropout objective function J pw,ηq and an effective regularized ERM objective function as in (1).
Theorem 1. If L has the form (3) for data X such that 1ndiag ` XJX ˘ “ I, then for every λ ą 0 there exists a function f such that pηpwq “ arg minη J pw,ηq if and only if there exists a function Ω that is concave in wd2 such that
min ηPH
J pw,ηq “ Lpwq ` λΩpwq. (11)
Furthermore, if f exists, then the corresponding Ω is unique, and if Ω exists, then there is a unique such f that is convex in ´ηd´1.
Proof. For linear regression under the standardized data assumption, combining the definition of η as a function of α with (4) makes J pw,ηq of the form (6). Then by the properties of the LF transform2 as discussed in Section 2.2, we obtain the existence and uniqueness of f and Ω.
That is, every subquadratic penalty Ω has a dual formulation via the η-trick and therefore has a corresponding adaptive dropout strategy. The converse holds as well, provided the dropout update function pη can be expressed as a minimizer of the joint objective. While this may seem restrictive, if pη is separable, we have the following general result.
Corollary 2. If pαjpwjq :“ pηjpwjq pηjpwjq`λ is a monotonically increasing differentiable function of |wj |, then there exist separable f and Ω satisfying Theorem 1.
Proof. Because the relationship between α and η is monotonic and invertible, pηjpwjq is also monotonically increasing. Thus, using (7), Ωpwjq “ şw2j a 1 2pηpt1{2qdt`Ca, for which B2 pBw2j q2 Ωpwjq ď 0.
Therefore, any adaptive dropout method that updates the dropout parameters α monotonically as a function of the magnitudes of the elements of w is equivalent to regularized ERM with a subquadratic penalty Ω. It is well-known that subquadratic penalties are sparsity-inducing [5], which agrees with the “rich get richer” intuition that larger wj , which receive larger αj , are penalized less and therefore are more likely to grow even larger, while conversely smaller wj receive smaller αj and are even more penalized. Corollary 2 holds generally for the η-trick and is not limited to adaptive dropout.
We emphasize that linear regression is the setting in which Theorem 1 gives an exact duality, but that we can still expect a similar correspondence more broadly. For instance, Wager et al. [39] showed that for generalized linear models, dropout elicits a similar effect to (4), albeit with a somewhat more complex dependence on w and the data. In Section 5, we empirically consider deep networks and demonstrate that the behavior is very similar between adaptive dropout and algorithms that solve the corresponding effective regularized ERM problem.

heading: 4 Several Sparsity Methods and Their Effective Penalties
text: Armed with the fact that adaptive dropout strategies correspond to regularization penalties, we now have a way to mathematically compare adaptive dropout methods. Table 2 lists the methods that we compare and a corresponding characterization of the dual formulation. These methods vary in their parameterizations, and most do not admit closed-form expressions for their effective penalties. However, given these characterizations, we can numerically compute the effective penalty and make a principled comparison, which we plot in Figure 1.
Because some of the methods we consider use slightly different variants of the dropout algorithm, we first make clear how these fit into our analysis framework.
Reparameterization Tricks. The problem of noise in stochastic gradients, especially when αj is very small, can limit the applicability of dropout methods for sparsity. One way researchers have found to reduce variance is through “reparameterization tricks” such as the local reparameterization trick [40, 27] and the additive noise reparameterization trick [32], both used in VARIATIONALDROPOUT, which consider alternative noise models without changing the optimization problem.
To consider the MAGNITUDEPRUNING algorithm, we develop another reparameterization trick. Inspired by the additive reparameterization trick from Molchanov et al. [32], we introduce another
2Results on the LF transform do not apply to functions with discontinuities at t´8,8u, such as ´ηd´1 ÞÑ fpηq for the `0 and HARDTHRESH(k) penalties, so our theorem does not prove the existence of such functions.
variable v and add the constraint v “ w, under which Lpsdwq “ Lpw ` ps´ 1q d vq. Then for least squares with standardized data, (4) becomes
Es rLpw ` ps´ 1q d vqs “ Lpwq ` 1
2 vJ
´ diag pαq´1 ´ I ¯ v. (12)
Under this parameterization, we can now use low-variance stochastic optimization for w and deterministic optimization for v, along with a strategy for enforcing the equality constraint v “ w such as ADMM [8], thus reducing the overall variance. A simple proximal variable update strategy under this reparameterization (see Appendix B) gives rise to an adaptive proximal gradient descent algorithm, which we use to describe the MAGNITUDEPRUNING algorithm.
Biased Masks. It is not uncommon for dropout strategies to use biased masks in the sense that E rsjs ‰ 1, e.g., for sj „ BERNOULLIpαjq. Under a few mild assumptions on the parameterization of this distribution, we can consider adaptive dropout in this setting as well. Suppose that µ :“ µpαq “ E rss is an invertible function of α. Define rsj :“ sj{µj , rαj :“ µ2j{E “ s2j ‰
, and rw :“ µdw. Then rs is an unbiased mask, and since sdw “ rsd rw, the expected loss has the same form as in (4), but with rα and rw in place of α and w. Let rηj :“ λ ` rα´1j ´ 1 ˘´1
, and suppose there exists a function ψ such that µj “ ψprηjq, which is true if the mapping between rα and µ is one-to-one. Now consider the expected dual regularized ERM formulation
minimize w,rη L pµdwq ` λ 2 ´ pµdwqJ diag prηq´1 pµdwq ` fprηq ¯ ,
subject to µj “ ψprηjq, @j. (13)
Thus, an adaptive dropout strategy that jointly optimizes rη and w given s „ MASKpαq solves the regularized ERM problem for rw, where α is set according to rη.

heading: 4.1 Standout
text: One of the earliest methods to use adaptive probabilities with dropout was the STANDOUT method of Ba and Frey [3], who proposed to augment a neural network with an additional parallel “standout” network of the same architecture that controlled the dropout probabilities for each activation, which they showed results in sparse activations. Interestingly, the authors noted that the method worked just as well if the standout net was not trained but instead simply copied the weights of the primary network at each iteration, which fits our adaptive dropout framework.
Consider a single hidden layer neural network with ReLU activations puq` “ max tu, 0u. Denote the pre-activations from the first layer as z “ W1x. The output of the network is given by py “ wJ2 ` sd pzq` ˘
, where the mask s „ MASK pσpzqq is from the standout network. Now let us consider the network as a function of the first layer activations pzq`. Using (4) and the fact that σptq´1 ´ 1 “ e´t, we know that the expected squared loss in this setting is
1 2 Es ” › ›y ´wJ2 psd pzq`q › › 2 2 ı “ 1 2 › ›y ´wJ2 pzq` › › 2 2 ` 1 2 pzqJ`diag ` e´z dw2wJ2 ˘ pzq`. (14)
However, terms where zj ă 0 make no contribution to the effective penalty, so we can substitute pzjq` for zj in e´z. This enables us to extract pηppzq`q as in Section 2.1
pηj ppzjq`q “ λepzjq`
rw2s2j . (15)
We note that (15) represents the implicit update of η each iteration as the standout network weights are copied from the primary network. By Corollary 2, we know that STANDOUT is therefore an adaptive dropout strategy with a subquadratic effective penalty Ω applied to the activations pzq`:
Ωppzq`q “ 1
2λ
ÿ
j
ż pzjq2`
0
rw2s2je´ ? tdt “ 1
λ
ÿ
j
rw2s2j ´ 1´ ppzjq` ` 1q e´pzjq` ¯ . (16)
This penalty is a smooth approximation to the `0 penalty, as shown in Figure 1, and thus naturally sparsifies the activations as W1 is trained. Additionally, λΩppzq`q has no dependence on λ, just as the adaptive dropout parameter update has no dependence on λ.

heading: 4.2 Variational Dropout
text: Variational Bayes interpretations of dropout arose with the works of Kingma et al. [27] and Gal and Ghahramani [14], providing an automated means of choosing the dropout parameter through variational inference. Molchanov et al. [32] later showed that if each weight is allowed to have its own dropout parameter, VARIATIONALDROPOUT results in sparse solutions.
The authors of VARIATIONALDROPOUT consider maximum a posteriori inference of w using the improper log-uniform prior, for which pplog |wj |q 9 c or pp|wj |q 9 1{|wj |. This is equivalent to solving the LOGSUM(0)-regularized ERM problem
minimize w
Lpwq ` ÿ
j
logp|wj |q. (17)
Obviously, this is minimized by taking w “ 0 for common loss functions, which is uninteresting, and Hron et al. [20] discuss other issues with the framework. However, VARIATIONALDROPOUT does not solve the problem in (17), and instead performs inference over a new variable rw, using an approximate posterior3 qnη,wprwq such that rw “ sdw, where s „ MASKpαq for Gaussian dropout, having α and η related by (8). Then maximizing the variational lower bound is equivalent to solving
minimize w,η
Ew rLpsdwqs ` 1
n DKL pqnη,wprwq}pprwqq , (18)
where DKLp¨}¨q is the Kullback–Leibler (KL) divergence. With the choice of the log-uniform prior, the KL divergence has no dependence on w and is purely a function of η [27]. Hron et al. [20] show that this quantity can be expressed in terms of Dawson’s integral F puq “ e´u2 şu
0 et
2
dt:
DKL pqnη,wp rwq}pp rwqq “ ż nη
0
F p a
t{2q? 2t dt, (19)
which we can compute via numerical integration using standard software implementations of F puq. Clearly then, the Monte Carlo variational Bayes optimization of w and η in VARIATIONALDROPOUT is an adaptive dropout strategy with λ “ 1n and fpηq “ 2DKL ` q 1 λη,w prwq}pprwq ˘
, and we can numerically compute the effective penalty Ω. VARIATIONALDROPOUT also uses additive and local reparameterization tricks to reduce variance.
As shown in Figure 1, the effective penalty for λ “ 1 is quite similar to the LOGSUM(2) penalty for λ “ 2. We explore this connection further experimentally in Section 5.

heading: 4.3 Hard Concrete “L0 Regularization”
text: While the desired regularization is typically an `0 penalty, its non-differentiability makes it difficult to perform gradient-based optimization, which motivates finding smooth approximations to the `0 penalty. Louizos et al. [29] propose to first consider Lpswq ` λ2 }sw}0, using the decomposition sw “ sdw for binary s, where }sw}0 “ }s}0. We take this opportunity to note that we can consider this problem using adaptive dropout with fpηq “ Es r}s}0s “ ř
j αj if we use biased masks sj „ BERNOULLIpαjq. Interestingly, when λ “ 1, the resulting penalty Ω turns out to be equal to the minimax concave penalty [44] MCPp1, 1q, giving the MCP an additional interpretation as a stochastic binary smoothing of the `0 penalty.
3The parameter α from Molchanov et al. [32] is distinct from ours but is related to η by α´1 “ nη.
However, Louizos et al. [29] do not solve this problem, but instead choose a distribution for s such that the random variables s themselves are differentiable with respect to α, allowing them to extract gradient information for α from L psdwq. They propose the following biased distribution, called the HARDCONCRETEβ,γ,ζpajq distribution:
zj “ σ pplog uj ´ logp1´ ujq ` log ajq{βq , uj „ UNIFORMr0, 1s (20) sj “ min t1,max t0, pζ ´ γqzj ` γuu . (21)
They then use as their penalty fprηq “ 2 ř j Prpsj ą 0q “ 2σplogpajq ´ β logp´γ{ζqq under the biased dropout reparameterization. The relationships between E rsjs, aj , rαj , and rηj are all invertible, so we can numerically determine the corresponding penalty Ω.
We plot the resulting penalty in Figure 1 using the default values β “ 23 , γ “ ´0.1, ζ “ 1.1 [29].

heading: 4.4 Magnitude Pruning
text: MAGNITUDEPRUNING [43, 45] is a straightforward way to induce sparsity by zeroing out small values. Here we specifically refer to the strategy of Zhu and Gupta [45], who eliminate all but the k largest parameters each iteration. Initially k “ d, and it is decayed as a function of iteration number until it reaches the desired sparsity level according to a general-purpose pruning schedule. This is equivalent to IHT [7] (except with decreasing k) and therefore almost surely corresponds to a proximal gradient variant of adaptive dropout where pαjpvq “ 1 tj P TOP-kpwqu, or pηjpvq “ 81 tj P TOP-kpvqu, implemented as in Appendix B. According to Table 1, the effective penalty is the HARDTHRESH(k) penalty, which we plot in Figure 1. On a philosophical note, this is by definition the “correct” penalty to use when searching for solutions with a constraint on the number of nonzeros, since it is the characteristic function of that set of solutions. The η-trick along with alternating optimization turns this combinatorial search problem into a sequence of tractable gradient-based (for w) and closed-form (for η) updates. It is therefore no surprise that Gale et al. [15] observed that this “simple” magnitude pruning algorithm matched or outmatched the other more sophisticated methods.

heading: 5 Empirical Comparison for VARIATIONALDROPOUT
text: With complex methods such as the adaptive dropout methods we discuss above, it is often difficult to isolate what drives their success. Under our theory, such methods should be able to be decomposed into dropout noise-related effects and η-trick effects. Diving further into the VARIATIONALDROPOUT algorithm, we compare it against other η-trick strategies, examining the effects of dropout noise, η-trick optimization strategy, and regularization with the underlying penalty.
We apply the methods on the task of sparsifying a LeNet-300-100 network on the MNIST dataset, a common benchmark for sparsification methods [17, 16, 12]. Experimental details along with layer-wise sparsification results are given in Appendix C. We compare the following methods. Except for VARIATIONALDROPOUT methods, we use the LOGSUM penalty.
• VARDROP+LR+AR. VARIATIONALDROPOUT as proposed by Molchanov et al. [32], using both the local reparameterization trick and the additive reparameterization trick.
• VARDROP+LR. VARIATIONALDROPOUT, using the local reparameterization trick but not the additive reparameterization trick.
• VARDROP. VARIATIONALDROPOUT with no reparameterization tricks. • η-TRICK. Joint gradient descent in w and logpηq of (6). This would be equivalent to
VARIATIONALDROPOUT with no noise in linear regression.
• ADAPROX. Proximal gradient descent in w of (6) using η “ pηpwq at each iteration. • ADATIKHONOV. Gradient descent in w of (6) using η “ pηpwq at each iteration. • LOGSUM. Gradient descent in w of (1) directly.
We plot the results in Figure 2. With all of the methods compared, we see similar behavior: the networks become more sparse over time as well as more accurate. In general, the methods appear to exhibit a sparsity–accuracy trade-off, even when they optimize identical objective functions (consider
VARDROP+LR+AR and VARDROP+LR, or ADAPROX and η-TRICK). This trade-off seems to be determined by the early iterations, depending on whether the method sparsifies the network quickly or not. We also observe that the stochastic noise due to dropout in VARDROP leads to very slow convergence, while the variance-reduced VARDROP+LR converges exceedingly similarly to its non-random counterpart η-TRICK. In addition, VARDROP+LR+AR behaves remarkably similarly to ADAPROX, which was inspired by the additive reparameterization trick (see discussion on reparameterization tricks in Section 4). These results suggests that the success of VARIATIONALDROPOUT is well explained by interpreting it as optimization of a dual formulation of a regularized ERM problem. Further, they suggest that the variance due to dropout noise at best yields similar performance to the non-dropout counterpart and at worst can drastically slow down convergence. Interestingly, the simple LOGSUM-regularized ERM approach performs as well as any of the other methods considered, and is nearly identical in behavior to ADATIKHONOV, suggesting that the sparsification performance of VARIATIONALDROPOUT is entirely due to the effective LOGSUM penalty.

heading: 6 Discussion
text: Given the duality between adaptive dropout and regularization that we have presented, it is no surprise that such methods excel at sparsifying deep networks. However, many questions still remain.
For one, is there any benefit to dropout noise itself in adaptive dropout optimization, beyond the η-trick connection? There are known benefits of standard dropout for deep network optimization [1, 19, 31, 41], but do these benefits transfer to adaptive dropout strategies? A crucial component of VARIATIONALDROPOUT, as demonstrated in Section 5, appears to be that its successful implementations remove most of the noise due to dropout. On the other hand, methods like HARDCONCRETEL0NORM from Louizos et al. [29] exploit the fact that sparse masks yield more efficient computation, and they do not seem to suffer from variance-related optimization issues even without taking efforts to mitigate such effects. This could be because they use a biased dropout distribution, which results in significantly lower variance of stochastic gradients. On the other hand, it is not clear that dropout noise is necessary to obtain these computational speedups; other methods where the network is sparse during training, such as MAGNITUDEPRUNING, should have the similar properties.
It is evident from Figure 2 that, even when using the same objective function, the optimization strategy can have a significant impact on the result. It is beyond the scope of this work to examine the convergence rates, even for convex problems, of the adaptive algorithms we consider in Section 5, although many of them can be cast as stochastic majorization-minimization (MM) algorithms, for which some theory exists [30]. However, for non-convex penalties and losses, such as in sparse deep network optimization, there are no guarantees about the quality of the solution. It is also not clear what benefit η-trick optimization provides in this setting, if any. For linear problems it has the advantage of drastically simplifying implementations of penalized methods by reducing them to successive least squares problems, but with modern automatic differentiation packages it is straightforward to implement any differentiable sparsity-inducing penalty. To the best of our knowledge, the only large-scale comparison of sparsity methods for deep networks is that of Gale et al. [15], and they do not consider classical penalty-based methods.
We have fully analyzed the adaptive-dropout–regularization duality in the linear regression case, and we know that the exact correspondence between dropout and Tikhonov regularization does not hold
in other settings, such as deep networks. However, from the neural tangent kernel (NTK) [23, 28] perspective, very wide networks become linearized, and parameter-level dropout becomes dropout for linear regression, like we study. Furthermore, recent work has shown that for very high dimensional settings, the choice between classification and regression loss functions is often irrelevant [33, 21]. For finite-width settings, good quadratic approximations to the general effective regularization of dropout have been developed [39, 41], which relate to the Fisher information. These approximations could be used to develop adaptive sparsification strategies that enjoy the data-sensitive properties of dropout, such as in logistic regression or deep networks.
The duality presented in this paper can be the basis of developing more efficient principled sparsification schemes as future work. In particular, using penalties that have been proposed in the compressed sensing literature such as scaled lasso [37], which is adaptive to noise level, or SLOPE [36], which is shown to be minimax optimal in feature selection, can lead to adaptive dropout schemes with better performance in sparsifying deep networks. In addition, analytical tools such as debiasing [25], which has been used for near-optimal feature selection [24], could be employed to design improved sparsity methods.
Acknowledgments and Disclosure of Funding
This work was supported by NSF grants CCF-1911094, IIS-1838177, and IIS-1730574; ONR grants N00014-18-12571, N00014-20-1-2534, and MURI N00014-20-1-2787; AFOSR grant FA9550-18-10478; and a Vannevar Bush Faculty Fellowship, ONR grant N00014-18-1-2047.

Review summaries:
For linear regression, the paper shows that several popular heuristics used in deep learning correspond to regularized empirical risk minimization with sub-quadratic penalties, thereby, arguing that these methods indeed induce sparsity. The analysis leverages the so-called \eta-trick, where the penalty is replaced with its variational (minimization) form. Empirical results are also provided to support the theory. 

This paper examines stochastic perturbation methods, such as dropout, through the lens of the "eta-trick".  This trick allows the optimization objective to be re-written as a joint objective in terms of the original parameters and auxiliary parameters eta.  This new objective consists of the original loss in addition to a quadratic penalty in the parameters and a formulation-specific function of eta.  The paper shows that any adaptive dropout method that updates the dropout parameters monotonically as a function of the weight magnitudes is equivalent to regularized risk minimization with a subquadratic penalty, which is known to induce sparsity.  The paper analyses standout, variational dropout, L0 regularization, and magnitude pruning from this perspective, deriving the corresponding penalty term (Table 2) and allowing for comparison.  The paper then experimentally compares variants of variational dropout, finding that performance is well-described by the eta-trick reformulation since stochastic variants suffer from the introduced noise.