arXiv research

We study the generalization properties of minimum-norm solutions for three over-parametrized machine learning models including the random feature model, the two-layer neural network model and the residual network model. We proved that for all three models, the generalization error for the minimum-norm solution is compa…

Study shows how networks converge to minimum norm solutions with regularization.

The paper studies the minimum ℓ₁-norm interpolator's risk behavior in over-parameterized settings.

The paper explores how over-parameterized linear regression models generalize without violating learning theory principles.

Normalization methods such as batch [Ioffe and Szegedy, 2015], weight [Salimansand Kingma, 2016], instance [Ulyanov et al., 2016], and layer normalization [Baet al., 2016] have been widely used in modern machine learning. Here, we study the weight normalization (WN) method [Salimans and Kingma, 2016] and a variant call…

Paper provides a performance guarantee for spectral clustering.

Study tightens bounds for interpolating noisy data using minimum l1-norm.

This work is substituted by the paper in arXiv:2011.14066. Stochastic gradient descent is the de facto algorithm for training deep neural networks (DNNs). Despite its popularity, it still requires fine tuning in order to achieve its best performance. This has led to the development of adaptive methods, that claim autom…

Study shows minimizing the norm of the ERM solution stabilizes kernel ridge-less regression.

Deep linear networks can closely approximate interpolants without improving risk.

The study analyzes robustness of estimators in linear models with adversarial errors.

Uniform convergence of interpolators proven for Gaussian data.

Batching stabilizes risk in high-dimensional linear regression models.

The paper shows how multi-task learning in neural networks is similar to kernel regression and Hilbert spaces.

In this work, we propose a new training method for finding minimum weight norm solutions in over-parameterized neural networks (NNs). This method seeks to improve training speed and generalization performance by framing NN training as a constrained optimization problem wherein the sum of the norm of the weights in each…

We focus on estimating \emph{a priori} generalization error of two-layer ReLU neural networks (NNs) trained by mean squared error, which only depends on initial parameters and the target function, through the following research line. We first estimate \emph{a priori} generalization error of finite-width two-layer ReLU …

We study implicit regularization when optimizing an underdetermined quadratic objective over a matrix $X$ with gradient descent on a factorization of $X$. We conjecture and provide empirical and theoretical evidence that with small enough step sizes and initialization close enough to the origin, gradient descent on a f…

This paper explores adaptive methods in over-parameterized linear regression.

We study the risk of minimum-norm interpolants of data in Reproducing Kernel Hilbert Spaces. Our upper bounds on the risk are of a multiple-descent shape for the various scalings of $d = n^α$, $α\in(0,1)$, for the input dimension $d$ and sample size $n$. Empirical evidence supports our finding that minimum-norm interpo…

This work provides closed-form solutions and minimum achievable errors for a large class of low-rank approximation problems in Hilbert spaces. The proposed theorem generalizes to the case of bounded linear operators the previous results obtained in the finite dimensional case for the Frobenius norm. The theorem provide…

Develops efficient method for nonconvex problems using Regula Falsi.

Our paper characterizes how ReLU affects GD's implicit bias in high-dimensional neural networks.

Adversarial training improves linear regression solutions, offering robustness against small perturbations.

Theoretical justification for deep networks' performance with regularization techniques.

The paper explores why a specific type of predictor works well in noisy data.

We introduce a norm on the space of test configurations, which we call the minimum norm. We conjecture that uniform K-stability with respect to this norm is equivalent to the existence of a constant scalar curvature Kähler metric. This notion of uniform K-stability is analogous to coercivity of the Mabuchi functional. …

We study risk of the minimum norm linear least squares estimator in when the number of parameters $d$ depends on $n$, and $\frac{d}{n} \rightarrow \infty$. We assume that data has an underlying low rank structure by restricting ourselves to spike covariance matrices, where a fixed finite number of eigenvalues grow with…

The support norm $sn(ξ)$ of a contact structure $ξ$ is the minimum of the negative Euler characteristics of the pages of the open books supporting $ξ$. In this paper we prove additivity of the support norm for tight contact structures.

Inflating the minimum norm interpolator improves linear regression generalization error.

A study on a surprising phase transition in model generalization error as parameters approach sample size.

We show that minimum-norm interpolation in the Reproducing Kernel Hilbert Space corresponding to the Laplace kernel is not consistent if input dimension is constant. The lower bound holds for any choice of kernel bandwidth, even if selected based on data. The result supports the empirical observation that minimum-norm …

A data filtering method for cluster analysis is proposed, based on minimizing a least squares function with a weighted $\ell_0$-norm penalty. To overcome the discontinuity of the objective function, smooth non-convex functions are employed to approximate the $\ell_0$-norm. The convergence of the global minimum points o…

In this work, we present a method to compute the Kantorovich-Wasserstein distance of order one between a pair of two-dimensional histograms. Recent works in Computer Vision and Machine Learning have shown the benefits of measuring Wasserstein distances of order one between histograms with $n$ bins, by solving a classic…

We give improved algorithms for the $\ell_{p}$-regression problem, $\min_{x} \|x\|_{p}$ such that $A x=b,$ for all $p \in (1,2) \cup (2,\infty).$ Our algorithms obtain a high accuracy solution in $\tilde{O}_{p}(m^{\frac{|p-2|}{2p + |p-2|}}) \le \tilde{O}_{p}(m^{\frac{1}{3}})$ iterations, where each iteration requires s…

Paper analyzes mistake and generalization of MNIC classifiers.

Optimizes minimum-volume prediction sets for multivariate regression.

In the absence of explicit regularization, Kernel "Ridgeless" Regression with nonlinear kernels has the potential to fit the training data perfectly. It has been observed empirically, however, that such interpolated solutions can still generalize well on test data. We isolate a phenomenon of implicit regularization for…

Riemannian cubics are critical points for the $L^2$ norm of acceleration of curves in Riemannian manifolds $M$. In the present paper the $L^\infty$ norm replaces the $L^2$ norm, and a less direct argument is used to derive necessary conditions analogous to those for Riemannian cubics. The necessary conditions are exami…

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in control theory, machine learning, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-HARD, and for most practical problems there are no efficient algorithms that…

Task shift from classification to regression is possible in overparameterized linear models with limited additional data.

Kernel interpolation is inconsistent for norms with smoothness above a constant.

The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper we propose some generalized CG (GCG) methods for solving the $\ell_1$-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite numb…

This work studies finite-sample properties of the risk of the minimum-norm interpolating predictor in high-dimensional regression models. If the effective rank of the covariance matrix $Σ$ of the $p$ regression features is much larger than the sample size $n$, we show that the min-norm interpolating predictor is not de…

A recent line of work studies overparametrized neural networks in the "kernel regime," i.e. when the network behaves during training as a kernelized linear predictor, and thus training with gradient descent has the effect of finding the minimum RKHS norm solution. This stands in contrast to other studies which demonstr…

Estimates long-term effects using past experiments as instruments with many weak instruments.

We propose a new framework for deriving screening rules for convex optimization problems. Our approach covers a large class of constrained and penalized optimization formulations, and works in two steps. First, given any approximate point, the structure of the objective function and the duality gap is used to gather in…

The study analyzes how covariance estimation errors affect the global minimum-variance portfolio under heavy-tailed distributions.

Study shows that ridgeless Gaussian kernel regression overfits even with varying bandwidth or dimensionality.