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.
Omega method mitigates noise in stochastic game optimization.
Optimistic NPG improves policy optimization in online RL with efficient sample complexity.
Accelerates policy optimization in RL with optimistic and adaptive updates.
This paper analyzes OGDA and EG methods for nonconvex minimax problems.
In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods. We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving…
Optimistic method adapted for faster convex-concave min-max problems.
Algorithm converges to Nash equilibria in competitive games.
Develops new algorithms for solving root-finding problems in large-scale settings.
A generalized optimistic method for saddle point problems with improved complexity.
We propose a new variant of AMSGrad, a popular adaptive gradient based optimization algorithm widely used for training deep neural networks. Our algorithm adds prior knowledge about the sequence of consecutive mini-batch gradients and leverages its underlying structure making the gradients sequentially predictable. By …
Owing to their connection with generative adversarial networks (GANs), saddle-point problems have recently attracted considerable interest in machine learning and beyond. By necessity, most theoretical guarantees revolve around convex-concave (or even linear) problems; however, making theoretical inroads towards effici…
We address the issue of limit cycling behavior in training Generative Adversarial Networks and propose the use of Optimistic Mirror Decent (OMD) for training Wasserstein GANs. Recent theoretical results have shown that optimistic mirror decent (OMD) can enjoy faster regret rates in the context of zero-sum games. WGANs …
Motivated by applications in Optimization, Game Theory, and the training of Generative Adversarial Networks, the convergence properties of first order methods in min-max problems have received extensive study. It has been recognized that they may cycle, and there is no good understanding of their limit points when they…
We study the iteration complexity of the optimistic gradient descent-ascent (OGDA) method and the extra-gradient (EG) method for finding a saddle point of a convex-concave unconstrained min-max problem. To do so, we first show that both OGDA and EG can be interpreted as approximate variants of the proximal point method…
Develops an accelerated algorithm for solving nonmonotone generalized equations.
Optimistic actor-critic tackles linear MDPs with parametric policies.
In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \t…
Paper analyzes regret bounds for unconstrained online optimization.
New ODE models show saddle-point optimization methods converge differently, with last-iterate convergence for OGDA.
New algorithm AG-OG optimizes separable convex-concave problems efficiently.
Optimistic algorithm reduces regret and constraint violations in online convex optimization with adversarial constraints.
Bayesian classifier improves robustness with optimistic score ratio.
New framework uses tempered optimism to handle imperfect experts in online learning.
We show that the optimistic limits of the colored Jones polynomials of the hyperbolic knots coincide with the optimistic limits of the Kashaev invariants modulo .
We discuss the relative merits of optimistic and randomized approaches to exploration in reinforcement learning. Optimistic approaches presented in the literature apply an optimistic boost to the value estimate at each state-action pair and select actions that are greedy with respect to the resulting optimistic value f…
Despite remarkable empirical success, the training dynamics of generative adversarial networks (GAN), which involves solving a minimax game using stochastic gradients, is still poorly understood. In this work, we analyze last-iterate convergence of simultaneous gradient descent (simGD) and its variants under the assump…
The optimistic limit is the mathematical formulation of the classical limit which is a physical method to expect the actual limit by using saddle point method of certain potential function. The original optimistic limit of the Kashaev invariant was formulated by Yokota, and a modified formulation was suggested by the a…
Optimistic estimate predicts best fitting performance of nonlinear models.
This paper introduces a set of algorithms for Monte-Carlo Bayesian reinforcement learning. Firstly, Monte-Carlo estimation of upper bounds on the Bayes-optimal value function is employed to construct an optimistic policy. Secondly, gradient-based algorithms for approximate upper and lower bounds are introduced. Finally…
In this article, we study the convergence of Mirror Descent (MD) and Optimistic Mirror Descent (OMD) for saddle point problems satisfying the notion of coherence as proposed in Mertikopoulos et al. We prove convergence of OMD with exact gradients for coherent saddle point problems, and show that monotone convergence on…
Optimistic initialisation is an effective strategy for efficient exploration in reinforcement learning (RL). In the tabular case, all provably efficient model-free algorithms rely on it. However, model-free deep RL algorithms do not use optimistic initialisation despite taking inspiration from these provably efficient …
We investigate the challenge of multi-output learning, where the goal is to learn a vector-valued function based on a supervised data set. This includes a range of important problems in Machine Learning including multi-target regression, multi-class classification and multi-label classification. We begin our analysis b…
New algorithm reduces regret in sequential decision-making problems.
While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to design a provably efficient policy optimization algorithm that incorporates exploration. To bridge su…
Characterizes concept classes for optimistic online learning.
We derive an alternative proof for the regret of Thompson sampling (\ts) in the stochastic linear bandit setting. While we obtain a regret bound of order as in previous results, the proof sheds new light on the functioning of the \ts. We leverage on the structure of the problem to show …
We show how to take any two parameter-free online learning algorithms with different regret guarantees and obtain a single algorithm whose regret is the minimum of the two base algorithms. Our method is embarrassingly simple: just add the iterates. This trick can generate efficient algorithms that adapt to many norms s…
Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al \cite{DISZ17} and follow-up work of Liang and Stokes \cite{LiangS18} have established that a variant of the widely used Gradient Descent/Ascent procedure, called "Optimistic Gradient Descent/Asce…
Optimizes algorithms for non-concave bandit problems.
New algorithms reduce forecasting errors by leveraging optimistic learning and hinting.
We consider a covariate shift problem where one has access to several different training datasets for the same learning problem and a small validation set which possibly differs from all the individual training distributions. This covariate shift is caused, in part, due to unobserved features in the datasets. The objec…
New method minimizes regret in AMDP with high probability.
Gradient methods converge exponentially in concave network games.
Unified framework for model- and value-optimistic reinforcement learning.
Hyperboost uses gradient boosting for hyperparameter optimization, outperforming state-of-the-art methods.
It is well known that in stochastic multi-armed bandits (MAB), the sample mean of an arm is typically not an unbiased estimator of its true mean. In this paper, we decouple three different sources of this selection bias: adaptive \emph{sampling} of arms, adaptive \emph{stopping} of the experiment, and adaptively \emph{…
In many cases an intelligent agent may want to learn how to mimic a single observed demonstrated trajectory. In this work we consider how to perform such procedural learning from observation, which could help to enable agents to better use the enormous set of video data on observation sequences. Our approach exploits t…
Efficiently solves exploration-exploitation in LQR using Lagrangian relaxation.