TITLE: Help explain why the proof works - Gradient Estimate Using the Maximum Principle
QUESTION [2 upvotes]: I found the following proposition and proof in a textbook for one of my classes, and the end of the proof seems a little "unfinished" to me.  In other words, as the author left it, I'm not entirely sure how what he/she did actually gives us what we want.
Here is the Proposition:

Let $\Omega \subset \subset \mathbb{R}^{n}$, and let $u \in C^{3}(\Omega) \cap C^{1} (\overline{\Omega})$ be a solution of the non-linear PDE
  $$Lu=f(x,u)\quad \text{on}\,\Omega, $$
  where $L = a_{ij}D_{i}{j}$ (the Laplacian) is an elliptic partial differential operator with $a_{ij}\in C^{1}(\overline{\Omega})$, and $0 < \lambda \leq (a_{ij}) \leq \Lambda$ (the ellipticity condition). The function $f$ is in $C^{1}(\overline{\Omega} \times \mathbb{R})$.
  Show that we must have
$$\sup_{\Omega}|Du|\leq \sup_{\partial \Omega}|Du|+C,$$
where $C$ is a constant depending only on the diameter of the domain $\Omega$, the lower bound $\lambda$, and the $C^{1}$ norms $||a_{ij}||_{C^{1}(\overline{\Omega}\times I)}$, where $I = \left[ \inf_{\overline{\Omega}}u, \sup_{\overline{\Omega}}u\right]$ is the range of the solution $u$.

The Essence of the Proof:

The author begins by calculating $L|Du|^{2}$, and then, by differentiating, etc., and using the ellipticity condition, establishes the following lower bound:
  $$L|Du|^{2} \geq \frac{\lambda}{2}|D^{2}u|^{2}-C_{1}|Du|^{2}-C_{2}.$$
He then goes on to establish the following lower bound for $L(|Du|^{2}+\alpha u^{2})$:
$$ L(|Du|^{2}+\alpha u^{2}) \geq \frac{\lambda}{2}|D^{2}Du|^{2} + |Du|^{2} - C_{3},$$
where we have chosen $\alpha > 0$ to be large.
However, there is apparently a problem with $C_{3}$, because it came from the terms $2\alpha u f - C^{\prime}$, where $C^{\prime}$ was another constant from an intermediate step, and is dependent on the sup norm of $u$. (At least, I think that's what the problem is, but I'm not entirely sure: maybe it's just to make sure that the $C_{3}$ is not too negative?)
To control the $C_{3}$ term, we introduce yet another function, $e^{\beta x_{1}}$, for $\beta > 0$.
Then, the following lower bound is established for $L(|Du|^{2}+\alpha u^{2}+e^{\beta x_{1}}$:
$$L(|Du|^{2}+\alpha u^{2}+e^{\beta x_{1}}) \geq \frac{\lambda}{2}|D^{2}Du|^{2} + |Du|^{2} + \left\{\beta^{2}a_{11}e^{\beta x_{1}}-C_{4} \right\}. $$
If we put the domain $\Omega \subset \{ x_{1} > 0 \}$, then $e^{\beta x_{1}}\geq 1$, $\forall x \in \Omega$.
So, by choosing $\beta$ large, we may make the $\displaystyle \beta^{2}a_{11}e^{\beta x_{1}}-C_{4}$ positive.
Then, if we set
  $$w = |Du|^{2}+\alpha|u|^{2} + e^{\beta x_{1}}$$
  for large $\alpha$, $\beta$ depending only on the diameter of $\Omega$, $diam(\Omega)$, $\lambda$, and the $C^{1}$ norms $||a_{ij}||_{C^{1}(\overline{\Omega})}$ and $||f||_{C^{1}(\overline{\Omega} \times I)}$, where $I = \left[ \inf_{\overline{\Omega}}u, \sup_{\overline{\Omega}}u\right]$ is the range of the solution $u$, then we obtain that
$$ Lw \geq 0 \quad \text{in}\,\Omega.$$
And by the Maximum Principle, we have that
$$ \sup_{\Omega}w \leq \sup_{\partial \Omega}w.$$

Now, my question is how does the very last statement in the proof give us that $\mathbf{\sup_{\Omega}|Du|\leq \sup_{\partial \Omega}|Du| + C}$, where $C$ is a constant fulfilling all the conditions mentioned in the statement of the proposition?
If someone could show me how this follows, I would be eternally grateful!
Thanks in advance :)

REPLY [1 votes]: I do not suppose this to be an answer, but comments are not permitted without login. May be you should specify which side of the inequality makes the trouble.
Obviously the argument follows a standard one which I just met in on page 14
(Theorem 8.1) of http://arxiv.org/pdf/math/0309021 . Does looking at that short proof help?
In the definition of $w$, I suggest to replace $|u|^2$ by $|u-x_0|^2$.
This of course does not change values of second order differential operator $L$.
(BTW, I suppose a derivative is missing in the definition of $L$.)
I do not understand the exponential term with $\beta$, therefore let us omit that for the purpose of this note
(or set $\beta=0$).
This way (with minus $x_0$ and no $\beta$) we see that for any fixed $x_0$, we have that $|Du(x_0)|^2 = w(x_0) \le \sup_\Omega w$ which is left hand side of the inequality. Then the other side of the inequality is supposed to be less than $\sup _ {\partial \Omega} |Du|^2$
which is, in the PDF file cited above, achieved by a different form of $w$ (zeroing the other terms on the boundary).
Thus for any fixed $x_0$ we estimated $|Du(x_0)|^2$. (Or we should/would.)
Might this be a half an answer?


TITLE: If $|ax^2 + bx + c| \le 1$ for all $x$ in $[0,1]$ then evaluate $|a|$, $|b|$ and $|c|$
QUESTION [2 upvotes]: Solve the following:
If $|ax^2 + bx + c| \le 1$ for all $x$ in $[0,1]$, then
i) $|a| \le 8$
ii) $|b| \ge 8$
iii) $|c| \le 1$
iv) $|a| + |b| + |c| \le 17$

