Safe Screening for Unbalanced Optimal Transport

• URL: http://arxiv.org/abs/2307.00247v1
• Date: Sat, 1 Jul 2023 06:22:14 GMT
• Title: Safe Screening for Unbalanced Optimal Transport
• Authors: Xun Su, Zhongxi Fang, Hiroyuki Kasai
• Abstract summary: We demonstrate the feasibility of applying Safe Screening to the UOT problem with $ell$-penalty and KL-penalty. We specifically propose a novel approximate projection, an elliptical safe region, and a two-hyperplane relaxation method. These enhancements significantly improve the screening efficiency for the UOT's without altering the algorithm's complexity.
• Score: 17.489075240435348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a framework that utilizes the Safe Screening technique to accelerate the optimization process of the Unbalanced Optimal Transport (UOT) problem by proactively identifying and eliminating zero elements in the sparse solutions. We demonstrate the feasibility of applying Safe Screening to the UOT problem with $\ell_2$-penalty and KL-penalty by conducting an analysis of the solution's bounds and considering the local strong convexity of the dual problem. Considering the specific structural characteristics of the UOT in comparison to general Lasso problems on the index matrix, we specifically propose a novel approximate projection, an elliptical safe region construction, and a two-hyperplane relaxation method. These enhancements significantly improve the screening efficiency for the UOT's without altering the algorithm's complexity.

Related papers

• One-Shot Safety Alignment for Large Language Models via Optimal Dualization [64.52223677468861]
  This paper presents a dualization perspective that reduces constrained alignment to an equivalent unconstrained alignment problem. We do so by pre-optimizing a smooth and convex dual function that has a closed form. Our strategy leads to two practical algorithms in model-based and preference-based scenarios.
  arXiv  Detail & Related papers  (2024-05-29T22:12:52Z)
• Spectral-Risk Safe Reinforcement Learning with Convergence Guarantees [13.470544618339506]
  We propose a spectral risk measure-constrained RL algorithm, spectral-risk-constrained policy optimization (SRCPO) In the bilevel optimization structure, the outer problem involves optimizing dual variables derived from the risk measures, while the inner problem involves finding an optimal policy. The proposed method has been evaluated on continuous control tasks and showed the best performance among other RCRL algorithms satisfying the constraints.
  arXiv  Detail & Related papers  (2024-05-29T02:17:25Z)
• SCPO: Safe Reinforcement Learning with Safety Critic Policy Optimization [1.3597551064547502]
  This study introduces a novel safe reinforcement learning algorithm, Safety Critic Policy Optimization. In this study, we define the safety critic, a mechanism that nullifies rewards obtained through violating safety constraints. Our theoretical analysis indicates that the proposed algorithm can automatically balance the trade-off between adhering to safety constraints and maximizing rewards.
  arXiv  Detail & Related papers  (2023-11-01T22:12:50Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  We introduce a general approach for seeking high dimensional non-linear optimization problems in which maintaining safety during learning is crucial. Our approach called LBSGD is based on applying a logarithmic barrier approximation with a carefully chosen step size. We demonstrate the effectiveness of our approach on minimizing violation in policy tasks in safe reinforcement learning.
  arXiv  Detail & Related papers  (2022-07-21T11:14:47Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport [36.97843660480747]
  This paper studies the equitable and optimal transport (EOT) problem, which has many applications. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP) Since this LP is prohibitively large for general solvers, Scetbon etal citescetbonequitable suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating algorithm (PAM) to solve the dual of the entropy regularized EOT.
  arXiv  Detail & Related papers  (2021-09-29T04:32:06Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Robust Reinforcement Learning with Wasserstein Constraint [49.86490922809473]
  We show the existence of optimal robust policies, provide a sensitivity analysis for the perturbations, and then design a novel robust learning algorithm. The effectiveness of the proposed algorithm is verified in the Cart-Pole environment.
  arXiv  Detail & Related papers  (2020-06-01T13:48:59Z)

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.