<p>Yes, it's possible with <span class="math-container">$O\left(\log^2(1/\epsilon)\right)$</span> function evaluations.</p>
<p>We write <span class="math-container">$f = (f_1,f_2)$</span>, so in your notation, e.g. <span class="math-container">$f_1(x,y) := f(x,y)_1$</span>. By replacing <span class="math-container">$f_1$</span> with <span class="math-container">$(x,y) \mapsto f_1(x,y)+\epsilon x$</span> and <span class="math-container">$f_2$</span> with <span class="math-container">$(x,y) \mapsto f_2(x,y)+\epsilon y$</span> (at the unimportant cost of changing <span class="math-container">$\epsilon$</span> to, say, <span class="math-container">$4\epsilon$</span>), we may assume that <span class="math-container">$f_1$</span> and <span class="math-container">$f_2$</span> are <em>strictly</em> increasing.</p>
<p>The key is that the monotonicity assumptions imply that the function <span class="math-container">$g : [-1,1] \to [-1,1]$</span> given by <span class="math-container">$$g(y) := f_2(x_y,y)$$</span> is continuous, where <span class="math-container">$x_y$</span> is the unique solution to <span class="math-container">$f_1(x_y,y) = 0$</span> (which exists since <span class="math-container">$f_1$</span> is strictly increasing and has <span class="math-container">$f_1(-1,y) \le 0 \le f_1(1,y)$</span>).</p>
<p>Indeed, it suffices to show that <span class="math-container">$x_{y_n} \to x_y$</span> whenever <span class="math-container">$y_n \to y$</span> (since <span class="math-container">$f_2$</span> is continuous). If, for contradiction, there were some <span class="math-container">$\delta &gt; 0$</span> and some subsequence <span class="math-container">$(y_{n_k})_k$</span> of <span class="math-container">$(y_n)_n$</span> with <span class="math-container">$x_{y_{n_k}} &gt; x_y+\delta$</span> for all <span class="math-container">$k$</span>, then <span class="math-container">$$0 = f_1(x_{y_{n_k}},y_{n_k}) \ge f_1(x_y+\delta,y_{n_k}) \to f_1(x_y+\delta,y) &gt; f_1(x_y,y) = 0,$$</span> where the limit is taken as <span class="math-container">$k \to \infty$</span>. The similar argument works for the case of some <span class="math-container">$\delta &gt; 0$</span> and some subsequence <span class="math-container">$(y_{n_k})_k$</span> with <span class="math-container">$x_{y_{n_k}} &lt; x_y-\delta$</span> for all <span class="math-container">$k$</span>.</p>
<p>Now that we know <span class="math-container">$g(y)$</span> is continuous, the bound <span class="math-container">$O\left(\log^2(1/\epsilon)\right)$</span> follows relatively straightforwardly from the bisection method. Indeed, for any fixed value of <span class="math-container">$y$</span>, the bisection method allows us to approximate <span class="math-container">$x_y$</span> up to an additive error of <span class="math-container">$\pm \epsilon$</span>, with <span class="math-container">$O\left(\log(1/\epsilon)\right)$</span> function evaluations. Because <span class="math-container">$f_2$</span> is Lipschitz, this allows us to calculate <span class="math-container">$g(y)$</span> up to an additive error of <span class="math-container">$\pm O(\epsilon)$</span>, which is sufficient to make the bisection method applied to the one-dimensional function <span class="math-container">$g$</span> work as needed, with <span class="math-container">$O\left(\log(1/\epsilon)\right)$</span> function evaluations of <span class="math-container">$g(y)$</span>.</p>

