PaperlayerView exact revision on arXiv

Source-linked AI summary

Introduction to Machine Learning

Laurent Younes

arXiv:2409.02668v2stat.MLcs.LG

TL;DR

The book addresses how machine-learning algorithms can be mathematically developed and analyzed. It presents foundations in mathematics, probability, optimization, kernels, prediction, generative modeling, and unsupervised learning, with a focus on understanding algorithms and their prerequisites and limitations. Its scope is intended for readers with backgrounds in mathematics and statistics, while measure-theoretic tools are generally limited and accompanied by alternative interpretations.

  • Problem

    Machine learning requires mathematical foundations for analyzing, reproducing, and predicting mechanisms observed through experiments and data.

  • Method

    The book develops mathematical and statistical foundations alongside explicit descriptions of algorithms spanning supervised, generative, and unsupervised learning.

  • Results

    The book provides techniques for developing and analyzing machine-learning algorithms, including stochastic gradient descent and proximal methods.

  • Takeaways & Limitations

    Readers are prepared to understand algorithms, assess their prerequisites and limitations, and extend or develop new algorithms.

  • Takeaways & Limitations

    The book assumes familiarity with linear algebra, matrix analysis, multivariate calculus, probability, and statistics.

Abstract

from arXiv · show

This book introduces the mathematical foundations and techniques that lead to the development and analysis of many of the algorithms that are used in machine learning. It starts with an introductory chapter that describes notation used throughout the book and serve at a reminder of basic concepts in calculus, linear algebra and probability and also introduces some measure theoretic terminology, which can be used as a reading guide for the sections that use these tools. The introductory chapters also provide background material on matrix analysis and optimization. The latter chapter provides theoretical support to many algorithms that are used in the book, including stochastic gradient descent, proximal methods, etc. After discussing basic concepts for statistical prediction, the book includes an introduction to reproducing kernel theory and Hilbert space techniques, which are used in many places, before addressing the description of various algorithms for supervised statistical learning, including linear methods, support vector machines, decision trees, boosting, or neural networks. The subject then switches to generative methods, starting with a chapter that presents sampling methods and an introduction to the theory of Markov chains. The following chapter describe the theory of graphical models, an introduction to variational methods for models with latent variables, and to deep-learning based generative models. The next chapters focus on unsupervised learning methods, for clustering, factor analysis and manifold learning. The final chapter of the book is theory-oriented and discusses concentration inequalities and generalization bounds.

14 Markov Random Fields

The section develops mathematical conditions and convergence results for optimization methods, including gradient, stochastic, proximal, constrained, and dual approaches.

  • A differentiable local minimum has zero gradient, while a twice-differentiable local minimum additionally has a positive semidefinite Hessian.
  • A stationary point with a positive definite Hessian is sufficient for a local minimum.
  • Steepest descent uses the negative gradient as a descent direction, although Euclidean steepness may not suit every optimization problem.
  • Under stated assumptions, descent algorithms produce iterates whose gradients approach zero and may achieve any prescribed gradient tolerance in finitely many steps.
  • Stochastic approximation converges in L2, and under additional conditions can converge almost surely; finite-time deviation bounds do not directly extend to infinite horizons.
  • Proximal methods converge for closed convex objectives, with proximal gradient descent decreasing the objective when α_t ≤ 2/L.

Introduction: Bias, Variance and Density Estimation

Density estimation frames the bias–variance dilemma: richer models reduce approximation bias but increase variance, so model complexity must be matched to sample size. The chapter develops parametric and kernel methods, their asymptotic behavior, and the curse of dimensionality.

  • Density estimation: Density estimation estimates an unknown probability density from independent training observations, either directly or through a finite-dimensional parametric family.The estimator maps a training set to an estimated density, while parameter estimation restricts candidates to densities indexed by θ.
  • Parametric estimation: Maximum likelihood selects the parameter maximizing empirical average log-likelihood, and its estimator is called the maximum likelihood estimator.When the true density lies outside the parametric class, consistency concerns convergence toward the best approximating model rather than the true density itself.
  • Parametric estimation: Kullback–Leibler divergence measures distributional discrepancy, is nonnegative, and equals zero exactly when the two probability measures coincide.This provides the criterion for interpreting maximum likelihood as selecting a best approximator within the parametric class.
  • Bias–variance dilemma: When the model class excludes the true density, convergence to its best approximator leaves approximation bias; enlarging the class reduces bias but increases finite-sample variance.Sieve methods address this trade-off by increasing the dimension of the parameter class as the sample size grows.
  • Kernel density estimation: Kernel density estimation requires the bandwidth σ to decrease while Nσ^d grows, balancing vanishing bias against vanishing variance.For smoother densities and kernels with vanishing moments, the convergence rate can reach N^(-2r/(2r+d)) and is minimax optimal.
  • Curse of dimensionality: Achieving accuracy ϵ in the worst case requires sample size of order (1/ϵ)^(1+d/2r), which grows exponentially with dimension and creates the curse of dimensionality.The analysis notes that this worst-case difficulty may be mitigated when data has a lower-dimensional structure or when domain knowledge identifies relevant structure.

