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.
Study shows limits on deep and shallow neural networks for approximating compact sets.
problem Understanding the limitations of deep and shallow neural networks in approximating compact sets.
method Proved Carl's type inequalities for approximation error, using Lipschitz widths.
result Lower bounds on approximation error for neural network outputs.
New algorithms approximate Rashomon set for sparse models, aiding expert interaction.
problem Lack of interaction between models and domain experts in classical machine learning.
method Approximate Rashomon set of sparse, generalized additive models using ellipsoids.
result Efficiently approximated Rashomon set facilitates model selection and exploration.
The paper introduces a new concept of higher order approximate differentiability for sets.
problem Characterizing higher order rectifiable sets.
method Introducing the approximate differential of order k for subsets of Euclidean space.
result The approximate differential of order k is a Borel map whose domain is a Borel set.
Smooth approximations proved for triangulable sets.
problem Universal approximation of continuous maps to triangulable sets.
method New approximation techniques for weakly C r \mathscr{C}^r C r triangulable sets. result Triangulable sets are C r \mathscr{C}^r C r -approximation targets. Deep Sets approximates functions on sets with high-dimensional latent space.
problem Modeling functions of sets (permutation-invariant functions).
method Deep Sets, a method known to be a universal approximator for continuous set functions.
result Deep Sets' universal approximation property is only guaranteed with a sufficiently high-dimensional latent space.
We give upper and lower bounds on the volume of a tubular neighborhood of the nodal set of an eigenfunction of the Laplacian on a real analytic closed Riemannian manifold M. As an application we consider the question of approximating points on M by nodal sets, and explore analogy with approximation by rational numbers.
New algorithms reduce online learning to approximate optimization, improving performance and oracle complexity.
problem Reducing online learning to approximate optimization problems.
method Two algorithms that guarantee optimal regret with poly-logarithmically many calls to the approximation oracle.
result Significantly improved oracle complexity in the bandit setting while maintaining optimal regret.
Vecchia approximations provide the best accuracy-runtime trade-off for Gaussian process approximations.
problem High computational cost of Gaussian processes for large data sets.
method Systematic comparison of different Gaussian process approximations.
result Vecchia approximations consistently provide the best accuracy-runtime trade-off.
Paper tackles non-monotone DR-submodular maximization with approximation and regret guarantees.
problem Maximizing non-monotone DR-submodular functions over specific sets.
method Frank-Wolfe algorithm for general convex sets, Stochastic Gradient Ascent for down-closed convex sets.
result First approximation guarantees for both offline and online settings.
Simplified proof for approximations of set systems.
problem Approximations of set systems in various fields.
method Modular, self-contained proof using Chernoff's bound.
result Accessible proof for a wider audience.
Optimal smooth subspaces approximate large data sets efficiently.
problem Approximating large data sets with invariant subspaces.
method Smooth functions under lattice translations or crystallographic groups, with optimal selection of Paley-Wiener space.
result Optimal lattice selection enhances approximation efficiency.
Bayesian optimization for set inputs using approximate set kernels.
problem Permutation-invariant optimization over sets with black-box functions.
method Developed a Bayesian optimization method with set kernel, efficient approximate set kernel, and constrained acquisition function.
result Our method outperforms other methods in numerical experiments.
Greedy algorithm approximates costs in interactive learning and covering problems.
problem Interactive learning and covering with response-dependent costs.
method Proposes a greedy algorithm and bounds its approximation factor.
result Greedy algorithm is near-optimal among all greedy algorithms in both settings.
Investigates the impact of finite VC dimension on neural network approximation and learning.
problem The influence of VC dimension on neural network approximation and learning from samples.
method Analysis of high-dimensional geometry and statistical learning theory, focusing on VC dimension.
result Finite VC dimension is beneficial for uniform convergence of empirical errors but not for approximation of functions from a probability distribution.
We propose a strategy for approximating Pareto optimal sets based on the global analysis framework proposed by Smale (Dynamical systems, New York, 1973, pp. 531-544). The method highlights and exploits the underlying manifold structure of the Pareto sets, approximating Pareto optima by means of simplicial complexes. Th…
We investigate the approximate j-dimensionality of the singularity sets of minimal surfaces prescribed by Simon. This leads to the clasification of 8 variations of approximately j-dimensional surfacs in terms of dimension and locally finite Hausdorff measure. We show that the singularity sets must either be well behave…
DQNs can approximate optimal Q-functions with high accuracy on compact sets.
problem Approximating optimal Q-functions in continuous-time Markov Decision Processes.
method Stochastic control, FBSDEs, residual network approximation theorems, large deviation bounds, viscosity solutions.
result DQNs can approximate optimal Q-functions on compact sets with arbitrary accuracy and high probability.
Smooth approximation of integral cycles mod 2 in Riemannian manifolds.
problem Approximating mod 2 integral cycles by smooth submanifolds.
method Approximation of mod 2 integral cycles by smooth submanifolds with controlled singularities.
result Every mod 2 integral cycle can be approximated by a smooth submanifold with a controlled singular set.
Paper improves confidence set construction for SGD using multiplier bootstrap.
problem Constructing accurate confidence sets for SGD.
method Multiplier bootstrap procedure for non-asymptotic validity.
result Derives approximation rates up to 1 / n 1/\sqrt{n} 1/ n for convex distance. Improved set prediction model using multiset-equivariant operations and approximate implicit differentiation.
problem Existing set prediction models struggle with multisets and cannot represent certain functions.
method Introduced multiset-equivariance, improved DSPN with approximate implicit differentiation, and applied to CLEVR object property prediction.
result Significantly improved object property prediction on CLEVR dataset.
Algorithm learns a better sketch matrix for low-rank approximations.
problem Efficiently compute low-rank approximations of large matrices.
method Uses a learned sketch matrix instead of random matrix for optimization.
result Learned sketch matrix reduces approximation loss significantly compared to random matrix.
RELM uses rough set theory to improve ELM's classification accuracy for high-dimensional data.
problem Improving classification accuracy for high-dimensional data.
method RELM uses rough set theory to divide data into upper and lower approximation sets, and applies attribute reduction to enhance performance.
result RELM achieves better accuracy and repeatability compared to comparison algorithms.
Paper tackles online DR-submodular maximization with various convex sets.
problem Maximizing DR-submodular functions online over different convex sets.
method Develops online algorithms with approximation guarantees for various convex sets.
result Achieves 1 / e 1/e 1/ e -approximation ratio with O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) regret for down-closed sets. New iterative methods improve Vecchia-Laplace approximations for large data sets.
problem Inaccurate and slow Vecchia-Laplace approximations for large data sets.
method Iterative methods to improve Vecchia-Laplace approximations, including preconditioners and novel methods for predictive variances.
result Order of magnitude speed-up and threefold increase in prediction accuracy compared to state-of-the-art methods.
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.
This study improves understanding of singular points in approximate harmonic maps.
problem Understanding singular points in approximate harmonic maps.
method Extending results from previous work, proving k-rectifiability of singular strata, and simplifying arguments.
result Singular strata of approximate harmonic maps are k-rectifiable, with quantitative bounds on strata.
New findings on how convolutional architectures approximate time series data.
problem Understanding the approximation properties of convolutional architectures in time series modeling.
method Mathematical analysis of convolutional architectures applied to time series modeling.
result A new definition of spectrum-based regularity for measuring temporal relationships under convolutional approximation.
Paper improves confidence intervals for LSA with multiplier bootstrap.
problem Improving confidence intervals for parameter estimation in LSA.
method Berry-Esseen bound for multivariate normal approximation and multiplier bootstrap.
result Valid confidence intervals for parameter estimation in LSA.
An efficient algorithm for k-median clustering in a sequential setting without substitutions.
problem Clustering a sequence of examples without being able to substitute centers later.
method An efficient algorithm with a multiplicative approximation factor of twice the offline algorithm's factor, and an optimal offline algorithm.
result The efficient algorithm achieves a good approximation of the optimal offline solution.
New bound on neural nets complexity for approximating functions.
problem Approximating continuous functions with shallow neural networks.
method Inspired by Stone-Weierstrass theorem, constructive proof.
result General upper bound on neuron count for accuracy.
This paper develops a method to approximate the whole Pareto set for expensive multi-objective optimization.
problem Finding an approximate Pareto front with limited expensive evaluations.
method A novel learning-based method to approximate the whole Pareto set for multi-objective Bayesian optimization (MOBO).
result The method approximates the whole Pareto set, not just a finite set, for MOBO.
Expectation propagation (EP) is a deterministic approximation algorithm that is often used to perform approximate Bayesian parameter learning. EP approximates the full intractable posterior distribution through a set of local approximations that are iteratively refined for each datapoint. EP can offer analytic and comp…
Non-uniform landmark sampling improves KCCA approximation accuracy.
problem Improving the Nyström approximation for large-scale KCCA.
method Proposes non-uniform sampling based on statistical leverage scores.
result Non-uniform sampling leads to better approximation accuracy.
Study on zero sets of sections of pseudo-effective line bundles on Kähler manifolds.
problem Distribution of common zero sets of sections of pseudo-effective line bundles.
method Analyzing the wedge product of curvature currents and approximating them by analytic cycles.
result Sufficient conditions for approximating wedge products of curvature currents by analytic cycles.
Paper presents efficient RL algorithm for linear dynamics without simulator assumptions.
problem Designing efficient RL algorithms with function approximation for linear settings.
method Optimistic modification of Least-Squares Value Iteration (LSVI).
result Achieves i l d e O ( d 3 H 3 T ) ilde{\mathcal{O}}(\sqrt{d^3H^3T}) i l d e O ( d 3 H 3 T ) regret, independent of states and actions. A new method approximates Laplacian eigenvectors for RL efficiently.
problem Efficiently learning state representations in RL.
method General and scalable approach to approximating Laplacian eigenvectors.
result Empirically shows improved performance in RL tasks.
Efficient algorithms for online learning with changing action sets, achieving no-approximate-regret guarantees.
problem Online learning with sleeping experts/bandits, where only a subset of actions are available each time.
method Developed computationally efficient algorithms providing no-approximate-regret guarantees for the general problem and better approximation ratios for special cases.
result Achieved no-approximate-regret guarantees for the general sleeping expert/bandit problems and better approximation ratios for specific cases.
New method for scalable set encoding with unbiased gradient approximation.
problem Limited expressive power and large set training issues in set functions.
method Universally MBC (UMBC) class of set functions and efficient MBC training algorithm.
result Unbiased approximation of full set gradient with constant memory overhead.
This work analyzes nonexpansive stochastic approximations with Markovian noise, proving convergence in reinforcement learning.
problem Applying stochastic approximation to reinforcement learning settings with nonexpansive operators.
method Investigates nonexpansive stochastic approximations with Markovian noise, providing asymptotic and finite sample analysis.
result First-time proof of convergence for classical tabular average reward temporal difference learning.
New ABC method improves Bézier simplex fitting for noisy data.
problem Overfitting in Bézier simplex fitting when sample points are not on the Pareto set.
method Extended Bézier simplex model to a probabilistic one and proposed a new learning algorithm based on approximate Bayesian computation (ABC) with Wasserstein distance.
result The new algorithm converges on a finite sample and outperforms deterministic methods on noisy instances.
Paper analyzes AVI scheme for noisy Bellman approximations.
problem Analyzing stability and convergence of noisy value iteration.
method Uses neural networks to approximate Bellman operator, considers biased approximations and sampling errors.
result Verifiable conditions for stability and convergence of AVI.
Non-negative L 1 L_1 L 1 -approximating polynomials for Gaussian distributions are proven for certain classes of sets.
problem Existence of non-negative L 1 L_1 L 1 -approximating polynomials for Gaussian distributions. method Proving the existence of degree- k k k non-negative polynomials that approximate indicator functions of sets with Gaussian surface area in L 1 L_1 L 1 -norm. result Proves the existence of non-negative L 1 L_1 L 1 -approximating polynomials for certain classes of sets with Gaussian surface area. In Carnot groups, directional pliability allows curve extensions and approximations.
problem Existence of curve extensions and approximations in Carnot groups.
method Directional pliability in subsets of directions guarantees Whitney-type extensions and Lusin approximations.
result Every horizontal curve in the Engel group intersects a C 1 C^{1} C 1 curve in a set of positive measure. We compute an approximate Fréchet mean for sets of sparse graphs.
problem Characterizing the location of a set of graphs in a metric space.
method We use the pseudometric defined by the ℓ₂ norm of eigenvalues of adjacency matrices.
result We describe an algorithm to approximate the Fréchet mean of a set of graphs.
Private algorithms approximate matrices with private data.
problem Approximate matrices with same spectrum using private data.
method Differential privacy algorithms for unitary orbit optimization.
result Upper and lower bounds on approximation error.
This paper compares expected and distributional reinforcement learning methods.
problem Understanding why distributional reinforcement learning performs better than expected reinforcement learning.
method Analyzes differences in tabular, linear, and non-linear approximation settings.
result Distributional RL can hurt performance if it does not induce identical behavior.
This paper studies optimal approximation factors in misspecified off-policy RL, identifying key factors under various settings.
problem Understanding optimal approximation factors in misspecified off-policy value function estimation.
method Examined various settings including weighted L 2 L_2 L 2 -norm, L ∞ L_\infty L ∞ norm, state aliasing, and state coverage. result Established optimal asymptotic approximation factors for different norms and identified two instance-dependent factors for L 2 ( μ ) L_2(μ) L 2 ( μ ) norm.