  We explore the properties of non-local effective actions which include
gravitational couplings. Non-local functions originally defined in flat space
can not be easily generalized to curved space. The problem is made worse by the
calculational impossibility of providing closed form expressions in a general
metric. The technique of covariant perturbation theory (CPT) has been pioneered
by Vilkovisky, Barvinsky and collaborators whereby the effective action is
displayed as an expansion in the generalized curvatures similar to the
Schwinger-De Witt local expansion. We present an alternative procedure to
construct the non-local action which we call {\em non-linear completion}. Our
approach is in one-to-one correspondence with the more familiar diagrammatic
expansion of the effective action. This technique moreover enables us to decide
on the appropriate non-local action that generates the QED trace anomaly in
4$D$. In particular we discuss carefully the curved space generalization of
$\ln \Box$, and show that the anomaly requires both the anomalous logarithm as
well as $1/\Box$ term where the latter is related to the Riegert anomaly
action.
