We provide a rigorous analysis of implicit regularization in an overparametrized tensor factorization problem beyond the lazy training regime. For matrix factorization problems, this phenomenon has been studied in a number of works. A particular challenge has been to design universal initialization strategies which provably lead to implicit regularization in gradient-descent methods. At the same time, it has been argued by Cohen et. al. 2016 that more general classes of neural networks can be captured by considering tensor factorizations. However, in the tensor case, implicit regularization has only been rigorously established for gradient flow or in the lazy training regime. In this paper, we prove the first tensor result of its kind for gradient descent rather than gradient flow. We focus on the tubal tensor product and the associated notion of low tubal rank, encouraged by the relevance of this model for image data. We establish that gradient descent in an overparametrized tensor factorization model with a small random initialization exhibits an implicit bias towards solutions of low tubal rank. Our theoretical findings are illustrated in an extensive set of numerical simulations show-casing the dynamics predicted by our theory as well as the crucial role of using a small random initialization.

Overparametrized neural networks tend to perfectly fit noisy training data yet generalize well on test data. Inspired by this empirical observation, recent work has sought to understand this phenomenon of benign overfitting or harmless interpolation in the much simpler linear model. Previous theoretical work critically assumes that either the data features are statistically independent or the input data is high-dimensional; this precludes general nonparametric settings with structured feature maps. In this paper, we present a general and flexible framework for upper bounding regression and classification risk in a reproducing kernel Hilbert space. A key contribution is that our framework describes precise sufficient conditions on the data Gram matrix under which harmless interpolation occurs. Our results recover prior independent-features results (with a much simpler analysis), but they furthermore show that harmless interpolation can occur in more general settings such as features that are a bounded orthonormal system. Furthermore, our results show an asymptotic separation between classification and regression performance in a manner that was previously only shown for Gaussian features.

A common problem in recommendation systems is to learn a model of user preferences based only on comparisons of the relative attractiveness of different items. We consider this problem in the context of an ideal point model of user preference, where each user can be represented as a point in a low-dimensional space together with a set of items. In this model, the closer an item is to a user’s ideal point, the more that user prefers the item. When an embedding of items is known a priori, the problem of localizing a user’s ideal point from comparisons amongst items is well studied. However, relatively little work exists on learning embeddings for new items based only on such comparisons. In this paper, we consider the problem of embedding a set of items using paired comparisons from a set of known users. Specifically, we present a novel convex lifted method of learning the embedding representation p1,…,pn∈ Rnof n items given noisy responses of the form "user ukprefers item pito item pj" for an arbitrary set of users {uk} in Rd. We provide a range of simulations that validate the efficacy of our approach.

Thomson’s multitaper method estimates the power spectrum of a signal from$N$equally spaced samples by averaging$K$tapered periodograms. Discrete prolate spheroidal sequences (DPSS) are used as tapers since they provide excellent protection against spectral leakage. Thomson’s multitaper method is widely used in applications, but most of the existing theory is qualitative or asymptotic. Furthermore, many practitioners use a DPSS bandwidth$W$and number of tapers that are smaller than what the theory suggests is optimal because the computational requirements increase with the number of tapers. We revisit Thomson’s multitaper method from a linear algebra perspective involving subspace projections. This provides additional insight and helps us establish nonasymptotic bounds on some statistical properties of the multitaper spectral estimate, which are similar to existing asymptotic results. We show using$K=2NW-O(\log (NW))$tapers instead of the traditional$2NW-O(1)$tapers better protects against spectral leakage, especially when the power spectrum has a high dynamic range. Our perspective also allows us to derive an$\epsilon $-approximation to the multitaper spectral estimate which can be evaluated on a grid of frequencies using$O\left({\log (NW)\log \tfrac {1}{ \epsilon }}\right)$FFTs instead of$K=O(NW)$FFTs. This is useful in problems where many samples are taken, and thus, using many tapers is desirable.

Bandlimiting and timelimiting operators play a fundamental role in analyzing bandlimited signals that are approximately timelimited (or vice versa). In this letter, we consider a time-frequency (in the discrete Fourier transform (DFT) domain) limiting operator whose eigenvectors are known as the periodic discrete prolate spheroidal sequences. We establish new nonasymptotic results on the eigenvalue distribution of this operator. As a byproduct, we also characterize the eigenvalue distribution of a set of submatrices of the DFT matrix, which is of independent interest.

In this paper, we provide a dictionary for representing the discrete vector one obtains when collecting a finite set of uniform samples from a baseband analog signal. Like the discrete prolate spheroidal sequences (DPSS's), the proposed orthogonal basis compactly captures most of the energy in oversampled bandlimited signals. The complexity of computing the representation of a signal using the proposed dictionary is comparable to the FFT, which is much less than that involving the DPSS basis. We also give non-asymptotic results to guarantee that the proposed basis not only provides a very high degree of approximation accuracy in an MSE sense for bandlimited sample vectors, but also that it can provide high-quality approximations of all sampled sinusoids within the band of interest.