Measuring Complexity of Learning Schemes Using Hessian-Schatten Total-Variation

• URL: http://arxiv.org/abs/2112.06209v1
• Date: Sun, 12 Dec 2021 11:47:31 GMT
• Title: Measuring Complexity of Learning Schemes Using Hessian-Schatten Total-Variation
• Abstract summary: Hessian-Schatten total-variation (HTV) We present closed-form expressions for computing the HTV of two general classes of functions. In this case, we show that the HTV reflects the total change in slopes between linear regions that have a common facet.
• Score: 31.54233601541908
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce the Hessian-Schatten total-variation (HTV) -- a novel seminorm that quantifies the total "rugosity" of multivariate functions. Our motivation for defining HTV is to assess the complexity of supervised learning schemes. We start by specifying the adequate matrix-valued Banach spaces that are equipped with suitable classes of mixed-norms. We then show that HTV is invariant to rotations, scalings, and translations. Additionally, its minimum value is achieved for linear mappings, supporting the common intuition that linear regression is the least complex learning model. Next, we present closed-form expressions for computing the HTV of two general classes of functions. The first one is the class of Sobolev functions with a certain degree of regularity, for which we show that HTV coincides with the Hessian-Schatten seminorm that is sometimes used as a regularizer for image reconstruction. The second one is the class of continuous and piecewise linear (CPWL) functions. In this case, we show that the HTV reflects the total change in slopes between linear regions that have a common facet. Hence, it can be viewed as a convex relaxation (l1-type) of the number of linear regions (l0-type) of CPWL mappings. Finally, we illustrate the use of our proposed seminorm with some concrete examples.

Related papers

• Generalized Splines and Gaussian Processes [15.333202915986627]
  We show that generalized splines take the role of linear regressors and generalized Gaussian processes on a nuclear space $S$ are the counterpart of Gaussian random vectors.<n>Our formalism involves a whitening/regularization operator $L: Sto S'$ whose continuous extension induces a native Hilbert space $Hsubset S'$ that plays a central role in our characterization.
  arXiv  Detail & Related papers  (2026-08-28T15:34:46Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• When does Gaussian equivalence fail and how to fix it: Non-universal behavior of random features with quadratic scaling [15.148577493784051]
  Gaussian equivalence theory (GET) states that the behavior of high-dimensional, complex features can be captured by Gaussian surrogates.<n>But numerical experiments show that this equivalence can fail even for simple embeddings under general scaling regimes.<n>We introduce a Conditional Equivalent (CGE) model, which can be viewed as appending a low-dimensional non-Gaussian component to an otherwise high-dimensional Gaussian model.
  arXiv  Detail & Related papers  (2025-12-03T00:23:12Z)
• Highly Adaptive Ridge [84.38107748875144]
  We propose a regression method that achieves a $n-2/3$ dimension-free L2 convergence rate in the class of right-continuous functions with square-integrable sectional derivatives. Har is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion. We demonstrate empirical performance better than state-of-the-art algorithms for small datasets in particular.
  arXiv  Detail & Related papers  (2024-10-03T17:06:06Z)
• Fast and interpretable Support Vector Classification based on the truncated ANOVA decomposition [0.0]
  Support Vector Machines (SVMs) are an important tool for performing classification on scattered data. We propose solving SVMs in primal form using feature maps based on trigonometric functions or wavelets.
  arXiv  Detail & Related papers  (2024-02-04T10:27:42Z)
• A Unified Analysis of Multi-task Functional Linear Regression Models with Manifold Constraint and Composite Quadratic Penalty [0.0]
  The power of multi-task learning is brought in by imposing additional structures over the slope functions. We show the composite penalty induces a specific norm, which helps to quantify the manifold curvature. A unified convergence upper bound is obtained and specifically applied to the reduced-rank model and the graph Laplacian regularized model.
  arXiv  Detail & Related papers  (2022-11-09T13:32:23Z)
• Learning Globally Smooth Functions on Manifolds [94.22412028413102]
  Learning smooth functions is generally challenging, except in simple cases such as learning linear or kernel models. This work proposes to overcome these obstacles by combining techniques from semi-infinite constrained learning and manifold regularization. We prove that, under mild conditions, this method estimates the Lipschitz constant of the solution, learning a globally smooth solution as a byproduct.
  arXiv  Detail & Related papers  (2022-10-01T15:45:35Z)
• Sparsest Univariate Learning Models Under Lipschitz Constraint [31.28451181040038]
  We propose continuous-domain formulations for one-dimensional regression problems. We control the Lipschitz constant explicitly using a user-defined upper-bound. We show that both problems admit global minimizers that are continuous and piecewise-linear.
  arXiv  Detail & Related papers  (2021-12-27T07:03:43Z)
• Support vector machines and linear regression coincide with very high-dimensional features [5.878391874426428]
  We show a phenomenon where every training example used to fit an SVM becomes a support vector. First, we prove a super-linear lower bound on the dimension (in terms of sample size) required for support vector proliferation in independent feature models. We also identify a sharp phase transition in Gaussian feature models, bound the width of this transition, and give experimental support for its universality.
  arXiv  Detail & Related papers  (2021-05-28T20:06:21Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Differentiating through the Fr\'echet Mean [51.32291896926807]
  Fr'echet mean is a generalization of the Euclidean mean. We show how to differentiate through the Fr'echet mean for arbitrary Riemannian manifold. This fully integrates the Fr'echet mean into the hyperbolic neural network pipeline.
  arXiv  Detail & Related papers  (2020-02-29T19:49:38Z)
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks [70.15611146583068]
  We develop exact representations of training two-layer neural networks with rectified linear units (ReLUs) Our theory utilizes semi-infinite duality and minimum norm regularization.
  arXiv  Detail & Related papers  (2020-02-24T21:32:41Z)
• Kernel and Rich Regimes in Overparametrized Models [69.40899443842443]
  We show that gradient descent on overparametrized multilayer networks can induce rich implicit biases that are not RKHS norms. We also demonstrate this transition empirically for more complex matrix factorization models and multilayer non-linear networks.
  arXiv  Detail & Related papers  (2020-02-20T15:43:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.