Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose a low complexity approximation method with closed analytic forms for doing logistic regression in the sparse, online setting. They first introduce the marginalized bayesian gaussian approximation approach, which essentially replaces the sigmoidal with a gaussian. They then give approximate expressions for the prediction and marginalization terms, as well as ways to approximate/update the posterior. 

This is an interesting approach. The pros are clear: closed-form analytic updates that attempt to retain the core advantages of a Bayesian approach. 

The authors should address the following questions/concerns:  	 
	 		
Assumptions: The diagonal Gaussian assumption appears to be quite strong. Are there comments/extensions on how to incorporate this for correlated/collinear covariates? 

Approximation: The approximation is based on a Gaussian approximation to the sigmoidal. Are there any theoretical/quantitative guarantees on the approximation error? Right now the approximation is just a heuristic.  

Experiments: since one of the main proposed advantage of this scheme is that it is computationally faster, it would be nice to have experiments/charts showing how much faster (in actual experiments) does this method run when compared to competitors like VB or a Gibbs sampler. Also, there is a Newton’s method step in the algorithm. Could the authors comment on how that affects run time? 

Motivation: If you are using a Gaussian to approximate the Sigmoidal, since you are using a Gaussian anyways, why not just use an online probit regression then, instead of the logistic? 

Overall, I think this is a potentially useful proposal that is interesting, but I think a) more experiments needs to be done with competitors to illustrate not just regret, but runtime comparisons b) there needs to be more theoretical rigor as to how an approximation performs and what the approximation error/bounds/guarantees are. 

I also looked at the citations more closely, and I discovered that there are some mis-citations: 
For example, you cited Terry Anderson. The theory and practice of online learning. Athabasca University Press, 2008, which upon further inspection is about online (as in over-the-internet) learning, not online learning in the machine learning sense. 

review_title: Interesting, but more work to be done

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes an algorithm  for online logistic regression  based on analytical formulas that approximate the Bayesian predictive posterior. These approximations are based on assuming a diagonal covariance Gaussian form for the posterior at each iteration that is optimized to fit the true posterior. Two alternatives are proposed for the optimization: one based on Newton's method and the other based on a Taylor series approximation, which experimentally yields similar results. Thanks to these closed formula approximations, the resulting algorithm has a constant low cost per observation and  is particularly suitable for sparse high-dimensional scenarios. It is empirically shown that the algorithm achieves a known regret lower bound on synthetic data when the true prior on the weights used to generate the data is provided to the algorithm.

Strong points:
- The introduction properly positions the work
- A low-complexity algorithm for online prediction suitable for sparse high-dimensional features is proposed

Weak points:
- No theoretical guarantees on the regret
- Regret is strongly dependent on the prior
- No experiments on real datasets

 
This paper proposes a low-complexity approximated bayesian algorithm that aims at attaining known regret lower bounds that have been recently shown [Shamir 2020] to be achievable by exact Bayesian methods. Unfortunately, no theoretical guarantees are provided on the impact of such approximations and the empirical performance is reported to be strongly affected by the choice of the prior. In particular, it is reported that the prior has to fit the data for good regret. This strong dependence on the prior makes it of limited practical interest in real life online scenarios. Therefore, I think that the paper is not strong enough and recommend its rejection.

Detailed comments:

Section 3 could be better structured and a "road map" at the beginning of the section would help the reader to quickly understand the different steps involved in the approximation. 

If I understood correctly, in order to build a synthetic dataset, 
- you sample the weights $w^\star$ using some prior (a gaussian with mean 0 and STD specified in the title of each plot).\
- At time $t$, you sample random features $x_{i,t}$ using different distributions, depending on the type.\
- You add up these features weighted by $w^\star$ to obtain the true log-odds that is used to define the probability distribution (through the sigmoid) from which $y_t$ is sampled.

Then, the following sentence is confusing:
"The “true” log-odds of the features drawn at t were added up, weighted by $x_{i,t}$, and converted to probability with the Sigmoid function."

In the following sentence you use $\tau$ that doesn't appear in eq. 4:
"Results describe a time series on (4), where summation is on $\tau$ up to example $t$ at time $t$."

"We demonstrate that it is sufficient to approximate the component of the posterior which will dominate
at the horizon, matching it by a diagonal Gaussian approximation ,"
How is this demonstrated?

Eq 11: (d) should be with $\approx$ instead of $=$

Since nonparametric Bayesian methods are mentioned in the abstract, it would be interesting to see a comparison against online nonparametric Bayesian methods.

In my opinion, the title should say "online prediction" instead of "online learning", since the latter does not necessarily imply predicting at each round and cumulating the loss. 

Typos:\
 -- mostly a function *of* the number\
 -- Jeffery's prior -> Jeffreys prior


=====POST-REBUTTAL COMMENTS======== 

I thank the authors for the response and the efforts in the updated draft, in particular with respect to the new experiment on the Criteo dataset. 
Regarding the following arguments:

1- *"The dependence of regret on the prior applies to any Bayesian method, in the same way that tuning the learning rate for gradient methods is necessary."*
 
