Minimum-norm solutions generalize well in over-parametrized neural networks.
problem Generalization error in over-parametrized neural networks.
method Analyzing three models: random feature model, two-layer neural network, and residual network.
result Generalization error for minimum-norm solutions is comparable to Monte Carlo rate, up to logarithmic terms.
Study shows how networks converge to minimum norm solutions with regularization.
problem Interpolating between known regions in shallow ReLU networks.
method Investigates empirical risk minimizers and weight decay regularizers.
result Empirical risk minimizers converge to minimum norm interpolants under specific conditions.
Weight normalization and reparametrized gradient descent adaptively regularize weights and converge to minimum l2 norm solutions.
problem Adapting to non-convex weight normalization for convergence to minimum l2 norm solutions.
method Weight normalization and reparametrized projected gradient descent (rPGD) for overparametrized least-squares regression.
result rPGD converges close to the minimum l2 norm solution, even for far-from-zero initializations.
Estimates generalization error for two-layer ReLU NNs through minimum norm solutions.
problem Estimating generalization error for two-layer ReLU NNs trained by mean squared error.
method Uses minimum norm solutions and Neural Tangent Kernel (NTK) regime to derive generalization error bounds.
result Derives an a priori generalization error bound for two-layer ReLU NNs without requiring exponentially large number of neurons.
The paper studies the minimum ℓ₁-norm interpolator's risk behavior in over-parameterized settings.
problem Understanding the risk behavior of minimum ℓ₁-norm interpolators in high-dimensional settings.
method Exact characterization of the risk behavior through a system of two non-linear equations.
result Observation of a multi-descent phenomenon in the generalization risk of the minimum ℓ₁-norm interpolator.
The paper explores how over-parameterized linear regression models generalize without violating learning theory principles.
problem Understanding how over-parameterized linear regression models generalize without violating learning theory principles.
method The paper uses the predictive normalized maximum likelihood (pNML) learner to investigate the minimum norm solution of over-parameterized linear regression models.
result The model generalizes well when the test sample lies in a subspace spanned by eigenvectors associated with large eigenvalues of the training data.
Paper provides a performance guarantee for spectral clustering.
problem Finding the global solution to the minimum ratio cut problem.
method Two-step spectral clustering method with a rounding step, analyzed using two-to-infinity norm perturbation bounds.
result Spectral clustering is guaranteed to output the global solution under certain conditions.
Study tightens bounds for interpolating noisy data using minimum l1-norm.
problem Predicting noisy data with minimum l1-norm interpolation.
method Provided matching upper and lower bounds for prediction error.
result Tight consistency up to negligible terms for d≫n. 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.
problem Stability of kernel ridge-less regression.
method Minimizing the norm of the ERM solution to minimize CV stability.
result Interpolating solution with minimum norm minimizes CV stability.
Deep linear networks can closely approximate interpolants without improving risk.
problem Understanding the risk bounds of deep linear networks compared to minimum ℓ2-norm solutions. method Bounding excess risk of interpolating deep linear networks trained using gradient flow.
result Deep linear networks can closely approximate or match minimum ℓ2-norm solutions in terms of risk. The study analyzes robustness of estimators in linear models with adversarial errors.
problem Analyzing robustness of estimators in linear models with adversarial errors.
method Develops a general theory for minimum norm interpolating estimators and RERM in linear models without conditions on errors.
result Quantitative bound for the prediction error relating it to Rademacher complexity, norm of minimum norm interpolator of errors, and subdifferential size.
Uniform convergence of interpolators proven for Gaussian data.
problem Interpolation learning in high-dimensional linear regression with Gaussian data.
method Generic uniform convergence guarantee in terms of Gaussian width.
result Consistency of interpolators for minimum-norm and near-minimal-norm cases.
Batching stabilizes risk in high-dimensional linear regression models.
problem Stability and risk behavior in high-dimensional overparameterized linear regression.
method Minimum-norm overparameterized linear regression model with batch-partitioning.
result Optimal batch size is inversely proportional to noise level and overparametrization ratio, leading to stable risk behavior.
The paper shows how multi-task learning in neural networks is similar to kernel regression and Hilbert spaces.
problem Understanding the solutions to multi-task shallow ReLU neural network learning problems.
method Analyzing the properties of solutions to multi-task shallow ReLU neural network learning problems, proving uniqueness and equivalence to minimum-norm interpolation problems in Hilbert spaces.
result The solutions to multi-task neural network interpolation problems are almost always unique and coincide with the solution to a minimum-norm interpolation problem in a Sobolev (Reproducing Kernel) Hilbert Space.
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 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.
problem Understanding why neural networks generalize well in over-parameterized settings.
method Characterizes two sub-classes of adaptive methods and their generalization performance.
result Adaptive methods in over-parameterized linear regression converge to the minimum norm solution.
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α, α∈(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…
Our paper characterizes how ReLU affects GD's implicit bias in high-dimensional neural networks.
problem Understanding the implicit bias of gradient descent on neural networks.
method Novel primal-dual analysis tracking predictions and coefficients.
result The implicit bias approximates the minimum-ℓ2-norm solution with high probability. Develops efficient method for nonconvex problems using Regula Falsi.
problem Nonconvex inverse problems with likelihood constraints.
method Regula Falsi root-finding techniques applied to level-set formulations.
result Proves extension of level-set methods to nonconvex problems.
Adversarial training improves linear regression solutions, offering robustness against small perturbations.
problem Vulnerability of linear models to adversarial perturbations.
method Formulated as a min-max problem, adversarial training minimizes the best solution under worst-case attacks.
result Adversarial training yields the minimum-norm interpolating solution in overparameterized models, equivalent to parameter shrinking methods in underparameterized models.
Theoretical justification for deep networks' performance with regularization techniques.
problem Understanding the performance of deep networks trained with the square loss.
method Analysis of gradient flow and theoretical justification of regularization techniques.
result Convergence to solutions with smaller Frobenius norms leads to better classification error bounds.
The paper explores why a specific type of predictor works well in noisy data.
problem Understanding why a specific type of predictor (minimum-norm interpolator) works well in noisy data.
method The paper uses uniform convergence and zero-error predictors in a norm ball to explain the success of the minimum-norm interpolator.
result The minimum-norm interpolator is consistent, and this can be explained by uniform convergence of zero-error predictors in a norm ball.
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. …
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.
problem Highly anisotropic covariances and diverging d/n in linear regression. method Inflating the minimum ℓ2 norm interpolator by a constant greater than one. result Inflating the minimum norm interpolator improves generalization error.
A study on a surprising phase transition in model generalization error as parameters approach sample size.
problem Understanding the generalization error of overparametrized ridge models.
method Finite sample analysis using continuous Newton method and ℓ2-norm solution performance. result The generalization error decreases after the threshold p=n for ridge models. 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 ℓ0-norm penalty. To overcome the discontinuity of the objective function, smooth non-convex functions are employed to approximate the ℓ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 ℓp-regression problem, minx∥x∥p such that Ax=b, for all p∈(1,2)∪(2,∞). Our algorithms obtain a high accuracy solution in O~p(m2p+∣p−2∣∣p−2∣)≤O~p(m31) iterations, where each iteration requires s…
Study shows interpolating predictor's risk is optimal in low-dimensional factor regression models.
problem Understanding the risk of interpolating predictors in high-dimensional factor regression models.
method Detailed finite-sample analysis of minimum-norm interpolating predictor's risk in factor regression models.
result The risk of the minimum-norm interpolating predictor approaches optimal benchmarks in low-dimensional factor regression models.
The paper analyzes the risk of a least squares estimator under a spike covariance model.
problem Risk analysis of the least squares estimator under a spike covariance model.
method Assumes spike covariance matrices, studies risk as d/nightarrow∞. result Risk of the minimum norm least squares estimator vanishes compared to the null estimator.
Paper analyzes mistake and generalization of MNIC classifiers.
problem Understanding the performance of interpolating classifiers.
method Elementary analyses of MNIC's regret and generalization.
result MNIC generalizes with a rate proportional to the norm of the interpolating solution and inversely proportional to the number of data points.
Optimizes minimum-volume prediction sets for multivariate regression.
problem Lack of efficient methods for multivariate conformal prediction.
method Optimization-driven framework for minimum-volume covering sets.
result Efficient and informative prediction sets with tight coverage.
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 L2 norm of acceleration of curves in Riemannian manifolds M. In the present paper the L∞ norm replaces the L2 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.
problem Transferability of latent knowledge from classification to regression in overparameterized linear models.
method Investigation of task shift in overparameterized linear regression, zero-shot and few-shot cases, with a focus on minimum-norm interpolation.
result Minimum-norm interpolators can transfer latent knowledge from classification to regression with limited additional data.
Kernel interpolation is inconsistent for norms with smoothness above a constant.
problem Inconsistency of kernel interpolation in reproducing kernel Hilbert spaces.
method Lower bounds for generalization error in Sobolev norms.
result Kernel interpolation is always 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 ℓ1-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite numb…
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.
problem Estimating long-term causal effects with limited short-term outcomes and many weak instruments.
method Nonparametric instrumental variable inference with many weak instruments, using past experiments as instruments.
result Automatic debiased machine learning estimators for linear functionals of the structural function and its minimum-norm projection are efficient in the many-weak-instruments regime.
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.
problem The impact of covariance estimation errors on the global minimum-variance portfolio under heavy-tailed distributions.
method Characterization of covariance-estimation error's effect on GMVP suboptimality, derivation of regret identity and bound, application to heavy-tailed returns.
result The decision geometry of GMVP regret is invariant to a (p-1)-dimensional projection of the error matrix, with invariance to the covariance-scale direction as an exact special case.
Study shows that ridgeless Gaussian kernel regression overfits even with varying bandwidth or dimensionality.
problem Analyzing overfitting in Gaussian kernel ridgeless regression with varying bandwidth or dimensionality.
method Examined the behavior of minimum norm interpolating solutions for fixed and increasing dimensions under varying bandwidth and sample size.
result Ridgeless solutions are never consistent and can be worse than null predictor with large enough noise, even with varying bandwidth or dimensionality.