Recover a integer valued function with *-learning

I have the following problem. From a technical model we have a function $f(n,p)$ approximating its runtime. The function $f$ which maps

$$
f: mathbb{N} times mathbb{P} to mathbb{R}_{+}
$$
where $mathbb{P} = {1,ldots,50} subsetmathbb{N}$. $n$ defines the amount of input and $p$ is a parameter of the process, which has a continuous influence on the runtime. We are interested in the value of $p$ such that $f(n,p)$ for a given $n$. At the run the experiment some $n$, like 500, 1000, 5000, and for all possible values of $p$ and then select the optimal $p$ by hand. Like for everything smaller than 750 use the optimal $p$ of the test run with $n=500$ and so on. Typically for a fixed $n$ the runtime over $p$ has the following style but with noise added:

For increasing $n$ the bottom moves to the right and due to noise the bottom is not flat. So in the example the optimal $p$ is somewhere between $20$ and $30$.

We are now searching for a function $g$:

$$
g: mathbb{N} to mathbb{P}
$$
which is defined by
$$
g(n) = operatorname{argmin}limits_{pinmathbb{P}} f(n,p)
$$

Since sampling $f$ for fixed $n$ is not a problem and I already have a large set of samples I think this will be a good problem to start with for looking into the machine learning area for myself.

My basic question is where to start? Search for machine learning tutorial I mostly end up with the image recognition examples and did see any good connections between those and my problem.
Any suggestions about stuff to read for this problem? Any idea which software to use? And finally how to extract $g$ such that we can provide this function to the users or implement somewhere? At the moment I know that $g$ is non-decreasing for increasing $n$.

Edit
The sampling results can also look like this

Thereby the spikes in the "mininum" point area are no noise. They are caused by technical internals of the regarded process. So while processing the data and removing the noise these points need to kept. And they make finding $g$ so hard because in one sampling run the minimal $p$ lies left, in the middle or right of them. For this reason I though this would be a good point to use machine learning to get some insights.