Prediction: Basic Concepts

Prediction learns a function of inputs that minimizes expected risk, with Bayes predictors providing the theoretical optimum and training data enabling practical approximations. The chapter develops prediction settings, risk functions, Bayes rules, model-based estimators, and the decomposition of generalization error into irreducible, bias, and variance terms.

  • Prediction seeks the best function of input X for predicting output Y under a specified criterion.
  • Risk functions assign costs to true and predicted outputs, and prediction minimizes expected risk, also called generalization error.
  • A Bayes predictor minimizes the conditional expected risk and is optimal because its generalization error is no greater than that of any other predictor.
  • Under squared loss, the conditional expectation E(Y | X = x) is the unique Bayes predictor up to probability-zero modifications.
  • For finite-output classification with zero-one loss, the Bayes predictor minimizes misclassification probability by selecting the posterior mode.
  • Because the true distribution is unavailable, practical prediction estimates it or its conditional form from training data, using model-based, Gaussian, naive Bayes, or kernel-density approaches.
  • The generalization error decomposes into Bayes error, approximation error, and estimation error, with larger model spaces reducing approximation error but increasing estimation error.
  • Cross-validation estimates average algorithm error over smaller random training sets and typically overestimates error for the full available sample size.

Inner Products and Reproducing Kernels

The chapter develops feature-space and inner-product foundations for linear methods, then shows how positive kernels encode these inner products and support kernelized learning. It also connects regularization to the bias–variance trade-off and characterizes several optimization formulations.

  • Feature spaces: Feature functions map inputs into an inner-product feature space where linear methods can operate, including spaces of potentially infinite dimension.Many methods can instead be expressed through inner products between feature representations.
  • Inner-product spaces: An inner product induces a norm, and completeness distinguishes Banach and Hilbert spaces; completeness ensures Cauchy sequences converge within the space.Hilbert spaces are complete inner-product spaces.
  • Positive kernels: A feature map defines a symmetric positive kernel through inner products, while positive definiteness is equivalent to linear independence of feature vectors at distinct inputs.Every positive kernel can later be represented by some feature function.
  • Kernel constructions: Translation-invariant kernels depend only on x−y, and specific measures generate familiar examples such as the Gaussian kernel.The construction also yields rational kernel forms from exponential measures.
  • Kernel methods: The kernel trick reduces computations to kernel evaluations, allowing methods to use high- or infinite-dimensional feature spaces with bounded dual cost.The dual problem has dimension 2N rather than the feature-space dimension.
  • Regularization: Regularization can reduce prediction error by introducing estimation bias to reduce variance, and constrained and penalized formulations can be equivalent.For ridge regression, changing the penalty parameter corresponds to changing the constraint level.

In particular |r(i)

This section develops lasso and related sparse-learning procedures through subgradient conditions, active-set updates, and dual certificates. It also states conditions for sparse recovery and connects kernelized optimization with finite-dimensional inner-product calculations.

  • Lasso optimality: The lasso subgradient permits coordinate signs z(i) equal to sign(b(i)) for nonzero coefficients and any value in [−1,1] at zero.These conditions characterize optimal solutions and support path-following algorithms.
  • Lasso path algorithms: As λ changes, the lasso algorithm adds variables when unused-variable covariance with the residual becomes too large and removes variables when coefficients cross zero.The procedure tracks changes in the active sign configuration.
  • LARS: LARS simplifies the lasso procedure by adding active variables at each step and selecting the unselected variable with the smallest angle to the current residual.This is equivalent to selecting the variable with largest absolute residual correlation.
  • Stopping and selection: The lasso algorithm can stop when all remaining variables have residual correlations below a λ-dependent threshold; an alternative criterion decreases with 1/N.The alternate form selects the variable with largest absolute residual covariance when the stopping condition fails.
  • Dual certificates: The dual formulation can certify a candidate sparse solution when its active coordinates match the prescribed signs and inactive correlations satisfy boundedness conditions.The relevant dual certificate is constructed from the active set.
  • Sparse recovery: Under suitable conditions involving restricted correlations and sparse support size, lasso and Dantzig-selector procedures can recover sparse solutions exactly or up to a small error.The stated conditions include δ(2q)+θ(q,2q)<1 and near-orthogonality of design columns.
  • Kernelized optimization: Kernelized formulations replace Euclidean inner products with kernel evaluations, while the resulting dual problem remains finite-dimensional.This enables bounded computational cost even when the feature dimension is large or infinite.

