Stochastic Gradient Descent with Adaptive Data

• URL: http://arxiv.org/abs/2410.01195v1
• Date: Wed, 2 Oct 2024 02:58:32 GMT
• Title: Stochastic Gradient Descent with Adaptive Data
• Authors: Ethan Che, Jing Dong, Xin T. Tong,
• Abstract summary: gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The influence of previous decisions on the data generated introduces bias in the gradient estimate, which presents a potential source of instability for online learning not present in the iid case. We show that the convergence speed of SGD with adaptive data is largely similar to the classical iid setting, as long as the mixing time of the policy-induced dynamics is factored in.
• Score: 4.119418481809095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Its convergence analysis is relatively well understood under the assumption that the data samples are independent and identically distributed (iid). However, applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The adaptively generated data stream involves samples that are non-stationary, no longer independent from each other, and affected by previous decisions. The influence of previous decisions on the data generated introduces bias in the gradient estimate, which presents a potential source of instability for online learning not present in the iid case. In this paper, we introduce simple criteria for the adaptively generated data stream to guarantee the convergence of SGD. We show that the convergence speed of SGD with adaptive data is largely similar to the classical iid setting, as long as the mixing time of the policy-induced dynamics is factored in. Our Lyapunov-function analysis allows one to translate existing stability analysis of stochastic systems studied in operations research into convergence rates for SGD, and we demonstrate this for queueing and inventory management problems. We also showcase how our result can be applied to study the sample complexity of an actor-critic policy gradient algorithm.

Related papers

• PEAKS: Selecting Key Training Examples Incrementally via Prediction Error Anchored by Kernel Similarity [6.6157730528755065]
  We study the Incremental Data Selection (IDS) problem, where examples arrive as a continuous stream, and need to be selected without access to the full data source. We propose PEAKS (Prediction Error Anchored by Kernel Similarity), an efficient data selection method tailored for IDS. Our evaluations demonstrate that PEAKS consistently outperforms existing selection strategies.
  arXiv  Detail & Related papers  (2025-04-07T16:42:09Z)
• CALF: A Conditionally Adaptive Loss Function to Mitigate Class-Imbalanced Segmentation [0.2902243522110345]
  Imbalanced datasets pose a challenge in training deep learning (DL) models for medical diagnostics. We propose a novel, statistically driven, conditionally adaptive loss function (CALF) tailored to accommodate the conditions of imbalanced datasets in DL training.
  arXiv  Detail & Related papers  (2025-04-06T12:03:33Z)
• Representation-based Reward Modeling for Efficient Safety Alignment of Large Language Model [84.00480999255628]
  Reinforcement Learning algorithms for safety alignment of Large Language Models (LLMs) encounter the challenge of distribution shift. Current approaches typically address this issue through online sampling from the target policy. We propose a new framework that leverages the model's intrinsic safety judgment capability to extract reward signals.
  arXiv  Detail & Related papers  (2025-03-13T06:40:34Z)
• Adaptive Conformal Inference by Betting [51.272991377903274]
  We consider the problem of adaptive conformal inference without any assumptions about the data generating process. Existing approaches for adaptive conformal inference are based on optimizing the pinball loss using variants of online gradient descent. We propose a different approach for adaptive conformal inference that leverages parameter-free online convex optimization techniques.
  arXiv  Detail & Related papers  (2024-12-26T18:42:08Z)
• Adaptive Data Analysis for Growing Data [19.68686581348877]
  Reuse of data in adaptive poses challenges regarding overfitting and the statistical validity results. We present the first generalization bounds for adaptive analysis in the dynamic data setting.
  arXiv  Detail & Related papers  (2024-05-22T06:17:58Z)
• Policy Gradient with Active Importance Sampling [55.112959067035916]
  Policy gradient (PG) methods significantly benefit from IS, enabling the effective reuse of previously collected samples. However, IS is employed in RL as a passive tool for re-weighting historical samples. We look for the best behavioral policy from which to collect samples to reduce the policy gradient variance.
  arXiv  Detail & Related papers  (2024-05-09T09:08:09Z)
• Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Data [17.991833729722288]
  We propose a novel policy learning algorithm, PESsimistic CAusal Learning (PESCAL) Our key observation is that, by incorporating auxiliary variables that mediate the effect of actions on system dynamics, it is sufficient to learn a lower bound of the mediator distribution function, instead of the Q-function. We provide theoretical guarantees for the algorithms we propose, and demonstrate their efficacy through simulations, as well as real-world experiments utilizing offline datasets from a leading ride-hailing platform.
  arXiv  Detail & Related papers  (2024-03-18T14:51:19Z)
• Neural variational Data Assimilation with Uncertainty Quantification using SPDE priors [28.804041716140194]
  Recent advances in the deep learning community enables to address the problem through a neural architecture a variational data assimilation framework. In this work we use the theory of Partial Differential Equations (SPDE) and Gaussian Processes (GP) to estimate both space-and time covariance of the state.
  arXiv  Detail & Related papers  (2024-02-02T19:18:12Z)
• A Conditioned Unsupervised Regression Framework Attuned to the Dynamic Nature of Data Streams [0.0]
  This paper presents an optimal strategy for streaming contexts with limited labeled data, introducing an adaptive technique for unsupervised regression. The proposed method leverages a sparse set of initial labels and introduces an innovative drift detection mechanism. To enhance adaptability, we integrate the ADWIN (ADaptive WINdowing) algorithm with error generalization based on Root Mean Square Error (RMSE)
  arXiv  Detail & Related papers  (2023-12-12T19:23:54Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Robust Fitted-Q-Evaluation and Iteration under Sequentially Exogenous Unobserved Confounders [16.193776814471768]
  We study robust policy evaluation and policy optimization in the presence of sequentially-exogenous unobserved confounders. We provide sample complexity bounds, insights, and show effectiveness both in simulations and on real-world longitudinal healthcare data of treating sepsis.
  arXiv  Detail & Related papers  (2023-02-01T18:40:53Z)
• Unleashing the Power of Graph Data Augmentation on Covariate Distribution Shift [50.98086766507025]
  We propose a simple-yet-effective data augmentation strategy, Adversarial Invariant Augmentation (AIA) AIA aims to extrapolate and generate new environments, while concurrently preserving the original stable features during the augmentation process.
  arXiv  Detail & Related papers  (2022-11-05T07:55:55Z)
• On the Sparse DAG Structure Learning Based on Adaptive Lasso [39.31370830038554]
  We develop a data-driven DAG structure learning method without the predefined threshold, called adaptive NOTEARS [30] We show that adaptive NOTEARS enjoys the oracle properties under some specific conditions. Furthermore, simulation results validate the effectiveness of our method, without setting any gap of edges around zero.
  arXiv  Detail & Related papers  (2022-09-07T05:47:59Z)
• Latent-Variable Advantage-Weighted Policy Optimization for Offline RL [70.01851346635637]
  offline reinforcement learning methods hold the promise of learning policies from pre-collected datasets without the need to query the environment for new transitions. In practice, offline datasets are often heterogeneous, i.e., collected in a variety of scenarios. We propose to leverage latent-variable policies that can represent a broader class of policy distributions. Our method improves the average performance of the next best-performing offline reinforcement learning methods by 49% on heterogeneous datasets.
  arXiv  Detail & Related papers  (2022-03-16T21:17:03Z)
• Provably Efficient Causal Reinforcement Learning with Confounded Observational Data [135.64775986546505]
  We study how to incorporate the dataset (observational data) collected offline, which is often abundantly available in practice, to improve the sample efficiency in the online setting. We propose the deconfounded optimistic value iteration (DOVI) algorithm, which incorporates the confounded observational data in a provably efficient manner.
  arXiv  Detail & Related papers  (2020-06-22T14:49:33Z)
• Dynamic Federated Learning [57.14673504239551]
  Federated learning has emerged as an umbrella term for centralized coordination strategies in multi-agent environments. We consider a federated learning model where at every iteration, a random subset of available agents perform local updates based on their data. Under a non-stationary random walk model on the true minimizer for the aggregate optimization problem, we establish that the performance of the architecture is determined by three factors, namely, the data variability at each agent, the model variability across all agents, and a tracking term that is inversely proportional to the learning rate of the algorithm.
  arXiv  Detail & Related papers  (2020-02-20T15:00:54Z)

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.