Computational complexity of kernel-based density-ratio estimation: a condition number analysis
From MaRDI portal
Abstract: The ratio of two probability densities can be used for solving various machine learning tasks such as covariate shift adaptation (importance sampling), outlier detection (likelihood-ratio test), and feature selection (mutual information). Recently, several methods of directly estimating the density ratio have been developed, e.g., kernel mean matching, maximum likelihood density ratio estimation, and least-squares density ratio fitting. In this paper, we consider a kernelized variant of the least-squares method and investigate its theoretical properties from the viewpoint of the condition number using smoothed analysis techniques--the condition number of the Hessian matrix determines the convergence rate of optimization and the numerical stability. We show that the kernel least-squares method has a smaller condition number than a version of kernel mean matching and other M-estimators, implying that the kernel least-squares method has preferable numerical properties. We further give an alternative formulation of the kernel least-squares estimator which is shown to possess an even smaller condition number. We show that numerical studies meet our theoretical analysis.
Recommendations
- Statistical analysis of kernel-based least-squares density-ratio estimation
- Minimax optimal conditional density estimation under total variation smoothness
- Conditional optimization of the functional computational kernel algorithm for approximating the probability density on the basis of a given sample
- On convergence of kernel learning estimators
- The accuracy and the computational complexity of a multivariate binned kernel density estima\-tor.
Cites work
- A least-squares approach to direct importance estimation
- A preconditioning technique for a class of PDE-constrained optimization problems
- A survey of nonlinear conjugate gradient methods
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Complexity theory of numerical linear algebra
- Convex Analysis
- Covariate shift adaptation by importance weighted cross validation
- Coverage processes on spheres and condition numbers for linear programming
- Density ratio estimation in machine learning. Foreword by Thomas G. Dietterich
- Density-ratio matching under the Bregman divergence: a unified framework of density-ratio estimation
- Direct importance estimation for covariate shift adaptation
- Discriminative learning under covariate shift
- Eigenvalues and Condition Numbers of Random Matrices
- Estimates on the distribution of the condition number of singular matrices
- Estimating Divergence Functionals and the Likelihood Ratio by Convex Risk Minimization
- Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average
- General formulas for the smoothed analysis of condition numbers
- scientific article; zbMATH DE number 5485458 (Why is no real title available?)
- scientific article; zbMATH DE number 3686285 (Why is no real title available?)
- scientific article; zbMATH DE number 503395 (Why is no real title available?)
- scientific article; zbMATH DE number 1049347 (Why is no real title available?)
- scientific article; zbMATH DE number 1969625 (Why is no real title available?)
- scientific article; zbMATH DE number 2018408 (Why is no real title available?)
- scientific article; zbMATH DE number 2119754 (Why is no real title available?)
- scientific article; zbMATH DE number 3252891 (Why is no real title available?)
- scientific article; zbMATH DE number 3322635 (Why is no real title available?)
- Improving predictive inference under covariate shift by weighting the log-likelihood function
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Input-dependent estimation of generalization error under covariate shift
- Least-squares independent component analysis
- Least-squares two-sample test
- Linear and nonlinear programming.
- Matrix Analysis
- Numerical inverting of matrices of high order
- Numerical Optimization
- On the Distribution of a Scaled Condition Number
- On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
- On the expected condition number of linear programming problems
- On the influence of the kernel on the consistency of support vector machines
- Probabilistic analysis of condition numbers for linear programming
- Robin-Robin preconditioned Krylov methods for fluid-structure interaction problems
- ROUNDING-OFF ERRORS IN MATRIX PROCESSES
- Sequential change‐point detection based on direct density‐ratio estimation
- Smoothed analysis of algorithms
- Smoothed analysis of complex conic condition numbers
- Smoothed analysis of integer programming
- Smoothed Analysis of Moore–Penrose Inversion
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Soft margins for AdaBoost
- Some results on Tchebycheffian spline functions and stochastic processes
- Statistical analysis of kernel-based least-squares density-ratio estimation
- Tails of Condition Number Distributions
- The complexity of semilinear problems in succinct representation
- The fundamental theorem of algebra and complexity theory
- The Probability That a Numerical Analysis Problem is Difficult
- Theory of Reproducing Kernels
- Training a Support Vector Machine in the Primal
- Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences
Cited in
(10)- Dimensionality reduction for density ratio estimation in high-dimensional spaces
- Least-squares two-sample test
- Change-point detection in time-series data by relative density-ratio estimation
- Statistical analysis of kernel-based least-squares density-ratio estimation
- Semi-supervised learning of class balance under class-prior change by distribution matching
- Direct density-ratio estimation with dimensionality reduction via least-squares hetero-distributional subspace search
- Bending analysis of quasicrystal plates using adaptive radial basis function method
- Learning under nonstationarity: covariate shift and class-balance change
- Online neural networks for change-point detection
- Model-based policy gradients with parameter-based exploration by least-squares conditional density estimation
This page was built for publication: Computational complexity of kernel-based density-ratio estimation: a condition number analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1945037)
