Fast Compute for ML Optimization Nick Polson, Vadim Sokolov Abstract We study optimization for losses that admit a variance-mean scale-mixture representation. Under this representation, each EM iteration is a weighted least squares update in which latent variables determine observation and parameter weights; these play roles analogous to Adam’s second-moment scaling and AdamW’s weight decay, but are derived from the model. The resulting Scale Mixture EM (SM-EM) algorithm removes user-specified learning-rate and momentum schedules. On synthetic ill-conditioned logistic regression benchmarks with p ∈ { 20 , … , 500 } p\in\{20,\ldots,500\} , SM-EM with Nesterov acceleration attains up to 13 × 13\times lower final loss than Adam tuned by learning-rate grid search. For a 40-point regularization path, sharing sufficient statistics across penalty values yields a 10 × 10\times runtime reduction relative to the same tuned-Adam protocol. For the base (non-accelerated) algorithm, EM monotonicity guarantees nonincreasing objective values; adding Nesterov extrapolation trades this guarantee for faster empirical convergence. Keywords: scale mixture of normals, EM algorithm, Pólya–Gamma augmentation, Robbins–Monro, Nesterov acceleration, logistic regression 1 Introduction Modern stochastic gradient descent (SGD) requires a step size (learning rate) \alpha_{t} that must be carefully tuned. Classical Robbins–Monro theory ( Robbins and Monro 1951 ) establishes that convergence requires \sum_{t}\alpha_{t}=\infty and \sum_{t}\alpha_{t}^{2}<\infty , but this leaves wide latitude in choosing a specific schedule. In practice, fixed step sizes are the default because backtracking line searches are prohibitively expensive for large-scale problems. A fundamental advance was the recognition that the Robbins–Monro recursion is, at its core, a proximal algorithm. Toulis and Airoldi 2017 showed that replacing the explicit SGD update \theta_{n}=\theta_{n-1}-\gamma_{n}\nabla\ell(\theta_{n-1}) with the implicit update \theta_{n}=\theta_{n-1}-\gamma_{n}\nabla\ell(\theta_{n}) yields an iteration that is unconditionally stable: the implicit step shrinks the explicit one by the observed Fisher information, \Delta\theta_{n}^{\mathrm{im}}\approx(I+\gamma_{n}\hat{\mathcal{I}}_{n})^{-1}\Delta\theta_{n}^{\mathrm{sgd}} , preventing divergence without sacrificing asymptotic efficiency. Toulis et al. 2021 formalized this insight by showing that the implicit update is exactly the proximal point algorithm of Rockafellar 1976 : \theta_{n}=\prox_{\gamma_{n}F}(\theta_{n-1})=\arg\min_{\theta}\left\{\tfrac{1}{2\gamma_{n}}\|\theta-\theta_{n-1}\|^{2}+F(\theta)\right\}, which contracts iterates toward the solution at every step. Their proximal Robbins–Monro framework unifies explicit SGD, implicit SGD, and stochastic proximal gradient methods, and provides convergence guarantees with improved stability. However, all variants still require a user-specified step size schedule \gamma_{n} satisfying the Robbins–Monro conditions, and the implicit equation must be solved approximately (e.g., by a Newton step involving the Hessian). Two further lines of work address the step size problem through different means. Momentum methods—Polyak’s heavy ball ( Polyak 1964 ) and Nesterov acceleration ( Nesterov 1983 ) —speed convergence by accumulating past gradient information, but still require a global step size tied to the Lipschitz constant L . Adaptive gradient methods—AdaGrad ( Duchi et al. 2011 ) , Adam ( Kingma and Ba 2015 ) , AdamW ( Loshchilov and Hutter 2019 ) —maintain per-parameter scaling via running estimates of gradient moments. Adam updates \theta_{t+1}=\theta_{t}-\frac{\alpha}{\sqrt{\hat{v}_{t}}+\epsilon}\,\hat{m}_{t}\,, (1) where \hat{m}_{t} and \hat{v}_{t} are bias-corrected first- and second-moment estimates. AdamW decouples weight decay from the gradient scaling: \theta_{t+1}=(1-\lambda)\theta_{t}-\frac{\alpha}{\sqrt{\hat{v}_{t}}+\epsilon}\hat{m}_{t} . Despite their practical success, these methods rely on heuristic moment estimates, and their hyperparameters ( \beta_{1},\beta_{2},\epsilon,\lambda ) require problem-specific tuning. Reddi et al. 2018 showed that Adam can fail to converge even on convex problems. In this paper, we take the proximal viewpoint of Toulis and Airoldi 2017 ; Toulis et al. 2021 a step further. Using the data-augmentation framework of Polson and Scott 2013 and Polson and Scott 2016 , we show that for losses admitting a scale mixture of normals representation, the proximal step can be solved in closed form as a weighted least squares problem, with the step size determined entirely by the model. Specifically, the EM algorithm ( Dempster et al. 1977 ) applied to the augmented representation yields an iteration in which latent variables \omega (observation weights) and \lambda (parameter weights) play roles analogous to the Fisher information preconditioner in implicit SGD, but are derived from the loss structure rather than estimated from gradient samples. The resulting Scale Mixture EM (SM-EM) algorithm eliminates the learning rate, momentum, and decay schedules entirely; the remaining regularization parameter can be selected by marginal likelihood. Because the latent weights adapt to local curvature, the method takes conservative updates in high-curvature regions and larger updates in flatter regions. Section 6 shows that this mechanism yields lower loss than Adam on the ill-conditioned synthetic benchmarks considered here, without tuning optimizer schedules. The remaining computational bottleneck is the O(p^{3}) linear solve in the M-step. Polson and Sokolov 2026 show that Halton’s sequential Monte Carlo method ( Halton 1994 ) reduces this cost substantially. By writing the M-step system in Neumann-series form and iteratively correcting residuals, the sequential method achieves geometric convergence at rate \rho^{N} (where \rho is the spectral radius of the iteration matrix). A subsampled variant further reduces the per-iteration cost from O(p^{2}s) to O(ps) for s correction steps. The full complexity comparison is: \underbrace{O(p^{3})}_{\text{Direct (Cholesky)}}\;\gg\;\underbrace{O(p^{2}s)}_{\text{Gauss--Seidel}}\;\gg\;\underbrace{O(ps)}_{\text{Sampled Seq.\ MC}}\,. In a scaling study on diagonally dominant systems at p=5{,}000 , the sampled sequential method is approximately 24\times faster than Gauss–Seidel ( Polson and Sokolov 2026 ) ; these timings illustrate asymptotic scaling and depend on implementation details. Scope. The approach applies to losses admitting a scale mixture of normals representation (logistic, hinge, check, bridge penalties); limitations and extensions are discussed in Section 8 . Section 2 reviews stochastic approximation and adaptive gradient methods. Section 3 develops the scale mixture representation. Section 4 shows how it replaces Robbins–Monro and connects to Adam/AdamW. Section 5 connects the framework to proximal operators and MAP estimation. Section 6 provides empirical comparisons. Section 7 gives further applications. Section 8 concludes. 2 Background 2.1 Robbins–Monro Stochastic Approximation The Robbins–Monro procedure ( Robbins and Monro 1951 ) seeks a root \theta^{\star} of M(\theta)=\mathbb{E}[H(\theta,\xi)]=0 , where \xi is a random variable, via the recursion \theta_{t+1}=\theta_{t}-\alpha_{t}\,H(\theta_{t},\xi_{t})\,. (2) When H(\theta,\xi)=\nabla_{\theta}\ell(\theta;\xi) for a loss \ell , this reduces to stochastic gradient descent (SGD)—Robbins–Monro and SGD are the same algorithm viewed from different perspectives: root-finding versus optimization. Classical convergence requires the step sizes \alpha_{t} to satisfy \sum_{t}\alpha_{t}=\infty (to reach any optimum) and \sum_{t}\alpha_{t}^{2}<\infty (to control variance). The ODE method of Kushner and Yin 2003 interprets the iterates as a noisy discretization of d\theta/dt=M(\theta) , and Polyak and Juditsky 1992 show that averaging the iterates \bar{\theta}_{T}=T^{-1}\sum_{t=1}^{T}\theta_{t} achieves the optimal O(1/T) rate. The convergence proof relies on a supermartingale argument: a Lyapunov function V(\theta_{t})=\|\theta_{t}-\theta^{\star}\|^{2} satisfies \mathbb{E}[V(\theta_{t+1})\mid\theta_{t}]\leq V(\theta_{t})-2\alpha_{t}M(\theta_{t})^{\top}(\theta_{t}-\theta^{\star})+\alpha_{t}^{2}C , and the Robbins–Monro conditions ensure that the accumulated noise converges almost surely. Despite well-developed theory, the practical difficulty remains: the constants hidden in the convergence conditions depend on the problem, and choosing \alpha_{t} too large causes divergence while choosing it too small causes stagnation. 2.2 Momentum and Acceleration Polyak’s heavy ball method ( Polyak 1964 ) adds a momentum term to gradient descent: \theta_{t+1}=\theta_{t}-\alpha\,\nabla f(\theta_{t})+\mu\,(\theta_{t}-\theta_{t-1})\,, (3) achieving a convergence rate of O(\sqrt{L/\mu}\log(1/\epsilon)) on strongly convex quadratics, where L/\mu is the condition number—a quadratic improvement over gradient descent. Nesterov 1983 introduced the accelerated gradient method, which evaluates the gradient at a lookahead point: v_{t}=\theta_{t}+\mu_{t}(\theta_{t}-\theta_{t-1})\,,\quad\theta_{t+1}=v_{t}-\alpha\,\nabla f(v_{t})\,, (4) and achieves the optimal O(1/t^{2}) rate for convex objectives with L -Lipschitz gradients ( Nesterov 2004 ) . Su et al. 2016 interpret Nesterov acceleration as a discretization of the ODE \ddot{X}+(3/t)\dot{X}+\nabla f(X)=0 , connecting it to continuous-time dynamics. Both methods require the step size \alpha=1/L , which depends on the global Lipschitz constant. In the stochastic setting, momentum does not improve worst-case rates beyond O(1/\sqrt{T}) ( Sutskever et al. 2013 ) , and Nesterov acceleration requires variance reduction techniques to transfer its deterministic gains. 2.3 Proximal Robbins–Monro Toulis and Airoldi 2017 introduced implicit stochastic gradient descent, in which the gradient is evaluated at the next iterate: \theta_{t+1}=\theta_{t}-\alpha_{t}\,\nabla\ell(\theta_{t+1};\xi_{t})\,. (5) Because \theta_{t+1} appears on both sides, the update is solved approximately via a Newton step: \theta_{t+1}\approx\theta_{t}-\alpha_{t}\,(I+\alpha_{t}H_{t})^{-1}\nabla\ell(\theta_{t};\xi_{t}) , where H_{t} is the Hessian of the loss. The factor (I+\alpha_{t}H_{t})^{-1} shrinks the explicit SGD step by the observed Fisher information, providing unconditional stability without sacrificing asymptotic efficiency ( Toulis and Airoldi 2017 ) . Toulis et al. 2021 formalized this connection by showing that the implicit update ( 5 ) is exactly a proximal point step, \theta_{t+1}=\prox_{\alpha_{t}\ell}(\theta_{t}) , thereby establishing the Robbins–Monro recursion as fundamentally a proximal algorithm ( Toulis et al. 2014 ) . However, the implicit equation still requires approximate solution (e.g., one Newton iteration per data point), and a step size schedule \alpha_{t} satisfying the Robbins–Monro conditions remains necessary. 2.4 Adaptive Gradient Methods AdaGrad ( Duchi et al. 2011 ) introduced per-parameter step sizes by accumulating squared gradients: \theta_{t+1}=\theta_{t}-\alpha\,g_{t}/\sqrt{G_{t}+\epsilon} , where G_{t}=\sum_{s=1}^{t}g_{s}^{2} . This achieves data-dependent regret bounds but suffers from monotonically decaying step sizes. Adam ( Kingma and Ba 2015 ) replaced the cumulative sum with exponential moving averages: \displaystyle m_{t} \displaystyle=\beta_{1}m_{t-1}+(1-\beta_{1})\,g_{t}\,, (6) \displaystyle v_{t} \displaystyle=\beta_{2}v_{t-1}+(1-\beta_{2})\,g_{t}^{2}\,, (7) \displaystyle\theta_{t+1} \displaystyle=\theta_{t}-\frac{\alpha}{\sqrt{\hat{v}_{t}}+\epsilon}\,\hat{m}_{t}\,, (8) where g_{t}=\nabla\ell(\theta_{t};\xi_{t}) and \hat{m}_{t},\hat{v}_{t} are bias-corrected. The per-parameter scaling 1/(\sqrt{\hat{v}_{t}}+\epsilon) adapts the effective step size to the curvature of the loss along each coordinate. Reddi et al. 2018 showed that Adam can fail to converge even on convex problems, owing to the non-monotone behavior of v_{t} ; Défossez et al. 2022 later established convergence under appropriate step size decay. The scaling 1/\sqrt{\hat{v}_{t}} approximates a diagonal preconditioner related to the Fisher information matrix ( Amari 1998 ) . Adam can be viewed as a diagonal approximation to natural gradient descent, but one derived from gradient samples rather than from the model structure. AdamW ( Loshchilov and Hutter 2019 ) decouples weight decay from the adaptive gradient scaling: \theta_{t+1}=(1-\lambda_{\mathrm{wd}})\,\theta_{t}-\frac{\alpha}{\sqrt{\hat{v}_{t}}+\epsilon}\,\hat{m}_{t}\,. (9) For SGD, L^{2} regularization and weight decay are equivalent; for Adam, they are not. Only decoupled weight decay preserves the correspondence between weight decay and a Gaussian prior on the parameters. The weight decay \lambda_{\mathrm{wd}} is a fixed hyperparameter that must be tuned jointly with the learning rate. All adaptive methods can be written as preconditioned SGD: \theta_{t+1}=\theta_{t}-\alpha_{t}P_{t}^{-1}g_{t} , where P_{t}=I for SGD, P_{t}=\mathrm{diag}(\sqrt{v_{t}}) for Adam, and P_{t}=F(\theta_{t}) for natural gradient. For generalized linear models, the natural gradient method reduces to Fisher scoring, which iterates \theta_{t+1}=\theta_{t}-I(\theta_{t})^{-1}\nabla\ell(\theta_{t}) where I(\theta)=X^{\top}WX is the expected Fisher information with W=\mathrm{diag}(w_{i}(1-w_{i})) for logistic regression. Fisher scoring is equivalent to IRLS ( Green 1984 ) . We show that the scale mixture framework derives P_{t} from the loss function’s generative structure: the SM-EM M-step uses the precision P_{t}=X^{\top}\hat{\Omega}_{t}X , which is a stabilized Fisher scoring step—the Pólya–Gamma weights \hat{\omega}_{i}=\tanh(z_{i}/2)/(2z_{i}) replace the IRLS weights w_{i}(1-w_{i}) that can cause numerical instability when observations are well separated. 2.5 Convergence Rates: When Does Acceleration Help? The achievable convergence rate depends critically on the problem structure and access to gradient information. Table 1 summarizes the landscape. Table 1: Convergence rates for convex objectives. Nesterov acceleration achieves O(1/t^{2}) only in the deterministic or variance-reduced settings; pure stochastic methods are limited by gradient noise. Setting Convex Strongly convex Method Deterministic O(1/t^{2}) linear O(\rho^{t}) Nesterov/FISTA Stochastic O(1/\sqrt{t}) O(1/t) SGD Finite-sum + VR O(1/t^{2}) linear SVRG/SAGA + accel. In the pure stochastic setting, irreducible gradient variance \mathbb{E}[\|g_{t}-\nabla f(\theta_{t})\|^{2}]=\sigma^{2}>0 prevents faster-than- O(1/\sqrt{t}) convergence for convex problems, regardless of momentum ( Lan 2012 ) . Variance reduction methods—SVRG ( Johnson and Zhang 2013 ) , SAGA ( Defazio et al. 2014 ) —reduce the effective variance to zero near the optimum by maintaining gradient tables, enabling acceleration. Allen-Zhu 2017 combined Nesterov momentum with SVRG to achieve the optimal \tilde{O}(\sqrt{nL/\mu}\log(1/\epsilon)) complexity for finite sums. The scale mixture EM framework sidesteps the stochastic-noise barrier: each full-batch EM iteration is deterministic, so Nesterov extrapolation can be applied without variance reduction. The base (non-accelerated) SM-EM inherits the EM monotonicity property, guaranteeing nonincreasing objective values. Adding Nesterov extrapolation sacrifices this monotonicity—the extrapolated iterates can temporarily increase the objective, as is standard for accelerated methods—but yields faster convergence empirically. Section 6 reports substantial speedups (32–55% on the ill-conditioned benchmarks). 3 Scale Mixtures and Data Augmentation Following Polson and Scott 2013 , consider a general regularized objective L(\beta)=\sum_{i=1}^{n}f(y_{i},x_{i}^{\top}\beta)+\sum_{j=1}^{p}g(\beta_{j}/\tau)\,, (10) where f is a loss function (negative log-likelihood) and g is a penalty (negative log-prior). Interpreting loss and penalty as negative log-densities, the optimizer \hat{\beta}=\arg\min L(\beta) is the mode of the pseudo-posterior p(\beta\mid y)\propto e^{-L(\beta)}=\underbrace{\prod_{i=1}^{n}p(z_{i}\mid\beta,\sigma)}_{\text{likelihood}}\;\cdot\;\underbrace{\prod_{j=1}^{p}p(\beta_{j}\mid\tau)}_{\text{prior}}\,, (11) where z_{i} is a working response ( y_{i}-x_{i}^{\top}\beta for regression, x_{i}^{\top}\beta for classification). This recasting is the key step: optimization of L(\beta) becomes finding the mode of a distribution, and every tool of Bayesian computation—EM, MCMC, variational methods—becomes available. In particular, one can sample from the full posterior over (\beta,\omega,\lambda) by Gibbs sampling, or find \hat{\beta} by the EM algorithm. The pseudo-posterior ( 11 ) is typically non-Gaussian and may be non-convex. The scale mixture representation resolves both difficulties by writing each factor as a marginal of a higher-dimensional Gaussian joint distribution, introducing latent variables \omega_{i} (for observations) and \lambda_{j} (for parameters). Conditional on (\omega,\lambda) , the augmented model is Gaussian in \beta —a weighted least squares problem. The augmentation “convexifies” the objective by lifting it to a higher dimension: although the marginal L(\beta) may have complex curvature, the complete-data log-posterior is quadratic in \beta for fixed (\omega,\lambda) . This lifted representation admits two dual algorithmic strategies ( Polson and Scott 2016 ) . The first is marginalization (EM): integrate out (\omega,\lambda) in the E-step to form Q(\beta\mid\beta^{(t)}) , then maximize the resulting weighted least squares in the M-step. The second is profiling (MM/majorize–minimize): construct a convex envelope of L(\beta) by optimizing over (\omega,\lambda) , yielding a majorizing function that is minimized at each step. Both strategies produce the same iterates—the EM conditional expectations \hat{\omega}_{i}=E[\omega_{i}\mid\beta,z] equal the envelope minimizers—a correspondence Polson and Scott 2016 call hierarchical duality . The envelope view connects directly to proximal algorithms (Section 5 ). The majorizing function defines a quadratic upper bound whose minimum is a proximal step with an adaptive step size determined by the latent variables. The tighter the majorizer, the faster the convergence: the half-quadratic envelope ( Geman and Reynolds 1992 ; Geman and Yang 1995 ) exploits the specific curvature of each loss via its sub-differential, outperforming generic Lipschitz bounds. This is the mechanism that gives SM-EM its adaptive, per-observation step sizes. 3.1 Variance-Mean Mixtures of Normals The key representation is as a variance-mean mixture of normals. If p(z_{i}\mid\beta,\sigma)=\int_{0}^{\infty}\phi\!\left(z_{i}\mid\mu_{z}+\kappa_{z}\,\omega_{i}^{-1},\;\sigma^{2}\omega_{i}^{-1}\right)dP(\omega_{i})\,, (12) where \phi(\cdot\mid m,s^{2}) denotes the Gaussian density with mean m and variance s^{2} , then the latent variable \omega_{i} simultaneously controls both the conditional mean (via \kappa_{z}\,\omega_{i}^{-1} ) and the conditional variance (via \sigma^{2}\omega_{i}^{-1} ). The parameter \kappa_{z} handles asymmetric losses; \kappa_{z}=0 recovers the classical normal variance mixture. An analogous representation holds for the penalty: p(\beta_{j}\mid\tau)=\int_{0}^{\infty}\phi\!\left(\beta_{j}\mid\mu_{\beta}+\kappa_{\beta}\,\lambda_{j}^{-1},\;\tau^{2}\lambda_{j}^{-1}\right)dP(\lambda_{j})\,. (13) This representation exists for a broad class of losses: squared error, absolute error, check loss (quantile regression), hinge loss (SVMs), and logistic loss all admit representations of the form ( 12 ) with specific mixing distributions P(\omega_{i}) ; see Polson and Scott 2011 and Polson and Scott 2013 for a catalog. Carlin et al. 1992 demonstrated that this structure extends to nonnormal and nonlinear state-space models: introducing latent scales \lambda_{t} and \omega_{t} into the state and observation equations x_{t}|x_{t-1},\lambda_{t}\sim N(F_{t}x_{t-1},\lambda_{t}\Sigma) and y_{t}|x_{t},\omega_{t}\sim N(H_{t}x_{t},\omega_{t}\Upsilon) gives complete conditionals x_{t}|\cdot\sim N(B_{t}b_{t},B_{t}) where the precision B_{t}^{-1}=\frac{\Sigma^{-1}}{\lambda_{t}}+\frac{H_{t}^{\top}\Upsilon^{-1}H_{t}}{\omega_{t}}+\frac{F_{t+1}^{\top}\Sigma^{-1}F_{t+1}}{\lambda_{t+1}} (14) is a weighted sum controlled by the latent variables—exactly the weighted least squares structure of our M-step ( 23 ). The conditional for \omega_{t} is \mathrm{GIG}(\frac{1}{2},1,(y_{t}-H_{t}x_{t})^{2}/\tau^{2}) , the same gradient-to-weight identity as Proposition 1 . Moreover, the complete conditional for model parameters (e.g., F ) has the form N(B_{F}b_{F},B_{F}) with B_{F}^{-1}=\sigma^{-2}\sum_{t}x_{t-1}^{2}/\lambda_{t}+\sigma_{F}^{-2} —the weighted sufficient statistics \sum x_{t-1}^{2}/\lambda_{t} are precomputed at each Gibbs sweep, foreshadowing the complete sufficient statistics structure exploited by Polson and Scott 2011 for fast model exploration. The two fundamental mixing families—the generalized inverse Gaussian (GIG) and the Pólya family—generate these losses through specific integral identities. The GIG mixture gives \frac{\alpha^{2}-\kappa^{2}}{2\alpha}e^{-\alpha|\theta-\mu|+\kappa(\theta-\mu)}=\int_{0}^{\infty}\phi\left(\theta\mid\mu+\kappa\omega,\omega\right)\,p_{\mathrm{gig}}\big(\omega\mid 1,0,\sqrt{\alpha^{2}-\kappa^{2}}\big)\,d\omega\,, (15) while the Pólya mixture gives \frac{1}{B(\alpha,\kappa)}\frac{e^{\alpha(\theta-\mu)}}{(1+e^{\theta-\mu})^{2(\alpha-\kappa)}}=\int_{0}^{\infty}\phi\left(\theta\mid\mu+\kappa\omega,\omega\right)\,p_{\mathrm{pol}}(\omega\mid\alpha,\alpha-2\kappa)\,d\omega\,, (16) where p_{\mathrm{gig}} and p_{\mathrm{pol}} denote the GIG and Pólya densities, respectively. In the improper limits, these identities specialize to three cases that generate the most common machine learning objectives: \displaystyle a^{-1}\exp\left\{-2c^{-1}\max(a\theta,0)\right\} \displaystyle=\int_{0}^{\infty}\phi(\theta\mid-av,cv)\,dv\,, (17) \displaystyle c^{-1}\exp\left\{-2c^{-1}\rho_{q}(\theta)\right\} \displaystyle=\int_{0}^{\infty}\phi(\theta\mid-(2q-1)v,cv)\,e^{-2q(1-q)v}\,dv\,, (18) \displaystyle\left(1+e^{\theta-\mu}\right)^{-1} \displaystyle=\int_{0}^{\infty}\phi(\theta\mid\mu-v/2,v)\,p_{\mathrm{pol}}(v\mid 0,1)\,dv\,, (19) where \rho_{q}(\theta)=\frac{1}{2}|\theta|+(q-\frac{1}{2})\theta is the check loss. Identity ( 17 ) generates the hinge loss (SVMs), ( 18 ) generates the check loss (quantile and Lasso regression), and ( 19 ) generates the logistic link. With GIG and Pólya mixing alone, one obtains all of \theta^{2},\quad|\theta|,\quad\max(\theta,0),\quad\rho_{q}(\theta),\quad\frac{1}{1+e^{-\theta}},\quad\frac{1}{(1+e^{-\theta})^{r}}\,, corresponding to ridge, Lasso, SVM, check loss, logit, and multinomial models, respectively. More general mixing families (e.g., stable distributions) generate bridge penalties |\theta|^{\alpha} . Each identity provides the E-step weight \hat{\omega} via the gradient-to-weight identity of Proposition 1 , so the entire SM-EM algorithm is determined once the mixing family is specified. 3.2 Latent Variables as Adaptive Weights Conditional on (\omega,\lambda) , the complete-data log posterior is \log p(\beta\mid\omega,\lambda)=c_{0}-\frac{1}{2\sigma^{2}}\sum_{i=1}^{n}\omega_{i}\!\left(z_{i}-\mu_{z}-\kappa_{z}\omega_{i}^{-1}\right)^{2}-\frac{1}{2\tau^{2}}\sum_{j=1}^{p}\lambda_{j}\!\left(\beta_{j}-\mu_{\beta}-\kappa_{\beta}\lambda_{j}^{-1}\right)^{2}, (20) which is a heteroscedastic Gaussian model: a weighted least squares problem with observation weights \omega_{i}/\sigma^{2} and parameter weights \lambda_{j}/\tau^{2} . The conditional expectations of the latent variables are determined by the gradients of f and g . Proposition 1 (Gradient-to-weight identity; Proposition 1 of Polson and Scott 2013 ) . The conditional first moments satisfy \displaystyle(z_{i}-\mu_{z})\,\hat{\omega}_{i} \displaystyle=\kappa_{z}+\sigma^{2}f^{\prime}(z_{i})\,, (21) \displaystyle(\beta_{j}-\mu_{\beta})\,\hat{\lambda}_{j} \displaystyle=\kappa_{\beta}+\tau^{2}g^{\prime}(\beta_{j})\,. (22) The weight \hat{\omega}_{i} assigned to observation i is the ratio of the gradient f^{\prime}(z_{i}) to the residual z_{i}-\mu_{z} . The algorithm never requires the full mixing distribution P(\omega_{i}) —only these first moments. Proposition 2 (Weighted least squares M-step; Proposition 2 of Polson and Scott 2013 ) . Given \hat{\Omega}=\mathrm{diag}(\hat{\omega}_{1},\ldots,\hat{\omega}_{n}) and \hat{\Lambda}=\mathrm{diag}(\hat{\lambda}_{1},\ldots,\hat{\lambda}_{p}) , the M-step update is \hat{\beta}=\left(\tau^{-2}\hat{\Lambda}+X^{\top}\hat{\Omega}\,X\right)^{-1}\!\left(X^{\top}(\mu_{z}\hat{\omega}+\kappa_{z}\mathbf{1})+\tau^{-2}(\mu_{\beta}\hat{\lambda}+\kappa_{\beta}\mathbf{1})\right). (23) The E-step computes \hat{\omega}_{i} and \hat{\lambda}_{j} via ( 21 )–( 22 ); the M-step solves the resulting weighted least squares ( 23 ). No step size is specified by the user—the latent variables determine the effective step size at each iteration. 4 Replacing Robbins–Monro with Scale Mixtures 4.1 The Latent Variable Step Size The Robbins–Monro update ( 2 ) can be written as \theta_{t+1}=\theta_{t}-\alpha_{t}\,\nabla\ell(\theta_{t}) , where \alpha_{t} is a scalar step size. In the scale mixture framework, the M-step update ( 23 ) is a regularized Newton step with an iteration-dependent, observation-specific precision matrix \hat{\Omega}_{t} . Each diagonal entry \hat{\omega}_{i,t} adapts to the local curvature of the loss at observation i . To see the analogy precisely, consider the scalar case. The E-step gives \hat{\omega}_{t}=f^{\prime}(z_{t})/(z_{t}-\mu_{z}) and the M-step gives \beta_{t+1}=\frac{\hat{\omega}_{t}\,z_{t}+\tau^{-2}\hat{\lambda}_{t}\,\mu_{\beta}}{\hat{\omega}_{t}+\tau^{-2}\hat{\lambda}_{t}}\,, (24) which can be rewritten as \beta_{t+1}=\beta_{t}-\underbrace{\frac{1}{\hat{\omega}_{t}+\tau^{-2}\hat{\lambda}_{t}}}_{\text{effective step size}}\left(\hat{\omega}_{t}(\beta_{t}-z_{t})+\tau^{-2}\hat{\lambda}_{t}(\beta_{t}-\mu_{\beta})\right). (25) The effective step size (\hat{\omega}_{t}+\tau^{-2}\hat{\lambda}_{t})^{-1} is adaptive: when \hat{\omega}_{t} is large (strong gradient signal), the step is small and precise; when \hat{\omega}_{t} is small (weak signal), the prior dominates and regularizes. This is a Robbins–Monro recursion where the step size is determined by the model. 4.2 Connection to Adam Adam’s per-parameter scaling 1/(\sqrt{\hat{v}_{t}}+\epsilon) approximates the inverse square root of the second moment of the gradient. In the scale mixture framework, the role of \hat{v}_{t} is played by \hat{\omega}_{t} . Remark 1 (Adam as a heuristic approximation) . Consider the scale mixture update with \hat{\omega}_{i}=f^{\prime}(z_{i})/(z_{i}-\mu_{z}) and the Adam update with \hat{v}_{t}=\beta_{2}\hat{v}_{t-1}+(1-\beta_{2})g_{t}^{2} . Both produce per-parameter scaling of the gradient. The difference is the source of the scaling: • Adam estimates \mathbb{E}[g_{t}^{2}] via an exponential moving average—a heuristic that treats all loss functions identically. • The scale mixture approach computes \hat{\omega}_{t} from the structure of the loss function. For logistic loss, \hat{\omega}_{i}=\tanh(z_{i}/2)/(2z_{i}) ; for quantile loss, \hat{\omega}_{i}=|y_{i}-x_{i}^{\top}\beta|^{-1} . Each loss function yields its own natural curvature estimate, with no hyperparameters ( \beta_{1},\beta_{2},\epsilon ) to tune. 4.3 Connection to AdamW AdamW uses a fixed weight decay \lambda_{\mathrm{wd}} applied to all parameters. In the scale mixture framework, weight decay arises from the penalty term g(\beta_{j}) via the latent variable \hat{\lambda}_{j} . From Proposition 1 , the adaptive weight decay for parameter j is \hat{\lambda}_{j}=\frac{\kappa_{\beta}+\tau^{2}g^{\prime}(\beta_{j})}{\beta_{j}-\mu_{\beta}}\,. (26) For an L^{2} penalty g(\beta)=\beta^{2}/2 , this gives \hat{\lambda}_{j}=\tau^{2} , recovering fixed weight decay. For non-quadratic penalties, \hat{\lambda}_{j} is parameter-specific and iteration-dependent: • Lasso ( g(\beta)=|\beta| ): \hat{\lambda}_{j}=\tau^{2}/|\beta_{j}| , which applies strong decay to small coefficients and weak decay to large ones. • Double-Pareto ( g(\beta)=\gamma\log(1+|\beta|/a) ): \hat{\lambda}_{j}=\gamma\tau^{2}/\!\bigl((a+|\beta_{j}|)\,|\beta_{j}|\bigr) , which interpolates between L^{1} and L^{0} behavior. • Horseshoe : heavy-tailed P(\lambda_{j}) allows \hat{\lambda}_{j} to be arbitrarily small for large |\beta_{j}| , providing near-zero shrinkage for signals. For the Lasso and double-Pareto, \hat{\lambda}_{j}\to\infty as \beta_{j}\to 0 , signaling that the coefficient should be removed from the active set. In practice, components with |\beta_{j}|<\delta (for a small threshold \delta , e.g. 10^{-8} ) are set to zero and excluded from the M-step linear system; see also Polson and Scott 2013 , §3.2. In each case, the scale mixture framework replaces AdamW’s single hyperparameter \lambda_{\mathrm{wd}} with an adaptive, per-parameter weight decay derived from the prior. 4.4 The Algorithm Combining the developments above yields the Scale Mixture EM algorithm for minimizing ( 10 ). Algorithm 1 Scale Mixture EM (SM-EM) 0: Data (X,y) , initial \beta^{(0)} , prior parameters (\tau,\mu_{\beta},\kappa_{\beta}) , loss parameters (\sigma,\mu_{z},\kappa_{z}) 1: for t=0,1,2,\ldots do 2: E-step (adaptive weights): 3: Compute residuals z_{i}^{(t)}=y_{i}-x_{i}^{\top}\beta^{(t)} (or z_{i}=x_{i}^{\top}\beta^{(t)} for classification) 4: \hat{\omega}_{i}^{(t)}=(\kappa_{z}+\sigma^{2}f^{\prime}(z_{i}^{(t)}))/(z_{i}^{(t)}-\mu_{z}) [observation weights] 5: \hat{\lambda}_{j}^{(t)}=(\kappa_{\beta}+\tau^{2}g^{\prime}(\beta_{j}^{(t)}))/(\beta_{j}^{(t)}-\mu_{\beta}) [parameter weights / adaptive decay] 6: M-step (weighted least squares): 7: \hat{\Omega}^{(t)}=\mathrm{diag}(\hat{\omega}_{1}^{(t)},\ldots,\hat{\omega}_{n}^{(t)}) 8: \hat{\Lambda}^{(t)}=\mathrm{diag}(\hat{\lambda}_{1}^{(t)},\ldots,\hat{\lambda}_{p}^{(t)}) 9: \beta^{(t+1)}=(\tau^{-2}\hat{\Lambda}^{(t)}+X^{\top}\hat{\Omega}^{(t)}X)^{-1}(X^{\top}(\mu_{z}\hat{\omega}^{(t)}+\kappa_{z}\mathbf{1})+\tau^{-2}(\mu_{\beta}\hat{\lambda}^{(t)}+\kappa_{\beta}\mathbf{1})) 10: end for For large-scale problems, the M-step can use a mini-batch E_{t}\subset\{1,\ldots,n\} , yielding a stochastic EM that maintains the Robbins–Monro structure. When the M-step is partitioned into blocks—updating subsets of \beta conditionally—the algorithm becomes an ECM procedure, which retains nonincreasing objective values while simplifying each conditional maximization step. 4.5 Convergence The EM monotonicity property ( Dempster et al. 1977 ) guarantees that the objective decreases at each iteration: L(\beta^{(t+1)})\leq L(\beta^{(t)}) . This holds for the full-batch algorithm without any step size condition. For the stochastic variant, convergence follows from the online EM theory of Cappé and Moulines 2009 , which establishes that the stochastic EM iterates converge to stationary points of the Kullback–Leibler divergence at the rate of the maximum likelihood estimator. The connection to classical Robbins–Monro is structural: the SM-EM iterates have the same form as a Robbins–Monro recursion, but the convergence mechanism differs. Proposition 3 (Robbins–Monro form; scalar case) . In the scalar case ( p=1 ), define \alpha_{t}\mathrel{\mathop{:}}=(\hat{\omega}_{t}+\tau^{-2}\hat{\lambda}_{t})^{-1} . The scale mixture iterates ( 25 ) have the form \beta_{t+1}=\beta_{t}-\alpha_{t}\,H(\beta_{t})\,, where H(\beta^{\star})=0 at the MAP estimate. The step sizes satisfy: 1. \alpha_{t}>0 for all t ; 2. \alpha_{t}\to(\omega^{\star}+\tau^{-2}\lambda^{\star})^{-1}>0 as \beta_{t}\to\beta^{\star} . Proof. For part (1), both \hat{\omega}_{t} and \hat{\lambda}_{t} are conditional expectations of latent variables with strictly positive support. For the Pólya–Gamma distribution, \mathbb{E}[\omega\mid z]=\tanh(z/2)/(2z)>0 for all z\neq 0 , so \alpha_{t}=(\hat{\omega}_{t}+\tau^{-2}\hat{\lambda}_{t})^{-1}>0 . For part (2), the map \beta\mapsto\hat{\omega}(\beta) is continuous by the dominated convergence theorem. If \beta_{t}\to\beta^{\star} , then \hat{\omega}_{t}\to\omega^{\star}>0 and \hat{\lambda}_{t}\to\lambda^{\star}>0 , giving \alpha_{t}\to(\omega^{\star}+\tau^{-2}\lambda^{\star})^{-1}>0 . For the recursion form, the M-step update ( 24 ) gives (\hat{\omega}_{t}+\tau^{-2}\hat{\lambda}_{t})\beta_{t+1}=\hat{\omega}_{t}z_{t}+\tau^{-2}\hat{\lambda}_{t}\mu_{\beta} . Subtracting (\hat{\omega}_{t}+\tau^{-2}\hat{\lambda}_{t})\beta_{t} and dividing yields \beta_{t+1}-\beta_{t}=-\alpha_{t}H(\beta_{t}) with H(\beta)=\hat{\omega}(\beta-z)+\tau^{-2}\hat{\lambda}(\beta-\mu_{\beta}) . At \beta^{\star} , the gradient of the regularized log-likelihood vanishes, so H(\beta^{\star})=0 . ∎ Remark 2 . Since \alpha_{t}\to c>0 , the classical Robbins–Monro conditions \sum_{t}\alpha_{t}^{2}<\infty do not hold for the full-batch algorithm. This is not a deficiency: full-batch SM-EM converges by the EM monotonicity property (each iteration decreases the objective L(\beta) ), not by stochastic approximation theory. The RM form is structural—it reveals that the latent variables play the role of adaptive step sizes—rather than the convergence mechanism. For a stochastic variant using mini-batch sufficient statistics with a diminishing gain sequence \eta_{t} satisfying \sum_{t}\eta_{t}=\infty , \sum_{t}\eta_{t}^{2}<\infty , Polyak–Juditsky averaging yields the optimal O(1/T) rate ( Polyak and Juditsky 1992 ; Kushner and Yin 2003 ) . 5 Proximal Operators and MAP Estimation 5.1 Convex Analysis Preliminaries The connection between scale mixtures and proximal algorithms rests on several facts from convex analysis (see, e.g., Boyd and Vandenberghe 2004 , §3.3; Rockafellar and Wets 1998 ). The convex conjugate of a function f:\mathcal{R}^{d}\to\overline{\mathcal{R}} is f^{\star}(\lambda)=\sup_{x}\{\lambda^{\top}x-f(x)\} . As f^{\star} is the pointwise supremum of a family of affine functions, it is convex even when f is not. Lemma 4 (Fenchel–Moreau duality; Boyd and Vandenberghe 2004 , §3.3.2) . Let f:\mathcal{R}^{d}\to\overline{\mathcal{R}} be a closed convex function. Then there exists a convex function f^{\star}(\lambda) such that \displaystyle f(x) \displaystyle=\sup_{\lambda}\left\{\lambda^{\top}x-f^{\star}(\lambda)\right\}, (27) \displaystyle f^{\star}(\lambda) \displaystyle=\sup_{x}\left\{\lambda^{\top}x-f(x)\right\}. (28) If f(x) is instead a concave function, then \sup is replaced by \inf in both equations. Any maximizing value of \lambda in ( 27 ) satisfies \hat{\lambda}\in\partial f(x) ; if f is differentiable, \hat{\lambda}=\nabla f(x) . One function g(x) is said to majorize f(x) at x_{0} if g(x_{0})=f(x_{0}) and g(x)\geq f(x) for all x\neq x_{0} . A function f(x) is completely monotone on A\subset\mathcal{R} if its derivatives alternate in sign: (-1)^{k}f^{(k)}(x)\geq 0 for all k=0,1,2,\ldots and all x\in A . For any function f(x) , the Moreau envelope E_{\gamma}f(x) and proximal mapping \prox_{\gamma f}(x) for parameter \gamma>0 are \displaystyle E_{\gamma}f(x) \displaystyle=\inf_{z}\left\{f(z)+\frac{1}{2\gamma}\|z-x\|_{2}^{2}\right\}\leq f(x)\,, (29) \displaystyle\prox_{\gamma f}(x) \displaystyle=\arg\min_{z}\left\{f(z)+\frac{1}{2\gamma}\|z-x\|_{2}^{2}\right\}. (30) The Moreau envelope is a regularized version of f : it approximates f from below and has the same set of minimizing values as f ( Rockafellar and Wets 1998 ) . The proximal mapping returns the value that solves the minimization problem defined by the Moreau envelope—it balances two goals: minimizing f and staying near x . When f(x)=\iota_{C}(x) is the indicator of a convex set C , \prox_{f}(x)=\arg\min_{z\in C}\|x-z\|_{2}^{2} reduces to Euclidean projection. 5.2 Envelopes and Half-Quadratic Representations The scale mixture representation has a dual interpretation via envelopes ( Polson and Scott 2016 ) . A penalty function \phi(\beta) with completely monotone derivative of \phi(\sqrt{2x}) admits the half-quadratic representation \phi(\beta)=\inf_{\omega\geq 0}\left\{\frac{\omega}{2}\beta^{2}-\psi^{\star}(\omega)\right\}, (31) where \psi^{\star} is the convex conjugate and the infimum is attained at \hat{\omega}=\phi^{\prime}(\beta)/\beta ( Geman and Reynolds 1992 ) . Alternatively, the Geman–Yang location representation ( Geman and Yang 1995 ) gives \phi(\beta)=\inf_{\lambda}\left\{\frac{1}{2}(\beta-\lambda)^{2}+\psi(\lambda)\right\}, (32) where \hat{\lambda}=\prox_{\psi}(\beta) is the proximal operator of \psi ( Moreau 1965 ) . The marginalizing prior (mixture) and profiling prior (envelope) yield the same function \phi but through different operations: integration versus optimization. Polson and Scott 2016 call these “hierarchical duals.” For algorithmic purposes, the envelope representation leads to MM algorithms where each iteration minimizes a quadratic majorizer, and the mixture representation leads to EM algorithms where each iteration computes a conditional expectation. Both yield the same iterates. 5.3 Proximal Gradient as Scale Mixture Iteration For the composite objective F(\beta)=f(\beta)+\phi(\beta) where \nabla f is L -Lipschitz, the proximal gradient method iterates \beta_{t+1}=\prox_{\gamma\phi}\!\left(\beta_{t}-\gamma\nabla f(\beta_{t})\right),\quad\gamma=1/L\,. (33) This is equivalent to the scale mixture iteration with a Gaussian location envelope of f ( Polson and Scott 2016 ) : the latent variable update \hat{\lambda}_{t+1}=\gamma^{-1}\beta_{t}-\nabla f(\beta_{t}) encodes the gradient step, and the \beta -update is the proximal (shrinkage) step. The MAP estimate satisfies the fixed-point equation \beta^{\star}=\prox_{\gamma\phi}\!\left(\beta^{\star}-\gamma\nabla f(\beta^{\star})\right)=(I+\gamma\,\partial\phi)^{-1}(I-\gamma\nabla f)\,\beta^{\star}\,, (34) which decomposes into a forward operator (I-\gamma\nabla f) (gradient step) and a backward operator (I+\gamma\partial\phi)^{-1} (proximal/prior step). Nesterov acceleration ( Nesterov 1983 ) replaces \beta_{t} in ( 33 ) with an extrapolated point v_{t}=\beta_{t}+\theta_{t}(\theta_{t-1}^{-1}-1)(\beta_{t}-\beta_{t-1}) , achieving O(1/t^{2}) convergence for convex objectives ( Beck and Teboulle 2009 ) . This introduces non-monotone behavior: the objective can increase at individual iterates. The base (non-accelerated) scale mixture EM avoids this by construction—the EM property guarantees monotonic descent. When Nesterov extrapolation is applied to SM-EM, the monotonicity guarantee is lost (as for any accelerated method), but the adaptive curvature estimates from the E-step still determine per-iteration scaling without user-specified step sizes. 5.4 Improved Step Sizes via Scale Mixtures Standard proximal gradient uses the global Lipschitz constant L to set \gamma=1/L , which is conservative when the curvature varies. The scale mixture approach replaces this with observation-specific curvature estimates. For the logistic loss f(z)=\log(1+e^{z}) , the half-quadratic representation gives ( Polson et al. 2013 ) \log\cosh(z/2)=\inf_{\omega\geq 0}\left\{\frac{\omega}{2}z^{2}-\psi^{\star}(\omega)\right\},\quad\hat{\omega}(z)=\frac{\tanh(z/2)}{2z}\,. (35) The curvature estimate \hat{\omega}(z)=\tanh(z/2)/(2z) is bounded between 0 and 1/4 and varies smoothly with z . Compared to the global bound L=1/4 (the maximum of w(z)(1-w(z)) where w(z)=1/(1+e^{-z}) ), the local estimate \hat{\omega}(z) is tighter for observations far from the decision boundary, leading to larger effective step sizes where the loss is flatter. This improves on the standard Lipschitz bound and provides the scale mixture analog of the diagonal scaling in Adam. 6 Empirical Comparison We compare scale mixture EM (SM-EM) with Adam, SGD with momentum, and the proximal Robbins–Monro (PRM) method of Toulis et al. 2021 , with and without Nesterov acceleration. The experiments evaluate two questions: (i) whether SM-EM reaches lower loss than Adam without optimizer-schedule tuning, and (ii) whether the sufficient-statistics structure of the M-step reduces runtime for regularization paths. All experiments use standardized synthetic logistic-regression data. SM-EM uses Pólya–Gamma augmentation with prior precision \tau^{-2}=0.01 ; Adam uses (\beta_{1},\beta_{2},\epsilon)=(0.9,0.999,10^{-8}) , batch size 256; PRM uses implicit updates with Hessian, batch size 20. SM-EM has no learning rate; for Adam and SGD we report both default and grid-tuned learning rates. All experiments use fixed random seeds for reproducibility. Since SM-EM is a full-batch, deterministic algorithm, its convergence trajectory is fully determined by the data realization; the stochastic methods (Adam, SGD, PRM) are also deterministic for a given seed due to fixed mini-batch orderings. Results are from single data realizations; the comparison targets algorithmic convergence behavior rather than statistical variability across datasets. We omit IRLS (Fisher scoring) as a baseline because it solves the same p\times p linear system per iteration as SM-EM; the comparison of interest is whether SM-EM’s model-derived weights outperform heuristic adaptive methods (Adam, SGD) that avoid the full Hessian. 6.1 Convergence and Learning Rate Sensitivity Figure 1 shows the negative log-likelihood versus iteration for a moderately conditioned problem ( \mathrm{cond}(X^{\top}X)\approx 50 ). SM-EM reaches the lowest loss in this setting ( 0.089 ) without learning-rate tuning. Adam with the default \alpha=10^{-3} has not converged after 80 epochs; even with tuned \alpha=10^{-2} , Adam converges more slowly (final loss 0.110 ). PRM converges but requires a tuned step-size schedule. Figure 2 sweeps Adam’s learning rate over [10^{-4},10^{-0.5}] : performance varies by about a factor of six, while SM-EM matches the best result in this sweep without optimizer tuning. Figure 1: Convergence on moderately conditioned logistic regression ( \mathrm{cond}\approx 50 ). SM-EM (no learning rate) achieves the lowest loss. PRM (implicit SGD) converges but requires step size tuning. Figure 2: Adam’s final loss as a function of learning rate \alpha . SM-EM (dashed line) matches the best Adam result in this sweep without learning-rate tuning. 6.2 Effect of Conditioning Figure 3 compares SM-EM, PRM, and Adam on a well-conditioned ( \mathrm{cond}\approx 50 ) and an ill-conditioned ( \mathrm{cond}\approx 500 ) problem. SM-EM performs best in these experiments and is less sensitive to conditioning, because the Pólya–Gamma weights \hat{\omega}_{i} provide local curvature estimates that adapt by observation. Adam’s fixed learning rate becomes increasingly suboptimal as the condition number grows. PRM, which uses Hessian information, handles ill-conditioning better than Adam but still requires a step-size schedule. Figure 3: Effect of conditioning. Left: \mathrm{cond}\approx 50 . Right: \mathrm{cond}\approx 500 . SM-EM converges robustly in both cases; Adam and PRM degrade as conditioning worsens. 6.3 Nesterov Acceleration Since each full-batch SM-EM iteration is deterministic, Nesterov extrapolation can be applied without variance reduction. Figure 4 shows the effect. On the well-conditioned problem ( \mathrm{cond}\approx 50 ), Nesterov provides modest improvement for both SM-EM and PRM. On the ill-conditioned problem ( \mathrm{cond}\approx 500 ), the effect is substantial: SM-EM+Nesterov achieves a 55% lower final loss than SM-EM alone (NLL 0.019 vs. 0.042 ), and PRM+Nesterov improves by 54% over standard PRM. The observed speedup is consistent with the O(\sqrt{L/\mu}) dependence predicted by Nesterov theory for fixed-step methods (Appendix A ), though the formal rate guarantee for adaptive curvature remains open. A separate experiment isolating SM-EM and PRM with Nesterov on the same ill-conditioned design ( \mathrm{cond}\approx 450 , n=2000 , p=20 ) gives similar conclusions (Table 2 ). SM-EM+Nesterov reduces final NLL by 32% relative to standard SM-EM ( 0.030 vs. 0.044 ), while PRM+Nesterov achieves a 53% reduction ( 0.063 vs. 0.135 ). A plausible mechanism is that SM-EM’s closed-form M-step already exploits current curvature information, so Nesterov extrapolation mainly improves trajectory efficiency. PRM also benefits, although mini-batch noise can reduce look-ahead accuracy. Table 2: Nesterov acceleration on an ill-conditioned problem ( \mathrm{cond}\approx 450 , n{=}2000 , p{=}20 , 100 iterations). Method NLL Accuracy Nesterov gain SM-EM 0.044 98.0% — SM-EM + Nesterov 0.030 97.8% 32% PRM 0.135 96.8% — PRM + Nesterov 0.063 98.0% 53% Figure 4: Nesterov acceleration. Left: \mathrm{cond}\approx 50 (modest effect). Right: \mathrm{cond}\approx 500 (55% for SM-EM, 54% for PRM). Table 2 reports a separate ill-conditioned experiment with 32% (SM-EM) and 53% (PRM) gains. 6.4 Scaling with Dimension Table 3 and Figure 5 report a sweep over p\in\{20,50,100,200,500\} with n=5{,}000 , \mathrm{cond}=500 , and 80 iterations. For Adam we report both the default learning rate \alpha=10^{-3} (no tuning) and the best learning rate selected by grid search over six values; for SGD+Momentum we report the grid-search best. SM-EM and SM-EM+Nesterov use no learning rate at all. Two patterns emerge. First, SM-EM without learning-rate tuning outperforms Adam with default tuning by 4 – 6\times in NLL across all dimensions: Adam at \alpha=10^{-3} converges slowly on these ill-conditioned problems, while SM-EM reaches lower losses automatically. Second, SM-EM+Nesterov outperforms grid-tuned Adam at every value of p —by 4\times at p=200 (NLL 0.007 vs. 0.028 ) and 13\times at p=500 (NLL 0.0015 vs. 0.019 ). The gap grows with p because SM-EM’s M-step uses the full curvature matrix X^{\top}\hat{\Omega}X , whereas Adam’s diagonal second-moment estimate \hat{v}_{t} omits off-diagonal Hessian structure. The cost per iteration is higher: the O(p^{3}) linear solve makes SM-EM slower in wall-clock time for p\geq 200 (Table 3 ). However, the total practitioner cost is lower: SM-EM runs once, while Adam requires a grid search over learning rates—each point on the grid takes as long as a single SM-EM run. The Halton Monte Carlo method described below further reduces SM-EM’s per-iteration cost for large p . Table 3: Final NLL and wall-clock time vs. dimension ( n{=}5000 , \mathrm{cond}{=}500 , 80 iterations). Adam ∗ uses grid-tuned learning rate. SM-EM SM-EM+Nest Adam ∗ Adam ( 10^{-3} ) p NLL Time NLL Time NLL Time NLL Time 20 0.050 0.03 0.036 0.03 0.040 0.04 0.233 0.04 50 0.043 0.04 0.017 0.04 0.026 0.06 0.167 0.06 100 0.042 0.10 0.019 0.10 0.029 0.12 0.157 0.12 200 0.036 0.34 0.007 0.34 0.028 0.10 0.137 0.10 500 0.021 1.29 0.0015 1.28 0.019 0.30 0.116 0.25 Figure 5: Left: Final NLL vs. p ( \mathrm{cond}{=}500 , n{=}5000 ). SM-EM+Nesterov (no learning-rate tuning) reaches lower NLL than grid-tuned Adam at every dimension tested; the gap widens with p . Adam at its default learning rate ( \alpha{=}10^{-3} ) has not converged in 80 epochs. Right: wall-clock time. SM-EM’s O(p^{3}) solve is the dominant cost for p\geq 200 . 6.5 Computational Cost and Scalability Table 4 summarizes final losses and wall-clock times. SM-EM is roughly 20\times faster than PRM per iteration: the M-step solves a p\times p linear system ( O(p^{2}n+p^{3}) ), while PRM must solve n/b implicit Newton steps per epoch, each involving a Hessian computation ( O(p^{2}b+p^{3}) per batch). Adam and SGD are faster per epoch due to simpler updates, but require careful learning rate tuning. With grid-tuned step sizes, SGD+Momentum matches SM-EM’s loss at \mathrm{cond}\approx 500 (Table 4 ); SM-EM’s advantage is that it achieves comparable loss automatically, with no step size to select. Halton Monte Carlo for the M-step. For large p , the O(p^{3}) direct solve in the M-step ( 23 ) can become a bottleneck. Halton 1994 introduced a sequential Monte Carlo method for linear systems that exploits the Neumann series representation: if the M-step system A\beta=b is written in fixed-point form \beta=c+H\beta with spectral radius \rho_{H}<1 , Halton’s method iteratively estimates and corrects the residual, achieving geometric convergence at rate \rho_{H}^{N} ( Halton 2008 ) . A subsampled variant reduces the per-iteration cost from O(p^{2}s) to O(ps) for s correction steps ( Polson and Sokolov 2026 ) . In a scaling study on diagonally dominant systems at p=5{,}000 , the sampled sequential method is approximately 24\times faster than Gauss–Seidel ( Polson and Sokolov 2026 ) ; this factor is implementation-dependent and illustrates asymptotic scaling rather than a portable constant. Complete sufficient statistics as offline preconditioning. A further computational advantage arises from the structure of the M-step, and it is best understood as a form of preconditioning. As noted by Polson and Scott 2011 in the context of SVMs, the complete-data sufficient statistics X^{\top}\hat{\Omega}X and X^{\top}\kappa decompose as sums over observations: X^{\top}\hat{\Omega}X=\sum_{i=1}^{n}\hat{\omega}_{i}\,x_{i}x_{i}^{\top} and X^{\top}\kappa=\sum_{i=1}^{n}\kappa_{i}\,x_{i} . The rank-one outer products G_{i}=x_{i}x_{i}^{\top} do not depend on \beta or the iteration index t ; they can be precomputed once offline at cost O(np^{2}) and cached. At each E-step, updating \hat{\Omega} requires only O(n) scalar operations (evaluating \hat{\omega}_{i} for each observation), after which the M-step matrix A=\tau^{-2}\hat{\Lambda}+\sum_{i}\hat{\omega}_{i}G_{i} is assembled by a weighted sum of the cached outer products at cost O(np^{2}) —the same as a single matrix–vector product, with no redundant feature-matrix operations. The analogy to preconditioning is close. In iterative linear algebra, a preconditioner P is an approximation to the system matrix that is computed once (offline) and applied at each iteration to accelerate convergence: instead of solving Ax=b , one solves the better-conditioned system P^{-1}Ax=P^{-1}b . The cached outer products \{G_{i}\}_{i=1}^{n} play an analogous role for SM-EM. The “preconditioner” here is the full set of data-dependent building blocks from which every iteration’s system matrix is assembled; only the scalar weights \hat{\omega}_{i}^{(t)} change across iterations. Standard preconditioners (incomplete Cholesky, Jacobi, etc.) approximate curvature once and hold it fixed. In SM-EM, recomputing \hat{\omega}_{i} at each E-step makes the effective preconditioner \hat{\Omega}^{(t)} iteration dependent. This is the computational counterpart of the statistical observation that latent variables provide local curvature estimates (Section 4.2 ). The offline/online decomposition also explains why SM-EM is cheap to warm-start. When the model changes—a new observation arrives, or the regularization parameter \tau is updated—only the O(n) weights \hat{\omega}_{i} and the O(p) weights \hat{\lambda}_{j} need to be refreshed; the cached \{G_{i}\} remain valid. By contrast, gradient-based methods must discard their momentum buffers ( m_{t} , v_{t} in Adam) and effectively restart, because those buffers encode a running average of stale gradients. For regularized models with adaptive penalties, a dimension-reduction effect provides further savings. As coefficients \beta_{j}\to 0 under Lasso-type penalties, the adaptive weight \hat{\lambda}_{j}=\tau^{2}/|\beta_{j}|\to\infty , effectively removing coordinate j from the active set. The M-step matrix then operates on the reduced set of active variables \gamma=\{j:|\beta_{j}|>\delta\} , and the sufficient statistics restricted to \gamma are submatrices of the precomputed quantities: (X^{\top}\hat{\Omega}X)_{\gamma}=X_{\gamma}^{\top}\hat{\Omega}X_{\gamma} ( Polson and Scott 2011 ) . Early iterations (large active set) are most expensive; later iterations (small active set) are cheap. This makes model exploration—evaluating many candidate penalty levels \tau —very fast, since the sufficient statistics are shared across all penalty values. Regularization path via amortized E-step. The shared-sufficient-statistics structure is especially powerful when solving a regularization path—evaluating penalty values \tau_{1}^{-2}>\tau_{2}^{-2}>\cdots>\tau_{K}^{-2} to select a prior precision. At each EM iteration, the E-step computes \hat{\Omega} once at cost O(np^{2}) ; the resulting matrix X^{\top}\hat{\Omega}X is then shared across all K penalty values, each requiring only an O(p^{3}) linear solve. The total cost per EM sweep is O(np^{2}+Kp^{3}) , compared with O(K\,np^{2}) if each penalty required a separate E-step, or O(K\cdot T\cdot np/b) for Adam running T epochs with batch size b on each of K trajectories. Figure 6 demonstrates this on a 40-point regularization grid ( n=5{,}000 , p=200 , \mathrm{cond}=200 , 30 EM iterations). The amortized SM-EM path completes in 0.5 s— 8\times faster than running individual SM-EM fits, 3.5\times faster than Adam, and 10\times faster than grid-tuned Adam (which must try four learning rates at each \tau^{-2} ). The amortized path also achieves a 5.5\times lower mean NLL than Adam ( 0.057 vs. 0.315 ), because SM-EM benefits from the full Hessian at every \tau^{-2} while Adam’s diagonal approximation degrades on the ill-conditioned design. Figure 7 shows the active-set shrinkage effect with adaptive Lasso penalties ( p=500 , \tau=1 ). The active set decreases from 500 to 282 variables over 80 EM iterations, reducing the per-iteration solve time by 1.5\times as the effective dimension falls. Figure 6: Regularization path ( n{=}5000 , p{=}200 , 40 penalty values). Left: SM-EM with amortized E-step reaches the same NLL as individual SM-EM fits; Adam has not converged at most penalty values. Right: wall-clock time comparison; amortized SM-EM completes the path in 0.5 s. Figure 7: Active-set shrinkage with adaptive Lasso ( p{=}500 , \tau{=}1 ). Left: the active set |\gamma| decreases as coefficients are driven to zero. Right: per-iteration wall-clock time decreases proportionally, since the M-step operates on the reduced |\gamma|\times|\gamma| system. Table 4: Final negative log-likelihood and wall-clock time (80 iterations/epochs). ∗ Grid-tuned learning rate. \mathrm{cond}\approx 50 \mathrm{cond}\approx 500 Method NLL Time (s) NLL Time (s) SM-EM (no lr) 0.089 0.02 0.042 0.02 SM-EM + Nesterov 0.087 0.02 0.019 0.02 PRM ( \alpha_{t}=0.5/\sqrt{1+t} ) 0.129 0.42 0.093 0.42 PRM + Nesterov 0.090 0.45 0.043 0.46 Adam ( \alpha=10^{-2} ) 0.110 0.04 0.059 0.04 SGD + Momentum ∗ 0.090 0.04 0.041 0.04 6.6 Adaptive Weights Figure 8 displays the SM-EM weights \hat{\omega}_{i}=\tanh(z_{i}/2)/(2z_{i}) for five randomly chosen observations across EM iterations. All weights start near the upper bound 1/4 and decrease as the model classifies observations with confidence: well-separated observations ( |z_{i}| large) receive small weights, while ambiguous observations near the decision boundary retain larger weights. The right panel shows Adam’s second-moment estimate v_{t}^{(j)} : these rise then fall, driven by gradient noise rather than by the structure of the loss. Figure 8: Left: SM-EM weights \hat{\omega}_{i} for five observations—model-derived, decreasing as observations become well-classified. Right: Adam’s v_{t}^{(j)} —heuristic, driven by gradient noise. 7 Applications 7.1 Logistic Regression For binomial logistic regression with n observations, p predictors, and trial counts m_{i} ( m_{i}=1 for binary data), the negative log-likelihood is \sum_{i=1}^{n}[m_{i}\log(1+e^{x_{i}^{\top}\beta})-y_{i}\,x_{i}^{\top}\beta] . Using the Pólya–Gamma representation ( Polson et al. 2013 ) , the latent variable \omega_{i} has conditional expectation \hat{\omega}_{i}=\frac{m_{i}}{2z_{i}}\tanh\!\left(\frac{z_{i}}{2}\right),\quad z_{i}=x_{i}^{\top}\beta\,, and the M-step reduces to the weighted least squares \hat{\beta}=\left(\tau^{-2}\hat{\Lambda}+X^{\top}\hat{\Omega}\,X\right)^{-1}X^{\top}\kappa\,, where \kappa_{i}=y_{i}-m_{i}/2 . This is more numerically stable than standard IRLS, whose weights w_{i}(1-w_{i})=O(e^{-|z_{i}|}) decay exponentially for well-separated observations, causing near-singular Hessians. The Pólya–Gamma weights \hat{\omega}_{i}=O(1/|z_{i}|) decay polynomially, maintaining better-conditioned systems. 7.2 Regularized Regression For the Lasso ( g(\beta)=|\beta| ), the penalty admits the scale mixture representation |\beta|=\inf_{\lambda\geq 0}\{\beta^{2}/(2\lambda)+\lambda/2\} . Combined with a quadratic loss, the E-step via ( 26 ) gives \hat{\lambda}_{j}=\tau^{2}/|\beta_{j}^{(t)}| and the M-step solves a ridge regression with precision \tau^{-2}\hat{\Lambda} . This is iteratively reweighted L^{2} penalization. Strawderman and Wells 2012 showed that hierarchical scale-mixture-of-normals priors yield a generalized grouped Lasso whose MAP estimate is a thresholding estimator with exact risk formulas, connecting the same augmentation structure to penalized likelihood theory. For the double-Pareto penalty g(\beta)=\gamma\log(1+|\beta|/a) , the proximal operator has the closed form \prox_{\gamma g}(u)=\frac{\mathrm{sgn}(u)}{2}\left\{|u|-a+\sqrt{(a-|u|)^{2}+4(a|u|-\gamma)_{+}}\right\}, and applying ( 26 ) gives the adaptive weight \hat{\lambda}_{j}=\gamma\tau^{2}/\!\bigl((a+|\beta_{j}|)\,|\beta_{j}|\bigr) , consistent with Section 4.2 . This provides a smooth interpolation between L^{1} behavior (for small |\beta_{j}| ) and negligible shrinkage (for large |\beta_{j}| ), replacing the fixed weight decay in AdamW with a data-adaptive alternative. 7.3 Quantile Regression For quantile regression with check loss \rho_{q}(\theta)=\frac{1}{2}|\theta|+(q-\frac{1}{2})\theta , the variance-mean mixture representation with \kappa_{z}=1-2q and generalized inverse Gaussian mixing gives \hat{\omega}_{i}=|y_{i}-x_{i}^{\top}\beta|^{-1} . The algorithm reduces to iteratively reweighted least squares with adaptive weights that downweight observations far from the quantile—analogous to Adam’s scaling but derived from the loss geometry. 7.4 Generalized Ridge Regression and Shrinkage Profiles The M-step ( 23 ) has a natural interpretation in the canonical basis of the design matrix. Let X=UDW^{\top} be the singular value decomposition and \alpha=W^{\top}\beta the rotated coefficients. In this basis, the least-squares estimates are \hat{\alpha}_{i}=\alpha_{i}+\epsilon_{i} with \epsilon_{i}\sim N(0,\sigma^{2}/d_{i}^{2}) , where d_{i} is the i th singular value. Placing independent priors \alpha_{i}\sim N(0,v_{i}) yields the generalized ridge estimator \alpha_{i}^{\star}=s_{i}\,\hat{\alpha}_{i}\,,\quad s_{i}=\frac{d_{i}^{2}\,v_{i}}{\sigma^{2}+d_{i}^{2}\,v_{i}}=\frac{d_{i}^{2}}{d_{i}^{2}+k_{i}}\,, (36) where k_{i}=\sigma^{2}/v_{i} is the component-specific ridge penalty. When all k_{i}=k , this recovers standard ridge regression. The connection to SM-EM is that the adaptive prior weights \hat{\lambda}_{j} in the M-step ( 23 ) play exactly the role of the component-specific penalties k_{i} in ( 36 ). SM-EM performs generalized ridge regression at every iteration, with data-adaptive penalties that shrink aggressively in low-signal directions (small d_{i} ) and minimally in high-signal directions (large d_{i} ). This anticipates the structure of modern global-local shrinkage priors ( Carvalho et al. 2010 ; Polson and Scott 2012 ) ; see Polson and Sokolov 2019 for a review of the regularization landscape from Tikhonov to horseshoe. Goldstein and Smith 1974 showed that generalized ridge dominates least squares in componentwise MSE when the smallest singular value exceeds a signal-to-noise threshold: \mathrm{MSE}(\alpha_{i}^{\star})<\mathrm{MSE}(\hat{\alpha}_{i}) for all i . This is a stronger guarantee than James–Stein, which ensures overall MSE reduction but not improvement for each parameter individually. The SM-EM M-step inherits this componentwise improvement because its adaptive weights \hat{\lambda}_{j} are derived from the model structure rather than from a global shrinkage factor. 8 Discussion This paper develops a scale-mixture alternative to Robbins–Monro for losses admitting variance-mean mixture representations. SM-EM uses latent variables \omega_{i} and \lambda_{j} as model-derived curvature and shrinkage weights, eliminating learning-rate, momentum, and decay schedules. In the synthetic logistic benchmarks of Section 6 , this tuning-free algorithm reaches lower final loss than grid-tuned Adam, with the gap growing in dimension and condition number; sharing sufficient statistics across penalty values further accelerates regularization paths. These empirical gains are specific to the reported settings (ill-conditioned synthetic logistic regression). The connection to proximal methods is deep. Toulis and Airoldi 2017 showed that implicit SGD incorporates Fisher information to achieve unconditional stability, and Toulis et al. 2021 formalized this by establishing that the Robbins–Monro recursion is fundamentally a proximal algorithm—the implicit update \theta_{t+1}=\theta_{t}-\alpha_{t}\nabla\ell(\theta_{t+1}) is equivalent to applying the proximal operator of \alpha_{t}\ell . The scale mixture framework goes further: it replaces the global proximal step (which still requires a step size \alpha_{t} ) with the envelope representation ( 31 ), yielding observation-specific curvature estimates that serve as automatic step sizes. In the language of Toulis and Airoldi 2017 , the implicit SGD shrinkage factor (I+\gamma_{n}\hat{\mathcal{I}}_{n})^{-1} is replaced by the Pólya–Gamma precision matrix (\tau^{-2}\hat{\Lambda}+X^{\top}\hat{\Omega}X)^{-1} , which is computed in closed form from the loss structure rather than approximated by a Newton step. The half-quadratic envelope of Polson and Scott 2016 provides the same function as the proximal operator but through profiling rather than integration, connecting MM algorithms (optimization) to EM algorithms (statistical inference) via hierarchical duality. The framework also provides a principled approach to hyperparameter selection via the evidence (marginal likelihood). Following MacKay 1992 (and adopting his notation for this paragraph), let \tau_{D}^{2}=1/\sigma^{2} and \tau_{w}^{2}=1/\sigma_{w}^{2} denote the data and prior precisions, and let A=\tau_{w}^{2}C+\tau_{D}^{2}B be the Hessian of the negative log-posterior at the MAP estimate, where B and C are the Hessians of the data misfit and prior energy. The log-evidence under a Laplace approximation is \log p(D\mid\tau_{w}^{2},\tau_{D}^{2})=-\tau_{w}^{2}E_{W}^{\mathrm{MP}}-\tau_{D}^{2}E_{D}^{\mathrm{MP}}-\tfrac{1}{2}\log\det A+\text{const}\,, and setting its derivative with respect to \tau_{w}^{2} to zero yields the effective number of parameters \gamma=k-\tau_{w}^{2}\,\mathrm{tr}(A^{-1})=k-\sum_{a=1}^{k}\frac{\tau_{w}^{2}}{\lambda_{a}+\tau_{w}^{2}}\,, (37) where \{\lambda_{a}\} are the eigenvalues of B . The connection to SM-EM follows from structure: the M-step matrix A=\tau^{-2}\hat{\Lambda}+X^{\top}\hat{\Omega}X matches MacKay’s posterior-Hessian form, with B=X^{\top}\hat{\Omega}X and C=\hat{\Lambda} . Since the complete sufficient statistics \{G_{i}=x_{i}x_{i}^{\top}\} are already cached, the trace \mathrm{tr}(A^{-1}) can be computed from the Cholesky factor of A at low additional cost, making evidence-based selection of \tau inexpensive within SM-EM iterations. The same trace computation enables generalized cross-validation ( Golub et al. 1979 ) , whose score \mathrm{GCV}(\tau)=n^{-1}\|y-\hat{y}\|^{2}/(1-\gamma/n)^{2} depends on \gamma and the residual norm. The effective degrees of freedom \gamma in ( 37 ) also aligns with the shrinkage profiles from Section 7 : each eigenvalue \lambda_{a} contributes \lambda_{a}/(\lambda_{a}+\tau_{w}^{2})=s_{a} , the same shrinkage weight as in generalized ridge regression ( 36 ). Nesterov acceleration complements the framework. Since each full-batch SM-EM iteration is deterministic, Nesterov extrapolation can be applied without variance reduction—unlike stochastic gradient methods, which require SVRG ( Johnson and Zhang 2013 ) or SAGA ( Defazio et al. 2014 ) to reduce noise before acceleration is effective. Empirically, SM-EM+Nesterov achieves 32–55% lower loss on the ill-conditioned benchmarks of Section 6 ; the formal O(1/t^{2}) guarantee for SM-EM’s adaptive curvature (as opposed to fixed-step proximal gradient) remains an open question (Appendix A ). For large-scale problems, the O(p^{3}) M-step solve can be replaced by Halton’s sequential Monte Carlo method ( Halton 1994 ; Polson and Sokolov 2026 ) , which achieves geometric convergence with O(ps) per-iteration cost—enabling SM-EM for problems where direct factorization is prohibitive. The complete sufficient statistics structure of the M-step ( Polson and Scott 2011 ) further reduces cost: the outer products x_{i}x_{i}^{\top} are precomputed once, and for sparse models the active set shrinks across iterations, making later EM steps progressively cheaper. Several limitations deserve mention. First, SM-EM applies only to losses admitting a scale mixture of normals representation; while this covers a broad class (logistic, hinge, check, bridge penalties—see Section 3 ), arbitrary neural network losses do not qualify. Second, the experiments here use logistic regression on synthetic data; real-data benchmarks and extensions to multi-class or deep models remain future work. For the multinomial case, Linderman et al. 2015 showed that stick-breaking with Pólya–Gamma augmentation yields conjugate Gaussian updates, suggesting a natural path for extending SM-EM beyond binary classification. Third, SM-EM as presented is a full-batch method. For problems where n is too large for full-batch evaluation, a stochastic EM variant is needed; the online EM framework of Cappé and Moulines 2009 provides a path, though the tuning-free guarantee would require additional analysis. Fourth, the O(p^{3}) M-step, while addressed by Halton Monte Carlo for very large p , means SM-EM is slower per iteration than SGD-based methods when p is large and the problem is well-conditioned enough for first-order methods to suffice. Extensions to full posterior inference via MCMC (Gibbs sampling on \omega,\lambda,\beta ) use the same data augmentation structure, and the Katyusha momentum of Allen-Zhu 2017 offers a path to accelerated stochastic variants for the finite-sum setting. Appendix A Convergence Theory for SM-EM with Nesterov Acceleration This appendix discusses the convergence theory underlying Nesterov acceleration as applied to the scale mixture EM algorithm. A.1 Half-Quadratic Framework Consider the composite objective F(w)=f(w)+\phi(w) where \phi is convex. Suppose f(w) admits a half-quadratic envelope: f(w)=\inf_{v}\left\{f(v)+\nabla f(v)^{\top}(w-v)+\frac{L(v)}{2}\left\|w-v\right\|^{2}\right\}, (38) where the infimum is attained at v=w . The standard proximal gradient method uses a constant L(v)=L ; in the scalar case, the scale mixture approach uses the adaptive choice L(v)=(\nabla f(v)+\kappa)/v (cf. the GR minimizer \hat{\omega}=\phi^{\prime}(x)/x in Table 5 ), which yields tighter quadratic bounds at points far from the optimum. In the multivariate case, L(v) is replaced by the observation-specific precision matrix X^{\top}\hat{\Omega}X . We assume a lower bound L\preceq L(v) for all v to guarantee fast convergence. Define the joint objective F(w,v)=f(v)+\nabla f(v)^{\top}(w-v)+\phi(w) . Finding the marginal mode w^{\star}=\arg\min_{w}F(w) reduces to alternating minimization of \min_{w,v}\left\{F(w,v)+\frac{L(v)}{2}\left\|w-v\right\|^{2}\right\}. The conditional mode for v given w_{t} is v_{t}=w_{t} (the ICM step); the conditional mode for w given v_{t} is the proximal operator w_{t+1}=\prox_{L(v_{t})^{-1}\phi}\!\left(v_{t}-L(v_{t})^{-1}\nabla f(v_{t})\right), (39) since completing the square in w yields \frac{L(v_{t})}{2}\left\|w-(v_{t}-L(v_{t})^{-1}\nabla f(v_{t}))\right\|^{2}+\phi(w) plus terms not depending on w . When L(v) is the adaptive choice from the scale mixture, this proximal step uses the model-derived curvature rather than the global Lipschitz constant. A.2 Three-Point Inequality For any convex \phi and parameter \gamma>0 , the Moreau envelope E_{\gamma\phi}(x)=\inf_{z}\{\frac{1}{2\gamma}\|z-x\|_{2}^{2}+\phi(z)\} satisfies the descent property E_{\gamma\phi}(y)\leq E_{\gamma\phi}(x)-\frac{1}{2\gamma}\left\|x-y\right\|^{2},\quad y=\prox_{\gamma\phi}(x). When L\preceq L(x) for all x , this generalizes to the three-point inequality: for y=\prox_{L(x)^{-1}\phi}(x) , \phi(y)+\frac{L(x)}{2}\|y-x\|_{2}^{2}\leq\phi(z)+\frac{L(x)}{2}\|z-x\|_{2}^{2}-\frac{L}{2}\left\|z-y\right\|^{2}\quad\forall z. (40) This reverse-triangle Pythagoras inequality is the key tool for establishing convergence rates. Combining ( 40 ) with the descent lemma l_{f}(w,v)\mathrel{\mathop{:}}=f(w)-f(v)-\nabla f(v)^{\top}(w-v)\leq\frac{L(v)}{2}\|w-v\|^{2} (which holds when \nabla f is Lipschitz) and convexity ( l_{f}\geq 0 ), each proximal step satisfies F(w_{t+1})\leq F(w^{\star})+\frac{L}{2}\left\|w^{\star}-v_{t}\right\|^{2}-\frac{L}{2}\left\|w^{\star}-w_{t+1}\right\|^{2}. (41) A.3 O(1/k^{2}) Convergence with Nesterov Acceleration To accelerate convergence beyond the O(1/k) rate of ( 41 ), introduce an auxiliary sequence u_{t} and weights \theta_{t} such that \displaystyle v_{t} \displaystyle=(1-\theta_{t})w_{t}+\theta_{t}u_{t}, (42) \displaystyle u_{t+1} \displaystyle=\frac{1}{\theta_{t}}\!\left(w_{t+1}-(1-\theta_{t})w_{t}\right). (43) The intermediate point v_{t} is a convex combination of w_{t} and u_{t} , chosen to ensure errors compound at rate O(1/k^{2}) . Theorem 5 (Nesterov, 1983; Beck and Teboulle, 2009) . Let f be convex with L -Lipschitz gradient. Define \lambda_{0}=0 , \lambda_{s}=(1+\sqrt{1+4\lambda_{s-1}^{2}})/2 , and \gamma_{s}=(1-\lambda_{s})/\lambda_{s+1} . Starting from x_{1}=y_{1} , iterate \displaystyle y_{s+1} \displaystyle=x_{s}-\frac{1}{L}\nabla f(x_{s}), \displaystyle x_{s+1} \displaystyle=(1-\gamma_{s})y_{s+1}+\gamma_{s}y_{s}. Then f(y_{t})-f(x^{\star})\leq 2L\|x_{1}-x^{\star}\|^{2}/t^{2} . Proof. For any x,y\in\mathbb{R}^{n} , L -smoothness of f gives \displaystyle f\!\left(x-\tfrac{1}{L}\nabla f(x)\right)-f(y) \displaystyle\leq-\tfrac{1}{2L}\|\nabla f(x)\|^{2}+\nabla f(x)^{\top}(x-y) \displaystyle=-\tfrac{L}{2}\|y_{s+1}-x_{s}\|^{2}-L(y_{s+1}-x_{s})^{\top}(x_{s}-y). Apply with (x,y)=(x_{s},y_{s}) and (x,y)=(x_{s},x^{\star}) . Let \delta_{s}=f(y_{s})-f(x^{\star}) . Multiply the first inequality by (\lambda_{s}-1) and add to the second: \lambda_{s}\,\delta_{s+1}-(\lambda_{s}-1)\,\delta_{s}\leq-\tfrac{L}{2}\lambda_{s}\|y_{s+1}-x_{s}\|^{2}-L(y_{s+1}-x_{s})^{\top}\!\left(\lambda_{s}x_{s}-(\lambda_{s}-1)y_{s}-x^{\star}\right). Multiplying by \lambda_{s} and using \lambda_{s-1}^{2}=\lambda_{s}^{2}-\lambda_{s} : \lambda_{s}^{2}\,\delta_{s+1}-\lambda_{s-1}^{2}\,\delta_{s}\leq\tfrac{L}{2}\!\left(\|u_{s}\|^{2}-\|u_{s+1}\|^{2}\right), where u_{s}=\lambda_{s}x_{s}-(\lambda_{s}-1)y_{s}-x^{\star} , using the identity \lambda_{s+1}x_{s+1}-(\lambda_{s+1}-1)y_{s+1}=\lambda_{s}y_{s+1}-(\lambda_{s}-1)y_{s} from the definition of x_{s+1} . Telescoping from s=1 to s=t-1 : \lambda_{t-1}^{2}\,\delta_{t}\leq\tfrac{L}{2}\|u_{1}\|^{2}. Since \lambda_{t-1}\geq t/2 by induction, we obtain \delta_{t}\leq 2L\|x_{1}-x^{\star}\|^{2}/t^{2} . ∎ Theorem 5 assumes a fixed Lipschitz constant L and uses 1/L as the step size. SM-EM uses adaptive curvature L(v_{t}) that varies per iteration (Section 3 ), so the theorem does not apply directly. Extending the O(1/t^{2}) guarantee to the adaptive setting requires the uniform lower bound L\preceq L(v) from ( 38 ) together with a generalized descent lemma for variable metrics; this extension is a direction for future work. In the experiments (Figure 4 ), SM-EM+Nesterov exhibits convergence consistent with the O(1/t^{2}) rate on the ill-conditioned problems tested, and the deterministic full-batch E-step ensures no stochastic noise enters the extrapolation. Appendix B Half-Quadratic Envelopes and Proximal Operators B.1 Table of Half-Quadratic Envelopes Table 5 catalogs the two standard half-quadratic representations for common penalty functions: the Geman–Reynolds (GR) scale representation \phi(x)=\inf_{s}\{\frac{1}{2}x^{2}s+\psi(s)\} with minimizer \hat{s}=\phi^{\prime}(x)/x , and the Geman–Yang (GY) location representation \phi(x)=\inf_{s}\{\frac{1}{2}(x-s)^{2}+\psi(s)\} with minimizer \hat{s}=\prox_{\psi}(x)=x-\phi^{\prime}(x) . The GR representation corresponds to the variance mixture (scale mixture of normals); the GY representation corresponds to the location mixture (Moreau envelope). Table 5: Half-quadratic envelopes for common penalties. GR: Q(x,s)=\frac{1}{2}x^{2}s (scale/variance mixture); GY: Q(x,s)=\frac{1}{2}(x-s)^{2} (location/Moreau envelope). Penalty \phi(x) GR minimizer \hat{s} GY minimizer \hat{s} L^{p} , \alpha\in(1,2] |x|^{\alpha} \alpha|x|^{\alpha-2} — \alpha - L^{1} \sqrt{\alpha+x^{2}} (\alpha+x^{2})^{-1/2} x-x/\sqrt{\alpha+x^{2}} L^{1} -Pareto \frac{|x|}{\alpha}-\log(1+\frac{|x|}{\alpha}) [\alpha(\alpha+|x|)]^{-1} x-x/[\alpha(\alpha+|x|)] Huber \begin{cases}x^{2}/2&|x|\leq\alpha\\ \alpha|x|-\alpha^{2}/2&|x|>\alpha\end{cases} \min(1,\alpha/|x|) — Logit \log\cosh(\alpha x) \alpha\tanh(\alpha x)/x x-\alpha\tanh(\alpha x) B.2 Proximal Operators for L^{p} Penalties The proximal operator \prox_{\lambda|\cdot|^{p}}(y)=\arg\min_{z}\{\frac{1}{2}(y-z)^{2}+\lambda|z|^{p}\} has closed-form solutions for several values of p : \displaystyle p=1 \displaystyle:\quad\mathrm{sgn}(y)\max(|y|-\lambda,0) (soft thresholding) \displaystyle p=\tfrac{3}{2} \displaystyle:\quad y+\tfrac{9\lambda^{2}}{8}\,\mathrm{sgn}(y)\!\left(1-\sqrt{1+\tfrac{16|y|}{9\lambda^{2}}}\right) \displaystyle p=2 \displaystyle:\quad y/(1+2\lambda) (ridge) \displaystyle p=3 \displaystyle:\quad\mathrm{sgn}(y)\!\left(\sqrt{1+12\lambda|y|}-1\right)\!/(6\lambda) For 0