Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
Majorization-minimization algorithms consist of iteratively minimizing a majorizing surrogate of an objective function. Because of its simplicity and its wide applicability, this principle has been very popular in statistics and in signal processing. In this paper, we intend to make this principle scalable. We introduce a stochastic majorization-minimization scheme which is able to deal with largescale or possibly infinite data sets. When applied to convex optimization problems under suitable assumptions, we show that it achieves an expected convergence rate of O(1/ √ n) after n iterations, and of O(1/n) for strongly convex functions.
Equally important, our scheme almost surely converges to stationary points for a large class of non-convex problems. We develop several efficient algorithms based on our framework. First, we propose a new stochastic proximal gradient method, which experimentally matches state-of-the-art solvers for large-scale ℓ 1 -logistic regression. Second, we develop an online DC programming algorithm for non-convex sparse estimation. Finally, we demonstrate the effectiveness of our approach for solving large-scale structured matrix factorization problems.
Summary: This paper suggests a stochastic 
      algorithm based on majorization-minimization principle, i.e., iteratively 
      minimizing a majorizing surrogate of an objective function, for convex, 
      strongly convex and also certain non-convex (DC) optimization problems. 
      The majorization-minimization principle is known to underlie a number of 
      known algorithms such as expectation-maximization (EM). The theoretical 
      results are also supported with various numerical experiments. 
      Quality: Overall the problem is well-motivated and the 
      conditions used in the analyses, theoretical developments and their proofs 
      (I did not check the ones used for the math background) seem correct. Yet 
      the paper is missing a number of quite related literature on first order 
      methods for nonconvex problems such as “Stochastic first-and zeroth-order 
      methods for nonconvex stochastic programming“ by Ghadimi and Lan. Also the 
      logarithmic loss in Corollary 3.2 due to decreasing step sizes indicates 
      this method is not an optimal algorithm. The same is true for strongly 
      convex function case given in Proposition 3.2. This should perhaps be 
      emphasized a bit clearer. The paper seems to be very closely 
      connected with the reference [19]. The authors should state for each 
      proposition, lemma, etc., whether they were from [19] or not, or whether 
      the corresponding analysis from [19] easily extends to this case or not. 
      The numerical results seem promising. Yet there is a caveat 
      between the theory presented and numerical results. First of all, almost 
      all of the theory is built upon assuming that the domain of the 
      optimization problem to be solved is bounded, i.e., for the stepsizes 
      theoretically analyzed one needs to know an upper bound on 
      \|\theta^*-\theta_0\|_2 where \theta^* is t he optimum solution and 
      \theta_0 is the initial point. Also this quantity naturally occurs, as is 
      the case with other first order methods, in the convergence rates. Yet in 
      the experiments, all of the problems tested have unbounded domains. 
      Moreover, the convergence analysis of the algorithms are carried over for 
      specific stepsize rules, i.e., {\gamma\over \sqrt{n}} etc. On the other 
      hand, the step size rules used in the experiments have quite different 
      forms, and changes from problem to problem. I think this is a bit 
      disturbing. The authors should either give justification for the step 
      sizes used in the experiments theoretically or should use the ones they 
      have build the theory for (at least for comparison purposes, they should 
      be included in the experiments, anyway). Comparisons against FISTA is nice 
      yet there are better (optimal) algorithms for strongly convex functions, 
      and comparisons against those should also be presented. Clarity: 
      The paper is mostly written in a clear fashion, with a reasonable 
      logical structure. On the other hand, reading the supplemental material is 
      almost essential in terms of digesting the notation, etc. I guess given 
      the page limitation, there is no other way to fix this issue either. There 
      are a few minor typos, grammatical errors. Also certain terms and notation 
      such as DC or use of options 2 & 3 in Algorithm 1, 
      $\overline{f}_n(\cdot)$ should be introduced earlier. Originality 
      & Significance: Despite the connections with the existing 
      algorithms, to the best of my knowledge the results seem original and 
      valuable (especially in the nonconvex case). Minor issues: a. 
      On page 4, line 180: “For space limitation details, all proofs…” should be 
      “For space limitation all proofs…” b. On page 4, line 198: 
      \log(\sqrt(n) should be \log(n) c. On page 5, before Proposition 3.5, 
      stating the motivation for the special partially separable structure 
      considered in Proposition 3.5 will be nicer. d. On page 6, lines 
      284-285, description of the step size rule is confusing. How do you select 
      w_n? e. On page 6, how did you decide on the sizes of the training and 
      test sets for the datasets? f. On page 7, line 234 define what an 
      ``epoch” is g. On page 10, line 491: “notation as us” should be 
      “notation to us” h. On page 14, line 715: “function” should be 
      “functions” i. On page 14, line 721: ”For … f^*+\mu A_0” should be 
      “for … f^*+\mu A_1” j. On page 16, line 821: “this” should be “these” 
      k. On page 16, line 823: f(\theta_{k-1}) should be E[f(\theta_{k-1})] 
      l. On page 16, line 863: \log(\sqrt{n}) should be \log(n) m. On 
      page 17, line 867: \log(\sqrt{n}) should be \log(n) n. On page 17, 
      line 901: w_n\leq 1 is also used in this derivation. It should be 
      mentioned. o. On page 17, line 908: {… \over \rho\delta} should be {… 
      \over \rho^2\delta}