Study Whittle index learning algorithms for restless bandits with constant stepsizes.
problem Optimizing decisions in restless multi-armed bandits with constant stepsizes.
method Developed Q-learning algorithms with constant stepsizes for index learning in restless bandits, extending to DQN and function approximations.
result The algorithms learn the Whittle index effectively.
New model OPSS allows constant approximation for maximum coverage problem.
problem Optimizing coverage functions from samples is hard.
method Proposed OPSS model with structured samples.
result Achieved constant approximation for maximum coverage problem.
Let M be a geometrically finite pinched negatively curved Riemannian manifold with at least one cusp. Inspired by the theory of diophantine approximation of a real (or complex) number by rational ones, we develop a theory of approximation of geodesic lines starting from a given cusp by ones returning to it. We define a…
In this paper, we introduce the notion of liquid time-constant (LTC) recurrent neural networks (RNN)s, a subclass of continuous-time RNNs, with varying neuronal time-constant realized by their nonlinear synaptic transmission model. This feature is inspired by the communication principles in the nervous system of small …
Stochastic Gradient Descent with a constant learning rate (constant SGD) simulates a Markov chain with a stationary distribution. With this perspective, we derive several new results. (1) We show that constant SGD can be used as an approximate Bayesian posterior inference algorithm. Specifically, we show how to adjust …
Paper tackles fair low-rank approximation and column subset selection.
problem Minimize loss over sub-populations in machine learning.
method Developed algorithms for fair low-rank approximation and fair column subset selection.
result Achieved polynomial time algorithms for fair low-rank approximation.
This paper proposes a method to approximate non-Gaussian likelihoods in Gaussian Processes.
problem Approximating non-Gaussian likelihoods in Gaussian Processes.
method Proposes a piece-wise constant approximation for the inverse-link function.
result Yields a closed form solution for the SVGP lower bound.
Transformers struggle to approximate smooth functions, relying on piecewise constant approximations.
problem Understanding the expressivity of Transformers for function approximation.
method Theoretical analysis and experimental validation of Transformer's ability to approximate smooth functions.
result Transformers cannot reliably approximate smooth functions, relying on piecewise constant approximations.
It is well known that Sparse PCA (Sparse Principal Component Analysis) is NP-hard to solve exactly on worst-case instances. What is the complexity of solving Sparse PCA approximately? Our contributions include: 1) a simple and efficient algorithm that achieves an n−1/3-approximation; 2) NP-hardness of approximatio…
Efficiently learns Single-Index Models with constant factor approximation.
problem Learning Single-Index Models under L22 loss with unknown link functions. method An efficient algorithm using alignment sharpness for optimization.
result Achieves constant factor approximation to optimal loss for various distributions and link functions.
Offline k-means clustering was studied extensively, and algorithms with a constant approximation are available. However, online clustering is still uncharted. New factors come into play: the ordering of the dataset and whether the number of points, n, is known in advance or not. Their exact effects are unknown. In this…
Smooth approximations near singularities of constant mean curvature surfaces are found.
problem Finding smooth approximations for constant mean curvature surfaces near singular points.
method Proving the existence of sequences of smooth CMC hypersurfaces converging to a given one in a ball centered at the singularity.
result Smooth approximations exist in a ball centered at the singularity of a CMC hypersurface.
EBUCB framework achieves optimal regret with bounded approximate inference error.
problem Theoretical gap between practical performance and theoretical justification of Bayesian bandit algorithms with approximate inference.
method Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that accommodates bandit problems with approximate inference.
result EBUCB achieves optimal regret order O(logT) under certain conditions on inference error. Paper approximates Kähler metrics with cone singularities near a hypersurface.
problem Approximating Kähler metrics near a hypersurface with cone singularities.
method Using conical approximations and holomorphic vector fields, the paper shows how to approximate Kähler metrics of Poincaré type near a smooth hypersurface.
result Constant scalar curvature Kähler metrics can be approximated by those with cone singularities of small angle along a hypersurface.
Study on bias of constant-step stochastic approximation with Markovian noise.
problem Understanding the bias in stochastic approximation algorithms with Markovian noise.
method Infinitesimal generator comparisons to analyze bias, Lyapunov equation for time-averaged bias, Richardson-Romberg extrapolation for bias reduction.
result Bias of the algorithm is of order O(α) and time-averaged bias is αV+O(α2), where V is a constant. Paper examines constant stepsize in LSA for Markovian data inference.
problem Improving statistical inference with constant stepsize in LSA for Markovian data.
method Established CLT, used averaged LSA iterates, applied Richardson-Romberg extrapolation.
result Constant stepsize leads to better CI coverage, especially with limited data.
We study the effects of approximate inference on the performance of Thompson sampling in the k-armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice. We show that even small constant inference error …
The paper proves barriers to approximating functions with small weights and depth in neural networks.
problem Proving barriers to approximating functions with constant depth neural networks.
method Reduction to open problems and natural-proof barriers in circuit complexity, and a new approach to polynomially-bounded functions.
result There are fundamental barriers to proving results beyond depth 4 for constant-depth neural networks.
Scalable method bounds Lipschitz constant of generative models.
problem Bounding the Lipschitz constant of generative models.
method Layerwise convex approximations using zonotopes.
result Efficient and tight bounds on generative models.
This study presents new analytic approximations of the stochastic-alpha-beta-rho (SABR) model. Unlike existing studies that focus on the equivalent Black-Scholes (BS) volatility, we instead derive the equivalent constant-elasticity-of-variance (CEV) volatility. Our approach effectively reduces the approximation error i…
Study on maximizing submodular functions with limited updates, achieving tight bounds and poly-time algorithms.
problem Online submodular maximization with constant recourse.
method Information-theoretic bounds and poly-time randomized algorithms.
result Achieved tight bounds of 2/3 and 3/4 for general and coverage functions, respectively, with a 0.51 approximation.
The paper analyzes the performance of constant step-size stochastic approximation algorithms.
problem Approximating solutions to root finding problems in optimization and machine learning.
method Examines stochastic approximation algorithms with constant step-size, proving convergence and analyzing the limiting behavior of averaged estimates.
result The Polyak-Ruppert-style averaged estimates converge to the true solution with optimal covariance, providing insights for practitioners.
We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max∣A∣=kmini∈{1,…,m}fi(A). While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objec…
Existing depth separation results for constant-depth networks essentially show that certain radial functions in Rd, which can be easily approximated with depth 3 networks, cannot be approximated by depth 2 networks, even up to constant accuracy, unless their size is exponential in d. However, the func…
New algorithm for clustering data streams with no substitutions.
problem Clustering sequential data with no point substitution.
method Careful risk estimation, linear bin division, multiscale center selection.
result First constant approximation algorithm for random-order k-median clustering.
This paper optimizes ReLU networks for approximating Hölder continuous functions.
problem Optimizing the approximation rate of ReLU networks in terms of width and depth.
method Constructive proof of ReLU networks' approximation power with specific width and depth constraints.
result Optimal approximation rate of ReLU networks with width and depth constraints.
Derives TAP approximation for Bayesian linear regression.
problem Log-normalizing constant of posterior distribution in high-dimensional linear regression.
method Variational representation and Thouless-Anderson-Palmer approximation.
result Proves TAP approximation for spherical prior in proportional asymptotic regime.
Polynomial-time RL algorithm for constant actions under linear Bellman completeness.
problem Efficient online reinforcement learning with few actions.
method Polynomial-time algorithm based on linear function approximation.
result First computationally efficient algorithm for RL with constant actions under linear Bellman completeness.
We study the problem of option replication under constant proportional transaction costs in models where stochastic volatility and jumps are combined to capture the market's important features. Assuming some mild condition on the jump size distribution we show that transaction costs can be approximately compensated by …
Classifies worst approximable rational numbers using hyperbolic geometry.
problem Classifying worst approximable rational numbers.
method Geometric approach using hyperbolic geometry.
result Clarifies distinction between two types of worst approximable rationals.
Proves depth 2 neural networks can't approximate certain functions as well as depth 3 networks.
problem Approximating functions with depth 2 networks in high dimensions.
method Lower bound proof using worst-to-average-case random self-reducibility.
result Proves depth 2 networks can't approximate certain functions as well as depth 3 networks, resolving an open problem.
Improved sketching for logistic and ℓ1 regression with near-linear dimensions.
problem Efficiently approximate ℓ1 and logistic regression problems. method New sketching techniques achieving near-linear dimensions for both problems.
result Achieved near-linear sketching dimensions for ℓ1 and logistic regression. Score-based methods fail with isolated components and incorrect mixing proportions.
problem Score-based methods struggle with distributions having isolated components and incorrect mixing proportions.
method Score-based methods, including score matching, are used but fail in the presence of isolated components and incorrect mixing proportions.
result Score-based methods cannot discover isolated components or identify correct mixing proportions.
Study on bias and extrapolation in LSA with Markovian data, showing bias reduction with Richardson-Romberg extrapolation.
problem Bias in LSA with constant stepsizes and Markovian data.
method Viewing LSA as a Markov chain, proving convergence and bias expansion, and applying Richardson-Romberg extrapolation.
result Bias is proportional to the stepsize up to higher order terms, and Richardson-Romberg extrapolation reduces the bias.
We propose a general algorithm for approximating nonstandard Bayesian posterior distributions. The algorithm minimizes the Kullback-Leibler divergence of an approximating distribution to the intractable posterior distribution. Our method can be used to approximate any posterior distribution, provided that it is given i…
Paper improves TD(0) convergence rate with LFA, i.i.d. samples, and averaging.
problem Improving convergence rate of TD(0) with linear function approximation.
method Polyak-Juditsky averaging, i.i.d. samples, strong mixing assumption.
result Established a new convergence rate for Mean-Square Error (MSE) of approximated function.
This article finds constant scalar curvature Kahler metrics on certain compact complex surfaces. The surfaces considered are those admitting a holomorphic submersion to a curve, with fibres of genus at least 2. The proof is via an adiabatic limit. An approximate solution is constructed out of the hyperbolic metrics on …
Squared families are a new model class derived from linear transformations, offering convenient properties and universal approximation.
problem Developing a new class of probability models that are easier to handle and have useful properties.
method Introducing squared families as families of probability densities obtained by squaring a linear transformation of a statistic, and showing their properties and applications.
result Squared families have convenient properties and can approximate target densities well.
The Clifford tori in the 3-sphere are a one-parameter family of flat, two-dimensional, constant mean curvature (CMC) surfaces. This paper demonstrates that new, topologically non-trivial CMC surfaces resembling a pair of neighbouring Clifford tori connected at a sub-lattice consisting of at least two points by small ca…
ELF simplifies normalizing flows, making them more efficient and universal.
problem Computational inefficiency of normalizing flows.
method ELF introduces a simple, one-layer network with closed-form Lipschitz constants, combining the ease of residual flows with the performance of autoregressive flows.
result ELF is a provably universal density approximator, more efficient computationally and parameter-wise.
Researchers approximate spectral targets on manifolds with constant negative curvature.
problem Prescribing an arbitrary finite portion of the Laplace-Beltrami spectrum on manifolds of constant negative curvature.
method Constructing macroscopically heterogeneous hyperbolic covering manifolds in d≥3 and using discrete spectral limit theorems in d=2. result Any finite strictly increasing target list can be approximated to arbitrary precision by a closed manifold of constant negative curvature.
We consider d-dimensional linear stochastic approximation algorithms (LSAs) with a constant step-size and the so called Polyak-Ruppert (PR) averaging of iterates. LSAs are widely applied in machine learning and reinforcement learning (RL), where the aim is to compute an appropriate θ∗∈Rd (that is a…
Optimal schedules improve transport map approximation and learning.
problem Improving the approximation and learning of transport maps.
method Optimal scheduling of transport maps to minimize spatial Lipschitz constant.
result The optimal schedule can be computed in closed form and results in a significantly smaller Lipschitz constant.
Improved particle approximation for mean-field neural networks.
problem Particle approximation error for mean-field neural networks.
method Improved particle approximation error by leveraging the problem structure in risk minimization.
result Established an LSI-constant-free particle approximation error concerning the objective gap.
We study approximations of the partition function of dense graphical models. Partition functions of graphical models play a fundamental role is statistical physics, in statistics and in machine learning. Two of the main methods for approximating the partition function are Markov Chain Monte Carlo and Variational Method…
Smooth activations enable optimal error rates in neural networks for Sobolev function classes.
problem Achieving optimal approximation and estimation error rates for neural networks in Sobolev function classes.
method Study of neural networks with smooth activations, proving optimal rates via approximation and statistical properties.
result Constant-depth networks with smooth activations achieve optimal rates of approximation and estimation, demonstrating smoothness adaptivity.
Approximates cycles in planar and bounded-genus graphs.
problem Finding many disjoint cycles in planar and bounded-genus graphs.
method Constant-factor approximation algorithms for vertex-disjoint and edge-disjoint cycles.
result First algorithms for vertex-disjoint paths in fully planar and bounded-genus instances.
We present an approximate inference method, based on a synergistic combination of Rényi α-divergence variational inference (RDVI) and rejection sampling (RS). RDVI is based on minimization of Rényi α-divergence Dα(p∣∣q) between the true distribution p(x) and a variational approximation q(x); RS draws samples…