Stochastic proximal gradient descent was presented to solve the deep model training with the proposed model selection based on group lasso regularization. However, the implementation details were not presented, especially regarding the iterative updates for the "loss-based gradient step". From the context, it seems that the iterative updates in the original deep model training procedure were simply modified based on Eq. 5. If that is the case, the claim of the generality of the method for "general deep networks" as it will depend on the optimization procedure of the deep model training. If the motivation of the presented work is to remove redundant neurons.

In this framework, the entries in Z are within [-1, 1]. In the context of stochastic block model, there is also an assignment matrix Z with entries {0, 1} (see Rohe et al 2011 Spectral clustering and the high-dimensional stochastic blockmodel). How does Z here (in the special binary case) compare with the Z matrix in Rohe et al. 2011? Why is it not allowed for all variables to be assigned to one block? It's possible that one wants to analyze the interaction network among genes from the same pathway (the same block).

The authors modify the MCBoost criterion, in order to allow for multi-class boosting that is based on arbitrary number of dimensions (compared to a previous formulation that limits the number of dimensions to the number of classes). This lift of the limits in terms of dimensionality allows for a boosting-like framework that is comprised of controllable amount of boosting functions, and thus can be used as. The connection between MC-Boost and MV-SVM is interesting, and the discussion is good. Is the fact that both MC-SVM and MC-Boost try to maximise the margin well known? The authors present improved results in terms of error rate, and in terms of mAP.

In this paper the authors proposed a stochastic optimization algorithm, STCM, for a three composite convex minimization problems. This problem can be write the sum of two proper, lower semicontinuous convex functions and a smooth function with restricted strong convexity. This work is based on the deterministic three operator splitting method proposed by Davis and Yin. The almost surely convergence and a convergence rate are established. Major comments: (1) The main result is quite clear, but lacks the support in details for important aspects. For example, it would be better to show some intuition of the proposed algorithm.

The paper of Dasgupta introduced a nice objective for hierarchical clustering, and presented a fairly simple algorithm for approximating the objective. I like this objective since it gives a nice principled way of comparing different algorithms (potentially new ones) for hierarchical clustering, as opposed to just showing bounds for linkage-based heuristics. I think the algorithm and analysis in this paper is very elegant. Every hierarchical clustering corresponds to an ultrametric; but they characterize the ultrametrics that correspond to the objective defined by Dasgupta, using some very nice properties. They use this characterization to come up with an LP and its rounding.

The initial motivation seems to be the work of Hoffman et al on the use of clustering to speedup stochastic methods for ERM. Their method was not proved to converge to the optimal due to the use of biased stochastic gradients. Also, that work seemed to work only for small clusters due to the approach chosen. This papers goes a long way to develop the basic idea into a satisfying theoretical framework which also gives rise to efficient implementations. This paper is truly a pleasure to read – a very fine example of academic exposition.

The idea of addressing finite-sum problems through augmented Lagrangian and ADMM type algorithm is straightforward but new. Convergence results of the new randomized variation for non-convex problems are also novel, to my best knowledge. Despite the notable originality, I think a couple of places need to be further discussed or clarified. Although existing work on nonconvex SVRG/SAGA algorithms [1,21] only provide analysis for smooth problems, I would presume similar results (replacing gradient by prox-gradient) can also be derived with slight modification given that the original algorithms are designed to handle nonsmooth regularization and adapted to non-uniform sampling as well. So it would be good if the author could add such comparison to nonconvex SVRG/SAGA in Table 1 when applicable. 2. It appears to me that in the NESTT-G algorithm (without reducing to the single variable form), at each iteration, setting the remaining (N-1) x variables to z would require O(Nd) computation and memory cost, which is not negligible.

However, this paper is not carefully written. For example, the references are missing on page 6, line 192 and page 7, line 206. The legend of red lines are missing for Figure 2c,d. The paper states only the necessary information but not sufficient for the readers to follow easily. I think the clarity of this paper could be greatly improved especially the authors did not use the full 8 pages.

The rebuttal answered all my technical questions, in particular the one about probability and expectations in Theorems 1(ii) and 3. My scores (which were given assuming the technicalities can be fixed) remain the same. The theoretical results do not feel that exciting. The regret bounds seem more or less what one might expect, and there is no comparison to bounds for other algorithms. I understand that there are no directly comparable bounds since you have both budget size and dimensionality of random projections as significant parameters, but still some discussion would be nice. The dependence on budget B in your bounds could perhaps be pointed out more explicitly.

Novelty: The novelty of the algorithm lies in providing global convergence guarantees for the online version of CCA. The algorithm has potential - however, this would have been better highlighted if real-applications were used (e.g. To this end, having an efficient online algorithm for such settings is valuable. Clarity: The authors do a great job presenting exactly the necessary information needed: from introducing CCA to the power method version of CCA, and to its ALS and stochastic formulation. At each step of the description, the authors provide remarks about what can go wrong: what happens when there is a gap, what about the normalization step (is it expensive?),