Computational Complexity of Sub-Linear Convergent Algorithms

2022-09-29 · Hilal AlQuabeh, Farha AlBreiki, Dilshod Azizov

Optimizing machine learning algorithms that are used to solve the objective function has been of great interest. Several approaches to optimize common algorithms, such as gradient descent and stochastic gradient descent, were explored. One of these approaches is reducing the gradient variance through adaptive sampling to solve large-scale optimization's empirical risk minimization (ERM) problems. In this paper, we will explore how starting with a small sample and then geometrically increasing it and using the solution of the previous sample ERM to compute the new ERM. This will solve ERM problems with first-order optimization algorithms of sublinear convergence but with lower computational complexity. This paper starts with theoretical proof of the approach, followed by two experiments comparing the gradient descent with the adaptive sampling of the gradient descent and ADAM with adaptive sampling ADAM on different datasets.

📄 PDF Abstract BibTeX arXiv:2209.14558

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Adam 설명 없음

Convergent Temporal-Difference Learning with Arbitrary Smooth Function Approximation

2009-12-01 · NeurIPS 2009 12 · Shalabh Bhatnagar, Doina Precup, David Silver, Richard S. Sutton 외

We introduce the first temporal-difference learning algorithms that converge with smooth value function approximators, such as neural networks. Conventional temporal-difference (TD) methods, such as TD($\lambda$), Q-l…

Q-Learning

On a convergent off -policy temporal difference learning algorithm in on-line learning environment

2016-05-19 · Prasenjit Karmakar, Rajkumar Maity, Shalabh Bhatnagar

In this paper we provide a rigorous convergence analysis of a "off"-policy temporal difference learning algorithm with linear function approximation and per time-step linear computational complexity in "online" learning …

A Convergent Off-Policy Temporal Difference Algorithm

2019-11-13 · Raghuram Bharadwaj Diddigi, Chandramouli Kamanchi, Shalabh Bhatnagar

Learning the value function of a given policy (target policy) from the data samples obtained from a different policy (behavior policy) is an important problem in Reinforcement Learning (RL). This problem is studied under…

Prediction Reinforcement Learning Reinforcement Learning (RL)

Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms

2025-08-01 · Andrea Martin, Ian R. Manchester, Luca Furieri arxiv

The design of many classical optimization algorithms is driven by the certification of linear convergence rates over classes of optimization problems. In this paper, we consider the problem of improving the average-case …

Convergent Reinforcement Learning with Function Approximation: A Bilevel Optimization Perspective

2018-09-27 · Zhuoran Yang, Zuyue Fu, Kaiqing Zhang, Zhaoran Wang

We study reinforcement learning algorithms with nonlinear function approximation in the online setting. By formulating both the problems of value function estimation and policy learning as bilevel optimization problems,…

Bilevel Optimization Q-Learning reinforcement-learning Reinforcement Learning+1