Solution from my textbook:

Put $x = 0, 1 \text{ and } \frac{1} {2}$ to get:
$$|c| \le 1$$
$$|a + b + c| \le 1$$
$$|a + 2b + 4c| \le 4$$
From the above three equations, we get,
$|b| \le 8 \text{ and } |a| \le 8$.
Therefore, $|a| + |b| + |c| \le 17$

However, I don't understand: how, from the three equations, can you find the values of $|a|$ and $|b|$?

REPLY [1 votes]: Let $f(x)=ax^2+bx+c$.
Thus, $$a+b+c=f(1),$$
$$\frac{1}{4}a+\frac{1}{2}b+c=f\left(\frac{1}{2}\right)$$ and $$c=f(0),$$ which gives
$$b=4f\left(\frac{1}{2}\right)-f(1)-3f(0),$$ $$a=2f(1)+2f(0)-4f\left(\frac{1}{2}\right)$$ and by the triangle inequality we obtain: $$|a|+|b|+|c|\leq2+2+4+4+1+3+1=17.$$
It's interesting that for $f(x)=8x^2-8x+1$ we have an equality.


TITLE: Square of integrable function is integrable
QUESTION [0 upvotes]: How do I show that if $f$ is integrable on $[a,b]$, then so is $f^2$ using the fact that $|f^2(x)-f^2(y)|\leq 2M|f(x)-f(y)|$ for $|f(x)|\leq M$ for all $x\in[a,b]$?

REPLY [0 votes]: $$\int_a^b f^2(x) dx \\ \leq \int_a^b |f^2(x) -f^2(y) + f^2(y)|dx\\ \leq \int_a^b |f^2(x)-f^2(y)| +f^2(y) dx \\ \leq2M\int_a^b|f(x)-f(y)|dx + C(b-a) \\ \leq2M\int_a^b|f(x)| + 2C(b-a) <\infty $$


TITLE: Show that for G be a abelian group, $g \in G, g^m=1$, where $m=|G|$
QUESTION [2 upvotes]: I am pretty sure there is a name for the following theorem, but unfortunately, I don't known it.
Theorem. Let $G$ be a abelian group with $m=|G|$, than for any $g \in G, g^m=1$.
Currently I don't have ideas how to approach a proof of this theorem, and will appreciate any help.