CC BY-SA 4.0
2023-04-23T17:20:56.647Z
Thanks! I am working on a paper that proves a slightly more generalized result (without the continuity condition), and some applications. I will be happy to add you as a co-author. By what name can I add you?
Erel Segal-Halevi
CC BY-SA 4.0
2023-04-27T06:41:13.830Z
@ErelSegal-Halevi Wow, thank you, I am honored. My name is Chester Lawrence (I have no affiliations nor grants to thank).
mathworker21
CC BY-SA 4.0
2023-05-24T20:32:58.737Z
I sent you a draft - did you get it?
Erel Segal-Halevi
CC BY-SA 4.0
2023-05-24T22:42:18.103Z
@ErelSegal-Halevi I just checked my spam and it was there. I'll look now.
mathworker21
CC BY-SA 4.0
2023-04-21T23:25:56.737Z
2023-04-21T23:25:56.737Z
mathworker21
<p>Let <span class="math-container">$f$</span> be a <a href="https://en.wikipedia.org/wiki/Lipschitz_continuity" rel="nofollow noreferrer">Lipschitz-continuous</a> function from the square <span class="math-container">$[-1,1]^2$</span> to itself, satisfying the following conditions:</p>
<ul>
<li>For all <span class="math-container">$y\in [-1,1]$</span>:    <span class="math-container">$~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$</span>, and <span class="math-container">$f(x,y)_1$</span> is monotonically-increasing with <span class="math-container">$x$</span>.</li>
<li>For all <span class="math-container">$x\in [-1,1]$</span>:    <span class="math-container">$~~~~f(x,-1)_2\leq 0\leq f(x,1)_2$</span>, and <span class="math-container">$f(x,y)_2$</span> is monotonically-increasing with <span class="math-container">$y$</span>.</li>
</ul>
<p>The <a href="https://en.wikipedia.org/wiki/Poincar%C3%A9%E2%80%93Miranda_theorem" rel="nofollow noreferrer">Poincare-Miranda theorem</a> guarantees that <span class="math-container">$f$</span> has a <em>root</em> -- a point <span class="math-container">$(x,y)$</span> for which <span class="math-container">$|f(x,y)|=0$</span>.</p>
<p>I am interested in computing an <em><span class="math-container">$\epsilon$</span>-root</em> of <span class="math-container">$f$</span> -- point <span class="math-container">$(x,y)$</span> for which <span class="math-container">$|f(x,y)|\leq \epsilon$</span>. The number of function evaluations should be polynomial in <span class="math-container">$\log_2(1/\epsilon)$</span> --- the binary representation of <span class="math-container">$\epsilon$</span> <sub>(where the Lipschitz constant is considered a fixed parameter)</sub>. <strong>Is it possible?</strong></p>
<hr />
<p>To motivate the question, here are some related results.</p>
<ol>
<li><p>If the function is one-dimensional (from <span class="math-container">$[-1,1]$</span> to itself), then the <a href="https://en.wikipedia.org/wiki/Bisection_method" rel="nofollow noreferrer">bisection method</a> can be used to find <span class="math-container">$\epsilon$</span>-root of <span class="math-container">$f$</span> using <span class="math-container">$O(\log(1/\epsilon))$</span> evaluations. This is true even without the monotonicity conditions.</p>
</li>
<li><p>Without the monotonicity conditions, finding an <span class="math-container">$\epsilon$</span>-root is computationally equivalent to finding an <span class="math-container">$\epsilon$</span>-fixed-point. It is <a href="https://www.sciencedirect.com/science/article/pii/0885064X89900174?via%3Dihub" rel="nofollow noreferrer">known</a> that finding an <span class="math-container">$\epsilon$</span>-fixed-point in two dimensions might require <span class="math-container">$\Omega(1/\epsilon)$</span> evaluations, that is, the number of evaluations is exponential in the binary representation of <span class="math-container">$\epsilon$</span>. (I <a href="https://cs.stackexchange.com/q/159373/1342">asked about it in this cs.SE post</a>.)</p>
</li>
</ol>
<p>Can the monotonicity condition make the two-dimensional problem polynomial in <span class="math-container">$\log(1/\epsilon)$</span>?</p>
<p>I am also interested in references to other conditions,  similar to monotonicity, that make the two-dimensional problem polynomial in <span class="math-container">$\log(1/\epsilon)$</span>.</p>

