Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)

• URL: http://arxiv.org/abs/2207.11161v1
• Date: Fri, 22 Jul 2022 15:57:52 GMT
• Title: Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)
• Authors: Huang Bojun
• Abstract summary: The paper shows that the Lagrangian enjoys strong duality, in spite of its nonlinearity, which paves the way to a general Lagrangian method to Q-function learning.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper discusses a new approach to the fundamental problem of learning optimal Q-functions. In this approach, optimal Q-functions are formulated as saddle points of a nonlinear Lagrangian function derived from the classic Bellman optimality equation. The paper shows that the Lagrangian enjoys strong duality, in spite of its nonlinearity, which paves the way to a general Lagrangian method to Q-function learning. As a demonstration, the paper develops an imitation learning algorithm based on the duality theory, and applies the algorithm to a state-of-the-art machine translation benchmark. The paper then turns to demonstrate a symmetry breaking phenomenon regarding the optimality of the Lagrangian saddle points, which justifies a largely overlooked direction in developing the Lagrangian method.

Related papers

• Neural Implicit Solution Formula for Efficiently Solving Hamilton-Jacobi Equations [0.0]
  An implicit solution formula is presented for the Hamilton-Jacobi partial differential equation (HJ PDE) A deep learning-based methodology is proposed to learn this implicit solution formula. An algorithm is developed that approximates the characteristic curves for state-dependent Hamiltonians.
  arXiv  Detail & Related papers  (2025-01-31T17:56:09Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Dual Lagrangian Learning for Conic Optimization [18.006916033168494]
  The paper introduces a systematic dual completion procedure, differentiable conic projection layers, and a self-supervised learning framework based on Lagrangian duality. It also provides closed-form dual completion formulae for broad classes of conic problems, which eliminate the need for costly implicit layers. The proposed methodology significantly outperforms a state-of-the-art learning-based method, and achieves 1000x speedups over commercial interior-point solvers with optimality gaps under 0.5% on average.
  arXiv  Detail & Related papers  (2024-02-05T15:14:08Z)
• Grasp Force Optimization as a Bilinear Matrix Inequality Problem: A Deep Learning Approach [0.4999814847776098]
  This paper is to undertake a grasp-mimetic grasping in multifingered hands as a bilinear matrix inequality (BMI) problem. Our analysis is to solve it using a deep approach to make the algorithm efficiently generate force grasps with optimal grasp quality on untrained/unseen objects.
  arXiv  Detail & Related papers  (2023-12-08T13:28:21Z)
• Convex Q Learning in a Stochastic Environment: Extended Version [1.680268810119084]
  The paper introduces the first formulation of convex Q-learning for Markov decision processes with function approximation. The proposed algorithms are convergent and new techniques are introduced to obtain the rate of convergence in a mean-square sense. The theory is illustrated with an application to a classical inventory control problem.
  arXiv  Detail & Related papers  (2023-09-10T18:24:43Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  We consider the linear programming (LP) formulation for deep reinforcement learning. The augmented Lagrangian method suffers the double-sampling obstacle in solving the LP. A deep parameterized augment Lagrangian method is proposed.
  arXiv  Detail & Related papers  (2021-05-20T13:08:06Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  Non-uniform refinement of objective functions leads to emphNon-uniform Smoothness (NS) and emphNon-uniform Lojasiewicz inequality (NL) New definitions inspire new geometry-aware first-order methods that converge to global optimality faster than the classical $Omega (1/t2)$ lower bounds.
  arXiv  Detail & Related papers  (2021-05-13T04:23:07Z)
• Stochastic Hamiltonian Gradient Methods for Smooth Games [51.47367707388402]
  We focus on the class of Hamiltonian methods and provide the first convergence guarantees for certain classes of smooth games. Using tools from the optimization literature we show that SHGD converges linearly to the neighbourhood of a gradient. Our results provide the first global non-asymotic last-rate convergence guarantees for the class of general games.
  arXiv  Detail & Related papers  (2020-07-08T15:42:13Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

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.