REPLY [11 votes]: There's a well-known elementary version for the case of abelian groups, that does not appeal to Lagrange's theorem.
Consider
$$
X = \prod_{x \in G} x.
$$
Since $G$ is abelian, the order within the product is immaterial.
Since the map
$$
G \to G, \qquad x \mapsto g x
$$
is a bijection, we have
$$
X = \prod_{x \in G} x = \prod_{x \in G} g x = g^{m} \prod_{x \in G} x = g^{m} X,\tag{X}
$$
where we have used again the fact that $G$ is abelian to take the $g$'s out of the product.
From (X) you get
$$
g^{m} = 1.
$$


TITLE: find $T$ so that $T \oplus W = M_{2 \times 3}(\mathbb R)$
QUESTION [0 upvotes]: Given
$$ W = \operatorname{span}\left\{\pmatrix{1&1&1\\ 1&2&3}, \pmatrix{1&0&1\\2&2&3}\right\},$$
Find $T$ so that $M_{2\times 3}(\mathbb R) = W \oplus T$.

How can I solve this problem?

REPLY [1 votes]: Here's a hint to one approach:
Sketch of Solution: It suffices to find a basis of the nullspace of the matrix
$$
A =
\pmatrix{1&1&1 & 1&2&3\\
1&0&1&2&2&3},
$$
whose rows are formed from the "vectorized" versions of the given matrices. Once we have a basis $w_1,w_2,w_3,w_4$ of this nullspace, we find that the vectors $v_1,v_2,w_1,w_2,w_3,w_4$ form a basis of $\Bbb R^6$. It follows that when we "unvectorize" these vectors, we get a basis of $\Bbb R^{2 \times 3}$.
The unvectorized versions of $w_1,\dots,w_4$ will form a basis of a space $T$ for which $\Bbb R^{2\times 3} = W \oplus T$.


TITLE: A question on measurable space and $\sigma$-algebra generated by a familly of subsets
QUESTION [0 upvotes]: Let $(E, \mathbb M)$ be a measurable space and $\mathbb C$ be a familly of subsets of $E$. Show that, for every $B \in \sigma(\mathbb C)$, there exists a countable familly $\mathbb D \subset \mathbb C$ such that $B \in \sigma(\mathbb D)$. ($\sigma(X)$ is the $\sigma$-algebra generated by $X$)
Denote $\mathbb G = \{ B \in \sigma(\mathbb C)$ such that there exists a countable familly $\mathbb D \subset \mathbb C$ satisfies $B \in \sigma(\mathbb D) \}$.
We can show that $\mathbb G$ is a $\sigma$-algebra on $E$. Now I have $2$ questions:

Why does this imply $\mathbb G = \sigma(\mathbb C)$? (We have $\mathbb G \subset \sigma(\mathbb C)$ and $\sigma(\mathbb C)$ is the smallest $\sigma$-algebra containing $\mathbb C$. Thus, it suffices to show that $\mathbb C \subset \mathbb G$)
Why does $\mathbb G = \sigma(\mathbb C)$ imply the conclusion?

REPLY [1 votes]: 1. Take $\mathbb{D}=\mathbb{C}$. Therefore $\mathbb{C}\subset\mathbb{G}$.
2. By definition of $\mathbb{G}$: For all $B\in\sigma(\mathbb{C})=\mathbb{G}$ there is a countable familly $\mathbb{D}\subset\mathbb{C}$ such that $B\in\sigma(\mathbb{D})$.


TITLE: Matrix multiplication with variables
QUESTION [0 upvotes]: How would I go about solving this? Not sure how to isolate the variable to solve for X. Thank you for any help!

$$\begin{pmatrix}-6&8\\2&3\end{pmatrix}X  + \begin{pmatrix}-2&-2\\2&-2\end{pmatrix} = \begin{pmatrix}-2&5\\-5&8\end{pmatrix}X $$

I know that I'd have to take the inverse of the first matrix, which would give me x + the second matrix = inverse of first matrix *third matrix * x. But how would I go from there?

REPLY [0 votes]: This is the easy way to understanding this question, however it needs lots of work.
enter image description here
enter image description here


TITLE: Solve for "x" and "y"
QUESTION [1 upvotes]: What would be the easiest way to solve the following set of equations:$$
x +  y^2 = 7 $$$$ x^2 + y = 11$$
I've been trying substitution method but end up in a $4$th degree bi-quadratic equation. Thanks for your time!
EDIT: Final equation: $y^4 - 14y^2 + y + 38 = 0$. I'm only concerned about the real solutions. Is it possible to write it as a product of two quadratic equations?

