I am trying to prove a convergence result on an iterative scheme which has the initial point defined as $$x_1 = \frac{1 - s(x_0)}{s(x_0)}$$ where s(x) is some unknown function.
Here is my theorem and attempted quick sketch of a proof:
For the function $s(x)$ defined as a general polynomial of the form $c_1x^{k_1} + c_2x^{k_2} + ... c_mx^{k_m}$ where $k_1 > k_2 > ... > k_m$ and $x \geq 0$, the convergence time of the algorithm is bounded by that of monic polynomials.
Proof: We proceed by bounding the polynomial cost function. For $0 \leq x < 1$, we have \begin{align*} c_1x^{k_m} < c_1x^{k_1} + c_2x^{k_2} + ... + c_mx^{k_m} < \tilde C x^{k_m} \end{align*} where $\tilde C := \sum_i^m c_i$ and identically for $x \geq 1$ \begin{align*} c_1x^{k_1} < c_1x^{k_1} + c_2x^{k_2} + ... + c_mx^{k_m} < \tilde C x^{k_1} \end{align*} For convenience, let $s_0 := c_1x^{k_1} + c_2x^{k_2} + ... + c_mx^{k_m}$. Using the above bound we demonstrate the following bounds on algorithm for the polynomial \begin{align*} c_1x^{k_m} &< s(x) < \tilde C x^{k_m} \\ \frac{1}{c_1x^{k_m}} - 1 &> \frac{1}{s(x)} - 1 > \frac{1}{\tilde C x^{k_m}} - 1 \end{align*} Thus, we have the algorithm bound \begin{align*} x_1(s=c_1x^{k_m}) > x_1(s=s_0) > x_1(s=\tilde C x^{k_m}) \end{align*} Lastly, manipulating the result from Banach we have \begin{align*} t \geq \ln\left(\frac{(1-L) |x_t - x^*|}{|x_1 - x_0|}\right) / \ln(L) \end{align*} and substituting the output of the algorithm for $x_1$ gives us \begin{align*} t \geq \ln\left(\frac{(1-L) |x_t - x^*|}{|x_1(s_0) - x_0|}\right) / \ln(L) \end{align*} Denote this bound as $\tau_{s_0}$. Combining the bound with the algorithm bound (tag) gives us \begin{align*} \tau_{c_1x_0^{k_m}} < \tau_{s_0} < \tau_{\tilde C x_0^{k_m}} \end{align*} bounding the polynomial function's convergence time with monomials. $\square$
