We introduce Bayesian least-squares policy iteration (BLSPI), an off-policy, model-free, policy iteration algorithm that uses the Bayesian least-squares temporal-difference (BLSTD) learning algorithm to evaluate policies. An online variant of BLSPI has been also proposed, called randomised BLSPI (RBLSPI), that improves…
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,742 papers · 148 categories
Trend · papers per month
48 results for “least square value iteration”
Paper improves worst-case regret bounds for RLSVI in reinforcement learning.
problem Minimizing regret in reinforcement learning with randomized value functions.
method Introduces a clipping variant of Thompson Sampling for RLSVI.
result Achieves a worst-case regret bound.
Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squaresmath.OC
We study randomized sketching methods for approximately solving least-squares problem with a general convex constraint. The quality of a least-squares approximation can be assessed in different ways: either in terms of the value of the quadratic objective function (cost approximation), or in terms of some distance meas…
We propose randomized least-squares value iteration (RLSVI) -- a new reinforcement learning algorithm designed to explore and generalize efficiently via linearly parameterized value functions. We explain why versions of least-squares value iteration that use Boltzmann or epsilon-greedy exploration can be highly ineffic…
We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL). When the state space is large or continuous, traditional tabular approaches are unfeasible and some form of function approximation is mandatory. In this paper, we introduce an optimistically-initialized variant of the popula…
New algorithm reduces bias and variance in weighted least-squares solutions.
problem Inconsistent linear least-squares problems with rapidly decaying singular values.
method Regularized block Kaczmarz (ReBlocK) algorithm.
result ReBlocK outperforms RBK and minibatch SGD for inconsistent problems.
Sublinear LSVI via LSH reduces runtime to sublinear in actions.
problem Efficiently estimating value functions in reinforcement learning with sublinear runtime.
method Formulated as approximate maximum inner product search, used LSH to solve with sublinear time complexity.
result Sublinear runtime while maintaining LSVI's regret.
New method for optimistic planning in MDPs using regularization.
problem Optimistic planning in infinite-horizon discounted MDPs.
method Regularized dynamic programming for approximate value iteration.
result Achieves near-optimal statistical guarantees in learning policies.
Papers learn from data to make decisions without interacting, improving on previous methods.
problem Achieving optimal decision-making from offline data with non-linear function approximation.
method Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI) with three innovative components.
result Achieves minimax optimal instance-dependent regret for non-linear function approximation.
Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Modelsstat.ML
A new method for estimating large-scale linear models with improved precision.
problem Estimating large-scale linear statistical models efficiently.
method Sequential Least-Squares Estimators with Fast Randomized Sketching (SLSE-FRS), integrating Sketch-and-Solve and Iterative-Sketching methods.
result SLSE-FRS produces high-precision estimators, outperforming state-of-the-art methods.
Quantization can be used to form new vectors/matrices with shared values close to the original. In recent years, the popularity of scalar quantization for value-sharing applications has been soaring as it has been found huge utilities in reducing the complexity of neural networks. Existing clustering-based quantization…
New algorithm improves online binary classification with constant time complexity.
problem Online binary classification with rebalancing.
method Non-iteratively reweighted recursive least-squares.
result Exacts converges to batch formulation and outperforms existing algorithms.
Support vector machines (SVMs) are an important tool in modern data analysis. Traditionally, support vector machines have been fitted via quadratic programming, either using purpose-built or off-the-shelf algorithms. We present an alternative approach to SVM fitting via the majorization--minimization (MM) paradigm. Alg…
Paper proposes a pre-conditioning technique to speed up gradient-descent convergence in distributed linear least-squares problems.
problem Expediting convergence of gradient-descent method for ill-conditioned distributed linear least-squares problems.
method Iterative pre-conditioning technique to improve convergence rate of gradient-descent method.
result Pre-conditioned gradient-descent achieves superlinear convergence for unique solutions and improved linear convergence otherwise.
The paper tackles robust reinforcement learning with performance guarantees.
problem Finding a robust policy for RMDP with state space uncertainties.
method Proposes RLSPI algorithm for learning optimal robust policy with performance bounds.
result Demonstrates the performance of RLSPI on standard benchmark problems.
We prove the statistical consistency of kernel Partial Least Squares Regression applied to a bounded regression learning problem on a reproducing kernel Hilbert space. Partial Least Squares stands out of well-known classical approaches as e.g. Ridge Regression or Principal Components Regression, as it is not defined as…
Developed an efficient iterative algorithm for SVI model.
problem SVI model's optimizer's strong dependence on input starting point.
method Fixed-point and least-square optimizer.
result Convergence results for fixed-point iterative algorithm in certain situations.
A fast sketching algorithm solves regularized least squares problems efficiently.
problem Solving large-scale optimization problems with convex or nonconvex regularization.
method Sketching for Regularized Optimization (SRO) algorithm that generates a sketch of the original data matrix and solves the sketched problem.
result General theoretical results for the approximation error between the original and sketched problems, including minimax rates for sparse signal estimation.
Least squares kernel based methods have been widely used in regression problems due to the simple implementation and good generalization performance. Among them, least squares support vector regression (LS-SVR) and extreme learning machine (ELM) are popular techniques. However, the noise sensitivity is a major bottlene…
This paper presents four different ways of looking at the well-known Least Squares Temporal Differences (LSTD) algorithm for computing the value function of a Markov Reward Process, each of them leading to different insights: the operator-theory approach via the Galerkin method, the statistical approach via instrumenta…
In this paper we investigate panel regression models with interactive fixed effects. We propose two new estimation methods that are based on minimizing convex objective functions. The first method minimizes the sum of squared residuals with a nuclear (trace) norm regularization. The second method minimizes the nuclear …
Continuous-time reinforcement learning: ellipticity enables model-free value function approximationcs.LG
New algorithm learns value and advantage functions for continuous-time Markov processes without structural assumptions.
problem Learning value and advantage functions for continuous-time Markov processes without structural assumptions.
method Proposes Sobolev-prox fitted -learning algorithm based on Hilbert-space positive definiteness and boundedness properties of Bellman operators.
result Identifies ellipticity as a key structural property enabling reinforcement learning for Markov diffusions.
We consider solving the -regularized least-squares (-LS) problem in the context of sparse recovery, for applications such as compressed sensing. The standard proximal gradient method, also known as iterative soft-thresholding when applied to this problem, has low computational cost per iteration but a r…
We describe stochastic Newton and stochastic quasi-Newton approaches to efficiently solve large linear least-squares problems where the very large data sets present a significant computational burden (e.g., the size may exceed computer memory or data are collected in real-time). In our proposed framework, stochasticity…
Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimizationcs.LG
New algorithm reduces sketching dimension to effective problem size.
problem Solving L2-regularized least-squares problems efficiently.
method Randomized algorithm using Gaussian and SRHT embeddings.
result Preserves convergence guarantees with reduced embedding dimension.
New robust MPCA method handles casewise and cellwise outliers in tensor data.
problem Outliers, especially casewise and cellwise, affect the performance of standard MPCA.
method Uses a single loss function to reduce the influence of both types of outliers and missing values.
result The new method improves robustness and performance in tensor data analysis.
Unified analysis of reweighted least-squares algorithms for linear models.
problem Recovering unknown signals from linear measurements using reweighted least squares.
method Unified asymptotic analysis of IRLS, lin-RFM, and alternating minimization algorithms.
result The algorithms can achieve favorable performance in a few iterations with appropriate reweighting.
Canonical Correlation Analysis (CCA) is a widely used statistical tool with both well established theory and favorable performance for a wide range of machine learning problems. However, computing CCA for huge datasets can be very slow since it involves implementing QR decomposition or singular value decomposition of h…
Consider Least Squares Monte Carlo (LSM) algorithm, which is proposed by Longstaff and Schwartz (2001) for pricing American style securities. This algorithm is based on the projection of the value of continuation onto a certain set of basis functions via the least squares problem. We analyze the stability of the algori…
We propose a stochastic approximation (SA) based method with randomization of samples for policy evaluation using the least squares temporal difference (LSTD) algorithm. Our proposed scheme is equivalent to running regular temporal difference learning with linear function approximation, albeit with samples picked unifo…
Principal component analysis (PCA) is often used to reduce the dimension of data by selecting a few orthonormal vectors that explain most of the variance structure of the data. L1 PCA uses the L1 norm to measure error, whereas the conventional PCA uses the L2 norm. For the L1 PCA problem minimizing the fitting error of…
Cross validation residuals are well known for the ordinary least squares model. Here leave-M-out cross validation is extended to generalised least squares. The relationship between cross validation residuals and Cook's distance is demonstrated, in terms of an approximation to the difference in the generalised residual …
This work provides a simplified proof of the statistical minimax optimality of (iterate averaged) stochastic gradient descent (SGD), for the special case of least squares. This result is obtained by analyzing SGD as a stochastic process and by sharply characterizing the stationary covariance matrix of this process. The…
Efficiently estimates rotations with corrupted data.
problem Rotation synchronization under high corruption and noise.
method Message passing algorithm with reweighted least squares.
result Superior performance over state-of-the-art methods.
Study on adversarial training dynamics in high dimensions using SGD.
problem Analyzing adversarial training of models in high-dimensional settings.
method Deriving deterministic equivalents for SGD iterates under Gaussian mixtures.
result No constant learning rate guarantees monotone descent in adversarial training.
In this paper we study the performance of the Projected Gradient Descent(PGD) algorithm for -constrained least squares problems that arise in the framework of Compressed Sensing. Relying on the Restricted Isometry Property, we provide convergence guarantees for this algorithm for the entire range of $0\leq p\…
New algorithm learns optimal policies without explicit rewards.
problem Learning optimal policies without explicit rewards.
method Developed a computationally tractable algorithm for reward-free navigation using linear value iteration.
result PAC guarantees on learning near optimal value functions and policies.
Reduced-rank method improves least-squares regression under output regularity.
problem Least-squares regression with infinite dimensional outputs.
method Reduced-rank method for solving least-squares problems with output regularity assumptions.
result Learning bounds and improved statistical performance compared to full-rank method.
SGD converges to optimal solution in perfect data fitting problem.
problem Noiseless least-squares with perfect data fitting.
method Last iterate of SGD with constant step-size.
result Convergence of SGD final iterate for non-strongly convex problem.
This paper analyzes multi-pass SGD for least squares, improving generalization bounds.
problem Improving generalization bounds for multi-pass SGD in the least squares problem.
method Develops an instance-dependent excess risk bound for least squares in the interpolation regime.
result SGD performs worse than GD instance-wise but saves computational time.
Policy evaluation or value function or Q-function approximation is a key procedure in reinforcement learning (RL). It is a necessary component of policy iteration and can be used for variance reduction in policy gradient methods. Therefore its quality has a significant impact on most RL algorithms. Motivated by manifol…
Minimax optimal convergence rates for classes of stochastic convex optimization problems are well characterized, where the majority of results utilize iterate averaged stochastic gradient descent (SGD) with polynomially decaying step sizes. In contrast, SGD's final iterate behavior has received much less attention desp…
We propose a version of least-mean-square (LMS) algorithm for sparse system identification. Our algorithm called online linearized Bregman iteration (OLBI) is derived from minimizing the cumulative prediction error squared along with an l1-l2 norm regularizer. By systematically treating the non-differentiable regulariz…
Improved neural network training with ADMM for hardware compatibility.
problem Training scalable and parallelizable neural networks.
method Alternating Direction Method of Multipliers (ADMM) combined with iterative least-square methods.
result Achieved significant accuracy improvements over SGD and Adam.
This work proves convergence of adaptive resampling for random Fourier features.
problem Sampling Fourier frequencies well for high-dimensional data.
method Data adaptive resampling of Fourier frequencies, asymptotically optimal.
result Proves convergence of adaptive resampling method for regression and classification problems.
We study the following basic machine learning task: Given a fixed set of -dimensional input points for a linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear pre…
Improves Bayesian optimisation for engineering design problems with many variables.
problem Efficiently searching for global minima in high-dimensional design spaces.
method Integrates input and output data to identify a reduced latent subspace using probabilistic partial least squares.
result Significant improvements in convergence to the global minimum compared to existing methods.
Iterative algorithms are ubiquitous in the field of data mining. Widely known examples of such algorithms are the least mean square algorithm, backpropagation algorithm of neural networks. Our contribution in this paper is an improvement upon this iterative algorithms in terms of their respective performance metrics an…