Nearest-Neighbor Methods

Nearest-neighbor methods make predictions from nearby training observations without imposing regularity on the decision or regression function. Under suitable weight conditions, they are consistent, achieve optimal rates for Lipschitz regression, and approach Bayes classification.

  • Nearest-neighbor estimators are non-parametric, require no training in their simplest form, and use proximity to training observations for prediction.They support both regression and classification.
  • Weighted nearest-neighbor regression assigns coefficients according to ordered distances, with tied observations receiving averaged weights.The p-nearest-neighbor estimator averages the outputs of the p closest observations, accounting for ties.
  • Consistency requires the number of neighbors pN to diverge while remaining negligible relative to sample size: pN →∞ and pN/N →0.Under the theorem’s assumptions, the estimator converges in L2 norm to E(Y | X).
  • For Lipschitz regression functions on R^d, p-nearest-neighbor estimation is minimax optimal at rate bN = N −1/(2+d).The rate exhibits the curse of dimensionality: achieving fixed worst-case accuracy requires exponentially more data as dimension increases.
  • Nearest-neighbor posterior estimates are consistent, so classification approaches Bayes’s rule as N grows.The asymptotic 1-NN misclassification error is bounded above by twice the Bayes error.

Tree-based Algorithms, Randomization and Boosting

Tree methods recursively partition the input space into regions with simpler predictions, while randomization and boosting extend their flexibility. The chapter also describes neural-network architectures whose design reflects the computational task, including smooth invertible transformations.

  • Decision trees: Prediction trees use divide-and-conquer partitioning to create regions where outputs are nearly constant, represented by binary trees.Internal nodes apply binary features, while leaves provide predictors.
  • Decision trees: A recursive tree algorithm stops according to sample size or output homogeneity, then predicts using leaf averages for regression or modes for classification.Non-terminal nodes select features and split the training subset into two child nodes.
  • Decision trees: CART commonly splits along coordinate-parallel hyperplanes, choosing feature and threshold combinations by minimizing an empirical risk.For regression, the optimal predictions in the two resulting regions are their respective output averages.
  • Randomization: Randomizing split features often significantly improves decision-tree performance and is the typical randomization method used in random forests.
  • Randomization: Order-based tree splits are invariant to increasing transformations of measured features, supporting settings where measurement changes preserve latent-variable ordering.The text identifies high-throughput biological measurements such as microarrays as an application context.
  • Boosting: Boosting can drive training error arbitrarily close to zero when base classifiers perform reliably better than chance, and can be interpreted as incremental objective improvement.The construction is connected to gradient boosting through iterative updates.
  • Neural networks: The described neural algorithm induces a smooth, invertible, diffeomorphic transformation with a smooth inverse.The transformation maps an input to the ODE solution at time T.

Comparing probability distributions

This section presents distances and divergences for comparing probability distributions, then introduces Markov-chain sampling and conditions for convergence to target distributions.

  • Comparing probability distributions: Distribution-comparison methods include total variation, Hellinger, KL, Wasserstein, and kernel-based distances.The section motivates these measures for evaluating learned distributions against observed ones.
  • Comparing probability distributions: The f-divergence family includes total variation at α = 1 and the Hellinger distance at α = 1/2.The α = 1 case equals two times total variation distance.
  • Markov-chain sampling: Irreducibility and aperiodicity are necessary for ergodicity and, with an invariant probability distribution, are sufficient under the stated conditions.A periodic chain cannot satisfy the desired convergence relation.
  • Markov-chain sampling: On finite state spaces, irreducibility and aperiodicity imply uniform ergodicity.A common sufficient condition is that some fixed power of the transition matrix has all positive entries.
  • Markov-chain sampling: Geometric ergodicity follows from drift and compactness conditions, and also holds for sufficiently small-step chains under the stated gradient-growth assumption.The cited results cover general Feller chains and a specific continuous-variable chain.

