In this paper, we study the Nystr{ö}m type subsampling for large scale kernel methods to reduce the computational complexities of big data. We discuss the multi-penalty regularization scheme based on Nystr{ö}m type subsampling which is motivated from well-studied manifold regularization schemes. We develop a theoretica…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Nyström approximation”
Paper develops a new kernel approximation framework.
problem High time and space complexity of kernel methods for large datasets.
method Perturbation-based kernel approximation framework using classical perturbation theory.
result Framework generalizes and improves upon existing methods.
Recent work has focused on combining kernel methods and deep learning to exploit the best of the two approaches. Here, we introduce a new architecture of neural networks in which we replace the top dense layers of standard convolutional architectures with an approximation of a kernel function by relying on the Nystr{ö}…
We consider the problem of metric learning for multi-view data and present a novel method for learning within-view as well as between-view metrics in vector-valued kernel spaces, as a way to capture multi-modal structure of the data. We formulate two convex optimization problems to jointly learn the metric and the clas…
Kernel methods are powerful and flexible approach to solve many problems in machine learning. Due to the pairwise evaluations in kernel methods, the complexity of kernel computation grows as the data size increases; thus the applicability of kernel methods is limited for large scale datasets. Random Fourier Features (R…
In this paper we model the problem of learning preferences of a population as an active learning problem. We propose an algorithm can adaptively choose pairs of items to show to users coming from a heterogeneous population, and use the obtained reward to decide which pair of items to show next. We provide computational…
Survey of kernels, RKHS, and their applications in machine learning.
problem Understanding kernels and their applications in machine learning.
method Review of historical context, mathematical definitions, and practical applications of kernels.
result Comprehensive overview of kernels, RKHS, and their applications.
We are interested in a framework of online learning with kernels for low-dimensional but large-scale and potentially adversarial datasets. We study the computational and theoretical performance of online variations of kernel Ridge regression. Despite its simplicity, the algorithm we study is the first to achieve the op…
In this paper, we study large-scale convex optimization algorithms based on the Newton method applied to regularized generalized self-concordant losses, which include logistic regression and softmax regression. We first prove that our new simple scheme based on a sequence of problems with decreasing regularization para…
This work improves knowledge distillation by transferring full kernel matrices efficiently.
problem Efficiently transferring full pairwise similarity matrices for model compression in deep learning.
method The authors propose a method to transfer the full similarity matrix effectively using the Nyström method, decomposing it into partial matrices.
result The difference between the full kernel matrices of teacher and student can be well bounded by partial matrices, improving optimization efficiency.
The study provides conditions for approximating Riemannian manifolds with polyhedral metrics.
problem Approximating Riemannian manifolds with polyhedral metrics.
method Conditions on curvature tensors for Lipschitz and local polyhedral approximations.
result Conditions are sufficient for local polyhedral approximations, conjectured to be sufficient for global approximations.
Geometric Gaussian approximations capture any distribution.
problem Approximating complex probability distributions.
method Geometric Gaussian approximations through diffeomorphisms or exponential maps.
result Geometric Gaussian approximations are universal, capturing any distribution.
Method approximates Riemannian barycenter on manifolds.
problem Computing the exact Riemannian barycenter is computationally expensive.
method Uses under- and over-approximations of Riemannian distance to compute an approximate barycenter.
result Approximation method is more efficient than exact methods and steepest descent.
We consider in this paper the optimal approximations of convex univariate functions with feed-forward Relu neural networks. We are interested in the following question: what is the minimal approximation error given the number of approximating linear pieces? We establish the necessary and sufficient conditions and uniqu…
Efficiently reduces tensor ranks using mean-field approximation.
problem Low-rank approximation of non-negative tensors.
method Mean-field approximation of tensor rank reduction.
result Our algorithm achieves faster and competitive tensor rank reduction.
Study approximates unknown function levels with queries.
problem Approximating unknown function levels through sequential queries.
method Introduce Bisect and Approximate algorithms to reduce to local function approximation.
result Rate-optimal sample complexity guarantees for H{ö}lder functions.
We study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such …
Softmax attention approximates complex functions and subsumes many known universal approximators.
problem Universal approximation of continuous sequence-to-sequence functions.
method Interpolation-based analysis of attention's internal mechanism, showing its ability to approximate ReLU functions.
result Softmax attention is a universal approximator for continuous sequence-to-sequence functions.
Improved matrix approximation using randomized algorithms.
problem Finding better approximations of given matrices.
method Randomized algorithms to compute as an improved approximation.
result Computed provides a better approximation than given .
Deviation inequalities for stochastic approximation methods.
problem Establishing bounds on the deviation of stochastic approximation methods.
method Martingale approximation method for separately Lipschitz functions.
result Established various deviation inequalities for stochastic approximation by averaging and minimization.
Neural approximate computing gains enormous energy-efficiency at the cost of tolerable quality-loss. A neural approximator can map the input data to output while a classifier determines whether the input data are safe to approximate with quality guarantee. However, existing works cannot maximize the invocation of the a…
Approximate symmetries of geodesic equations on 2-spheres are studied. These are the symmetries of the perturbed geodesic equations which represent approximate path of a particle rather than exact path. After giving the exact symmetries of the geodesic equations, two different approaches to study the approximate symmet…
We are concerned with an approximation problem for a symmetric positive semidefinite matrix due to motivation from a class of nonlinear machine learning methods. We discuss an approximation approach that we call {matrix ridge approximation}. In particular, we define the matrix ridge approximation as an incomplete matri…
Transformers use ReLUs to approximate softmax efficiently.
problem Analyzing resource usage in softmax transformer models.
method Translating ReLU approximation results to softmax attention mechanisms.
result Economic resource bounds for softmax attention mechanisms.
Approximating complex curves with simple parametric curves is widely used in CAGD, CG, and CNC. This paper presents an algorithm to compute a certified approximation to a given parametric space curve with cubic B-spline curves. By certified, we mean that the approximation can approximate the given curve to any given pr…
Recently, variational approximations such as the mean field approximation have received much interest. We extend the standard mean field method by using an approximating distribution that factorises into cluster potentials. This includes undirected graphs, directed acyclic graphs and junction trees. We derive generaliz…
Adaptive approximations improve variational inference for complex models.
problem Efficiently approximate marginal distributions and partition functions in complex probabilistic models.
method Two classes of adaptive approximations that include Bethe, tree-reweighted, and convex free energies.
result Proposed approximations automatically adapt to a given model and outperform existing methods.
Non-negative -approximating polynomials for Gaussian distributions are proven for certain classes of sets.
problem Existence of non-negative -approximating polynomials for Gaussian distributions.
method Proving the existence of degree- non-negative polynomials that approximate indicator functions of sets with Gaussian surface area in -norm.
result Proves the existence of non-negative -approximating polynomials for certain classes of sets with Gaussian surface area.
Paper introduces new approximations for lognormal sums, matching comonotonicity and moments.
problem Approximating sums of lognormal random variables accurately.
method Introduces new approximations based on weighted distribution theory, emphasizing comonotonicity and moment matching.
result Approximations perform better than classical methods, especially in the right tail of the distribution.
Paper analyzes normal approximation for two-timescale stochastic algorithms, revealing interaction between fast and slow timescales.
problem Non-asymptotic bounds for accuracy of normal approximation in linear two-timescale stochastic approximation algorithms.
method Established bounds for normal approximation in terms of convex distance, focusing on last iterate and Polyak-Ruppert averaging.
result Normal approximation rate for the last iterate improves with increased timescale separation, while it decreases in the averaged setting.
One-pass algorithm finds small subset for subspace approximation with additive error.
problem Finding a small subset of data points for subspace approximation.
method One-pass subset selection with additive approximation guarantee for .
result First one-pass algorithm with additive error for subspace approximation.
We are interested in approximation of a multivariate function by linear combinations of products of univariate functions , . In the case it is a classical problem of bilinear approximation. In the case of approximation in the space the bili…
A new method for efficient Gaussian process inference using sparse approximations.
problem Scalable and accurate inference for latent Gaussian processes.
method Variational approximation with sparse inverse Cholesky factors and double Kullback-Leibler minimization.
result The proposed method can achieve highly accurate approximations with polylogarithmic time complexity.
In this paper, we propose a low-rank approximation method based on discrete least-squares for the approximation of a multivariate function from random, noisy-free observations. Sparsity inducing regularization techniques are used within classical algorithms for low-rank approximation in order to exploit the possible sp…
Neural network based approximate computing is a universal architecture promising to gain tremendous energy-efficiency for many error resilient applications. To guarantee the approximation quality, existing works deploy two neural networks (NNs), e.g., an approximator and a predictor. The approximator provides the appro…
Approximation of supply curvesq-fin.PR
The paper approximates supply curves using a one-step basis method.
problem Computing supply curves accurately and efficiently.
method Derives L2 approximation expression and proposes node selection procedure.
result Illustrates the approach with European electricity market bid curves.
The paper defines a new concept of approximability for Lagrangian submanifolds.
problem Understanding the approximability of Lagrangian submanifolds.
method Introducing a new notion of categorical approximability for metric spaces, showing it applies to specific types of Lagrangian submanifolds.
result Examples of Lagrangian submanifolds are found that are approximable but not precompact.
Boosting Nyström Methodstat.ML
Boosting Nyström improves accuracy of matrix approximations.
problem Generating low-rank approximations of large matrices efficiently.
method Iteratively generate multiple weak Nyström approximations, combine them to form a strong approximation.
result Boosting Nyström yields more efficient and accurate low-rank approximations.
High-probability bound for distributed stochastic approximation tracking error.
problem Analyzing the convergence of distributed stochastic approximation schemes.
method Analysis using ODE approach to stochastic approximation.
result High probability bound for tracking error between iterates and limiting differential equation.
Nyström KPCA balances computational efficiency and statistical accuracy.
problem Computational burden in large sample situations for kernel methods.
method Theoretical analysis of Nyström approximate kernel principal component analysis (KPCA).
result Nyström approximate KPCA matches statistical performance of non-approximate KPCA while being computationally beneficial.
Improves Laplace approximation for Bayesian inference on Riemannian manifolds.
problem Inaccurate Gaussian approximations for complex targets and finite-data posteriors.
method Develops alternative variants of the Laplace approximation using a Riemannian metric.
result Exact approximations at the limit of infinite data, improving practical performance.
We approximate derivatives of functions on manifolds by embedding them and applying vector-valued operators.
problem Derivatives of manifold-valued functions are harder to approximate than vector-valued functions.
method Embed the manifold into a higher space, approximate the derivative of the vector-valued function, and project back.
result We provide error bounds for the approximation of manifold-valued function derivatives.
Efficient Approximations for the Marginal Likelihood of Incomplete Data Given a Bayesian Networkcs.LG
We discuss Bayesian methods for learning Bayesian networks when data sets are incomplete. In particular, we examine asymptotic approximations for the marginal likelihood of incomplete data given a Bayesian network. We consider the Laplace approximation and the less accurate but more efficient BIC/MDL approximation. We …
Proposes efficient Gaussian approximations for non-Gaussian likelihoods.
problem Computational challenges in learning and inference with non-Gaussian likelihoods.
method Variational inference and moment matching in transformed bases.
result Good approximation quality for binary and multiclass classification.
Gradient descent trains shallow neural networks to approximate functions in 1D.
problem Approximating functions in 1D with shallow neural networks trained by gradient descent.
method Gradient descent optimization of non-convex weight space for finite width networks in 1D.
result Gradient descent can approximate functions in 1D with a minimal number of weights, balancing practical performance and theoretical capabilities.
Method uses DNNs to approximate functions with specific asymptotic behavior.
problem Approximating functions with given asymptotic behavior.
method Specifically constructed terms combined with unconstrained DNN.
result Enforcing asymptotic behavior leads to better approximation and faster convergence.
We build on the dynamical systems approach to deep learning, where deep residual networks are idealized as continuous-time dynamical systems, from the approximation perspective. In particular, we establish general sufficient conditions for universal approximation using continuous-time deep residual networks, which can …
There are many methods developed to approximate a cloud of vectors embedded in high-dimensional space by simpler objects: starting from principal points and linear manifolds to self-organizing maps, neural gas, elastic maps, various types of principal curves and principal trees, and so on. For each type of approximator…