CC BY-SA 4.0
2023-04-16T15:34:06.833Z
Is $f(-1,y)\leq 0\leq f(1,y)$ supposed to be $f(-1,y)_1 \leq 0\leq f(1,y)_1$?
mathworker21
CC BY-SA 4.0
2023-04-16T17:05:26.083Z
Shouldn't the running time also depend on the Lipschitz constant?
Chao Xu
CC BY-SA 4.0
2023-04-16T21:19:09.850Z
This probably answers the question: https://link.springer.com/chapter/10.1007/11561071_78
Chao Xu
CC BY-SA 4.0
2023-04-17T09:24:23.343Z
@mathworker21 yes, fixed.
Erel Segal-Halevi
CC BY-SA 4.0
2023-04-17T11:54:37.837Z
@ChaoXu yes, the runtime also depends on the Lipschitz constant. For simplicity, I assumed that it is a fixed constant. The paper you linked to is very interesting, but it considers functions from a 2-dimensional array to $\mathbb{R}$, not to to $\mathbb{R}^2$. Also, the property of monotonicity is defined differently.
Erel Segal-Halevi
<approximation-algorithms><time-complexity><na.numerical-analysis><computing-over-reals><fixed-points>
Computing an approximate root of a two-dimensional monotone function
Erel Segal-Halevi
# Computing an approximate root of a two-dimensional monotone function

(Asked by: username_0 on 2023-04-16)

