Optimal oracle inequalities for solving projected fixed-point equations

• URL: http://arxiv.org/abs/2012.05299v1
• Date: Wed, 9 Dec 2020 20:19:32 GMT
• Title: Optimal oracle inequalities for solving projected fixed-point equations
• Authors: Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright
• Abstract summary: We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
• Score: 53.31620399640334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear fixed point equations in Hilbert spaces arise in a variety of settings, including reinforcement learning, and computational methods for solving differential and integral equations. We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. First, we prove an instance-dependent upper bound on the mean-squared error for a linear stochastic approximation scheme that exploits Polyak--Ruppert averaging. This bound consists of two terms: an approximation error term with an instance-dependent approximation factor, and a statistical error term that captures the instance-specific complexity of the noise when projected onto the low-dimensional subspace. Using information theoretic methods, we also establish lower bounds showing that both of these terms cannot be improved, again in an instance-dependent sense. A concrete consequence of our characterization is that the optimal approximation factor in this problem can be much larger than a universal constant. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation, establishing their optimality.

Related papers

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• On Bellman equations for continuous-time policy evaluation I: discretization and approximation [3.704688279256839]
  We study the problem of computing the value function from a discretely-observed trajectory of a continuous-time diffusion process. We develop a new class of algorithms based on easily implementable numerical schemes that are compatible with discrete-time reinforcement learning.
  arXiv  Detail & Related papers  (2024-07-08T14:05:03Z)
• A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization [0.0]
  We consider optimization problems involving an expected value of a nonlinear function of a base random vector and a conditional expectation of another function depending on the base random vector. We propose a specialized singlescale method for non constrained learning problems with a smooth outer function and a different conditional inner function.
  arXiv  Detail & Related papers  (2024-05-17T14:35:50Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Compressive Fourier collocation methods for high-dimensional diffusion equations with periodic boundary conditions [7.80387197350208]
  High-dimensional Partial Differential Equations (PDEs) are a popular mathematical modelling tool, with applications ranging from finance to computational chemistry. Standard numerical techniques for solving these PDEs are typically affected by the curse of dimensionality. Inspired by recent progress in sparse function approximation in high dimensions, we propose a new method called compressive Fourier collocation.
  arXiv  Detail & Related papers  (2022-06-02T19:11:27Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  Gaussian processes scale prohibitively with the size of the dataset. Many approximation methods have been developed, which inevitably introduce approximation error. This additional source of uncertainty, due to limited computation, is entirely ignored when using the approximate posterior. We develop a new class of methods that provides consistent estimation of the combined uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
  arXiv  Detail & Related papers  (2022-05-30T22:16:25Z)
• On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples [1.0650780147044159]
  Sparse approximation has become indispensable for approxing smooth, high-dimensional functions from limited samples. This paper introduces algorithms and theoretical guarantees that assert exponential or algebraic rates of convergence, along with robustness to sampling, algorithmic and physical discretization errors.
  arXiv  Detail & Related papers  (2022-03-25T20:56:07Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  Existing algorithms fail to match at least one of these lower bounds. We develop an accelerated, variance-reduced fast temporal difference algorithm that simultaneously matches both lower bounds and attains a strong notion of instance-optimality.
  arXiv  Detail & Related papers  (2021-12-24T17:21:04Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.