In this paper, we develop a family of algorithms for optimizing "superpositionstructured" or "dirty" statistical estimators for high-dimensional problems involving the minimization of the sum of a smooth loss function with a hybrid regularization. Most of the current approaches are first-order methods, including proximal gradient or Alternating Direction Method of Multipliers (ADMM). We propose a new family of second-order methods where we approximate the loss function using quadratic approximation. The superposition structured regularizer then leads to a subproblem that can be efficiently solved by alternating minimization. We propose a general active subspace selection approach to speed up the solver by utilizing the low-dimensional structure given by the regularizers, and provide convergence guarantees for our algorithm. Empirically, we show that our approach is more than 10 times faster than state-of-the-art first-order approaches for the latent variable graphical model selection problems and multi-task learning problems when there is more than one regularizer. For these problems, our approach appears to be the first algorithm that can extend active subspace ideas to multiple regularizers.

We investigate architectures of discriminatively trained deep Convolutional Networks (ConvNets) for action recognition in video. The challenge is to capture the complementary information on appearance from still frames and motion between frames. We also aim to generalise the best performing hand-crafted features within a data-driven learning framework.

Strengths: The paper picks a very relevant problem. While the stochastic gradient method is easily parallelizable, parallelization strategies for the otherwise beneficial in terms of convergence rates approximate proximal methods are not known yet. The paper proposes natural approaches to parallelize the proximal methods: to compute the updates by independent workers and perform the averaged update (PIA), to build a model for the averaged function and compute the update which can be decomposed as a sum of independently computed terms (PMA), or to build an average of the models and compute an update, which can be parallelized through solving a dual problem (PAM). The paper clearly explains these strategies. It proves upper bounds for the errors in case of smooth and non-smooth functions.

The main concern is about the utilization of the over-parameterization in tensor decomposition. In other words, for a rank-r tensor, tensor decomposition aims to find the r components which have physical interpretation. However, the proposed approach instead finds m O(r {2.5 \ell}) components, which could be far away from the target r components. For example, even for third-order tensor, it finds m O(r 7.5) components, much larger than r. 2. Perhaps the goal of this paper is to understand the effect of over-parameterization in tensor decomposition. However, if this is the case, the objective function is quite different to the classical one, and the algorithm is also different to simple gradient descent.

This is a good contribution, with highly non-trivial theoretical results about the role of over-parameterization in tensor decomposition. Some reviewers are worried about the lack of numerical experiments and the weak connection to practical algorithms, but this is acceptable for papers with solid theoretical contribution at NeurIPS. The authors make it clear in the rebuttal that their goal is not develop an algorithm for neural networks. They also promised to add some numerical experiments. For these reasons, I recommend accept (poster).

We thank the reviewers for their careful feedback and kind comments. We respond to the comments by each reviewer in detail below: Reviewer_1: Regarding our optimization innovations: In addition to what was noted by the reviewer, another major contribution of our work is the efficient Hessian vector multiplication schemes (Algorithms 1 and 2) that enable the use of conjugate gradient methods to be applied in the collaborative filtering setting. The Hessian vector multiplication methods coupled with conjugate gradient makes GRALS highly efficient, much more so than just a direct application of conjugate gradient schemes. Reviewer_2: 1. Regarding lack of comparison to the 3 suggested papers: Salakhutdinov and Mnih, Probabilistic Matrix Factorization [NIPS 2008], Mackey et al., Divide-and-Conquer Matrix Factorization [NIPS 2011], Lee et al., Local Low-Rank Matrix Approximation [ICML 2013]. The SGD method we compare to in the paper was proposed in Zhou et al. 2012, which extends the work of Salakhutdinov and Minh to the kernel setting.

This is previously done by leveraging assumptions over the distribution (its smoothness (\beta-Holder condition, \gamma-neighbour average smoothness) and "margin" (\alpha-margin condition, namely, upper bounding the probability of instances whose expected label expectation is 1/2)) along with using weighted k-NN, with several methods for defining the weights and their resulting convergence rate. The paper proposes a new method, called MS-k-NN, of estimating several unweighted k-NN estimators, for different values of k (\nu(k) for simplicity of notation in the review). For each k, a radius r is associated by taking the distance from the query to its k-closest neighbour. Then, pairs (r(k), \nu(k)) are obtained, and parameters b are obtained by linear regression in order to estimate \nu(k) by a polynomial in r(k). It is proven that this method obtains the optimal convergence rates obtained by more cumbersome methods of weighted k-NN. It is shown that experimentally, over a few datasets, the performance of MS-k-NN is similar to that of the weighted k-NN.

The paper presents a new nonparametric learning method, which seems to combine certain elements of k-nearest neighbors with elements of local regression estimation. It recovers the optimal rates for classification with smooth regression functions and Tsybakov noise, previously established for a local polynomial regression method, but uses a predictor representation involving far fewer parameters, as in a simple weighted k-NN predictor. The reviewers favor accepting the paper. However, they have some reservations, as they would prefer the paper be presented differently, with more space dedicated to presenting the new techniques, and with more investigation into the strengths of this particular method compared to the well-known standard techniques.

This paper considers efficient implementations of non-convex sparse learning formulations. Recent studies have shown that many convex sparse learning formulations are inferior to their non-convex counterparts in both theory and practice. However, it is still quite challenging to efficiently solve non-convex sparse optimization problems for large-scale data. This paper presents a novel algorithm HONOR which is applicable for a wide range of non-convex sparse learning formulations. One of the key ideas in HONOR is to incorporate the second-order information to greatly speed up the convergence, while unlike most existing second-order methods it avoids solving a regularized quadratic programming and only involves matrix-vector multiplications without explicitly forming the inverse Hessian matrix. Thus, HONOR has a low computational complexity at each iteration and it is scalable to large-size problems.

The rebuttal from the authors was concise. However, I was not convinced about the assumption in Eq. 14 of the paper and how the authors defended it. The authors say: "Many documents (text categorization),[..] or time series signals (speech recognition) in a training set are alike. This fact is not systematically exploited by any existing stochastic optimization method!" I don't think this is correct.