Source-linked AI summary
A Weighted Kernel Method for Approximation that Adapts to Learned Multivariable Structure
John E. Darges, Laura Weidensager
TL;DR
High-dimensional black-box approximation from limited evaluations is challenging when input importance and interactions are unknown. The paper learns input-specific factors for weighted ANOVA kernels by selecting the RKHS that gives the target minimum norm; experiments report improved approximation when the target has exploitable multivariable structure.
Problem
Approximating high-dimensional black-box functions from limited evaluations is difficult when the method cannot adapt to unknown input importance and interactions.
Source: §1 · p. 1Method
TSKs parameterize weighted ANOVA kernels with input-specific factors learned by choosing the RKHS in which the target function has minimum norm.
Source: §1 · p. 2Results
Numerical experiments show that TSK adaptation improves approximation when the target possesses exploitable multivariable structure.
Source: §6 · p. 20Takeaways & Limitations
The conclusion favors adapting approximation-space geometry to target structure rather than prescribing weights or selecting sparse components in advance.
Source: §6 · p. 20The product form of TSK weights restricts the method to certain weight families and can be unsuitable for complicated interactions lacking low-order terms.
Source: §6 · p. 20
Abstract
from arXiv · showhide
Approximating the input-output behavior of a multivariable black-box function from limited data is challenging when blind to the importance of its inputs and their interactions. We introduce total sensitivity kernels (TSKs), a method based on families of weighted ANOVA kernels that learn and adapt to this multivariable structure. TSKs parameterize the weights on each multivariable component of the target function by factors for each input. We propose learning these factors directly from function evaluations by selecting the reproducing kernel Hilbert space (RKHS) in which the target function has minimum norm. Under suitable conditions, we show that this norm-minimization problem admits a unique solution, and we establish consistency of a finite-data formulation based on minimum-norm interpolation. The learned TSK factors characterize the participation of individual inputs across interactions and main effects, providing a kernel-dependent notion of input sensitivity related to total Sobol indices. Numerical experiments demonstrate that adapting the kernel to learned multivariable structure can substantially improve approximation accuracy over a standard product kernel.
1. Introduction
High-dimensional approximation is difficult when the method cannot exploit unknown differences in input importance and interaction structure. The paper introduces total sensitivity kernels (TSKs), which learn weighted ANOVA-kernel structure by selecting an RKHS in which the target has minimum norm.
1. Introduction
- High-dimensional functions can remain tractable when a few ANOVA components explain most variation, but the number of possible input-group components grows exponentially with dimension.The ANOVA decomposition expresses a function as mutually orthogonal components indexed by subsets of inputs.Source: §1 · p. 1
- Weighted ANOVA spaces rescale multivariable components, so the choice of weights changes how strongly each component is penalized in the norm.Structured parameterizations such as product and product-order-dependent weights avoid assigning a separate value to each of the 2^d components.Source: §1 · p. 2
- The approach learns a structured weighted RKHS rather than prescribing weights or selecting a sparse component set in advance.ANOVA kernels supply the component-based foundation, while the learned factors adapt the associated approximation space to the target.Source: §1 · p. 2
- TSKs use d input-specific factors to parameterize the weights of 2^d ANOVA components, adapting a weighted ANOVA-kernel RKHS to the target’s multivariable structure.The factors are learned by choosing the RKHS in which the target function has minimum norm; under suitable conditions, the optimization is strongly convex and has a unique solution.Source: §1 · p. 2
- The finite-data procedure replaces the unknown target’s norm with the norm of its minimum-norm interpolant, and its objective is related to Gaussian-process ARD objectives.The paper establishes consistency for this finite-data formulation; evaluations are assumed noise-free and inputs independent.Source: §1 · p. 2
2. Background
The background introduces notation for input subsets, kernel-induced function spaces, and kernel ridge regression. It also motivates choosing a kernel by the target function’s RKHS norm, which controls a leading approximation-bias term in the stated error bound.
2. Background
- Input subsets u index components, and x_u denotes the vector restricted to inputs in u; an RKHS is associated with a kernel and has the reproducing property.For distinct data points, the kernel evaluations form a symmetric positive definite matrix.Source: §2 · p. 3, §2.1 · p. 3
2.1. Reproducing Kernel Hilbert Spaces.
- A Fourier feature map induces a kernel, and tensor-product kernels correspond to independently distributed coordinates in a product probability measure.The measure factors into one-dimensional distributions for the individual inputs.Source: §2.1 · p. 3
2.2. Kernel ridge regression and generalization bounds.
- Kernel ridge regression minimizes regularized empirical risk over an RKHS, with the regularization parameter controlling the trade-off between data fit and generalization.Its stated generalization bound assumes the target belongs to the RKHS and separates estimation error from regularization bias.Source: §2.2 · pp. 3–4
- For shift-invariant kernels, the bound’s leading approximation-bias constant is governed by the target’s RKHS norm, motivating kernel selection that minimizes that norm.The bound balances estimation error, which vanishes as sample size grows, against regularization bias.Source: §2.2 · p. 4
3. Theory of total sensitivity kernels
Total sensitivity kernels (TSKs) adapt weighted ANOVA kernels to a target function by learning input-specific factors that select an RKHS with small target-function norm. The theory establishes strong convexity of this norm objective under stated kernel assumptions and interprets the learned factors as RKHS-based sensitivity weights, not exact Sobol indices.
3. Theory of total sensitivity kernels
- TSKs modify ANOVA-like kernels with tunable input-importance parameters, and larger factors weight interactions involving that input more heavily.The factors parameterize the component weights of the kernel and its associated RKHS.Source: §3 · p. 4
3.1. RKHS properties.
- Changing TSK factors changes the RKHS inner product and norm, while the RKHSs contain the same functions.The resulting norm resembles a weighted sum of ANOVA component energies.Source: §3.1 · p. 5
3.2. Optimal TSK factors.
- Minimizing the RKHS norm selects the factorized kernel geometry that best aligns with the target’s multivariable structure and lowers one term in the KRR error bound.The same function belongs to the RKHSs indexed by different factors; the factors change how its components are penalized.Source: §3.2 · p. 6
- Under strictly positive-definite univariate kernels with unit diagonal, the theoretical squared RKHS norm is strongly convex in the TSK factors, so any minimizing factors are unique if they exist.Strong convexity is established on (0, 1)^d.Source: §3.2 · pp. 6, 8
3.3. Interpretation of the TSK factors Σ.
- Learned factors act as continuous feature-selection weights and proxies for total sensitivity: values near 1 indicate explanatory energy, while values near 0 shrink an input.The factors are RKHS-based sensitivity weights, not exact variance-based Sobol indices, because the kernel construction does not guarantee L2-orthogonality of the components.Source: §3.3 · pp. 8–9
4. Weight learning: algorithms and theory
The finite-data method replaces the unknown theoretical norm objective with the minimum RKHS norm of an interpolant and optimizes that empirical surrogate. Under the stated sampling and kernel setup, the surrogate converges uniformly to the theoretical objective, while the algorithm uses L-BFGS and addresses numerical stalling near factors of 1.
4.1. Finite-data TSK.
- With finite evaluations, the method minimizes an empirical surrogate based on the squared RKHS norm of the minimum-norm interpolant of the data.The target function is unknown, so the theoretical objective is replaced by a discrete analogue.Source: §4 · p. 9, §4.1 · pp. 9–10
- g_M converges uniformly to the theoretical objective g on [η, 1−η]^d under i.i.d. sampling from a distribution supported on the domain.The result holds for any η in (0, 1).Source: §4.1 · p. 10
- Strong convexity of g and uniform approximation by g_M bound the empirical factors’ error from the true minimizer, supporting stability of the learned kernel and approximation error.The authors state that the learned-kernel approximation error deviates from the optimum by a term proportional to O(√ϵ_M).Source: §4.1 · pp. 10–11
- Unlike the exact objective, the finite-data objective currently has no convexity guarantee, although numerical Hessian checks were consistently positive definite at randomly sampled factors.The authors speculate that convexity may hold with high probability under random sampling.Source: §4.1 · p. 11
4.2. The Algorithm.
- The learning algorithm first optimizes TSK factors with L-BFGS, then performs kernel ridge regression.The finite-data objective has explicit gradient and Hessian expressions.Source: §4.2 · p. 11
- In high dimensions, products in the kernel matrix and its derivatives can become numerically small near factors of 1, making the objective appear nearly constant and stalling optimization.The authors initialize factors away from 1 to mitigate this effect.Source: Initialization matters · p. 12
5. Numerical experiments
The experiments compare TSK with fixed kernels and ARD across g-function complexity levels and higher-dimensional benchmarks. TSK performs especially well when its learned component weights align with the target’s multivariable structure.
5. Numerical experiments.
- The experiments use limited evaluation budgets and compare TSK with standard product and unweighted ANOVA kernels, adding ARD for Gaussian-kernel tests.The higher-dimensional experiments examine functions with different multivariable structures; validation sets contain 104 points.Source: §5 · pp. 12–13, §5.2 · p. 15
5.1. Case study: Sobol’ g-function.
- For the low-complexity g-function, TSK error is less than one fourth of standard-kernel error and half of ANOVA-kernel error; for medium complexity, it performs twice as well as the standard kernel.Across all three complexity cases, TSK outperforms the standard kernel and is roughly similar to or better than ANOVA; the advantage grows as complexity decreases.Source: §5.1 · pp. 13–15, Figure 1 · p. 14
5.2. Higher-dimensional examples.
- For the 100D benchmark, TSK and ARD approximate accurately while standard and unweighted ANOVA kernels are much less accurate; TSK-factor rankings match Sobol’ rankings, though their values do not.The learned factors recover meaningful structure in a function with main effects and pairwise interactions.Source: 100D function · p. 15, Figure 2 · p. 16
- For the diffusion problem, the standard product kernel predicts values close to zero with RRSE approximately one, while unweighted ANOVA behaves similarly and TSK and ARD approximate accurately.Learned TSK factors indicate that a relatively small subset of the 62 KL coefficients contributes substantially.Source: One-dimensional diffusion model · p. 17, Figure 3 · p. 18
- On the modified Grienwank function, TSK’s approximation error is an order of magnitude smaller than ARD’s, for a function combining unequal main effects with interactions of multiple orders.This comparison differs from the preceding examples, illustrating that TSK and ARD exploit structure differently and neither is best across all four examples.Source: Modified Grienwank function · p. 17, Figure 4 · p. 19
- Across three higher-dimensional examples, TSK factor optimization improves on the standard kernel by at least two orders of magnitude, while TSK and ARD both substantially improve accuracy over fixed kernels.The unweighted ANOVA kernel provides only modest improvement and is nearly identical to the standard kernel on the two diffusion problems.Source: Modified Grienwank function · p. 17, Table 2 · p. 20
6. Conclusion and outlook
The paper adapts weighted RKHS geometry to an unknown function’s multivariable structure by learning input-specific TSK factors. It concludes that this adaptation improves approximation when exploitable structure is present, while identifying limits in the weight family and directions for extending the theory and implementation.
6. Conclusion and outlook
- TSKs reduce 2^d ANOVA component weights to d input-specific factors learned by finding the RKHS in which the target has minimum norm.Under suitable conditions, the factors are unique to the target function.Source: §6 · p. 20
- Numerical experiments show that this adaptation improves approximation when the target has exploitable multivariable structure.Source: §6 · p. 20
- Product-form weights restrict TSKs to certain weight families and are unsuitable for some complicated interactions, especially high-order terms without low-order terms.Source: §6 · p. 20
- Future work could extend TSK theory to other weight structures and examine its relation to sensitivity notions beyond classical ANOVA.The paper specifically highlights product-order-dependent weights and kernel-based sensitivity indices.Source: §6 · p. 20
- Random features are proposed as a route to better scalability, and TSKs may be integrated into methods such as automatic relevance determination and multiple kernel learning.Source: §6 · p. 20
- The established theory concerns exact minimum-norm interpolation with independently distributed inputs; noisy observations and dependent inputs remain future extensions.Source: §6 · p. 20