Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation

• URL: http://arxiv.org/abs/2501.00799v2
• Date: Tue, 07 Jan 2025 17:32:19 GMT
• Title: Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation
• Authors: Samrat Mukhopadhyay, Debasmita Mukherjee,
• Abstract summary: We consider the problem of textitonline sparse linear approximation, where one predicts the best sparse approximation of a sequence of measurements in terms of linear combination of columns of a given measurement matrix.<n>We propose Follow-The-Approximate-Sparse-Leader, an efficient online meta-policy to address this online problem.
• Score: 0.46040036610482665
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider the problem of \textit{online sparse linear approximation}, where one predicts the best sparse approximation of a sequence of measurements in terms of linear combination of columns of a given measurement matrix. Such online prediction problems are ubiquitous, ranging from medical trials to web caching to resource allocation. The inherent difficulty of offline recovery also makes the online problem challenging. In this letter, we propose Follow-The-Approximate-Sparse-Leader, an efficient online meta-policy to address this online problem. Through a detailed theoretical analysis, we prove that under certain assumptions on the measurement sequence, the proposed policy enjoys a data-dependent sublinear upper bound on the static regret, which can range from logarithmic to square-root. Numerical simulations are performed to corroborate the theoretical findings and demonstrate the efficacy of the proposed online policy.

Related papers

• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
  arXiv  Detail & Related papers  (2025-11-27T06:16:17Z)
• Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction [4.42171635795004]
  We study the problem of online multi-step-ahead prediction for unknown linear systems.<n>Using conditional distribution theory, we derive an optimal parameterization of the prediction policy as a linear function of future inputs, past inputs, and past outputs.<n>We show that the online algorithm achieves logarithmic regret with respect to the optimal Kalman filter in the multi-step setting.
  arXiv  Detail & Related papers  (2025-11-16T05:49:44Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
  This paper focuses on applying entropic mirror descent to solve linear systems.<n>The main challenge for the convergence analysis stems from the unboundedness of the domain.<n>To overcome this without imposing restrictive assumptions, we introduce a variant of Polyak-type stepsizes.
  arXiv  Detail & Related papers  (2025-05-05T12:33:18Z)
• Online Conformal Probabilistic Numerics via Adaptive Edge-Cloud Offloading [52.499838151272016]
  This work introduces a new method to calibrate the HPD sets produced by PLS with the aim of guaranteeing long-term coverage requirements. The proposed method, referred to as online conformal prediction-PLS (OCP-PLS), assumes sporadic feedback from cloud to edge. The validity of OCP-PLS is verified via experiments that bring insights into trade-offs between coverage, prediction set size, and cloud usage.
  arXiv  Detail & Related papers  (2025-03-18T17:30:26Z)
• Regret Analysis of Policy Optimization over Submanifolds for Linearly Constrained Online LQG [12.201535821920624]
  We study online linear quadratic Gaussian problems with a given linear constraint imposed on the controller. We propose online optimistic Newton on manifold (OONM) which provides an online controller based on the prediction on the first and second order information of the function sequence.
  arXiv  Detail & Related papers  (2024-03-13T14:06:18Z)
• Multivariate Online Linear Regression for Hierarchical Forecasting [1.5361702135159843]
  We introduce MultiVAW, a method that extends the well-known Vovk-Azoury-Warmuth algorithm to the multivariate setting. We apply our results to the online hierarchical forecasting problem and recover an algorithm from this literature as a special case.
  arXiv  Detail & Related papers  (2024-02-22T14:33:54Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  We propose an efficient online approximate Bayesian inference algorithm for estimating the parameters of a nonlinear function from a potentially non-stationary data stream. The method is based on the extended Kalman filter (EKF), but uses a novel low-rank plus diagonal decomposition of the posterior matrix. In contrast to methods based on variational inference, our method is fully deterministic, and does not require step-size tuning.
  arXiv  Detail & Related papers  (2023-05-31T03:48:49Z)
• An Online Algorithm for Chance Constrained Resource Allocation [10.791923293928987]
  This paper studies the online resource allocation problem (RAP) with chance constraints. To the best of our knowledge, this is the first time chance constraints are introduced in the online RAP problem.
  arXiv  Detail & Related papers  (2023-03-06T16:17:19Z)
• Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression [14.521929085104441]
  We establish a high-dimensional Central Limit Theorem (CLT) for linear functionals of online gradient descent (SGD) We develop an online approach for estimating the expectation and the variance terms appearing in the CLT, and establish high-probability bounds for the developed online estimator. We propose a two-step fully online bias-correction methodology which together with the CLT result and the variance estimation result, provides a fully online and data-driven way to numerically construct confidence intervals.
  arXiv  Detail & Related papers  (2023-02-20T02:38:36Z)
• Online Statistical Inference in Decision-Making with Matrix Context [5.2071564436846245]
  We propose an online procedure to conduct statistical inference with adaptively collected data. Standard low-rank estimators are biased and cannot be obtained in a sequential manner. Existing approaches in sequential decision-making algorithms fail to account for the low-rankness and are also biased.
  arXiv  Detail & Related papers  (2022-12-21T22:03:06Z)
• Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality [57.91411772725183]
  In this paper, we consider the offline shortest path problem when the state space and the action space are finite. We design the simple value-based algorithms for tackling both offline policy evaluation (OPE) and offline policy learning tasks. Our analysis of these simple algorithms yields strong instance-dependent bounds which can imply worst-case bounds that are near-minimax optimal.
  arXiv  Detail & Related papers  (2022-06-10T07:44:56Z)
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
  We study offline reinforcement learning (RL) in partially observable Markov decision processes. We propose the underlineProxy variable underlinePessimistic underlinePolicy underlineOptimization (textttP3O) algorithm. textttP3O is the first provably efficient offline RL algorithm for POMDPs with a confounded dataset.
  arXiv  Detail & Related papers  (2022-05-26T19:13:55Z)
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge [24.880035784304834]
  We derive high probability regret bounds for online ridge regression and the forward algorithm. This enables us to compare online regression algorithms more accurately and eliminate assumptions of bounded observations and predictions.
  arXiv  Detail & Related papers  (2021-11-02T13:57:53Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)

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.