MISSO: Minimization by Incremental Stochastic Surrogate Optimization for Large Scale Nonconvex and Nonsmooth Problems
Authors: Belhal Karimi
Hoi To Wai
Eric Moulines
Ping Li
Venue:  (2021)
Keywords: nonconvex
optimization
stochastic
sampling
MCMC
majorization-minimization

Abstract: Many constrained, nonconvex and nonsmooth optimization problems can be tackled using the majorization-minimization (MM) method which alternates between constructing a surrogate function which upper bounds the objective function, and then minimizing this surrogate. For problems which minimize a finite sum of functions, a stochastic version of the MM method selects a batch of functions at random at each iteration and optimizes the accumulated surrogate.
However, in many cases of interest such as variational inference for latent variable models, the surrogate functions are expressed as an expectation. In this contribution, we propose a doubly stochastic MM method based on Monte Carlo approximation of these stochastic surrogates.
We establish asymptotic and non-asymptotic convergence of our scheme in a constrained, nonconvex, nonsmooth optimization setting. We apply our new framework for inference of logistic regression model with missing data and for variational inference of Bayesian variants of LeNet-5 and Resnet-18 on respectively the MNIST and CIFAR-10 datasets.

Under review as a conference paper at ICLR 2021
MISSO: MINIMIZATION BY INCREMENTAL STOCHAS- TIC SURROGATE OPTIMIZATION FOR LARGE SCALE NONCONVEX AND NONSMOOTH PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Many constrained, nonconvex and nonsmooth optimization problems can be tack- led using the majorization majorizationn-miiiizzaie minimization (MM) method which alternates between constructing surrogate function which upper bounds the objective function, and then minimizing this surrogate. For problems which minimize a finite sum functions, stochastic version of the MM method selects batch of functions at random at each iteration and optimizes the accumulated surrogate. However, in many cases of interest such variational inference for latent variable mod- els, the surrogate functions are expressed as an expectation. In this contribution, we propose a doubly stochastic MM method based on Monte Carlo approxima- tion of these stochastic surrogates. We establish asymptotic and -on-asymptotic convergence of our scheme in a constrained, nonconvex, nonsmooth optimization setting. We apply our new framework for inference of logistic regression model with missing data and for variational inference of Bayesian variants of LeNet-5 and Resnet-18 18 on respectively the MNIST and CIFAR-10 datasets.
INTRODUCTION
We consider the constrained minimization problem of finite sum of functions:
min L()) := Σ ()) 8E8
(1)
where is convex, compact, and closed subset of IR, and for any i E [1,n]. the function L; IRP IR bounded from below and (possibly) nonconvex and nonsmooth.
To tackle the optimization problem (1), a popular approach is to apply the majorization minimization (MM) method which iteratively minimizes majorizing surrogate function. A large number of ex- isting procedures fall into this general framework, for instance gradient-based or proximal methods or the Expectation-Maxinne tional Bayes inference techniques (Jordan et al., 1999); see for example (Razaviyayn et al., 2013) and (Lange, 2016) and the references therein. When the number of terms n in (1) large, the vanilla MM method may be intractable because it requires to construct surrogate function for all the n terms L, each iteration. Here, remedy to apply the Minimization by Incremental Sur- rogate Optimization (MISO) method proposed by Mairal (2015), where the surrogate functions are updated incrementally. The MISO method can interpreted as a combination of MM and ideas which have emerged for variance reduction in stochastic gradient methods (Schmidt et al., 2017). An extended analysis of MISO has been proposed in (Qian et al., 2019).
majorization-miiiiizztioon
(EM) algorithm (McLachlan Krishnan, 2008) and some varia-
The success of the MISO method rests upon the efficient minimization of surrogates such as con- vex functions, see (Mairal, 2015, Section 2.3). A notable application of MISO-like algorithms is described in (Mensch et al., 2017) where the authors builds upon the stochastic majorization- minimization framework of Mairal (2015) to introduce a method for sparse matrix factorization. Yet, in many applications of interest, the natural surrogate functions are intractable, yet they defined as expectation of tractable functions. For instance, this is the case for inference in latent variable models via maximum likelihood (McLachlan & Krishnan, 2008). Another application is

---

Under review as a conference paper at ICLR 2021
variational inference (Ghahramani, 2015), in which the goal is to approximate the posterior distribu- tion of parameters parameterss given the observations; see for example (Neal, 2012; Blundell et al., 2015; Polson et al., 2017; Rezende al., 2014; Li & Gal, 2017).
This paper fills the gap in the literature by proposing a method called Minimization by Incremental Stochastic Surrogate Optimization (MISSO), designed for the nonconvex and nonsmooth finite sum optimization, with a finite-time convergence guarantee. Our work aims at formulating a generic class of incremental stochastic surrogate methods for nonconvex optimization and building the the- ory to understand its behavior. In particular, we provide convergence guarantees for stochastic EM and Variational Inference-type methods, under mild conditions. In summary, our contributions are:
we propose a unifying framework of analysis for incremental stochastic surrogate optimiza- tion when the surrogates are defined as expectations of tractable functions. The proposed MISSO method is built on the Monte Carlo integration of the intractable surrogate function, i.e., a doubly stochastic surrogate optimization scheme.
we present an incremental update of the commonly used variational inference and Monte Carlo EM methods as special cases of our newly introduced framework. The analysis of those two algorithms is thus conducted under this unifying framework of analysis.
we establish both asymptotic and non- asymptotic convergence for the MISSO method. In particular, the MISSO method converges almost surely to a stationary point and in (n/ec) iterations to e-stationary point, see Theorem 1.
in essence, we relax the class of surrogate functions used in MISO (Mairal, 2015) and allow for intractable surrogates that can only be evaluated by Monte-Carlo approximations. Working at the crossroads of Optimization and Sampling constitutes what we believe to be the novelty and the technicality of our framework and theoretical results.
In Section 2, we review the techniques for incremental minimization of finite sum functions based on the MM principle; specifically, we review the MISO method (Mairal, 2015). and present class of surrogate functions expressed as expectation over latent space. The MISSO method is then introduced for the latter class of intractable surrogate functions requiring approximation. In Sec- tion 3, provide the asymptotic and asymptotiiiic convergence analysis for the MISSO method (and of the MISO (Mairal, 2015) one as a special case). Section 4 presents numerical applications including parameter inference for logistic regression with missing data and variational inference for two types of Bayesian neural networks. The proofs of theoretical results are reported as Supplement.
Notations. We denote [1, n²] nu, Unless otherwise specified, || || denotes the standard Euclidean norm and <- (-) is the inner product in the Euclidean space. For any function f f - R, f'(0, d) is the directional derivative of f at 0 along the direction d, i.e.
f(0 + td) f(0)
I' d) = lim
t
The directional derivative is assumed exist for the functions introduced throughout this paper.
INCREMENTAL MINIMIZATION OF FINITE SUM NONCONVEX FUNCTIONS
The objective function in (1) is composed of finite sum of possibly nonsmooth and nonconvex functions. A popular approach here is to apply the MM method, which tackles (1) through alter- nating between two steps - (i) minimizing a surrogate function which upper bounds the original objective function; and (ii) updating the surrogate function to tighten the upper bound.
As mentioned in the introduction, the MISO method (Mairal, 2015) is developed as an iterative scheme that only updates the surrogate functions partially at each iteration. Formally, for any e nJ. we consider surrogate function Ž, 0) which satisfies the assumptions (H1, H2):
HI. For all i E [1, and 0 E θ, 2.(00: 0) is convex w.r.t. O, and it holds
2, 0) 2 (O), A
(3)
where the equality holds when 0 0.
2

---

