Efficient local planning with linear approximations for agents with limited simulator access.
problem Planning with limited simulator access in reinforcement learning.
method Confident Monte Carlo Least Square Policy Iteration (Confident MC-LSPI) and Politex (Confident MC-Politex) algorithms.
result The algorithms can learn the optimal policy with local simulator access, even for linear Q-functions.
This paper improves Bayesian neural nets by using local linearization.
problem Underfitting in Bayesian neural networks.
method Local linearization of Bayesian neural networks to create a generalized linear model (GLM) for predictions.
result The GLM predictive resolves common underfitting problems of the Laplace approximation.
We investigate finite-time decoupled convergence in nonlinear two-time-scale stochastic approximation.
problem Achieving decoupled convergence in nonlinear two-time-scale stochastic approximation.
method Nested local linearity assumption, suitable step size selection, convergence analysis of matrix cross term, fourth-order moment convergence rates.
result Finite-time decoupled convergence rates can be achieved in nonlinear two-time-scale stochastic approximation with proper step size selection.
This paper introduces a new method for semi-supervised learning on high dimensional nonlinear manifolds, which includes a phase of unsupervised basis learning and a phase of supervised function learning. The learned bases provide a set of anchor points to form a local coordinate system, such that each data point x on…
Folded concave penalization methods have been shown to enjoy the strong oracle property for high-dimensional sparse estimation. However, a folded concave penalization problem usually has multiple local solutions and the oracle property is established only for one of the unknown local solutions. A challenging fundamenta…
Recently, Petrik et al. demonstrated that L1Regularized Approximate Linear Programming (RALP) could produce value functions and policies which compared favorably to established linear value function approximation techniques like LSPI. RALP's success primarily stems from the ability to solve the feature selection and va…
Existing works on "black-box" model interpretation use local-linear approximations to explain the predictions made for each data instance in terms of the importance assigned to the different features for arriving at the prediction. These works provide instancewise explanations and thus give a local view of the model. T…
Paper develops Gaussian approximations and bootstrap for federated LSA with trade-off bounds.
problem Analyzing convergence rates and trade-offs in federated linear stochastic approximation.
method Established Berry-Esseen-type bounds for federated LSA, developed multiplier bootstrap for inference.
result First federated Gaussian approximations with explicit trade-off terms and non-asymptotic validity guarantees.
Two log-linear approximations speed up optimal transport for deep learning applications.
problem Computing optimal transport in high dimensions is computationally expensive.
method Locality-sensitive hashing (LSH) and Nyström approximation with LSH-based sparse corrections.
result Log-linear time algorithms for entropy-regularized OT perform well in high-dimensional spaces.
We analyze the (unconditional) distribution of a linear predictor that is constructed after a data-driven model selection step in a linear regression model. First, we derive the exact finite-sample cumulative distribution function (cdf) of the linear predictor, and a simple approximation to this (complicated) cdf. We t…
Study p-parabolicity on graphs using various energy functionals.
problem Characterize p-parabolicity on infinite locally summable graphs. method Analyze p-energy functionals and use approximation by finite graphs. result Prove various characterizations of p-parabolicity. Improved API to achieve optimal error bound and query complexity in local planning.
problem Efficient local planning in discounted MDPs with linear approximation.
method Confident Approximate Policy Iteration (CAPI) for stationary policies, applying to local access simulators.
result Achieves optimal accuracy and query complexity bounds, improving over API.
Here are considered some categorical aspects of "Differential calculus" archetype of local approximation of arbitrary morphisms by "linear" ones.
In this paper, we propose and study random maxout features, which are constructed by first projecting the input data onto sets of randomly generated vectors with Gaussian elements, and then outputing the maximum projection value for each set. We show that the resulting random feature map, when used in conjunction with …
The paper introduces a method for dimension reduction using sub-Riemannian geometry.
problem Dimension reduction for manifold learning and surface reconstruction.
method Combining local linear approximations of a point cloud to obtain lower dimensional bundles.
result Sub-Riemannian geodesics can successfully be applied to problems like constructing an approximating submanifold and computing distances.
Paper proposes a privacy-preserving RL algorithm for linear MDPs with theoretical guarantees.
problem Protecting users' private data in personalized services using RL.
method Local differential privacy (LDP) for RL with linear function approximation.
result Achieves a regret bound of $O(d^{5/4}H^{7/4}T^{3/4}\left(\log(1/δ)
ight)^{1/4}\sqrt{1/\varepsilon})$ for linear mixture MDPs.
FedSARSA converges with heterogeneous agents, achieving linear speed-up.
problem Convergence analysis of Federated SARSA with heterogeneous agents.
method Linear function approximation, local training, multi-step error expansion.
result FedSARSA achieves linear speed-up with respect to the number of agents.
The Bass model is calibrated to vanilla options using a fixed-point equation.
problem Calibration of the Bass local volatility model to vanilla options.
method Solving a fixed-point equation to achieve calibration.
result Existence and uniqueness of the solution to the fixed-point equation, and linear convergence of the fixed-point iteration scheme.
In statistical dimensionality reduction, it is common to rely on the assumption that high dimensional data tend to concentrate near a lower dimensional manifold. There is a rich literature on approximating the unknown manifold, and on exploiting such approximations in clustering, data compression, and prediction. Most …
A new method for creating simpler models from complex ones.
problem Creating accurate approximations of complex models at reduced costs.
method Sequential adaptive surrogate modeling based on locally spectral expansions.
result Stochastic spectral embedding (SSE) shows good approximation capabilities and scalability.
Study shows TAP free energy minimization provides better posterior inference in high-dimensional linear models.
problem Deviation from true posterior mean and underestimation of posterior uncertainty in variational inference.
method Minimization of TAP free energy in a high-dimensional asymptotic framework, showing geometric and statistical properties.
result Local minimizer of TAP free energy provides consistent estimate of posterior marginals and correctly calibrated posterior inference.
Let G be a compact Lie group. (Compact) topological G-manifolds have the G-homotopy type of (finite-dimensional) countable G-CW complexes (2.5). This partly generalizes Elfving's theorem for locally linear G-manifolds [Elf96], wherein the Lie group G is linear (such as compact).
Neural networks can approximate complex stochastic equations well.
problem Approximating general stochastic differential equations.
method Identified neural network classes approximating continuous functions.
result Neural stochastic differential equations can approximate general stochastic differential equations arbitrarily well.
Quasispheres can be approximated by smooth spheres.
problem Characterizing quasispheres using geometric conditions.
method Proving every quasisphere is a limit of smooth spheres and providing necessary and sufficient conditions for uniform quasispheres.
result Every quasisphere can be approximated by uniform quasispheres that satisfy specific geometric conditions.
Neural Local Wasserstein Regression models distribution-on-distribution regression with flexible, localized transport maps.
problem Estimating distribution-on-distribution regression with global optimal transport maps or linearization limitations.
method Proposes Neural Local Wasserstein Regression, a flexible nonparametric framework using locally defined transport maps in Wasserstein space.
result Demonstrates effective capture of nonlinear and high-dimensional distributional relationships.
Let G be a matrix group. Topological G-manifolds with Palais-proper action have the G-homotopy type of countable G-CW complexes (3.2). This generalizes E Elfving's dissertation theorem for locally linear G-manifolds (1996). Also we improve the Bredon--Floyd theorem from compact groups G (1960).
Paper addresses linear regression with partially mismatched data using local search with theoretical guarantees.
problem Linear regression with partially mismatched data.
method Optimization formulation and greedy local search algorithm with theoretical guarantees.
result Local search algorithm converges to nearly-optimal solution at a linear rate under certain conditions.
We explain how the Transference Principles from Diophantine approximation can be interpreted in terms of geometry of the locally symmetric spaces Tn=SO(n)\SL(n,R)/SL(n,Z) with n>1, and how, via this dictionary, they become transparent geometric remarks and can be easily proved. Indeed, a finite family …
New method improves Gaussian kernel approximations for high-frequency data.
problem Limited scalability of kernel-based models to large data sets.
method Local random feature approximations using Maclaurin expansions and polynomial sketches.
result Significant improvement in kernel approximations and downstream performance for high-frequency data.
This paper deals with the exact calibration of semidiscretized stochastic local volatility (SLV) models to their underlying semidiscretized local volatility (LV) models. Under an SLV model, it is common to approximate the fair value of European-style options by semidiscretizing the backward Kolmogorov equation using fi…
We present an algorithm for approximating a function defined over a d-dimensional manifold utilizing only noisy function values at locations sampled from the manifold with noise. To produce the approximation we do not require any knowledge regarding the manifold other than its dimension d. We use the Manifold Movin…
We describe a local model for any Singular Riemannian Foliation in a neighbourhood of a closed saturated submanifold of a regular stratum. Moreover we construct a Lie groupoid which controls the transverse geometry of the linear approximation of the Singular Riemannian Foliation around these submanifolds. We also discu…
Survey of Locally Linear Embedding and its variants.
problem Representing high-dimensional data in a lower-dimensional space while preserving local structure.
method Explains various LLE and variant methods, including kernel LLE, inverse LLE, feature fusion, out-of-sample embedding, incremental LLE, landmark LLE, supervised LLE, robust LLE, fusion with other methods, and weighted LLE.
result Comprehensive overview of LLE and its variants.
New bounds show diffusion models converge nearly linearly in data dimension.
problem Improving convergence bounds for diffusion models.
method Refined discretization of reverse SDE using stochastic localization.
result Linear convergence in data dimension with logarithmic factors.
Improved bounds for function approximation in nonlinear sets.
problem Achieving high probability error with limited samples in nonlinear function approximation.
method Restricting model class to a neighbourhood of the best approximation and estimating sample complexity using tangent and normal spaces' complexities and curvature.
result Improved worst-case bounds for sample complexity in more general sets like tensor networks and neural networks.
Efficient clustering in high dimensions with Quick Shift and LSH.
problem Density-based clustering in high-dimensional data.
method Combines Quick Shift and LSH for efficient density estimation.
result Achieves almost linear time complexity for consistency.
We show LLMs can be locally linear, enabling better control of activations.
problem Suboptimal control of LLM activations during generation.
method Model LLM inference as a linear dynamical system, compute feedback controllers using Jacobians, and adapt classical control theory.
result Robust, fine-grained control of LLM activations across models and tasks.
Paper addresses ERM in LDP, reducing sample complexity for smooth and convex losses.
problem Achieving error α in ERM with non-interactive LDP, especially for high-dimensional data.
method Developed algorithms using Bernstein polynomial and polynomial approximation techniques.
result For smooth and convex losses, sample complexity is linear in dimensionality.
New GP model estimates piecewise continuous functions.
problem Piecewise continuous regression functions in scientific and engineering applications.
method Local Gaussian process model with partitioned local data and joint estimation of boundaries.
result Superior performance over conventional GP models in estimating piecewise regression functions.
SurvLIME-Inf simplifies explanation of survival models using a linear programming approach.
problem Explain complex survival models using simple linear programming.
method Uses L∞-norm for feature importance and explains black-box models. result SurvLIME-Inf outperforms SurvLIME in small training set scenarios.
Given a piecewise linear (PL) function p defined on an open subset of Rn, one may construct by elementary means a unique polyhedron with multiplicities $\D(p)$ in the cotangent bundle Rn×Rn∗ representing the graph of the differential of p. Restricting to dimension 2, we show that any smooth functi…
Various valuation adjustments, or XVAs, can be written in terms of non-linear PIDEs equivalent to FBSDEs. In this paper we develop a Fourier-based method for solving FBSDEs in order to efficiently and accurately price Bermudan derivatives, including options and swaptions, with XVA under the flexible dynamics of a local…
In this paper, we propose a communication- and computation-efficient algorithm to solve a convex consensus optimization problem defined over a decentralized network. A remarkable existing algorithm to solve this problem is the alternating direction method of multipliers (ADMM), in which at every iteration every node up…
Efficiently checks local robustness in neural networks using geometric projections.
problem Ensuring robustness of neural networks against adversarial inputs.
method Systematic search for decision boundaries in convex polyhedral regions using geometric projections.
result Shows geometric projections can efficiently check robustness in neural networks.
Latent force models are systems whereby there is a mechanistic model describing the dynamics of the system state, with some unknown forcing term that is approximated with a Gaussian process. If such dynamics are non-linear, it can be difficult to estimate the posterior state and forcing term jointly, particularly when …
SCAFFLSA reduces communication complexity for federated learning with heterogeneous clients.
problem Quantifying and reducing communication complexity in federated learning with heterogeneous clients.
method Proposes SCAFFLSA, a variant of FedLSA using control variates to correct for client drift.
result SCAFFLSA achieves logarithmic communication complexity for statistically heterogeneous agents, scaling with the inverse of the desired accuracy.
Let M be a smooth manifold and S a semi-spray defined on a sub-bundle C of the tangent bundle TM. In this work it is proved that the only non-trivial k-jet approximation to the exact geodesic deviation equation of S, linear on the deviation functions and invariant under an spec…
SyMPLER improves time series forecasting in nonstationary environments with explainable models.
problem Nonstationary time series forecasting with limited interpretability.
method Dynamic piecewise-linear approximations based on Statistical Learning Theory generalization bounds.
result SyMPLER achieves comparable performance to black-box and explainable models while maintaining interpretability.