REPLY [1 votes]: First note that your two original equations represents two parabolas with orthogonal axes, so they have four intersection points, i.e. the systems has four solutions.
Your equation $y^4-14y^2+y+38=0$ has the obvious solution $y=2$ so it factorize in:
$$
(y-2)(y^3+2y^2-10y-19)=0
$$
Since a cubic has always a real solution there are at least two real solution of your quartic.
Now you can study the function $f(y)=y^3+2y^2-10y-19$ . The derivative is $f'=3y^2+4y-10 $ and you can solve the second degree equation for stationary points, finding two real solutions $y=\dfrac{-2\pm\sqrt{34}}{3}$.
With a bit of work you can see that the function has a positive maximum  and a negative minimum, so it must have three real solutions as we expected.


TITLE: Turning point where A>B becomes B>A
QUESTION [0 upvotes]: For the relationship
$$A^2=246*B^5=C$$
When $ C>1$, $$A>B$$ for certain values of C such as $0.25$
$$ A>B$$
$$ A^2=246*B^5=0.25\,$$
$$ A=\sqrt{0.25}=0.5\,$$
$$ B=(0.25/256)^{1/5}=0.25$$
$$\ ∴A>B\,$$
But when C gets closer to $0$ e.g. $3\cdot 10^{-3}$
$$ B>A$$
$$ A^2=246*B^5=3\cdot 10^{-3},$$
$$ A=\sqrt{3\cdot 10^{-3}}=0.05$$
$$ B=(3\cdot 10^{-3}/256)^{1/5}=0.1$$
$$\ ∴B>A\,$$
1.Where is (or how do I find) the turning point between when $A>B$ to $B>A$?
I know it is somewhere at a positive near $0$ value.
2.Why does this occur at such an unusual place? E.g. if $A>B$ for all values over $0$ and  $B>A$ for all values <$0$ this would make some sense, but what does it occur at a value between $3E-3$ and $0.25$.

If you are after some context, I ran into the problem when working on a question I asked on Chemistry Stack Exchange here but it is a bit out of scope.

REPLY [1 votes]: The turning point is when $A=B$, that is $A^2=246A^5$ or $A=\frac{1}{\sqrt[3]{246}}$. Then $$C=A^2=\frac{1}{246^{2/3}}=\frac{\sqrt[3]{246}}{246}.$$


TITLE: Convergence of eigenvectors
QUESTION [1 upvotes]: Let $T$ be a compact operator on $l^2$. Let $T_n$ be finite rank operators and $T_n \to T$ in the operator norm. Is it true that the eigenvalues and eigenvectors of $T_n$ converge to eigenvalues and eigenvectors of $T$?

REPLY [0 votes]: For eigenvectors there is no chance. One may approximate the identity map $T$ on $\Bbb R^2$ with a symmetric matrix $T_n$ whose eigenvalues are $1$ and $1-1/n$. The eigenvectors are perpendicular to each other, but otherwise their direction is entirely optional. So by choosing directions erratically one can avoid convergence. Of course some subsequence will converge.


TITLE: Connect a set of nodes with another set of the same size without intersections
QUESTION [1 upvotes]: I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection

REPLY [0 votes]: Here is a solution: A graph $G$ is planar then $|E(G)|\leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| \leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9\leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| \leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $\sum_{a\in F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|\leq\sum_{a\in F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.


TITLE: Is sup of max, same as max of sup?
QUESTION [2 upvotes]: Let $\sigma_1, \sigma_2 \dots \sigma_n$ be functions of $\omega \in \mathbb{R}_+$.
Is $\sup_{\omega}(\max_{i=1:n} (\sigma_i))$ same as $\max_{i=1:n}( \sup_{\omega}(\sigma_i))$?
Could you also please give me more insight by giving some related references?

REPLY [3 votes]: First, for each $i=1:n$ it is obvious that $\sup_{\omega}(\sigma_i)\le \sup_{\omega}(\max_{i=1:n} (\sigma_i))$ as the LHS sup is taken over a no greater function than in the RHS. And from this follows $\max_{i=1:n}( \sup_{\omega}(\sigma_i))\le \sup_{\omega}(\max_{i=1:n} (\sigma_i))$.
Second, it is also clear that for each $\omega$, we have $(\max_{i=1:n} (\sigma_i))\le \max_{i=1:n}( \sup_{\omega}(\sigma_i))$, because the max on LHS is taken over a set of numbers $\sigma_i(\omega)$, each of which is no greater than their counterpart in RHS, namely $\sup_\omega\sigma_i(\omega)$. Hence $\sup_\omega(\max_{i=1:n} (\sigma_i))\le \max_{i=1:n}( \sup_{\omega}(\sigma_i))$
Therefore the two sides equal.


TITLE: Series expansion as a means of 'proving' Simpson's Rule?
QUESTION [1 upvotes]: I've been working out questions regarding Newton Raphson and Simpson's Rule, whilst they're fairly easy to execute, the latter seems to boggle my mind a little bit more in terms of what the examiner's usually ask. Below is a part of a question (which is an amallgemation of the previous two).

Evaluate the integral $\int_{0}^{0.4} \ln(1+x^3)dx$ by means of (i) Simpson's Rule with an interval width of $h = 0.1$ and (ii) Integrating the first two terms of the series expansion of $\ln(1+x^3)$. Give answer to 4 d.p

So working the first one out went quite well, my answer boiled down to $$\int_{0}^{0.4} \ln(1+x^3)dx \approx 0.0063$$
However the second part is where my mind is blown as I'm not sure what he's asking for. I do remember something to do with the expansion of $\ln$ being something like $(-1)^{r-1} \frac{x^r}{r}$ however am not sure how this applies to Simpson's rule or anything similar to it.
I presume that this question is to prove the accuracy of the above approximation.

REPLY [1 votes]: The second part is a different method of approximation, unrelated to Simpson's rule: By the geometric series formula $1/(1 + t) = 1 - t + t^{2} - \cdots$ for $|t| < 1$, and the fact that a convergent power series may be integrated term by term,
$$
\ln(1 + u)
  = \int_{0}^{u} \frac{1}{1 + t}\, dt
  = \int_{0}^{u} [1 - t + \cdots]\, dt
  = u - \frac{u^{2}}{2} + \cdots\quad\text{for $|u| < 1$.}
$$
Substituting $u = x^{3}$, $\ln(1 + x^{3}) \approx x^{3} - \frac{1}{2} x^{6}$ for $|x| < 1$. So, you can integrate this polynomial approximation using the fundamental theorem of calculus, and use the value as a numerical approximation of
$$
\int_{0}^{0.4} \ln(1 + x^{3})\, dx.
$$

 Answer: $\frac{1}{4}(0.4)^{4} - \frac{1}{14}(0.4)^{7} \approx 0.0063$.


TITLE: Evaluate the antiderivative at a particular point without integrating
QUESTION [0 upvotes]: If $g(x)$ is the antiderivative of $f(x)=\frac{e^x}{x^2}\:$   and $\:g(3)=0$, what is $g(6)$? $\:\:\:$If it were a function I could integrate, it'd be a snap - but not this one.
It feels like it should be relatively easy and using FTC 2. I'm sure I'm missing the obvious...
Can anyone help?
Thanks!!
Anna

REPLY [0 votes]: We have $$g(x)=\int_a^x\frac{e^t}{t^2}\,\mathrm{d}t,$$ for some value of $a$. Since $g(3)=0$ it must be that $a=3$, and $$g(6)=\int_3^6\frac{e^t}{t^2}\,\mathrm{d}t$$  I don't see how one can do any better than this.


text:
\section{Deterministic ZO with Residual Feedback}
\label{sec:det}
\vspace{-5pt}
In this section, we consider the problem (P),

where the objective function evaluation is fully deterministic. To solve this problem, we propose a zeroth-order estimate of the gradient based on the following one-point residual feedback scheme
\begin{align}
\text{(Residual feedback): } \;\;\; \widetilde{g}(x_t) := \frac{u_t}{\delta}\big(f(x_t + \delta u_t) - f(x_{t-1} + \delta u_{t-1})\big), \label{eqn:GradientEstimate_Noiseless}
\end{align}

where $u_{t-1}$ and $u_t$ are independent random vectors sampled from the standard multivariate Gaussian distribution. To elaborate, the gradient estimate in \eqref{eqn:GradientEstimate_Noiseless} evaluates the function value at one perturbed point $x_t + \delta u_t$ at each iteration $t$ and the other function value evaluation $f(x_{t-1} + \delta u_{t-1})$ is inherited from the previous iteration.
Therefore, it is a one-point feedback scheme based on the residual between two consecutive feedback points, and we name it {\it one-point residual feedback}.
Next, we show that this estimator is an unbiased gradient estimate of the smoothed function $f_\delta(x)$ at $x_t$.
\begin{lem}
	\label{lem:UnbiasedEstimate_Noiseless}

	We have that $\mathbb{E}\big[\tilde{g}(x_t)\big] = \nabla f_\delta(x_t)$ for all $x_t \in  \mathbb{R}^d$.
\end{lem}
\begin{proof}
	Taking the expectation of $\tilde{g}(x_t)$ in \eqref{eqn:GradientEstimate_Noiseless} with respect to the random vectors $u_t$ and $u_{t-1}$, we obtain that

	\begin{align*}
\mathbb{E}\big[\tilde{g}(x_t)\big] = \frac{1}{\delta}\mathbb{E}\big[ f(x_t + \delta u_t)  u_t - f(x_{t-1} + \delta u_{t-1})u_t\big] =  \frac{1}{\delta}\mathbb{E}\big[f(x_t + \delta u_t) u_t \big] = \nabla f_\delta(x_t),
\end{align*}
	where the second equality follows from the fact that $u_{t}$ is independent from $u_{t-1}$ and $x_{t-1}$ and has zero mean. The last equality is a fact proved in \cite{nesterov2017random}.
\end{proof}

Since $\tilde{g}(x_t)$ is an unbiased estimate of $\nabla f_\delta(x_t)$, we can use it in Stochastic Gradient Descent (SGD) as follows
\begin{equation}
\label{eqn:SGD}
x_{t+1} = x_t - \eta \tilde{g} (x_t),
\end{equation}
where $\eta$ is the stepsize. To analyze the convergence of the above ZO algorithm with residual feedback, we need to bound the variance of the gradient estimate under proper choices of the exploration parameter $\delta$ in \eqref{eqn:GradientEstimate_Noiseless} and the stepsize $\eta$. In the following result, we present the bounds on the second moment of the gradient estimate $\mathbb{E}[\| \tilde{g}(x_t)\|^2]$, which will be used in our analysis later.

\begin{lem}
	\label{lem:BoundSecondMoment_Det}
	Consider a function $f \in C^{0,0}$ with Lipschitz constant $L_0$. Then, under the SGD update rule in~\eqref{eqn:SGD}, the second moment of the residual feedback satisfies
	\begin{equation*}
	\mathbb{E}[\|\tilde{g} (x_t)\|^2] \leq \frac{2 d L_0^2 \eta^2}{\delta^2} \mathbb{E}[ \|\tilde{g}(x_{t-1})\|^2] + 8L_0^2 (d+4)^2.
	\end{equation*}
	Furthermore, if $f(x)$ also belongs to $C^{1,1}$ with constant $L_1$, then the second moment of the residual feedback satisfies
	\begin{equation*}
	\mathbb{E}[\|\tilde{g} (x_t)\|^2] \leq \frac{2 d L_0^2 \eta^2}{\delta^2} \mathbb{E}[ \|\tilde{g}(x_{t-1})\|^2] \; + 8(d+4)^2 \|\nabla f(x_{t-1})\|^2 + 4L_1^2 (d+6)^3 \delta^2.
	\end{equation*}
\end{lem}
Lemma~\ref{lem:BoundSecondMoment_Det} shows that the second moment of the residual feedback $\mathbb{E}[\|\tilde{g} (x_t)\|^2]$ can be bounded by a perturbed contraction under the SGD update rule. This perturbation term is crucial to establish the iteration complexity of ZO with our residual feedback. In particular, with the traditional one-point feedback, the perturbation term is in the order of $O({\delta^{-2}})$ and significantly degrades the convergence speed \cite{hu2016bandit}. In comparison, our residual feedback induces a much smaller perturbation term. Specifically, when $f\in C^{0,0}$, the perturbation is the order of $O(L_0^2d^2)$ that is independent of $\delta$, and when $f\in C^{1,1}$, the perturbation is in the order of $O(d^2\|\nabla f(x_{t-1})\|^2 +L_1^2d^3\delta^2)$.
Therefore, it is expected that ZO with our residual feedback can achieve a better iteration complexity than that of ZO with the traditional one-point feedback.

\vspace{-3pt}
\subsection{Convergence Analysis}
\vspace{-3pt}
We first consider the case where the objective function $f$ is nonconvex. When $f$ is differentiable, we say a solution $x$  is $\epsilon$-accurate if $\mathbb{E}[\| \nabla f(x) \|^2 ]\le \epsilon$. However, when $f$ is nonsmooth, we follow the convention adopted in \cite{nesterov2017random} and define a solution $x$ to be $\epsilon$-accurate if $\mathbb{E}[ \| \nabla f_\delta(x) \|^2] \leq \epsilon$ holds for the Gaussian-smoothed function. In addition, we also require $f_\delta$ to be $\epsilon_f$-close to the original $f$, which requires $\delta \leq \frac{\epsilon_f}{L_0 \sqrt{d}}$ according to Lemma~\ref{lem:GaussianApprox}. Under this setup, the convergence rate of ZO with residual feedback is presented below. For simplicity, all the complexity results in this paper are presented in $\mathcal{O}$ notations. The explicit form of the constant terms can be found in the proof in the supplementary material.

\begin{thm}
	\label{thm:Nonconvex_Noiseless}
	Assume that $f \in C^{0,0}$ with Lipschitz constant $L_0$ and that $f$ is also bounded below by $f^\ast$. Moreover, assume that SGD in~\eqref{eqn:SGD} with residual feedback is run for $T>1/\epsilon_f$ iterations and that $\tilde{x}$ is selected from the $T$ iterates uniformly at random. Let also $\eta = \frac{\sqrt{\epsilon_f}}{2d L_0^2 \sqrt{T}}$ and $\delta = \frac{\epsilon_f}{ L_0 d^{\frac{1}{2}}}$. Then, we have that $\mathbb{E}\big[ \|\nabla f_\delta(\tilde{x}) \|^2\big]  = \mathcal{O}(d^2 \epsilon_f^{-0.5} T^{-0.5})$.

\end{thm}

Based on the above convergence rate result, the required iteration complexity to achieve a point $x$ that satisfies $|f(x) - f_\delta(x)| \leq \epsilon_f$ as well as $\mathbb{E}[ \|\nabla f(\tilde{x})\|^2 ] \leq \epsilon$ is of the order $\mathcal{O}(\frac{d^{4}}{ \epsilon_f \epsilon^2})$. This complexity result is close to the complexity result $\mathcal{O}(\frac{d^{3}}{ \epsilon_f \epsilon^2})$ of ZO with two-point feedback in \cite{nesterov2017random}.
When $f(x) \in C^{1,1}$ is a smooth function, we obtain the following convergence rate result for ZO with residual feedback.
\begin{thm}
	\label{thm:Nonconvex_NoiselessSmooth}
	Assume that $f(x) \in C^{0,0}$ with Lipschitz constant $L_0$ and that $f(x) \in C^{1,1}$ with Lipschitz constant $L_1$. Moreover, assume that SGD in \eqref{eqn:SGD} with residual feedback is run for $T$ iterations and that $\tilde{x}$ is selected from the $T$ iterates uniformly at random.
	Let also $\eta = \frac{1} { \widetilde{L} (d+4)^2 T^{\frac{1}{3}} }$, and $\delta = \frac{1}{\sqrt{d} T^{\frac{1}{3}}}$, where $\widetilde{L} = \max(2L_0,$ $32L_1)$. Then, we have that $\mathbb{E}\big[ \|\nabla f(\tilde{x})\|^2\big] = \mathcal{O}(d^2 T^{-\frac{2}{3}})$.

\end{thm}

In particular, to achieve a point $x$ that satisfies $\mathbb{E}\big[ \|\nabla f(\tilde{x})\|^2\big] \leq \epsilon$, the required iteration complexity is of the order $\mathcal{O}(d^3\epsilon^{-\frac{3}{2}})$. To the best of our knowledge, the best complexity result for ZO with two-point feedback is of the order $\mathcal{O}(d\epsilon^{-1})$, which is established in \cite{nesterov2017random}.
Next, we consider the case where the objective function $f$ is convex. In this case, the optimality of a solution $x$ is measured via the loss gap $f(x) - f(x^\ast)$, where $x^\ast$ is the global optimum of $f$.
\begin{thm}
	\label{thm:Convex_Noiseless}
	Assume that $f(x)\in C^{0,0}$ is convex with Lipschitz constant $L_0$. Moreover, assume that SGD in \eqref{eqn:SGD} with residual feedback is run for $T$ iterations and define the running average $\bar{x} = \frac{1}{T} \sum_{t=0}^{T-1} x_t$. Let also $\eta = \frac{1}{2 d L_0 \sqrt{T}}$ and $\delta = \frac{1}{\sqrt{T}}$.  Then, we have that $f(\bar{x})  - f(x^\ast) = \mathcal{O}(d T^{-0.5})$.

	Moreover, assume that additionally $f(x) \in C^{1,1}$ with Lipschitz constant   $L_1$, and let $\eta = \frac{1}{2 \tilde{L} (d+4)^2 T^{\frac{1}{3}}}$ and $\delta = \frac{\sqrt{d}}{T^{\frac{1}{3}}}$, where $\tilde{L} = \max\{L_0, 16L_1\}$. Then, we have that $f(\bar{x})  - f(x^\ast) = \mathcal{O}(d^2 T^{-\frac{2}{3}})$.

\end{thm}

To elaborate, to achieve a solution $x$ that satisfies $f(\bar{x}) - f(x^\ast) \leq \epsilon$, the required iteration complexity is of the order $\mathcal{O}(d^2\epsilon^{-2})$ when $f\in C^{0,0}$. Such a complexity result significantly improves the complexity $\mathcal{O}(d^2\epsilon^{-4})$ of ZO with the traditional one-point feedback and is slightly worse than the best complexity $\mathcal{O}(d\epsilon^{-2})$ of ZO with two-point feedback. On the other hand, when $f(x) \in C^{1,1}$, the required iteration complexity of ZO with residual feedback further reduces to $\mathcal{O}(d^{3}\epsilon^{-1.5})$, which is better than the complexity $\mathcal{O}(d\epsilon^{-3})$ of ZO with the traditional one-point feedback whenever $\epsilon< d^{-4/3}$.

config: arxiv


TITLE: Full Binary Trees - Maximizing the arithmetic mean of powers of leaf node levels.
QUESTION [0 upvotes]: I have a full binary tree with $n$ leaf nodes. Therefore we  get the following constraint $\sum_{i=1}^{n}2^{-l_{i}} = 1$ where $l_i$ is the level occupied by each leaf node.
I have the metric $\frac{1}{n}\sum_{i=1}^{n}2^{l_{i}}$.
What I would like to show is, that the more unbalanced the tree is, the higher the metric. Since there is no universal metric for tree unbalance-ness, I dont know how to go about it.
Possible Directions -

I tried to show that an act of unbalancing a tree increases the
metric.
I can show that the metric is lower bounded by $n$ using the
AM-HM inequality.

REPLY [0 votes]: Let $\ell_1$ be the minimum depth of a leaf and $\ell_n$ the maximum depth; since the tree is full, there must be a sibling pair of leaves at depth $\ell_n$. If $\ell_n\ge\ell_1+2$, remove a sibling pair at depth $\ell_n$, and give a leaf at depth $\ell_1$ a pair of children; this loses two leaves at depth $\ell_n$, adds one at depth $\ell_n-1$, adds two at depth $\ell_1+1$, and loses one at depth $\ell_1$, for a net change in $\sum_{k=1}^n2^{\ell_k}$ of
$$2^{\ell_n-1}-2\cdot 2^{\ell_n}+2\cdot 2^{\ell_1+1}-2^{\ell_1}=3\left(2^{\ell_1}-2^{\ell_n-1}\right)<0\,.$$
(I ignore the factor of $\frac1n$, since $n$ is not changed by this procedure.) Thus, as long as the tree is not balanced, this procedure will reduce your metric.