I agree that, for batch methods, the prior can be tuned to the data. Nevertheless, in an online prediction setting, the prior needs to be chosen before observing the data and once you start predicting you can't go back and change the prior for the already predicted sequence. 

2- *"To the best of our knowledge, none of the literature that proposed practical (online) Bayesian methods proposed regret bounds or even studied regret for these methods"*

Regarding both arguments, there is recent literature that proposes a practical nonparametric online prediction method with regret guarantees for a fixed given prior:

*Lhéritier, Alix, and Frederic Cazals. "Low-Complexity Nonparametric Bayesian Online Prediction with Universal Guarantees." Advances in Neural Information Processing Systems. 2019.*

Therefore, unfortunately, my first two concerns (theoretical guarantees on the regret and strong dependence on the prior) remain so I retain my original decision.
review_title: Fast approximate Bayesian algorithm but no guarantees on the quality of the approximations and no convincing experiments

final_score: rating: 4: Ok but not good enough - rejection
review_content: PAPER SUMMARY

This paper proposes a new posterior approximation scheme for probabilistic logistic regression. In the online learning setup, the proposed approximation leads to a closed-form parameter update. In particular, the key ideas here include: 

(1) A probit approximation of the sigmoid likelihood in Eq. (5). This, along with the assumed statistical independence among individual features and another integral approximation trick used in (Murphy, 2012), leads to a posterior representation in forms of a normalized product between a sigmoid and a normal PDF. 

(2) Matching the location and density of its mode to that of another Gaussian surrogate to yield the closed-form update that expresses the parameter at round (t + 1) in terms of its counterpart at round (t) analytically in Eq. (15)

NOVELTY & SIGNIFICANCE

If I understand correctly, the main arguments in favor of the proposed method are: (a) the iterative update derived from Eq. (15) only involves a single sample at round (t) which is more efficient than VB's or EM's stochastic gradient updates that require re-iterating over multiple mini-batches of past data; and (b) the new approximation scheme performs empirically better than existing method, and matches state-of-the-art regret lower-bound.

Given the current form of the manuscript, these arguments, however, are not very convincing to me as I elaborated in the followings:

First, regarding (a), while it is true that VB's or EM's offline updates are more expensive than the update derived from Eq. (15), it seems to me they can still be made more efficient in online setting with very minor modifications. For instance, in both VB and EM, the lower-bound function often factorizes additively across data point so if we cache all gradient computation in step (t), the computation of new gradient in step (t + 1) also involves only the latest data sample which is likely not more expensive than iteratively solving Eq. (15) -- I would like to hear the authors' thoughts on this.  

Second, the claim that the new approximation scheme performs better than existing methods is not well-supported. In this regard, I wonder why the improved loss is only demonstrated in a very controlled, synthetic experiment settings. One could always argue that as far as only synthetic experiments are involved, there might exist other settings for which we might see the opposite. To me, positive results on a single set of synthetic experiments often do not speak conclusively to whether one method would be more useful than another in practice -- a better way to demonstrate this is to also evaluate the proposed method on real-world benchmark datasets (especially those extracted from practical domains that were mentioned in the introduction)     

Furthermore, the evaluation does not seem to include all the most relevant baselines (more on this later) as well as processing time comparison. Given that one of the key contribution claims here is the computation advantage over EM's and VB's, both theoretical complexity and empirical demonstration of averaged running time should be provided. 

In addition, I also find part of the positioning of this paper somewhat misleading, especially when it criticizes stochastic gradient methods for incurring additional losses while the target posterior keeps moving with subsequent samples. Isn't this also true for the proposed method? While Eq. (15) is analytic, solving it for the parameter update is clearly not analytically tractable which also requires iterative update; and then even the resulting approximated posterior has to be matched again to another Gaussian surrogate. Lastly, the conclusion surprisingly summarizes that with proper prior, the method "matches regret lower-bound" -- this seems like an overclaim as there is no theoretical analysis in the paper to back this up.

TECHNICAL SOUNDNESS

I have gone through the derivations and I do not spot any serious issues, but there are parts that seem to lack justification. For instance, could the authors please detail the steps that lead to Eq. (5)? Also, it will be even better if the authors could provide plots to visually demonstrate how the derivative of sigmoid is close to the scaled normal CDF.

I also find it a bit strange that this paper highlights the sparse aspect of data as an issue but in the end, it appears more to be a necessary setting that justifies the assumed diagonal form of the variance matrix, which is a necessity for most of the technical derivations in this paper.  

CLARITY

While the paper is sufficiently clear, I find the introduction is a bit too long. It could have made its points using much less space. In the current form, it kind of distracts the readers from those key points by throwing in many subsidiary positionings that are better discussed & organized in related work. 

The claim on analytic update is also a bit exaggerating as solving Eq. (15) for an update equation is after all not tractable and we will have to resort to iterative method such as Newton's or Taylor series expansion anyway. 

EXPERIMENT

