Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper develops an interesting approach for solving multi-class classification with softmax loss.

The key idea is to reformulate the problem as a convex minimization of a "double-sum" structure via a simple conjugation trick.  SGD is applied to the reformulation: in each step samples a subset of the training samples and labels, which appear both in the double sum.  The main contributions of this paper are: "U-max" idea (for numerical stability reasons) and an ""proposing an "implicit SGD" idea.

Unlike the first review, I see what the term "exact" in the title is supposed to mean. I believe this was explained in the paper. I agree with the second reviewer that the approach is interesting. However, I also agree with the criticism (double sum formulations exist in the literature; comments about experiments); and will not repeat it here. I will stress though that the statement about Newton in the paper is not justified. Newton method does not converge globally with linear rate. Cubic regularisation is needed for global convergence. Local rate is quadratic.  

I believe the paper could warrant acceptance if all criticism raised by reviewer 2 is addressed.

I apologise for short and late review: I got access to the paper only after the original review deadline.
review_title: Interesting, but with flaws.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The problem of numerical instability in applying SGD to soft-max minimization is the motivation. It would have been helpful if the author(s) could have made a formal statement. 
Since the main contributions are two algorithms for stable SGD it is not clear how one can formally say that they are stable. For this a formal problem statement is necessary. The discussion around eq (7) is helpful but is intuitive and it is difficult to get a formal problem which we can use later to examine the proposed algorithms.

The proposed algorithms are variants of SGD but it is not clear why they should converge faster than existing strategies.
Some parts of the text are badly written, see for example the following line(see paragraph before Sec 3)

"Since the converge of SGD is
inversely proportional to the magnitude of its gradients (Lacoste-Julien et al., 2012), we expect the
formulation to converge faster."
 
which could have shed more light on the matter. 

The title is also misleading in using the word "exact". I have understand it correct the proposed SGD method solves the optimization problem to an additive error.

In summary the algorithms are novel variants of SGD but the associated claims of numerical stability and speed of convergence vis-a-vis existing methods are missing. The choice of word exact is also not clear.

review_title: Paper explores SGD based explorations to reduce instability in soft-max minimization

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper presents interesting algorithms for minimizing softmax with many classes. The objective function is a multi-class classification problem (using softmax loss) and with linear model. The main idea is to rewrite the obj as double-sum using the dual formulation and then apply SGD to solve it. At each iteration, SGD samples a subset of training samples and labels. The main contribution of this paper is: 1) proposing a U-max trick to improve the numerical stability and 2) proposing an implicit SGD approach. It seems the implicit SGD approach is better in the experimental comparisons. 

I found the paper quite interesting, but meanwhile I have the following comments and questions: 

- As pointed out by the authors, the idea of this formulation and doubly SGD is not new. (Raman et al, 2016) has used a similar trick to derive the double-sum formulation and solved it by doubly SGD. The authors claim that  the algorithm in (Raman et al) has an O(NKD) cost for updating u at the end of each epoch. However, since each epoch requires at least O(NKD) time anyway (sometimes larger, as in Proposition 2), is another O(NKD) a significant bottleneck? Also, since the formulation is similar to (Raman et al., 2016), a comparison is needed. 

- I'm confused by Proposition 1 and 2. In appendix E.1, the formulation of the update is derived, but why we need Newton to get log(1/epsilon) time complexity? I think most first order methods instead of Newton will have linear converge (log(1/epsilon) time)? Also, I guess we are assuming the obj is strongly convex?

- The step size is selected in one dataset and used for all others. This might lead to divergence of other algorithms, since usually step size depends on data. As we can see, OVE, NCE and IS diverges on Wiki-small, which may be fixed if the step size is chosen for each data (in practice we can choose using subsamples for each data). 

- All the comparisons are based on "epochs", but the competing algorithms are quite different and can have very different running time for each epoch. For example, implicit SGD has another iterative solver for each update. Therefore, the timing comparison is needed in this paper to justify that implicit SGD is faster. 

- The claim that "implicit SGD never overshoots the optimum" needs more supports. Is it proved in some previous papers? 

- The presentation can be improved. I think it will be helpful to state the algorithms explicitly in the main paper.
review_title: The paper presents interesting algorithms for minimizing softmax with many classes. 

Meta-review: The key concern from the reviewers that was not addressed is that none of the experimental results illustrate convergence vs. time instead of convergence vs. number of iterations.  While the authors point out that their method is O(ND) instead of O(KND), the reviewers really wanted to see graphs demonstrating this, given that the implicit SGD method requires an iterative solver. The revised paper is otherwise much improved from the original submission, but falls a bit short of ICLR acceptance because of the lack of a measurement of convergence vs. time.

Pros:
+ Promising unbiased algorithms for optimizing the log-likelihood of a model using a softmax without having to repeatedly compute the normalizing factor.

Cons:
- The key concern from the reviewers that was not addressed is that none of the experimental results illustrate convergence vs. time instead of convergence vs. number of iterations.

Decision: Reject