Optimization - If the sum of objective functions are similar, will sum of argmax's be similar

131 Views Asked by At

Suppose that there are $n$ distinct objective functions $f_1,..,f_n$. And another $n$ distinct objective functions $g_1,..,g_n$.

Each $f_i: X \to R$, and each $g_i: X \to R$, where $X$ is some set (on which it's ok to place any restrictions - ex. you can make $X$ discrete, compact, whatever).

Let $\DeclareMathOperator{argmax}{argmax}x^*_{i,f} = \argmax f_i (x)$, and $x^*_{i,g} = \argmax g_i (x)$

If it is the case that $|\sum_i f_i(x) - \sum_i g_i(x)| < \frac{\epsilon}{n}$ for any $x$, then is it the case that $|\sum_{i = 1}^n x^*_{i, f} - x^*_{g,f}| < \frac{\delta}{n}$ for some positive $\delta$?

Colloquially, if the sum of the objective functions are close, will the sum of the argmax's be close?

1

There are 1 best solutions below

0
On

Let's let n = 1. Here is a counter-example, as I interpret the question.

Let f(x) = 0 for all x other than 0, at which f(0) = $\epsilon/2$.

Now choose and fix $\delta$. Let g(x) = 0 for all x other than $\delta$, at which $g(\delta) = \epsilon/2$.

$|f(x) - g(x)| < \epsilon$ for all x. But $|x_f^* - x_g^*| = \delta$, no matter what $\delta$ was picked.