On the experimental evaluation, my key concern (as mentioned above) is the lack of evaluation of real-world dataset, and in addition, some of the more recent methods such as (Nguyen, 2017a; 2017b) were not included in the baseline.

The presentation of the evaluation is also problematic when the results seem to be collected on only 1 single run. As a standard practice, please re-run the same experiment multiple times and report the margin of error. It is also unclear why the Y-axis is t/log(t) -- first of all, do you mean r_t /log(t) instead?; and secondly, why do we divide it by log(t) but not t? Aren't we ultimately interested in the limit of the average regret r_t/t?

Furthermore, despite the claim that this method is proposed for the setting with huge feature sets (with billions of dimensions), the synthetic experiment is mostly around 200; and up to 2000, which is a bit disappointing. On the same note, despite having a main claim of computational efficiency, there is not a single experiment that showcase this advantage over existing methods.

REVIEW SUMMARY  

The paper aims to develop a posterior approximation scheme for sparse online logistic regression. While the key idea is to achieve faster computation time and better regret rate than existing methods, this point has not been demonstrated sufficiently due to a complete lack of complexity analysis and experiments on large-scale, real-world data with more recent benchmark. The paper also appears to overclaim on the analytic tractability of its update as I have pointed out above. 

Note: This is only my preliminary assessment and there is of course the possibility that I might miss some important points. In that case, I am looking forward to receiving detailed clarifications from the authors.
review_title: Interesting paper but the experimentation is too limited. Several contribution claims appear debatable and requires further clarification.

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################
Summary:

The paper proposes an algorithm for learning the parameters of a logistic regression model in an online setting. The proposed algorithm is based on two approximations: the posterior at iteration t over the model parameters is assumed to be multivariate Gaussian distribution with a diagonal covariance matrix and the logistic/sigmoid function is approximated by the CDF of the normal distribution. The numerical results show the usefulness of the proposed algorithm.


##########################################################################
Reason for score:

My overall impression is that the proposed algorithm is of sufficient interest to warrant the acceptance of the paper. 


##########################################################################
Pros:

1. The paper proposes analytical expressions for updating the parameters of the logistic regression model in an online setting. The computation cost for updating the parameter is reduced.

2. The paper is overall well written and the authors describe in detail each step in the development of the proposed algorithm. 

##########################################################################
Cons:

1. For me it is not clear why you settled on a logistic regression problem instead of probit regression and present the logistic regression as an extension. From my understanding, the keystones for the proposed algorithm are the approximation of the prior as a multivariate Gaussian with diagonal covariance and the marginalization step (which itself is due to the Gaussian assumption). From my point of view, the introduction of the extra approximation layer due to the use of the logistic regression is detrimental to the easy understanding of the paper. I believe it would have been better to just introduce a section that describes the modifications to make in order to apply the proposed algorithm to the logistic regression problem. 

2. In section 1 on page 2 you make a statement about the role of an approximation in minimizing the the uncertainty. For me it is not clear how the proposed algorithm addresses this statement. Could you please elaborate on the subject? Also, on page 3 you say that it is sufficient to match the component of the posterior that dominates at the horizon. What do you exactly mean by the component of the posterior? 


##########################################################################
Miscellaneous:

1. It's welcoming that the proposed algorithm has very good results, however I'm a bit surprised that the results are that good. My wariness comes from the fact that in equation 13 you match an approximation to the posterior distribution, which itself was obtained using an approximation. I would expect the errors due to the approximations to accumulate as more and more data items are processed. However, the regret seems to remain steady as you increase the number of items seen. Do you have an explanation as to why the errors due to the approximations do not accumulate?

2. There are some typos here and there in the article, however I believe you can easily detect them with the help of a spell checker.
review_title: Analytical approximate parameter update rules for model paramereters in online Bayesian logistic regression.

Meta-review: This paper proposes a new approximate algorithm for Bayesian logistic regression in the online setting. The primary approximation involved in the algorithm is the use of a diagonal Gaussian approximation. (A probably more minor approximation is approximating the sigmoid with a Gaussian.) The main discussion focused on two issues: Firstly, there was some sentiment that the paper lacked theoretical guarantees. Second, there were concerns about the experimental results. I feel that it is not a serious flaw that the paper lacks a theoretical regret bound. Given the current state of algorithms for this problem practical algorithms remain very much of interest. However, the general sentiment of reviewers was that the experimental results were not as strong (or as numerous) as would be hoped. For an algorithm without a theoretical regret bound, I do agree that stronger empirical evidence would be expected. This was partially addressed in a revision but still I agree with the consensus that more extensive numerical evidence should be expected, and for that reason I am recommending rejection.

Finally, I'll mention some other issues that I view as not counting substantially against the paper. Firstly is the dependence on the prior. Here I am in agreement with the authors that this is an aspect shared by all Bayesian methods. This issue is a (valid) argument about the value of all Bayesian methods, but not one I think we will resolve here. Second, there were suggestions from the reviewers about improvements that could be made to the baseline methods. Here I don't feel that it's fair that we ask the authors to make novel improvements to other algorithms, unless those improvements are very "obvious".
Decision: Reject