Scaled Least Squares Estimator for GLMs in Large-Scale Problems
We study the problem of efficiently estimating the coefficients of generalized linear models (GLMs) in the large-scale setting where the number of observations n is much larger than the number of predictors p, i.e. n p 1. We show that in GLMs with random (not necessarily Gaussian) design, the GLM coefficients are approximately proportional to the corresponding ordinary least squares (OLS) coefficients. Using this relation, we design an algorithm that achieves the same accuracy as the maximum likelihood estimator (MLE) through iterations that attain up to a cubic convergence rate, and that are cheaper than any batch optimization algorithm by at least a factor of O(p). We provide theoretical guarantees for our algorithm, and analyze the convergence behavior in terms of data dimensions. Finally, we demonstrate the performance of our algorithm through extensive numerical studies on large-scale real and synthetic datasets, and show that it achieves the highest performance compared to several other widely used optimization algorithms.
The paper is based on the fact that, when the predictors are normally distributed, the regression coefficients of a GLM (with canonical link) are proportional to the corresponding GLM coefficients.  The authors propose to exploit this fact to reduce the computational burden of fitting GLMs. In particular, they estimate the coefficients by OLS and then they find the proportionality constant using an univariate root-finding method.  They also show that the results approximately apply outside the Gaussian context, and provide bounds on the discrepancy between GLM and (scaled) OLS coefficients.
The main idea of the paper is an interesting and, at least to me, novel one. Sections 1 to 3 are extremely well written, while the second half of the paper seems a bit more hurried.  It would be worthwhile pointing out early in the paper that the proposed approach applies only when the canonical link is used (currently stated in line 92). However, the authors say: "Motivated by the results in the previous section, we design a computationally efficient algorithm for any GLM task that is as simple as solving the least squares problem; it is described in Algorithm 1." The "any" suggests that the canonical link is not required. Please clarify.  In the right plot of Figure 1 it might be more useful plotting the relative accuracy of the proposed method, that is MSE(SLS)/MSE(MLE). Also, are you using sub-sampling or the full sample for SLS here?  In Figure 1 STS does strictly worse than MLE in terms of accuracy. Given that here the design is Gaussian and given Proposition 1, it is not entirely clear to me why this should happen. It is because estimating the constant c introduces extra variance?  I am a bit puzzled by the decision of using sub-sampling here. The STS method should be applicable whether or not subsampling is used. Hence using subsampling makes the results in Section 5 harder to interpret. That is, in terms of speed-up and accuracy what is the contributions of STS and what is that of subsampling?  L204 The authors say: "On the other hand, each of the MLE algorithms requires some initial value for , but no such initialization is needed to find the OLS estimator in Algorithm 1. This raises the question of how the MLE algorithms should be initialized, in order to compare them fairly with the proposed method." It would have been useful to include also Iteratively Reweighted Least Squares (IRLS) in this comparison, given its popularity. Also, Wood (2006) page 66 explains that a default initialization is available for this method.    L215 The authors say: " For each dataset, the minimum achievable test error is set to be the maximum of the final test errors, where the maximum is taken over all of the estimation methods." Using this approach, if one of the methods fails, the test error will be set to a fairly high number. Have all methods converged on all datasets?   In Section 5 the authors use two simulated datasets. Are the results in Figure 2 and Table 1 the output of a single run and an average of several runs? At least a handful of run are needed in order to provide some confidence in the results.  Figure 2 is quite crammed. Maybe some space could be saved by eliminating redundant legends and axes labels. The lines in the legend are extremely small. Maybe it is also worth pointing out in the caption that STS does not start from zero on the x axis because of the fixed cost paid by OLS.  Lines 253-257 are quite confusing. What is the take home message of Corollary 1? I don't immediately see what the lasso results implies for the unpenalized GLM regression. Corollary 1 makes the assumption beta > eta / s, what is the meaning of this assumption and is it realistic? Similarly the authors set lambda = eta / (c*s), why this choice?  Lambda_min seems to be undefined in Proposition 2. It this defined in the Appendix, but something about it must be said also in the main text.   MINOR POINTS:  L46 I am not sure about this sentence: "For logistic regression with Gaussian design (which is equivalent to Fisher’s discriminant analysis)". Friedman et al. (2008) on page 127 say that they are quite different, even with Gaussian design. In particular, discriminant analysis is more efficient in this case, because it exploits the normality of the predictors.  L161 "that we can attain up to a cubic rate of convergence (by, for instance, using Hayley’s method)" this is a repetition.  L296 "Another interesting line of research is to find similar proportionality relations between the parameters in other large-scale optimization problems such as support vector machines. Then the problem complexity can be significantly reduced as in the case of GLMs." The latter sentences should be conditional on the former, but at the moment it is an assertion.  REFERENCES:  - Wood, Simon. Generalized additive models: an introduction with R. CRC press, 2006.  - Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. 2nd Edition. Springer, Berlin: Springer series in statistics, 2008.