Markov Random Fields

This section develops conditional independence and graphical representations for Markov random fields, including their behavior under conditioning, marginalization, and tree or loopy structures.

  • Independence and conditional independence: Conditional independence means that X and Y are independent after conditioning on Z, so Z supplies the relevant information connecting them.For discrete variables, the joint conditional probability factors into the two conditional marginals.
  • Independence and conditional independence: Mutual information is nonnegative and equals zero exactly when X and Y are independent.It is also the KL divergence between the joint distribution and the product of its marginals.
  • Markov random fields: Conditioning a G-Markov field on partial evidence preserves the Markov property on the induced subgraph.Marginalization also preserves a Markov property, but the resulting graph may be substantially more complex.
  • Markov random fields: Positive G-Markov processes are characterized by strictly positive local interactions on the graph’s cliques.The Hammersley-Clifford theorem gives the equivalence between positivity, the Markov property, and clique-factorized interactions.
  • Acyclic models and trees: Acyclic graph models correspond to tree-based Markov representations and have favorable computational properties.Undirected acyclic graphs can be represented through forests, and tree-Markov processes correspond to their associated undirected graphs.
  • General loopy Markov random fields: Acyclicity is restrictive for models requiring feedback or lattice symmetries, motivating loopy fields such as the two-dimensional Ising model.Gaussian Markov random fields are especially useful when their graph-associated precision matrix is sparse.

Probabilistic Inference for Random Fields

Inference in random fields seeks marginal probabilities, but direct summation is generally intractable on loopy graphs. Sampling, belief propagation, and graph transformations provide exact solutions in special structures and approximations otherwise.

  • Marginal probabilities require sums whose number of terms grows exponentially with the graph size, making direct computation intractable for general loopy graphs.
  • Monte Carlo methods approximate inference on loopy graphs, while acyclic graphs admit more direct computation.
  • Local Gibbs and Metropolis-Hastings updates avoid computing the global normalizing constant, but convergence can be slow for strongly structured, large graphs.
  • Acceleration methods update large configuration blocks to overcome local-mode barriers and can substantially speed sampling convergence.
  • Belief propagation is exact on trees: its stationary distributions equal the target marginals, and sum-product and max-product converge in finite time on acyclic factor graphs.
  • For loopy graphs, Bethe-consistency characterizes belief-propagation stationarity, while junction-tree methods rely on triangulation and decomposability.

Bayesian Networks

Bayesian networks represent distributions through local conditional factors on directed acyclic graphs. Their graph structure determines conditional independences, supports efficient inference in special cases, and distinguishes observational relationships from interventions.

  • A Bayesian network on a DAG factorizes its joint distribution into local probability distributions conditioned on each node’s parents.
  • The induced moral graph captures the Markov structure of a Bayesian network, rather than treating every directed edge as causal.
  • D-separation in a DAG is equivalent to graph separation in the corresponding restricted moral graph.
  • Bayesian-network factorizations are equivalent to decompositions over the graph’s associated structure, and Markov-equivalent DAGs share the same relevant separations.
  • On singly connected DAGs, parents of a node are mutually independent, enabling recursive sum-product inference with correct marginal probabilities.
  • Intervening on variables changes the distribution by manipulating the network, and conditioning on ancestors can yield the corresponding manipulated distribution.

Latent Variables and Variational Methods

Variational methods approximate posterior distributions over latent variables by optimizing within a tractable family. The book presents MAP, Laplace, and mean-field approximations, together with their computational trade-offs.

  • Latent-variable models separate observed X from hidden Z, with inference focused on approximating the posterior distribution of Z given X.
  • Variational Bayes replaces the full distribution family with a computationally feasible subset and selects the approximation using Kullback-Leibler divergence.
  • Restricting the variational family to point masses yields the MAP approximation, which selects posterior modes.
  • The mode approximation is often crude and difficult to optimize, limiting its practical use for complex posterior distributions.
  • The Laplace approximation uses the posterior mode and inverse Hessian to form a Gaussian approximation when these quantities are feasible to compute.
  • Mean-field approximation imposes independent components on the variational distribution and can be feasible when the log joint density has a compatible decomposition.

