The notion of PAC in approximation algorithms In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is there a way to generalize this idea for approximation algorithms? What I thought of:
Given a language $L \subseteq \{0,1\}^*$, a confidence parameter $\delta\in[0,1]$, an error parameter $\epsilon &gt; 0$, and a distribution $D$ over $L$, the algorithm $A$ is a PAC algorithm for $L$ if with probability at least 1 - $\delta$ it holds that $\text{ERR}(A,D)\leq \epsilon$, where $\text{ERR}(A,D) := \Pr_{x\text{~}D}(A \text{ answers wrong on } x)$.
One drawback of this definition is the following: suppose $L$ is a countable infinite set, and let $l_1, l_2,...,l_k,...$ be some enumeration of the elements of $L$. Since $D$ is a probability distribution over $L$, $\sum_{i}D(l_i) = 1$, and hence there must be some index $k$ such that $\sum_{j&gt;k} D(l_j) &lt;\epsilon$.
The algorithm $A$ can be defined as: remember the answers of the first $k$ words. When receiving $w \in \{0,1\}^*$ check if $w$ is saved (and if so answer correctly). Otherwise, answer "0".
Clearly this algorithm is a PAC by the above definition, but not a clever one.
Is there a way to define PAC algorithm for a formal language? Or: can we use the theory of machine learning in the theory of approximation algorithms?
Approximation algorithms don't make sense here, because here the output of the algorithm is 0 or 1.  (0 represents "the input is not in $L$", 1 represents "the input is in $L$".)  Approximation algorithms are useful when the output is a continuous variable, as then we can ask for the algorithm to output something that is close to the correct answer, but the concept is not useful when talking about algorithms that output a boolean.

Also, in your proposed definition, once you have fixed an algorithm $A$ and a distribution $D$ over $L$, the condition $ERR(A,D) \le \epsilon$ is either true or false.  It's not an event that you can assign a probability to.  So, it doesn't make sense to ask it to hold with probability at least $1-\delta$.