On the Stochastic (Variance-Reduced) Proximal Gradient Method for
Regularized Expected Reward Optimization
- URL: http://arxiv.org/abs/2401.12508v1
- Date: Tue, 23 Jan 2024 06:01:29 GMT
- Title: On the Stochastic (Variance-Reduced) Proximal Gradient Method for
Regularized Expected Reward Optimization
- Authors: Ling Liang and Haizhao Yang
- Abstract summary: We consider a regularized expected reward optimization problem in the non-oblivious setting that covers many existing problems in reinforcement learning (RL)
In particular, the method has shown to admit an $O(epsilon-4)$ sample to an $epsilon-stationary point, under standard conditions.
We show that the sample complexity can be improved from $epsilon-4)$ to $O(epsilon-3)$ under additional conditions.
- Score: 12.244251361123396
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a regularized expected reward optimization problem in the
non-oblivious setting that covers many existing problems in reinforcement
learning (RL). In order to solve such an optimization problem, we apply and
analyze the classical stochastic proximal gradient method. In particular, the
method has shown to admit an $O(\epsilon^{-4})$ sample complexity to an
$\epsilon$-stationary point, under standard conditions. Since the variance of
the classical stochastic gradient estimator is typically large which slows down
the convergence, we also apply an efficient stochastic variance-reduce proximal
gradient method with an importance sampling based ProbAbilistic Gradient
Estimator (PAGE). To the best of our knowledge, the application of this method
represents a novel approach in addressing the general regularized reward
optimization problem. Our analysis shows that the sample complexity can be
improved from $O(\epsilon^{-4})$ to $O(\epsilon^{-3})$ under additional
conditions. Our results on the stochastic (variance-reduced) proximal gradient
method match the sample complexity of their most competitive counterparts under
similar settings in the RL literature.
Related papers
- A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness [4.097563258332958]
We propose a fast quasi-Newton method when there exists non-uniformity in smoothness.
Our algorithm can achieve the best-known $mathcalO(epsilon-3)$ sample complexity and enjoys convergence speedup.
Our numerical experiments show that our proposed algorithm outperforms the state-of-the-art approaches.
arXiv Detail & Related papers (2024-03-22T14:40:29Z) - Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
The optimistic gradient method is useful in addressing minimax optimization problems.
Motivated by the observation that the conventional version suffers from the need for a large batch size, we introduce and analyze a new formulation termed Samevareps-generativeOGOG.
arXiv Detail & Related papers (2024-01-26T01:16:59Z) - Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective.
We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices.
Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
arXiv Detail & Related papers (2023-10-31T16:15:13Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
We show the worst-case complexity of convergence $tildeO(t-1/4)$ and MoreautildeO(vareps-4)$ for smooth non- optimization.
We obtain first online nonnegative matrix factorization algorithms for dependent data based on projected gradient methods with adaptive step sizes and optimal convergence.
arXiv Detail & Related papers (2022-03-29T17:59:10Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm.
We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
arXiv Detail & Related papers (2021-12-29T18:46:52Z) - Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic
Optimization [1.7513645771137178]
We consider unconstrained optimization problems with no available gradient information.
We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a simulation function using finite differences within a common random number framework.
We develop modified versions of a norm test and an inner product quasi-Newton test to control the sample sizes used in the approximations and provide global convergence results to the neighborhood of the optimal solution.
arXiv Detail & Related papers (2021-09-24T21:49:25Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks.
We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution.
We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
arXiv Detail & Related papers (2021-07-02T16:21:52Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
In this paper, we demonstrate the power of a widely used estimator based on moving average (SEMA) problems.
For all these-the-art results, we also present the results for all these-the-art problems.
arXiv Detail & Related papers (2021-04-30T08:50:24Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information.
We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
arXiv Detail & Related papers (2020-12-21T17:29:58Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks.
In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems.
Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
arXiv Detail & Related papers (2019-12-26T22:10:10Z)
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.