Learning Graphical Models

Learning graphical models combines Bayesian estimation, conjugate priors, likelihood optimization, and maximum-entropy procedures. These methods provide finite-sample smoothing, consistency results, and convergence guarantees under stated conditions.

  • Relative-frequency estimates are unbiased with variance P(A)(1−P(A))/N, but rare events can receive zero estimated probability.
  • Bayesian estimation treats the unknown event probability as random and updates prior beliefs using observed Bernoulli data.
  • Beta priors are conjugate for binomial observations, while Dirichlet priors are conjugate for multinomial distributions and Bayesian-network conditional probabilities.
  • Choosing positive prior parameters yields positive MAP estimates even when an event has not been observed.
  • With sufficiently small step sizes, stochastic updates using Gibbs or Metropolis sampling converge almost surely to the maximum-likelihood estimator.
  • For consistent expectation assignments satisfying the stated condition, the maximum-entropy algorithm converges to the maximum-entropy extension.
  • Under mild conditions, estimators obtained from the modeled family are generally consistent as the sample size increases.

Deep Generative Methods

The chapter develops generative models that transform simple random variables into complex data distributions, covering normalizing flows, variational autoencoders, GANs, and reverse diffusions.

  • General framework: Feed-forward generative methods construct complex random variables through nonlinear transformations of simpler ones, often using high-dimensional parametrizations.The framework includes structural equation models and deep-learning implementations.
  • Normalizing flows: For invertible g, the density of X is obtained from the known density of Z through the change-of-variable formula, and training maximizes the resulting log-likelihood subject to anti-overfitting constraints.The inverse h of g is used to express the likelihood from training data.
  • Normalizing flows: Normalizing flows use compositions of diffeomorphisms to transform data into samples from a normal distribution while enabling likelihood-based optimization.The transformations can be implemented greedily, neurally, or continuously in time.
  • Normalizing flows: Continuous-time normalizing flows track particle trajectories and log-Jacobian determinants through an ODE, yielding an optimal-control formulation when the divergence is explicit.The inverse generative map can also be obtained by solving an ODE backward from latent variables.
  • Variational autoencoders: VAEs replace deterministic mappings with conditional distributions, modeling X as a nonlinear function of latent Z plus Gaussian noise and approximating Z given X with a neural Gaussian distribution.The approximate posterior uses neural networks for its mean and symmetric factor of the covariance.

Clustering

The chapter presents clustering as the organization of data into homogeneous groups, supporting Euclidean, kernel, manifold, graph, and dissimilarity-based settings through hierarchical and optimization-based methods.

  • Problem setting: Clustering divides training data into homogeneous subsets to improve understanding and support subsequent processing adapted to each group.The framework allows only a discrepancy matrix to be observed, without coordinate representations.
  • Problem setting: Clustering can use Euclidean metrics, kernel-induced feature distances, intrinsic manifold distances, distances on positive-definite matrices, or weighted-graph geodesics.The chapter therefore accommodates data that are not naturally Euclidean.
  • Partition trees: Hierarchical clustering organizes data in a binary tree by recursively splitting subsets or agglomeratively merging singletons until the full dataset is formed.Leaves represent terminal nodes, and a complete hierarchy has singleton leaves.
  • Bottom-up construction: Agglomerative clustering repeatedly merges the pair of current clusters with minimal extended dissimilarity until one cluster remains.The procedure starts from singleton trees and updates the collection after each merge.
  • Bottom-up construction: The extended subset dissimilarity determines agglomerative behavior: maximum distance favors small-diameter clusters, whereas minimum gaps favor connected clusters.The maximum and minimum linkage algorithms are equivalent to specific diameter and connectivity constructions.
  • Partitional methods: K-means-style methods reduce their objective at every step but may converge to poor local minima, so initialization heuristics and multiple random restarts are used.The stopping criterion follows stabilization of the cost because only finitely many partitions exist.
  • Partitional methods: As σ^2 tends to zero, soft K-means approaches K-means, while deterministic annealing is experimentally more robust against bad local minima.The limiting class allocation selects nearest centers unless ties occur.
  • Spectral clustering: For spectral clustering, an elbow-based criterion returned the correct number of clusters, namely 3, in both illustrated examples.The criterion selects the value of p at which C reaches its maximum.

Dimension Reduction and Factor Analysis