Let $f$ be a [Lipschitz-continuous](https://en.wikipedia.org/wiki/Lipschitz_continuity) function from the square $[-1,1]^2$ to itself, satisfying the following conditions:

* For all $y\in [-1,1]$: $~~~~f(-1,y)\_1\leq 0\leq f(1,y)\_1$, and $f(x,y)\_1$ is monotonically-increasing with $x$.
* For all $x\in [-1,1]$: $~~~~f(x,-1)\_2\leq 0\leq f(x,1)\_2$, and $f(x,y)\_2$ is monotonically-increasing with $y$.

The [Poincare-Miranda theorem](https://en.wikipedia.org/wiki/Poincar%C3%A9%E2%80%93Miranda_theorem) guarantees that $f$ has a *root* -- a point $(x,y)$ for which $|f(x,y)|=0$.

I am interested in computing an *$\epsilon$-root* of $f$ -- point $(x,y)$ for which $|f(x,y)|\leq \epsilon$. The number of function evaluations should be polynomial in $\log\_2(1/\epsilon)$ --- the binary representation of $\epsilon$ (where the Lipschitz constant is considered a fixed parameter). **Is it possible?**

---

To motivate the question, here are some related results.

1. If the function is one-dimensional (from $[-1,1]$ to itself), then the [bisection method](https://en.wikipedia.org/wiki/Bisection_method) can be used to find $\epsilon$-root of $f$ using $O(\log(1/\epsilon))$ evaluations. This is true even without the monotonicity conditions.
2. Without the monotonicity conditions, finding an $\epsilon$-root is computationally equivalent to finding an $\epsilon$-fixed-point. It is [known](https://www.sciencedirect.com/science/article/pii/0885064X89900174?via%3Dihub) that finding an $\epsilon$-fixed-point in two dimensions might require $\Omega(1/\epsilon)$ evaluations, that is, the number of evaluations is exponential in the binary representation of $\epsilon$. (I [asked about it in this cs.SE post](https://cs.stackexchange.com/q/159373/1342).)

Can the monotonicity condition make the two-dimensional problem polynomial in $\log(1/\epsilon)$?

I am also interested in references to other conditions, similar to monotonicity, that make the two-dimensional problem polynomial in $\log(1/\epsilon)$.

**Tags:** approximation-algorithms, time-complexity, na.numerical-analysis, computing-over-reals, fixed-points
> **Comments:**
> **username_1**: Is $f(-1,y)\leq 0\leq f(1,y)$ supposed to be $f(-1,y)_1 \leq 0\leq f(1,y)_1$?  
> **username_2**: Shouldn't the running time also depend on the Lipschitz constant?  
> **username_2**: This probably answers the question: https://link.springer.com/chapter/10.1007/11561071_78  
> **username_0**: @mathworker21 yes, fixed.  
> **username_0**: @ChaoXu yes, the runtime also depends on the Lipschitz constant. For simplicity, I assumed that it is a fixed constant. The paper you linked to is very interesting, but it considers functions from a 2-dimensional array to $\mathbb{R}$, not to to $\mathbb{R}^2$. Also, the property of monotonicity is defined differently.  

---

## 1 answers

### Answer by username_1 on 2023-04-21. Score: 3 | Accepted answer

Yes, it's possible with $O\left(\log^2(1/\epsilon)\right)$ function evaluations.

We write $f = (f\_1,f\_2)$, so in your notation, e.g. $f\_1(x,y) := f(x,y)\_1$. By replacing $f\_1$ with $(x,y) \mapsto f\_1(x,y)+\epsilon x$ and $f\_2$ with $(x,y) \mapsto f\_2(x,y)+\epsilon y$ (at the unimportant cost of changing $\epsilon$ to, say, $4\epsilon$), we may assume that $f\_1$ and $f\_2$ are *strictly* increasing.

The key is that the monotonicity assumptions imply that the function $g : [-1,1] \to [-1,1]$ given by $$g(y) := f\_2(x\_y,y)$$ is continuous, where $x\_y$ is the unique solution to $f\_1(x\_y,y) = 0$ (which exists since $f\_1$ is strictly increasing and has $f\_1(-1,y) \le 0 \le f\_1(1,y)$).

Indeed, it suffices to show that $x\_{y\_n} \to x\_y$ whenever $y\_n \to y$ (since $f\_2$ is continuous). If, for contradiction, there were some $\delta > 0$ and some subsequence $(y\_{n\_k})\_k$ of $(y\_n)\_n$ with $x\_{y\_{n\_k}} > x\_y+\delta$ for all $k$, then $$0 = f\_1(x\_{y\_{n\_k}},y\_{n\_k}) \ge f\_1(x\_y+\delta,y\_{n\_k}) \to f\_1(x\_y+\delta,y) > f\_1(x\_y,y) = 0,$$ where the limit is taken as $k \to \infty$. The similar argument works for the case of some $\delta > 0$ and some subsequence $(y\_{n\_k})\_k$ with $x\_{y\_{n\_k}} < x\_y-\delta$ for all $k$.

Now that we know $g(y)$ is continuous, the bound $O\left(\log^2(1/\epsilon)\right)$ follows relatively straightforwardly from the bisection method. Indeed, for any fixed value of $y$, the bisection method allows us to approximate $x\_y$ up to an additive error of $\pm \epsilon$, with $O\left(\log(1/\epsilon)\right)$ function evaluations. Because $f\_2$ is Lipschitz, this allows us to calculate $g(y)$ up to an additive error of $\pm O(\epsilon)$, which is sufficient to make the bisection method applied to the one-dimensional function $g$ work as needed, with $O\left(\log(1/\epsilon)\right)$ function evaluations of $g(y)$.

> **Comments:**
> **username_0**: Thanks! I am working on a paper that proves a slightly more generalized result (without the continuity condition), and some applications. I will be happy to add you as a co-author. By what name can I add you?  
> **username_1**: @ErelSegal-Halevi Wow, thank you, I am honored. My name is Chester Lawrence (I have no affiliations nor grants to thank).  
> **username_0**: I sent you a draft - did you get it?  
> **username_1**: @ErelSegal-Halevi I just checked my spam and it was there. I'll look now.  

---