Under review as a conference paper at ICLR 2021
H2. For any 0, θ, E [1,n] and some > 0, the difference function ē(0; 10,
Th (0, [()) defined for all O. and differentiable for all 0 E θ where R
O = { Rd, inforge ge 1 0' < t} is an e-neighborhood set of O. Moreover, for some constant
L, the gradient satisfies
0
21E(0; (0.))%))))))) VOE
We remark that H1 is a common assumption used for surrogate functions, see (Mairal, 2015, Section 2.3). H2 can be satisfied when the differ- ence function Œ(; {0, )i=)) is L-smooth, i.e., ē
Algorithm The MISO method (Mairal, 2015).
Input: initialization (())
2: Initialize the surrogate function as i E [[,
is differentiable
θ and its gradient Vē is L- Lipschitz, V0 E e. H2 can be implied by apply-
AQ( := (0:
3: for k 0, 1..., Kmax do
ing (Razaviyayn al., 2013, Proposition 1).
4: Pick is uniformly from [1,
5: Update A,t (0) as:
The inequality (3) implies (, 0) 2 (0)
-0o for any 0 E e. The MISO method is an incremental version of the MM method, as summarized by Algorithm 1, which shows that the MISO method maintains an iteratively up- dated set of upper- bounding surrogate functions {AA, (0) } and updates the iterate via minimiz- ing the average of the surrogate functions.
(0) (,000
if = in otherwise.
(O).
Set ((++)) arg min oc0
a E (0).
7: end for
Particularly, only one of the n surrogate functions is updated at each iteration [cf. Line 5] and the sum function n
1 Σ A (0) is designed to be 'easy optimize', which, for example, can be a sum of quadratic functions. As such, the MISO method is suitable for large-scale optimization as the computation cost per iteration is independent of n. Under H1, H2, it was shown that the MISO method converges almost surely to stationary point of (1) (Mairal, 2015, Prop. 3.1).
We now consider the case when the surrogate functions (, 0) are intractable. Let Z be mea- surable set, Pt: Z x > IR+ a probability density function, r; x θ + IR: a measurable function and μ4 a-finite measure. We consider surrogate functions which satisfy H1, H2 and that can be expressed as an expectation, i.e.:
(0,00) = ri (0:00 2: 2));(zz;; O)z, A xxx0)
(5)
Plugging (5) into the MISO method is not feasible since the update step in Step 6 involves a mini- mization of an expectation. Several motivating examples of (1) are given in Section 2.
In this paper, we propose the Mininization by Incremental Stochastic Surrogate Optimization (MISSO) method which replaces the expectation in (5) by Monte Carlo integration and then op- timizes the objective function (1) in an incremental manner. Denote by M E N the Monte Carlo batch size and let (2m E M= be a set of samples. These samples can be drawn (Case 1) i..dd from the distribution (: 0) or (Case 2) from a Markov chain with stationary distribution pa(:; O); see Section 3 for illustrations. To this end, we define the stochastic surrogate as follows:
M Σ
(0: (2m JM M
(0;00. 2m)
(6)
M
and we summarize the proposed MISSO method in Algorithm 2. Compared to the MISO method, there is a crucial difference in that the MISSO method involves two types of randomness. The first level of randomness comes from the selection of ig in Line 5. The second level of randomness stems from the set of Monte Carlo approximated functions A² (0) used in lieu of A (0) in Line 6 when optimizing for the next iterate (4). We now discuss two applications of the MISSO method.
Example 1: Maximum Likelihood Estimation for Latent Variable Model. Latent variable mod- els (Bishop, 2006) are constructed by introducing unobserved (latent) variables which help explain the observed data. We consider n independent observations (()., 2, E [m]] where yi is observed and 2; is latent. In this incomplete data framework, define (fi(z,, 0), 0 ²) to be the complete
3

---

Under review as a conference paper at ICLR 2021
Algorithm 2 The MISSO method.
1: Input: initialization 0 sequence of non- non-negative numbers {Mas I
2: For all i [1, draw Mo Monte Carlo samples with the stationary distribution p=(:;((0))
3: Initialize the surrogate function as
O0) = Z,(0; 0 (
Ma)) i [1,n]]
4: for k = 0. 1,..., max do
5: Pick a function index is uniformly on [1,
6: Draw Max Monte Carlo samples with the stationary distribution pı(:; (()).
7:
Update the individual surrogate functions recursively as:
1(,00 (zim)-=)) if (0),
(0)
otherwise.
8: Set ((++1) arg [()+)((0) = E (0).
9:
end for
data likelihood models, ie.. the joint likelihood of the observations and latent variables. Let
g ( = S[ f(( 0), (dz;), E [L, e
denote the incomplete data likelihood, i.e., the marginal likelihood of the observations yi. For ease of notations, the dependence on the observations is made implicit. The maximum likelihood (ML) estimation problem sets the individual objective function (0) to be the i-th negated incomplete data log- likelihod L, := - log (o).
Assume, without loss of generality, that gi (0) + for all 0 e O. We define by pz(zi, 0) fz (0) the conditional distribution of the latent variable given the observations A sur- fi(2, 0)
rogate function (f: 0) satisfying H1 can be obtained through writing fi(zi, 0) p+(2;,0) Pr Pz(zi, and applying the Jensen inequality:
(, | log ()(((s,) 0)) p. pi(z,, (dz))
(0:00:)
We note that H2 also be verified for common distribution models. We can apply the MISSO method following the above specification of (0: 0, 24) and pz(z,, Ø).
Example 2: Variational Inference. Let ((v,, 31), E n]] be i.i.d. input-output pairs and w e
W C Rd be latent variable. When conditioned on the input data = (x,, [I,n]), the joint distribution of = (ys, E [1, nl) and w is given by:
ply. w|z) ((w) IT= P(Mela,, w)
Our goal is compute the posterior distribution p(w w). In most cases, the posterior dis- tribution p(wly, .)) is intractable and is approximated using a family of parametric distributions, (g(w, 0), 0 E O). The variational inference (VI) problem (Blei et al., 2017) boils down minimiz- ing the Biclbacck-Libbler (KL) divergence between q(w, 0) and the posterior distribution p( ((wlpp p(wly, z):
min L()) == KL (g(w; 0) (p((ll, x)) == () [oo (a(w; 0)/p(wlp.x)))
(9)
Using (8), we decompase L(0) = n -- Σt (0) + const. where:
(0) := E [log x,, w)] + E By( (w:
(0) d(0). (10)
Directly optimizing the finite sum objective function in (9) can be difficult. First, with n > 1, evaluating the objective function L(0) requires full pass the entire dataset. Second, for some
4

---

Under review as a conference paper at ICLR 2021
complex models, the expectations in (10) can be intractable even if we assume simple parametric model for q 0). Assume that L; L-smooth. We apply the MISSO method with a quadratic surrogate function defined as:
L 0 01 (0,0) E E
(V)0) (
0)
(11)
is easily checked that the quadratic function (,; F) satisfies HI, H2. To compute the gradient (O), we apply the re-parametrization technique suggested in (Paisley et al., 2012; Kingma & Welling, 2014; Blundell et al., 2015). Let t I2 x θ R' be differentiable function w.zt. 0 E θ which is designed such that the law of w f(z, 0) is a(., 0), where Na I). By (Blundell et al., 2015, Proposition 1), the gradient of (-) in (10) is:
((no) log lay w)] (2 Jg Jg( (2, V. logp(us/s w)) w=
(12)
where for each E Rd, (z 0) is the Jacobian of the function ((z, .) with respect to O evaluated at O. In addition, for most cases, the term Vd(0) can be evaluated in closed form as the gradient of the KL between the prior distribution (.) and the variational candidate q(., O).
+ L
00; = v - J (z, V log (unkk, w)) w 0 0
- 1 10-011 (13)
2
Finally, using (11) and (13), the surrogate function (6) is given by (,; 0, {zm J.M
JM
M Σn M
Em=1 rr(0; 0, 2m) where {2m)m= M are i.i.d samples drawn from A/
CONVERGENCE ANALYSIS
We now provide asymptotic and non non-asymptotic convergence results of our method. Assume: HB. For all E [1. θ, 2, E Z, r.(:;,20 2.) is convex on and is lower bounded.
We particularly interested in the constrained optimization setting where @ is a bounded set. To this end, we control the supremum norm of the MC approximation, introduced in (6), as:
H4. For the samples (zt,m
1M m= there exist finite constants C, and Car such that
M
C = sup sup
E 0
sup AE
Σ
rr:(0: 0, z. (0:
BEe MS0 VM
m=1
M
2, 1:00-000 0,0) (0
Zi.m)
Cg == sup sup VM Zee MD0
sup OE
M
0
m
for all i E [1, and we denoted by Eg( the expectation w.r.t. a Markov chain {zi,m ) JM m= with initial distribution E)(:0),, transition kernel 1, and stationary distribution ps(:;0. 0).
Some intuitions behind the controlling terms: It is common in statistical and optimization prob- lems, to deal with the manipulation and the control of random variables indexed by sets with an infinite number of elements. Here, the controlled random variable is an image of a continuous func- tion defined as r: 0 - - (0; (0:0 0) for all 2 E Z and for fixed (0, 0 E ? To characterize such control, we will have recourse to notion of metric entropy (or bracketing number) as de- veloped in (Van der Vaart, 2000; Vershynin, 2018; Wainwright, 2019). A collection of results from those references gives intuition behind our assumption H4, which is classical empirical processes. In (Vershynin, 2018, Theorem 8.2.3), the authors recall the uniform law of large numbers:
M
CL VM
sup JEF
Σ f (#)m) -Ccm)-E(((E))) [[((+))] <
for all Zi,,, i E [1, M]
M
1=1
where JF is class of L-Lipschitz functions. Moreover, in (Vershynin, 2018, Theorem 8.1.3 and (Wainwright, 2019, Theorem 5.22), the application of the Dudley inequality yields:
1 VM / /'''
E(sup|Xy Xoll FeF
VlogA (F. llo..
5

---

Under review as a conference paper at ICLR 2021
where N (F, || E) the bracketing number and denotes the level of approximation (the brack- eting number goes to infinity when 6 - 0). Finally, in (Van der Vaart, 2000, p.271, Example), N (F, - |loo E) is bounded from above for class of parametric functions F fo 0 O:
(F, olo, S (diaam
O (
for all 0<E< diam θ
The authors acknowledge that those bounds are a dramatic manifestation of the curse of dimension- ality happening when sampling is needed. Nevertheless, the dependence the dimension highly depends on the class of surrogate functions F used our scheme, as smaller bounds on these con- trolling terms can be derived for simpler class of functions, such quadratic functions.
Stationarity measure. As problem (1) is a constrained optimization task, we consider the following stationarity measure:
L' 0 0)
g inf O
and g g+ (+) g-
(14)
0 01
min (0, (()} denote the positive and negative part of g(0), respectively. Note that 0 is stationary point if and only if (0) = - (Fletcher et al., 2002). Furthermore, suppose that the sequence (0()))20 has limit point 0 that is stationary point, then one has limx-+x g- () = 0. Thus, the sequence (0(*) Je20 is said to satisfy an asymptotic stationary point condition. This is equivalent to (Mairal, 2015, Definition 2.4).
where 9+ (0) = max g (0)), g- (0)
To facilitate our analysis, we define 77th as the iteration index where the i-th function is last accessed in the MISSO method prior to iteration k, ni+t1 k for instance. We define:
Kma
( (0) = + (() (0) = 2 (0) ((),, M(y
M (15)
We first establish a non-asymptotic convergence rate for the MISSO method:
Theorem 1. Under H1-114. For any Kmax E N. let K be an independent discrete E.V. drawn uniformly from {0, Kmax 1} and define the following quantity:
A Kmn)) 2n (800) - (Kmm)) (0) (Kmm))))) 4LC,M
Then we have following non-asymptotic bounds:
(2 (e(()))((())))))))) (0())) S
((Km))
and (lg S
A ((Km))
Cgr
M (z) (16)
Kmax
Kmax
Kmax
Note that ((K..)) is finite for any Kmax N.
Iteration Complexity of MISSO. As expected, the MISSO method converges to a stationary point of (1) asymptotically and at sublinear rate Blge | ((/A(K..)) Kmax). In other terms, MISSO requires ((T.ff)) iterations to reach an e-stationary point when the suboptimality condition, that characterizes stationarity, is LE' [[lg- [13]) Note that this stationarity criterion are similar to the usual quantity used stochastic nonconvex optimization, i.e. E[1 (((()((())) In fact, when the optimization problem (1) is unconstrained, i.e., θ IR",, then E ( K} = E [(
Sample Complexity of MISSO. Regarding the sample complexity of our method, setting M(x) k22 n2/n2, as a non-decreasing sequence of integers satisfying Σ M 112 < xc, in order to keep A (K...) nL, then the MISSO method requires EaL/e 2²/n²² nL3 /e2 samples to reach an e-ttationary point.
Furthermore. we remark that the MISO method can be analyzed in Theorem I special case of the MISSO method satisfying C, Cg = 0. In this case, while the asymptotic convergence
is well known from (Mairal, 2015) [ef. H4], Eq. (16) gives non-asymptotic rate of [[ s

---

Under review as a conference paper at ICLR 2021
O(ynL//Max/ which is new to our best knowledge. Next, show that under additional assumption on the sequence of batch size M(1). the MISSO method converges almost surely to a stationary point:
Theorem 2. Under HI-H4. In addition, assume that (M(a)) is a non-decreasing sequence of integers which satisfies Σx=o Mik < co. Then:
1. the negative part the
the stationarity measure converges a.s. to zero, i... lim -- (0(k)) -- 0.
2. the objective value C(O(k)) converges a.s. to a finite number C i.e., lim ((O(K)) a.
In particular, the first result above shows that the sequence (0(0) produced by the MISSO method satisfies an asymptotic stationary point condition.
4 NUMERICAL EXPERIMENTS
4.1 BINARY LOGISTIC REGRESSION WITH MISSING VALUES
This application follows Example described in Section 2. We consider a binary regression setup, ((y,, 2,), i [nl] where y/s E {0, } is binary response and 2 = (Zz,J E R [p]) covariate vector. The vector of covariates = [ 2t,bb is not fully observed where we denote by miis the missing values and 2r, the observed covariate. It is assumed that (zz, i [n]] are i..d and marginally distributed according to (/,,, 52) where 3 E RP and Ω is positive definite px p matrix. We define the conditional distribution of the observations yı given 2; = (2i, 2i,abs) as:
(M) = S(8"
2, ) (1 S66 x,))
(17)
where for u E R. S(u) = 10(1===)), (60, ... 5pp) are the logistic parameters and ž, = 2)) Here, 0- (6,3,57 52) the parameter to estimate. For E [n]] the complete log- og-likelihood reads:
;pp))))))))))))))))))
log fe 0) 5 2 - llog (1 + exp(6" 2)) log (2()) + Tr (S- (3 - T)
Fitting logistic regression model on the TraumaBase dataset: We apply the MISSO method to fit a logistic regression model on the TraumaBase (http: htap:://trauuee htttt//tauaabaeeeeee eu) dataset, which consists of data collected from 15 trauma centers in France, covering measurements on patients from the initial to last stage of trauma. This dataset includes information from the first stage of the trauma, namely initial observations the patient's 's accident site to the last stage being intense care at the hospital and counts more than 200 variables measured for more than 7 7000 patients. Since the dataset considered is heterogeneous coming from multiple sources with frequently missed entries we apply the latent data model described in (17) to predict the risk of severe hemorrhage which one of the main cause of death after a major trauma.
Similar to (Jiang et al., 2018), we select p = 16 influential quantitative measurements, on n 6384 patients. For the Monte Carlo sampling of 2i,mis+ required while running MISSO, we run Metropolis-Hastings algorithm with the target distribution p(-|zz,obss ye; ((k)).
0.005
100
0.000
90
-0.005
80
0.030
-0.015
SAEM
MISSO
MI5S050
60
SAEM
MISSO
MI5S050
0.020
MI5S010
50
MI55010
2
10
Epochs
Epochs
Figure/ 1: Convergence of parameters 8 and B for the SAEM, the MCEM and the MISSO methods. The convergence is plotted against number of passes over the data.
We compare in Figure 1 the convergence behavior of the estimated parameters and / using SAEM (Delyon et al., 1999) (with stepsize 7 1/k:a where 0.6 after tuning), MCEM (Wei
7

---

Under review as a conference paper at ICLR 2021
1,05
MC-ADAM
8888 MI550
MC-SAC
MC-ADAM
MC-Adagrad
MISSO
1.00
MC-Momentum
3.0
Negated ELBO
0.95
Negated ELBO
2.5
0.90
2.0
0.85
1.5
0.80
1.0
0.75
0.5
0.70
0.0
20
0.0
2.5
7.5
12.5
15.0
20.0
Epoch
Epoch
(a) LeNet-5 on MNIST
(b) ResNet-18 18 on CIFAR-10
Figure 2: Negated ELBO versus epochs elapsed for fitting (a) Bayesian L on MNIST and (b) Bayesian ResNet-18 on CIFAR-10. The solid curve is obtained from averaging over 5 independent runs of the methods, and the shaded area represents the standard deviation.
& Tanner, 1990) and the proposed MISSO method. For the MISSO method, we set the batch size to M(x) = 10 + h22 and we examine with selecting different number of functions in Line 5 in the method - the default settings with (MISSO), 10% (MISSO10) and 50% (MISSO50) minibatches per iteration. From Figure 1, the MISSO method converges epochs than the MCEM, SAEM methods. It is worth noting that the difference among the MISSO runs for different number selected functions demonstrates variance-cost tradeoff. Though wall clock times are similar for all methods, they are reported in the appendix for completeness.
static value with less number of
4.2 TRAINING BAYESIAN CNN USING MISSO
This application follows Example 2 described in Section 2. We use variational inference and the ELBO loss (10) to fit Bayesian Neural Networks on different datasets. At iteration k; minimizing the sum of stochastic surrogates defined as in (6) and (13) yields the following MISSO update
step (i) pick a function index is uniformly on [m]: step (ii) sample a Monte Carlo batch { (zm y Jm=1
from (0, I); and step (iil) update the parameters, with w t(0((=-1), 2m1) as
(T (I)
((0)
Me Fe
ped
80)
V. log p(uis [z,, 1) + V V d((kk(()))))
Medi
M(k)
m=1
where (7*)
Me and d(0) = - - (olog()) (o² + n2)/2 1/2)).
Bayesian LeNet-5 on MNIST (LeCun et al., 1998): We apply the MISSO method to fit a Bayesian variant of LeNet-5 (LeCun al., 1998). We train this network on the MNIST dataset (LeCun, 1998). The training set is composed of = 55 000 handwritten digits, 28 x 28 images. Each image labelled with its corresponding number (from zero to nine). Under the prior distribution т, see (8), the weights are assumed independent and identically distributed according to (0 1). We also assume that q(:; 0) = NNu,, I²)). The variational posterior parameters are thus = (14, o) where (He, l E [d]) where d is the number of weights in the neural network. We use the re- ce-parametrization as w = t(,,2) 2) = μ + az with 2 ~ 10,
Bayesian ResNet-18 (He et al., 2016) on CIFAR-10 (Krizhevsky et al., 2012): We train here the Bayesian variant of the ResNet-18 neural network introduced in (He et al., 2016) on CIFAR-10. The latter dataset is composed of 60 000 handwritten digits, 32 32 colour images in 10 classes, with 6 000 images per class. As in the previous example, the weights are assumed independent and identically distributed according ( I). Standard hyperparameters values found in the literature, such as the annealing constant or the number MC samples, were used for the benchmark methods. For efficiency purpose and lower variance, the Flipout estimator (Wen al., 2018 8) is used.
8

---

Under review as a conference paper at ICLR 2021
Experiment Results: We compare the convergence of the Monte Carlo variants of the follow- ing state of the art optimization algorithms - the ADAM (Kingma & Ba, 2015), the Momen- tum (Sutskever et al., 2013) and the SAG (Schmidt et al., 2017) methods versus the Bayes by Back- prop (BBB) (Blundell et al., 2015) and our proposed MISSO method. For all these methods, the loss function (10) and its gradients were computed by Monte Carlo integration based on the parametrization described above. The mini-batch of indices and MC samples are respectively set to 128 and M()) k. The learning rates are set 10 for LeNet-5 and 10 for Resnet-18.
Figure 2(a) shows the convergence the negated evidence lower bound against the number of passes data (one pass represents an epoch). As observed, the proposed MISSO method outperforms Bayes by Backprop and Momentum, while similar convergence rates are observed with the MISSO, ADAM and SAG methods for our experiment on MNIST dataset using Bayesian variant of LeNet- 5. On the other hand, the experiment conducted on CIFAR-10 (Figure 2(b)) using a much larger network, i.e., Bayesian variant of ResNet- 18 showcases the need of a well-tuned adaptive methods to reach lower training loss (and also faster). Our MISSO method is similar to the Monte Carlo variant of ADAM but slower than Adagrad optimizer. Recall that the purpose of this paper to provide a common class of optimizers, such as VI, in order to study their convergence behaviors, and not to introduce a novel method outperforming the baselines methods. We report wall clock times for all methods in the appendix for completeness.
5 CONCLUSION
We present unifying framework for minimizing a nonconvex and nonsmooth finite-sum objective function using incremental surrogates when the latter functions are expressed as expectation and are intractable. Our approach covers large class nonconvex applications machine learning such as logistic regression with missing values and variational inference. We provide both finite- time and asymptotic guarantees our incremental stochastic surrogate optimization technique and illustrate our findings training binary logistic regression with missing covariates to predict hemor- rhagic shock and Bayesian variants of two Convolutional Neural Networks on benchmark datasets.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Christopher M Bishop. Pattern recognition and machine learning. springer. 2006.
David M. Blei, Alp Kucukelbir, and Jon D. McAuliffe. Variational inference: A review for statis- ticians. Journal of the American Statistical Association, 1 1126518):55-887, 2017. doi: 10.
1180001621499.217..8887777 1285773.
URL https:/ /too:///ooiio org/10.g//oooooo.ooooooo. 11w.1..1100000011522220
Charles Blundell, Julien Comebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learning, pp. 1613-1622, 2015.
Bernard Delyon, Mare Lavielle, and Eric Moulines. Convergence of a stochastic approximation version of the em algorithm. Ann. Statist. 27(1):94-128, 03 1999. doi: 1...214/00/00118311111 103.
URL wwt.hhtt:///em /ooi org. /ttp://..........////////1/13330 /t11////////111111111111
Roger Fletcher, Nicholas IM Gould, Sven Leyffer, Philippe Toint, and Andreas Wächter. Global convergence of trust-region sqp-filter algorithm for general nonlinear programming. SIAM Jour- nal on Optimization, 13(3):635-63 659, 2002.
Z Ghahramani. Probabilistic machine learning and artificial intelligence. Nature, 521(7553):452- 459, May 2015. doi: 10.1038/nature144555 URL https: http///wwww./// ncbi -nmm nih.gov/ pubmed/ (tlomed/260144450 7444/. On Probabilistic models.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Wei Jiang, Julie Josse, and Mare Lavielle. Logistic regression with missing covariates-paramete parameter estimation, model selection and prediction. 2018.
Michael Jordan, Zoubin Ghahramani, Tommi S. Jaakkola, and Lawrence K. Saul. An introduction to variational methods for graphical models. Mach. Learn., 37(2):183-233, November 1999. ISSN 0885-6125, doi: 10.1023/A:10076659077777 URL ht //tii.///oooooo/ http://i......111//...1..//1 10C7665907178
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL
abs 2tabb//4122 /1412 6980.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, ICLR 20/4, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http: / atwaa.ivv...//... org/ abs 13111111122 6114.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Kenneth Lange. MM Optimization Algorithms. SIAM--ociety for Industrial and Applied Mathe- matics, USA, 2016. ISBN 1611974399, 9781611974393.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exxb/mmist// 1998.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):2278-222) 1998.
Yingzhen Li and Yarin Gal. Dropout inference in bayesian neural networks with alpha-divergences. In Proceedingy of the 34th International Conference Machine Kearning-Volume 70, pp. 2052- 2061. JMLR. org, 2017.
Julien Mairal. Incremental
optimization with application to large-scale machine learning. SIAM Optim., 25(2):829 855, 2015. ISSN 1052-6234. doi: 10.1137/ 140957639. https:/ http://///ooooog///////o/oo org 1137/1
10

---

Under review as a conference paper at ICLR 2021
Geoffrey J. McLachlan and Thriyambakam Krishnan. The EM algoritim and extensions. Wi- ley Series in Probability and Statistics. Wiley-Interscienee [John Wiley & Sons), Hoboken, NJ, second edition, 2008. ISBN 978-0-471-201704 doi: 10.1002/9780470111611.. URL
https: /toi .org/ o. 1002/ 90012//970477000 701 91 61
Arthur Mensch, Julien Mairal, Bertrand Thirion, and Gaël Varoquaux. Stochastic subsampling for factorizing huge matrices. IEEE Transactions on Signal Processing, 66(1):113-128, 2017.
Sean Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
J.W. Paisley, D.M. Blei, and M.I. Jordan. Variational bayesian inference with stochastic search. In ICML. icml.ce Omnipress, 2012.
Nicholas G Polson, Vadim Sokolov, et al. Deep learning: bayesian perspective. Bayesian Analysis, 12(4):1275-1304, 2017
Xun Qian, Alibek Sailanbayev, Konstantin Mishchenko, and Peter Richtárik. Miso is making comeback with better proofs and rates. arXiv preprint arXiv:1906.0444 2019.
Meisam Razaviyayn, Mingyi Hong, and Zhi-Quan Luo. A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Optimization, 1262):1126-1153, 2013.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and ap- proximate inference in deep generative models. In International Conference on Machine Learn- ing. pp. 1278-1286, 2014.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-112, 2017.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning. pp. 1139-1147, 2013,
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
Roman Vershynin. High- digensiima probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Martin J Wainwright. High- digensiimesion statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Greg C. G. Wei and Martin A. Tanner. A monte carlo implementation of the em algorithm and the poor man's data augmentation algorithms. Journal of the American Statistical As- sociation, 1599914,,9,-744, 1990. doi: 10.1080/01621459..0 199..99999999...
449400900.......99990444444400, 10474930. URL https: com/ wwwp/bs//o../eee cttp://aaaaaaa/.000000//1111111. 1990 19t. 10474930.
/ wwwwwtaandoont
Yeming Wen, Paul Vicol, Jimmy Ba, Dustin Tran, and Roger Grosse. Flipout: Efficient pseudo-
independent weight perturbations on mini-batches. arXiv preprint arXiv: 103.00438 2018.
11

---

Under review as a conference paper at ICLR 2021
A PROOFS OF THE THEORETICAL RESULTS
A.1 PROOF OF THEOREM 1
Theorem. Under HI-H4. For any Kmax E EN, let K be an independent discrete r.v. drawn uniformly from (0. .... maxx - 11 and define the following quantity:
A (Kmm)) == 2nLE ( - (m (m((k)))) 44C,
Then we have following non-asymptotic bounds:
A (mar)) and (0 S
A (Kmoe)
Cg M (k)
F (0(K)))
max
K Kmax
K Kmax
Proof We begin by recalling the definition
(0) = 1 (0)
i=1
Notice that
[(++1) (0) E. (0, ,,
1
(rtt))) M Mottt))
- (0) + n
1 -
(0; (0; ) Ma)) Ln (0
( Maxe
Furthermore, we recall that
1 +
(0) = (0) - C(
Due to H2, we have
V ( (0(+))) 2 (
(18)
To prove the first bound in (16), using the optimality of g(++1), one has
(o(+2)) s ((*+1)
(19)
= - - #/4 (Z., (0 ((0) ( M Zi, (0(*), o (Zig.m (ommmm=) Im=l ))
Let F& be the filtration of random variables up iteration ks i.e. lie-1 (2ll-1) s We observe that the conditional expectation evaluates to
(t-1) Mie-1
0000)k
Jmm.
Egg E C (0()),
{ I m=
(k)
Mas
[ [F
Mas
C(O(()) + E,
E
Ti (O (A))
(k) -(()))) -
((())) ix [Fe
M(a)
m=
C.
- <(((())) +
MM(
where the last inequality is due H4. Moreover,
B Cr, (o ( ( m |Fn] - E 2,000
) [(() (0(*)
Taking the conditional expectations on both sides of (19) and re-arranging terms give:
(o(A)) L(((k)) < nE 2ik)
7 (
C.
(20)
MM(x
12

---

Under review as a conference paper at ICLR 2021
Proceeding from (20), observe the following lower bound for the left hand side
2 (o(b)) - ((O(k)) (a) Z(ch (o - (th) (O)()) + e(h) (o(ck)
(0) ((h) (0(())) ( (o(h)) 1
(0())))
2L
M ky
Σ
((+)) (0 (8),
(Tt)
- 0(7))
1
Zim
M(r m=1
2L
(0(0))
where (a) is due to (0(A)) lef. HI], (b) is due to (18) and have defined the summation in the last equality as -8(h) (0 Substituting the above into (20) yields
V (e(+)(( (0(1) 12 nE (0(+)) ( +
C. + ((()))
(21)
2L
M(())
Observe the following upper bound on the total expectations:
C.
B (())
n
M
which is due to H4. It yields
B[ (0
(O 1P < 2nLE ( - - (0+t)((((+11))) +
2LC,
E
2LC,
VM(x
M
1=1
Finally, for any Kmax E N, we let be a discrete r.v. that uniformly drawn from {0, 1, Kmax 1}. Using H4 and taking total expectations lead to
Kmac
E (1 = K Kmax
(K) |F
(22)
20LE (0(0)
[( (Kmae) (0(mm))) }
2LC,
1
E
K max
K max
M()
M
For all [1, n]], the index is selected with probability equal to x dently on the past. We observe:
1 when conditioned indepen-
1 5-1
E (xt)
M 1/ 1/2 (R-S)
(23)
n1
1=1
Taking the sum yields:
K
J-1
Knn
R-(++1)
BIM 1/2
1
Mik-j)
1/2
2
1-
1
M
1/2
(xt)
n2
k=0
k=0
j=1
k=0
1=0
Kmix1
Kmn
k-(+1)
Kmix
May
1/2
M.
1=0
k=1+1
1=0
(24)
where the last inequality is due to upper bounding the geometric series. Plugging this back into (22) yields
E (I
(O(K))))
EI Ell (0 )P
K max
k=
2nLE(
(0(0)) (mmm) (@(Kmar)) )
Kmn 4LC,
A(Kra))
K Kmax
K Kmax
M((k)
=
Kmax
k=0
13

---

Under review as a conference paper at ICLR 2021
This concludes our proof for the first inequality in (16).
To prove the second inequality of (16), we define the shorthand notations g(k) g(O(k)), g(
m0, ( J. 9 ma g (6) We observe that
(k) ('(((k) 0 ((k)
g inf
AE
[0(k) - 01
Li=1 (0(), 0 ((k); 0(())) (V(())((())) - ((4))
inf
A0
0((k) 01
||0(k) 01
Σ Li=1 (0(,, 0 O()); 0l+)))
2 ( + inf AE
(((k) 01
where the last inequality is due to the Cauchy- Shuchy-Schwarz inequality and we have defined (, d: 1) the directional derivative of ((())())) 0 along the direction d. Moreover, for any E o
(0(k) 0 ---0 0(();
1=1
200
(o ((k)) -ii) (B(h), 0 - -(h))
Σ n i=1
1
2, (0 0(k); g(+))
+
(
1 n
1 0 0(0)
(1 0 O((); o (
M (
where the inequality is due to the optimality of (() and the convexity of [(k) (0) [ef. H3J. Denoting scaled version of the above term as:
M ( Em=l ((((()) 0 (00; o(!)) = (,(a(,) 0 0 0)))
1/2 E (+3))
(M)
| 011
We have
(k)) 2 (e(h (k))
inf (-c (x) (0)) 2 - ( sup
(1)) (0))
(25)
AE8
AEG
Since (*) = 9 and 9
(k) (k) 0. this implies
(k) < (2 (0(*))
sup (k) (0)
(26)
oc
Consider the above inequality when 1: K, iee. the random index, and taking total expectations both sides gives
Elg < E v I1l + E(sup el (K)(
We note that
A(Kmax)
Elllve
K Kmax
where the first inequality due to the convexity of (-)2 and the Jensen's inequality, and
[uu o
(K)
(K))())
Kmx
E Elsup el (k) (0)
(a)
S
Cgr
Kmac
E
n
M 1/2
Kmax
K
Kmax
(+
k=0
k==
(
Cgr
Knon
M 1/2
K
(K)
max
k=
where (a) due to H4 and (b) is due (24). This implies
EE (K)
A (Kma)
Cet
Kmm-
Σ
M 11112
1/2
Kmax
Kmax
k=0
and concludes the proof of the theorem.
14

---

Under review as a conference paper at ICLR 2021
A.2 PROOF OF THEOREM 2
Theorem. Under H1-H4. In addition, assume that (M(4)h20 is a non-decreasing sequence of integers which satisfies o M cc. Then:
1. the negative part of the stationarity measure converges a.s. to zero, i.c., lim g- (0(k)) a. 0.
k-+20
2. the objective value (()())) converges a.s. to finite number L. i.c., lime-+0o (()(k) a C.
Proof We apply the following auxiliary lemma which proof can be found in Appendix A.3 for the readability of the current proof:
Lemma 1. Let (Vi) be non negative sequence of random variables such that [[]] co.
Let (Xx) a non negative sequence of random variables and (Ex)a20 be sequence of random variables such that Ex= Exll < co. for any k 2 1:
V& S V Xk-1 + FX-1
(27)
then:
(i) for all k 2 0. [[V&] < oo and the sequence (Vi)a2a converges a.s. to finite limit Voo-
(ii) the sequence (B(V k20 converges and lim k-o
[[[[] E[Voo).
(iii) the series k Xs converges almost surely and Σ Ek=o E[Xx] co.
We proceed from (19) by re-arranging terms and observing that
( S (ix) 3/2 (O(t,
(0(*); (( - C.,, (Q(t)) k(k)))
-((itt Li++1) (iatt)(o(ht)))) (o(k+1))) + (ci+) (ik) (o(k))
(C (0( (10), (k) ) - ( ((()))
May)
(rti) Mick
(c, (o o g() E. (O(k), g
Our idea to apply Lemma 1. Under HI, the finite sum of surrogate functions (0). defined in (15), is lower bounded by a constant > for any 0, To this end, we observe that
V2 = 2 k) (O(k))
inf Cs 2 0 k00
(28)
non-negative random variable.
Secondly, under H1, the following random variable is neg-tigetive
X₂ 1.4 (o( L., (B o(1)) 20.
(29)
Thirdly, define
Fx = -Z(((()))(((tt)) - - + (O(K) _ (0(8))
+ 1 n (o(h)) (k), [2(()) 1
) (
(30)
(Tt)) Mirt))
+ (C., (0 (1)))) Li, (0( ( f I Immt" ))
Note that from the definitions (28), (29), (30), we have V441 Vi - Xx + Ex for any à 2 1. Under H4, we observe that
B[IE,, (0(8); (k)) ( ) E. (0(k);
< C.M 1/2
(k)
(T))) (rtb) M
E C,, (0(k); g(Tit)) Li, (( f2 m==
< C.E.
M M-1/2 1/2
(7!
15

---

Under review as a conference paper at ICLR 2021
E (Ol (10) S -.E,, G,E
M 1/2 1/2 (T()
Therefore,
E - e. (Mi))
+ E M 1/2 + Σ 2i=1 (+t)
1/2 + M Mob
Using (24) and the assumption on the sequence (M(x) J220 we obtain that
EEI (2 2n)
M 1/2 oc.
k=0
Therefore, the conclusions in Lemma 1 hold. Precisely, we have Ex Xx 00 and
Σx=o x < co almost surely. Note that this implies
1
E E[C, (0 ( (0000)00) 2., (0(K); (()))]
00
k=U
k=O
80
= 1 20
- -
n
Since (((A)) 2 0, the above implies
lim (0(k)) a.s. k+000
(31)
and subsequently applying (18), we have lo ||ē(k) (0(()) 0 almost surely. Finally, it follows from (18) and (26) that
lim ( S lim V ((k) + lim sup le (2) (0)1=0, 1-+00
= 0,
(32)
k=+20
k0 BEe
where the last equality holds almost surely due to the fact that Σ Elsupace (8) (0)) < co. This concludes the asymptotic convergence of the MISSO method.
Finally, we prove that (()(k) converges almost surely. As a consequence of Lemma 1, is clear that (Ve converges almost surely and so is (O(+) )220 ie., we have lim3 (0())) L. Applying (31) implies that
L = lim (o(k)) lim L(((k)) k-+00
10+00
This shows that (()(k)) converges almost surely L.
A.3 PROOF OF LEMMA
Lemma. Let (V+)a20 be negative sequence of random variables such that E[Vo Let (Xx) a non negative sequence of random variables and (Ex)uz0 be sequence of random variables such that C < co. for any k 2 1:
V/ S V X + Ex-1
then:
(i) for all k 2 0, [V[x]] < oo and the sequence (Vx) converges a.s. to a finite limit V
(ii) the sequence (E(V converges and lim [V[] Voo]
k-+00
(iii) the series Eie X converges almost surely and Ex= [E(Xa] xc.
16

---

Under review as a conference paper at ICLR 2021
Proof We first show that for all & 2 B[V]]
< co. Note indeed that:
0 05 S Vo-
E S Vo
+
Σ
Bj
(33)
j=1
j=1
==1
showing that [[V]] < E[V] Σラー Ej]
< <0.
Since 0 1 X - V V En also obtain for all & 2 0, [[Xx] < co. Moreover, since
ビ 00 E
|B3]
the series 2j=1 Ej converges a.s. We may therefore define:
W&
Vv
Fg
(34)
Note that B[] < [VA] + Eie 2j=k+1 [bgl
60.. For all h: 2 1, we get:
00
W& S Va-1 Xx Σ
E,
S
W k-1 X3 S Wa-1
(35)
j=k
B[W]] S
Hence the sequences (W&)u20 and (E(Wa)) :20 are non increasing. Since for all k 2 0, WR > اド= Eyg -oo and B[WA]] - E -oc, the (random) sequence (W&)
converges a.s. limit Wo and the (deterministic) sequence (E(Wa]) converges limit Woo Since [W&l < Vo + Ee= EEyl the Fatou lemma implies that:
Ellim inf [W&]] 1-+00
E W
lim inf B|[ S EVVo + Σ
B E3 < 00,
(36)
k-+00
showing that the random variable Woo is integrable.
In the sequel, set Us A Wo- WE. By construction we have for all h: 2 0, Uk 2 0, Us S Uk+1 and
B[UA] & B|]l [[[W < co and by the monotone convergence theorem, we get:
lim B[Ux] k000
E lim Uz)
(37)
k-000
Finally, we have:
lim BlUx] [[W) Who k+o
and
E lim Uk] = E(Wo] B[] k
(38)
showing that o[W wx and concluding the proof of (ii). Moreover, using (35) we have that We S Wh-1- X2 which yields:
X, S Wo Wo <0,
(39)
E[X,] < [[W] woo 00,
an concludes the proof of the lemma.
B PRACTICAL DETAILS FOR THE BINARY LOGISTIC REGRESSION ON THE TRAUMABASE
B. TRAUMABASE DATASET QUANTITATIVE VARIABLES
The list of the 16 quantitative variables we in our experiments follows age, weight, height, BMI (Body Mass Index), the Glasgow Coma Scale. the Glasgow Coma Scale motor com- ponent, the minimum systolic blood pressure, the minimum diastolic blood pressure, the maximum
17

---

Under review as a conference paper at ICLR 2021
number of heart rate (or pulse) per unit time (usually minute), the systolic blood pressure rival of ambulance, the diastolic blood pressure at arrival of ambulance, the heart rate at arrival of ambulance, the capillary Hemoglobin concentration, the oxygen saturation, the fluid expanston colloids, the fluid expansion cristalloids, the pulse pressure for the minimum value of diastolic and systolic blood pressure, the pulse pressure arrival of ambulance.
B.2 METROPOLIS HASTINGS ALGORITHM
During the simulation step of the MISSO method, the sampling from the target distribution mis = p(2i,mis) Rioss Ui; O) is performed using Metropolis- (MH) algo-
rithm (Meyn & Tweedie, 2012) with proposal distribution g(Zi,mis; 8) := p( Ris 6) where
(3, Q2) and (E, 2.) The parameters of the Gaussian conditional distribution of 2i.mia /2i
read:
ç = .miss + Amise
D obs, obe (Zi,obs - Bobs)
Σ = Amis,mis + Dbmse, S obs obs Llbss milss,mis..
where we have used the Schur Complement Robe,obs in Q and noted Bmss (resp. Bobe) the missing (resp. observed) elements of B. The MH algorithm is summarized in Algorithm 3.
Algorithm 3 MH aglorithm
1: Input: initialization 2i,mis,0 ~ ( (Zi, d)
2: for m L, .M do
3: Sample 2i,mis.m ~ Q 5)
4: Sample 2((1,, 1l))
mai, (0) ( m)))) ):8)
5: Calculate the ratio r = x aii.aii (R, 1):8)
6: if u < then
7:
Accept Zi,mis,m
8: else
9:
mim + 2i,mis,m-1
10: end if
11:
end for
12:
Output: Mi M
B.3 MISSO UPDATE
Choice of surrogate function for MISO: We recall the MISO deterministic surrogate defined in (7):
2, log (p.(mmmi fl (2). 0)) (2( (dz))
where 0 = (8, 8, and 0 (5, 3, ②). We adapt it to our missing covariates problem and decom- pose the surrogate function defined above into an observed and a missing part.
Surrogate function decomposition We adapt it to our missing covariates problem and decompose the term depending on 6, while & is fixed, in two following parts leading
(,(00)) 0)
| log (f Zi,obs (Pi,mii O (dzr,.
/ log (ps lr. o.s d) Ei B, 22)] pr(zs, (d24,
log Pe(val miss zi,bbs, 5) (2i, 0) (dZi, /
log pe(2i, 8, 8,12)p((2, (2112, (dz,,mm..)
(8,0
(3,00)
(40)
18

---

Under review as a conference paper at ICLR 2021
The mean and the covariance Ω of the latent structure can be estimated minimizing the sum of MISSO surrogates z.") (1, 0, {2m JM (mmm)m) defined as MC approximation of (3, S2 0), for all
i [[<]] in closed-form expression.
We thus keep the surrogate - (3, S2, 0) as is, and consider the following quadratic approximation of (6, (6, O) to estimate the vector of logistic parameters ò:
4 (6, 0)
V log pa (Jii 21,obs 8= 8 (Z () 8)
-66 (6-
72 log pi Pi miss Zi,obs, p) (2i 8) Pi Pii(ii,iiss ())i(d22,,mss( ō)
Recall that:
V log Pi mimmsss 2r, 8) 2: (yi S(6) 21))
2 log (: 2i Ri, 0) - -iZZ S(0
where 5(u) is the derivative of S(u). Note that S(u) - 1/4 and since, for all e [n]. the x matrix 2,2, is semi-definite positive
assume that:
LI. For all E [m] and e > O, there exist, for all zı E Z, a positive definite matrix Hi(zi) == [ziz]] +ela) such that for all ô E 18,,-2z, S(0 2) S H; (z,)))
Then, use, for all E [n:]. the following surrogate function estimate 6:
(6.0) - 2.. DJ (8 8) + (0 8) 8)_
(41)
where:
D, = / v Vlogpi pe (x 2i,o 8) 6= 8 Ps (24 ()
H. | (z pa 0)11, (dzz,
Finally, at iteration k; the total surrogate is:
(0) 2, (10,)(tt)((z)) (zrm Mort
((2) (3, 0115), 3 Fm
Mort
( (6 - )(r:))
(42)
1
((+)) (11 (6 - o(+t))T
+
2n
where for all E [n]]
M Mir
- s((stt))) sm,(((11))
M
Zim
mmm
(T))))
4M
Fim
5,m
Minimizing the total surrogate (42) boils down to performing a quasi-Newton step. It perhaps sen- sible to apply some diagonal loading which is perfectly compatible with the surrogate interpretation we just gave.
The logistic parameters are estimated as follows:
Mc.
(kk) = arg min
Σ 21 (5, g(t)), (2mmbma))
JEB
19

---

Under review as a conference paper at ICLR 2021
where 2. (6, 06+,), {zim famm)==i? is the MC approximation of the MISO surrogate defined in (41)
m
and which leads to the following quasi-Newton step:
16
((h)
8(72)
71
with ((4) - - D and (k) E (T))
MISSO updates: At the k-th iteration, and after the initialization, for all i [n]] of the latent variables )z the MISSO algorithm consists in picking an index in uniformly on [n>], complet- ing the observations by sampling a Monte Carlo batch (k) mism J J= of missing values from the
conditional distribution miii ohss Vi, ((x-12) using an MCMC sampler and computing the estimated parameters as follows:
M
(8() arg min
E E( (8, (,00())000))))) m2
M
1
(k)
BEB
M(r!'
i,m
M (
(2) arg min
1
(12) (3(8), Ω2 g(T)), fzsm Jm=1
M
1 Σ
(43)
Wimm
nee
M(r))
1=1
1=1
m=1
(kk)
((. (11()) D(k) ((kk)
n1 i=1
where 2(x) (k)
mim Z1,obs) is composed a simulated and an observed part, ((k)
- ((0)) (6)
E u
(+)) and W. 2i,m (=
(k) (k)
g( Be-
sides, 2. 2 22 0, {
JM MM) and -. (B, S2, 0, (m))))) are defined MC approximation of (0)) (8, 22 0) and (.2) (3, 2, for all i E [xx] as components of the surrogate function (40).
B.4 WALL CLOCK TIME
We provide Table 1, the running time for each method, plotted in Figure 1, employed to train logistic regression with missing values on the TraumaBase dataset (p = 16 influential quantitative measurements, on 6384 patients).
The running times are sensibly the same since for each method the computation complexity per epoch is similar. We remark a slight delay using the MISSO method with a batch size of 1, as our code implemented
R, not totally optimized and parallelized. Yet, when the batch size tends to 100%, we retrieve the duration of MCEM, which is consistent with the fact that MISSO with full batch update boils down to the MCEM algorithm.
Table 1: Logistic Regression with missing values: rumning time in seconds for 10 epochs.
SAEM
MCEM
MISSO
MISSO10
MISSO50
Logistic Regression
2033.2
1972.4
2244.8
2139.4
2005.2
We plot Figure 3, the updated parameters for the Logistic regression example against the time elapsed (in seconds).
20

---

Under review as a conference paper at ICLR 2021
SAEM MCEM
MISSO
MISSO50
0.000
MISSO10
80
0.010
70
60
-0.020
MCEM
MISSO10
0
250
500
750
1000 1250 1500 1750 2000
250
1000 1250 1500 1750 2000 Wall clock time (in seconds)
500 750
Wall clock time (in seconds)
Figure 3: Convergence of parameters o and for the SAEM, the MCEM and the MISSO methods.
The convergence is plotted against time elapsed (in seconds).
C PRACTICAL DETAILS FOR THE INCREMENTAL VARIATIONAL INFERENCE
C.I NEURAL NETWORKS ARCHITECTURE
Bayesian LeNet-5 Architecture: We describe in Table 2 the architecture of the Convolutional
Neural Network introduced in (LeCun et al., 1998) and trained on MNIST:
layer type
width
stride
padding
input shape
nonlinearity
convolution (5 x 5)
I X 32 x 32
ReLU
max-pooling (2 2)
2
0
6 28 x 28
convolution (5 x 5)
1 x 14 X
ReLU
max-pooling (2 2)
2
0
16
10 10
fully-connected
120
400
ReLU
fully-connected
84
120
ReLU
cully-connected
10
84
Table LeNet-5 architecture
Bayesian ResNet-18 Architecture: We describe Table the architecture of the Resnet-18 we
train CIFAR-10:
layer type
Output Size
18
nonlinearity
convl
112 x 112 x 64
7 7, 64, stride
ReLU
[ x 3,
conv2x
x 64
ReLU
3 3,64
3 x 128
conv3x
28 28 128
x
ReLU
3 x 3, 128
3 x 3, 256
conv4x
14 x 14 x 256
x2
ReLU
3 x 3, 256
3 x 3, 512
conv5x
7 7 x 512
x
ReLU
3 x 3, 512
average pool fully connected
1 x 512
x 7 average pool
ReLU
1000
512 x 1000 fully connections
softmax
1000
Table 3: ResNet-18 architecture
C.2 ALGOITHTS UPDATES
First, we initialize the means μ for f [d] and variance estimates (0), At iteration minimizing the sum of stochastic surrogates defined as in (6) and (13) yields the following MISSO update
21

---

Under review as a conference paper at ICLR 2021
step (i) pick a function index ij uniformly on [n]] step (ii) sample a Monte Carlo batch { {zm Mag
Im=1
from (0, I); and step (iil) update the parameters as
13 Σ
n
7 n2
(2) ー 72 Pe
7 Y2
(()) ML.
and
(k)
Σ
(77))
((h) 0,
(44)
n 1m1
where we define the following gradient terms for all i E [1, n|]:
((k)
log p(gl(,s w)
10=0(00-11),10 + Vu ((
ped
(R)
m=
(45)
M(k)
8(8) 0,
mm V. (ogg(vil);; (0Ck
+ vod(O(k-1))
M(a)
Note that our analysis in the main text does require the parameter to be in compact set. For the current estimation problem considered, this can be enforced in practice by restricting the parameters in ball. In our simulation for the BNNs example, we did not implement the algorithms that stick closely to the compactness requirement for illustrative purposes. However, we observe empirically that the parameters are always bounded. The update rules can be easily modified to respect the requirement. For the considered VI problem, we recall the surrogate functions (11) are quadratic and indeed a simple projection step suffices to ensure boundedness of the iterates.
For all benchmark algorithms, we pick, at iteration k, a function index i& uniformly on [n]] and sample a Monte Carlo batch {am I==1 ) Maas from the standard Gaussian distribution. The updates of the parameters jr for all & E [d] and break down as follows:
Monte Carlo SAG update: Set
(k) Pt 14
1k-1) 2
(A) Ma.
and ((k) = (k-1) 7
((A)
i=1
(kk-1) where 8(h) 8 8(k-1) 1) and ((h) = =8th 0,
1) for i + in and are defined by (45) for i ig. The learning
rate is set to y = 10-3
Bayes By Backprop update: Set
Me = u1 (k-1) 1) 2 8()) Mede and ((k) = _ -()))))))
0.4k
where the learning rate y 10
Monte Carlo Momentum update: Set
(k) (k-1) 1l 1e
(Ak) and (a) = (1-1) + +.(())
where
8 ((k) = ao(kk-1 Hed
1k- - 2 8(R) and
b(h) = abbk ((k-1) - 7 8(N)
n Medie
n
where a and y, respectively the momentum and the learning rates, are set to 10-3
Monte Carlo ADAM update: Set
(k) = 14 n "1
(k-1)
N m (k) /(/ (/mm(/) (k) +e) and (4)) = (k-1)) - 2 Im (k) /(V /n (k) +c),
n
where
m! (k) mh-11) (k-1) ((1 - -p)) with
m pim (k-1) + (1 pt ((k)
pr
Meith
((k) w/t (k-1)) 1)/11111111 - pb)) with
((()) = p20 + (1 p1) ( 8 (k)
Me
0.
and
m = m (k-1) /11 - x with
m (k) = pim (k-1) (k-1) + (1 - p1) ((K)
0,
(() = of 1) /11 / with (k) = p2u (k- ()-)) + (1 - p1) (8())
7.11
The hyperparameters set as follows: 7 10-3 pl 0.9, p2 0.999, 10-8
22

---

Under review as a conference paper at ICLR 2021
C.3 WALL CLOCK TIME
We provide Table 4, the running time for each method, plotted in Figure 2, used to train a Bayesian variant of LeNet-5 on MNIST. The incremental method MISSO and MC-SAG displays similar wall clock time, despite being a bit worse given (a) the initialization that requires to compute a vector of gradients kept in memory and updated through the iterations and (b) the average operation for each parameters update to compute the aggregated drift term, see (44).
Table 4: Bayesian Deep Neural Network: running time in seconds for 100 epochs.
MC-Adam
MC-Momentum
BBB
MC-SAG
MISSO
LeNet-5 on MNIST
12889
12816
12690
13822
13367
We plot Figure 4, the learning curves for the MNIST example against the time elapsed (in seconds).
9.5
MC-Adam
MC-SAG
MISSO
BBB
MC-Momentum
Negated ELBO
8.5
8.0
2000
4000
6000
8000
10000
12000
Wall clock time (in seconds)
(a) LeNet-5 on MNIST
Figure 4: Negated ELBO versus wall clock time for fitting a Bayesian LeNet-5 on MNIST. Plotted on the average of the 5 repetitions.
23


Reviews:
[{"review_id": "w0bFEdBZ_D8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed MISSO, which is an extension of MISO to handle surrogate functions that are expressed as an expectation. MISSO just used the Monte Carlo samples from the distribution to construct objectives to minimize.\n\nIt seems to me that MISSO is just a straigforward extension of MISO, also the empirical results seems to suggest the proposed MISSO has no advantage over Monte Carlo variants of other optimizers, such as MC-SAG, MC-ADAM, thus it is not clear to me what is the significant aspect of this work. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ikvdmh1Y77D", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This manuscript contributes a stochastic optimization method for finite sums where the loss function is itself an intractable expectation. It builds upon stochastic majorization-minimizations methods, in particular MISO, that it extends to use Monte-Carlo approximation of the loss.\n\nI am happy to see some attention put to the majorization-minimizations methods, which have many interesting benefits. The paper contributes nice theoretical results, in particular non-asymptotic results. However, I believe that these theoretical results are not enough to situate the contribution with regards to the wider landscape of optimization methods for machine learning.\n\nIn this respect, the empirical study is crucial, however it is not completely convincing. Expressing figures 1 and 2 as a function of the number of epoch, rather than as an estimate of runtime is not meaningful: it discards the cost of running the inner loop, which varies from one approach to another. It would leed to believe that MISSO50 is the best option, which is probably not the case.\n\nAlso, MC-ADAM seems to outperform MISSO for variational inference\n\nWith regards to the broader contribution, it is very appreciable to have a wider theory of stochastic optimization with MM methods. It would have been good, however, to have a discussion of the link of the contributed method to the follow up work by Mairal and colleagues, Stochastic Approximate MM (Mensch et al 2017).\n\n\n**Additional comments after the discussion**\n\nThe authors have thoroughly replied to all the comments from the various reviewers.\n\nAfter reading all the discussions (other reviews as well as replies from the authors), it appears to me that the practical relevance of this contribution is not completely clear. The computational cost of each iteration is large. The benchmarks do not show clear improvements in computational.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QmXEmpx0JW", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summarize what the paper claims to do/contribute. Be positive and generous.\n\nIn this paper, the authors consider solving the optimization of the summation of a finite number of component functions. The proposed algorithm is based on a previous work called Minimization by Incremental Surrogate Optimization (MISO). The MISO is a majorization minimization algorithm, which shares a similar update style of the SAG method. However, different from SAG, whose convergence is not available for nonconvex optimization, and is even very tricky in convex case, MISO enjoys a global convergence guarantee due to its majorization property. Based on this existing method, for the problems whose majorization surrogate is very hard to construct, e.g. variational inference of latent variable models, the authors of this paper propose a sample average approximation of the exact majorization surrogate function. The convergence of the proposed algorithm is also provided in this paper. \n\n2. Clearly state your decision (accept or reject) with one or two key reasons for this choice.\nThis paper is marginally below the acceptance threshold. \n\n3. Provide supporting arguments for the reasons for the decision. \n\n(i). (Weakness) For the hard cases where each component is an expectation itself, the strategy applied here is to do a simple sample average approximation. This requires the sample size of in each iteration (M_k) to satisfy the condition that \\sum_k M_k^{-1/2}<\\infty. That is, in the $k$-th iteration, the sample size will be at least k^2. According to Theorem 1, the number of iteration should be K\\geq nL/\\epsilon^2. Consequently, the total sample complexity of this method seems to be \\sum_{i=1}^{K} k^2 ~ n^3L^3\\epsilon^{-6}. The $n^3L^3$ dependence seems very bad. However, let us do a simple estimation of a naive method: 1. In each step compute the \\epsilon-accurate estimation of the gradient for each component, this needs O(n \\epsilon^{-2}) samples per iteration. Then if the function is L-smooth (this paper can handle nonsmooth cases) then the total iterations will be O(L\\epsilon^{-2}). Then the total sample complexity seems only O(nL\\epsilon^{-4}). This might need some clarification. \n\n(ii). (Strength) This paper provides a non-asymptotic rate of convergence for the MISSO algorithm, which implies a non-asymptotic rate for the MISO method, whose non-asymptotic rate is not known before, which should be appreciated. Moreover, the numerical experiment in this paper is well presented. \n\n4. Provide additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\n(i). The MISSO (and MISO) share a similar updating style with SAG, it will be better if the authors could add some discussion on their relation and difference. Or, if such discussion exists in other literature, add a reference to that. \n\n(ii). After the Theorem 2. It may make sense to give the sample complexity of the result. Namely, to get the optimality measure \\leq \\epsilon, how many sampled are needed. Specifically, by the reviewer’s rough estimation, the dependence on n and L is O(n^3L^3), see my argument before, this dependence is not reasonable. My question is that can the authors carefully balance the parameters and derive a more reasonable sample complexity? If the O(n) and O(L) dependence can be achieved, the reviewer is willing to change to a higher score. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QCk_fNmpO92", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper propose a doubly stochastic MM method based on Monte Carlo approximation of these stochastic surrogates for solving nonconvex and nonsmooth optimization problems. The proposed method iteratively selects a batch of functions\nat random at each iteration and minimize the accumulated surrogate functions (which are expressed as an expectation). They establish asymptotic and non-asymptotic convergence of the proposed algorithm. They apply their method for inference of logistic regression model and for variational inference of Bayesian CNN on the real-word data sets.\n\nWeak Points.\nW1. The authors do not discuss the connections with state-of-the-art second-order optimization algorithms such as K-FAC.\nW2. The proposed algorithm still falls into the framework of MM algorithm and a simple convex quadratic surrogate function is considered. The convergence rate of the algorithm is expected.\n\nStrong Points.\nS1. The proposed method can be viewed as a combination of MM and stochastic gradient method with variance reduction, which explains its good performance. \nS2. The paper contains sufficient details of the choice of the surrogate function and all the compared methods in the experiments.\nS3. The authors establish asymptotic and non-asymptotic convergence of the proposed algorithm. I found the technical quality is very high.\nS4. Extensive experiments on binary logistic regression with missing values and Bayesian CNN have been conducted.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7WMCspilEAL", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper develops a stochastic MM-type algorithm to minimize a finite sum. Essentially, the stochastic method draws one sample at each iteration, and find a majorization surrogate for the corresponding loss, and find the minimizer for the updated total loss.\n\nOverall, I don't find the paper well-developed and doesn't meet the bar of a top conference like ICLR for the following major concerns:\n\n1. The major flaw is that in each iteration, the algorithm requires us to find the minimizer of the updated total loss (Step 8 of algorithm 2). This step is computationally as expensive as the update step in a batched MM algorithm. For a stochastic-type algorithm, I would expect the update only finds the minimizer of the stochastically picked individual surrogate function.\n\n2. By minimizing a stochastically picked individual surrogate function, the convergence follows by existing literature on stochastic proximal gradient method, there Theorem 2 follows without much difficulty.\n\n3. The convergence rate of the proposed method is not derived, which shouldn't be too difficult to derive.\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends the Majorization Minimization principle, particularly the MISO method, to problems where the surrogate of randomly selected batch functions are intractable, such as in formulations rising from Variational Inference. There is a large gap between the reviewers' evaluations even after the author rebuttal and discussions. While the strength of the proposed method looks to be its generality, the main criticism from the reviews are the limited applicability and less convincing arguments and empirical evidences against alternatives such as Monte Carlo versions of popular adaptive stochastic optimization methods. Weighing these considerations and considering strengths of other submissions on similar topics, I have to recommend rejection of the paper at the current form.
Decision: Reject