Dimension-reduction methods represent high-dimensional data through lower-dimensional structures, while factor and generative-process methods model latent features or distributions. PCA and its extensions use eigenstructure, kernels, low-rank penalties, or specialized latent-process constructions to obtain these representations.

  • Factor analysis represents potentially high-dimensional data as functions of a generally small number of factors.
  • Principal component analysis: The optimal PCA subspace lies within the span of the centered training data, and the first p eigenvectors provide the relevant solution subspace.
  • Principal component analysis: PCA solutions are given by the first p eigenvectors of the covariance matrix, or empirical covariance for standard Euclidean PCA.
  • Generalized PCA: Generalized PCA approximates data by a finite union of subspaces and can recursively refine the resulting hyperplane decomposition.
  • Nuclear norm minimization and robust PCA: Nuclear-norm minimization yields singular-value thresholding solutions and preserves principal directions while shrinking singular values rather than hard-thresholding them.
  • Nuclear norm minimization and robust PCA: Robust PCA can exactly reconstruct a low-rank component and a sparse residual with high probability under diffuse singular vectors, sufficiently small rank, and random sparse support.
  • Independent component analysis: ICA is identifiable up to permutation and diagonal scaling, so recovering independent components requires identifying the corresponding transformed variables under these indeterminacies.
  • Latent-feature processes: The Indian buffet process provides an incremental simulation process for feature labels as the number of potential features tends to infinity.

Data Visualization and Manifold Learning

Data-visualization methods seek interpretable low-dimensional representations from similarities or dissimilarities, while manifold-learning methods preserve global or local structure beyond ordinary Euclidean geometry. MDS reduces dissimilarities through spectral optimization, and Isomap can reveal intrinsic curve structure.

  • Data-visualization methods target interpretable low-dimensional representations for visual exploration rather than generative modeling.
  • These methods can use similarity or dissimilarity matrices directly and therefore do not require Euclidean coordinates.
  • Multidimensional scaling: MDS seeks a small-dimensional Euclidean representation whose pairwise distances match a supplied dissimilarity matrix.
  • Kernel and feature-space representations: Kernelized formulations represent data through an implicit feature map and compute transformations from the associated Gram matrix or kernel values.
  • Kernel and feature-space representations: An exact isometry requires the span of the feature vectors to be p-dimensional; otherwise, the method finds a best p-dimensional approximation of the training data.
  • Multidimensional scaling: The PCA-based formulation of MDS is equivalent to minimizing a similarity-matching objective over centered low-dimensional representations.
  • Weighted MDS: Weighted MDS incorporates graph weights, with constraints determined by the connected components of the associated weighted graph.
  • Weighted MDS: MDS can be optimized by alternating minimization over auxiliary variables, using elementary updates for the representation and auxiliary directions.

Generalization Bounds

This section develops generalization bounds for predictors learned from training data, moving from concentration inequalities to complexity-based and stability-based guarantees. It also shows why finite-class bounds are insufficient for large or infinite hypothesis classes and introduces measures such as VC-dimension, Pγ-dimension, and uniform stability.

  • Generalization bounds provide high-probability guarantees on predictors’ generalization error, although they may require impractically large training sets.The chapter emphasizes both their theoretical role and their limited practical usefulness in realistic settings.
  • Model selection and stability: The section also develops alternative penalties and guarantees based on model dimension, minimum description length, and algorithmic stability.Penalized likelihood introduces a dimension factor log2 N, while stability bounds apply when the loss is bounded and uniform stability is sufficiently small.
  • Concentration inequalities: For a fixed predictor, concentration inequalities can bound the gap between empirical risk and generalization risk.Hoeffding’s inequality gives such a bound for bounded losses, but the argument must account for predictors estimated from the same training set.
  • Complexity control: Finite-class concentration bounds become poor when the function class is large and do not apply directly when the class is infinite.This motivates complexity measures and union-bound arguments based on VC-dimension and related quantities.
  • VC-dimension: VC-dimension controls growth of shattering numbers and yields generalization bounds for classes with finite VC-dimension.The section also gives examples such as VC-dim(F) = d + 1 and bounds for neural-network classes.
  • Pγ-dimension: Pγ-dimension controls covering numbers and can remain bounded independently of the input dimension, including in infinite-dimensional settings.The resulting bound can be inserted into generalization-error estimates, contrasting with the input-dimension dependence of VC-dimension for separating hyperplanes.
Loading 2409.02668v2…