skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Approximate Generalized Matching: f-Matchings and f-Edge Covers
Award ID(s):
1637546 1815316
PAR ID:
10359266
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Algorithmica
Volume:
84
Issue:
7
ISSN:
0178-4617
Page Range / eLocation ID:
1952 to 1992
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Abstract We consider the inequality $$f \geqslant f\star f$$ for real functions in $$L^1({\mathbb{R}}^d)$$ where $$f\star f$$ denotes the convolution of $$f$$ with itself. We show that all such functions $$f$$ are nonnegative, which is not the case for the same inequality in $L^p$ for any $$1 < p \leqslant 2$$, for which the convolution is defined. We also show that all solutions in $$L^1({\mathbb{R}}^d)$$ satisfy $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x \leqslant \tfrac 12$$. Moreover, if $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x = \tfrac 12$$, then $$f$$ must decay fairly slowly: $$\int _{{\mathbb{R}}^{\textrm{d}}}|x| f(x)\ \textrm{d}x = \infty $$, and this is sharp since for all $r< 1$, there are solutions with $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x = \tfrac 12$$ and $$\int _{{\mathbb{R}}^{\textrm{d}}}|x|^r f(x)\ \textrm{d}x <\infty $$. However, if $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x =: a < \tfrac 12$$, the decay at infinity can be much more rapid: we show that for all $$a<\tfrac 12$$, there are solutions such that for some $$\varepsilon>0$$, $$\int _{{\mathbb{R}}^{\textrm{d}}}e^{\varepsilon |x|}f(x)\ \textrm{d}x < \infty $$. 
    more » « less
  2. null (Ed.)
  3. null (Ed.)
    Imitation learning (IL) aims to learn a policy from expert demonstrations that minimizes the discrepancy between the learner and expert behaviors. Various imitation learning algorithms have been proposed with different pre-determined divergences to quantify the discrepancy. This naturally gives rise to the following question: Given a set of expert demonstrations, which divergence can recover the expert policy more accurately with higher data efficiency? In this work, we propose f-GAIL – a new generative adversarial imitation learning model – that automatically learns a discrepancy measure from the f-divergence family as well as a policy capable of producing expert-like behaviors. Compared with IL baselines with various predefined divergence measures, f-GAIL learns better policies with higher data efficiency in six physics-based control tasks. 
    more » « less
  4. null (Ed.)