text:
# Lecture 10: Accelerating SGD with Averaging and Variance Reduction¶

## CS4787 — Principles of Large-Scale Machine Learning Systems¶

In [12]:
import numpy
import scipy
import matplotlib
from matplotlib import pyplot
import time

matplotlib.rcParams.update({'font.size': 14, 'figure.figsize': (10.0, 8.0)})

## Announcements¶

Third pset with released tonight.

## Recall¶

Over the past couple of lectures, we've been talking about how to accelerate gradient-based training. Specifically, we've been focusing on the condition number $\kappa$ as a source of difficulty in solving large-scale optimization problems from empirical risk minimization.|

• The number of steps of gradient descent required to guarantee a certain objective gap $\epsilon$ is proportional to the condition number, and so if an objective has a widely varying range of curvatures, it will take more time to solve.

However, we also said that we usually want to run SGD instead of GD to remove the dependence on $n$, the size of the dataset. And there was another significant term that affects the convergence of stochastic gradient descent: the variance of the noise $\sigma^2$.

• The further our stochastic gradient samples are from the "true" full gradient, the larger our "noise ball" will be.

• So, to achieve a target objective gap $\epsilon$, the larger $\sigma^2$ is, the smaller we'll need to set the fixed step size $\alpha$...and the more iterations we'll need to run.

We saw one way to address this when we looked at diminishing step size schemes. Today we'll look at a few more methods of doing this in more detail: increasing minibatch size schemes, averaging the iterates, and variance reduction.

### A Warm-up: Reducing the dependence on the variance by increasing the minibatch size¶

Recall that, in the non-strongly-convex case, we derived the convergence rate for minibatch with-replacement SGD

$$\frac{1}{T} \sum_{t = 0}^{T - 1} \Exv{ \norm{ \nabla f(w_t) }^2 } \le \underbrace{\frac{ 2 \left( f(w_0) - f^* \right) }{\alpha T}}_{\text{like gradient descent}} + \underbrace{\frac{\alpha \sigma^2 L}{B}}_{\text{"noise ball" term}}.$$

We saw a few lectures ago that we could achieve asymptotic convergence (rather than convergence to a noise ball) by decreasing the step size as iterations increase. The motivation: we can decrease the noise ball term to 0 as we train by decreasing $\alpha$.

Another way we can decrease this noise ball term is to increase the batch size $B$. Let's look at what happens when we do that.

### Recall: The assumptions we've been using¶

Assume the loss function is $L$-smooth ($\norm{\nabla f(w) - \nabla f(v)} \le L \cdot \norm{w - v}$, or equivalently for twice-differentiable functions $\Abs{ \frac{\partial^2}{\partial \eta^2} f(w + \eta v) } \le L \norm{v}^2$, i.e. the curvature in any direction is no larger in magnitude than $L$), and that the stochastic gradient variance at any $w$ is bounded by

$$\Exv{ \norm{ \nabla f_i(w) - \nabla f(w) }^2 } = \frac{1}{n} \sum_{i=1}^n \norm{ \nabla f_i(w) - \nabla f(w) }^2 \le \sigma^2.$$

Also suppose that the step size satisfies $\alpha \le 1/L$ (we used this in some of our proofs to simplify expressions by hiding $\alpha^2$ terms) and that $f$ actually has a global minimum $f^*$.

Recall that, from the analysis we did in Lecture 5 of the loss-at-the-next-timestep, we got

$$\Exv{ f(w_{t+1}) } \le \Exv{ f(w_t) } - \frac{\alpha}{2} \Exv{ \norm{ \nabla f(w_t) }^2 } + \frac{\alpha^2 \sigma^2 L}{2}.$$

Now, this is just for plain SGD (with no minibatching). If we used a with-replacement minibatch of size $B_t$ at time $t$, what would we get here instead? (Hint: think about how changing the minibatch size affects the variance of the stochastic gradient estimator.)

Using a with-replacement minibatch of size $B_t$ will decrease the variance by a factor of $B_t$. So we'd get:

$$\Exv{ f(w_{t+1}) } \le \Exv{ f(w_t) } - \frac{\alpha}{2} \Exv{ \norm{ \nabla f(w_t) }^2 } + \frac{\alpha^2 \sigma^2 L}{2 B_t}.$$

### Continuing the analysis¶

Starting from

$$\Exv{ f(w_{t+1}) } \le \Exv{ f(w_t) } - \frac{\alpha}{2} \Exv{ \norm{ \nabla f(w_t) }^2 } + \frac{\alpha^2 \sigma^2 L}{2 B_t}.$$

We can move the third term to the left side and the first term to the right, and then sum up over $T$ iterations to get

$$\frac{\alpha}{2} \sum_{t=0}^{T-1} \Exv{ \norm{ \nabla f(w_t) }^2 } \le \sum_{t=0}^{T-1} \left( \Exv{ f(w_t) } - \Exv{ f(w_{t+1}) } + \frac{\alpha^2 \sigma^2 L}{2 B_t} \right).$$

Most of this sum telescopes, so it simplifies to

\begin{align*}\frac{\alpha}{2} \sum_{t=0}^{T-1} \Exv{ \norm{ \nabla f(w_t) }^2 } &\le \Exv{ f(w_0) } - \Exv{ f(w_T) } + \frac{\alpha^2 \sigma^2 L}{2} \sum_{t=0}^{T-1} \frac{1}{B_t} \\&\le f(w_0) - f^* + \frac{\alpha^2 \sigma^2 L}{2} \sum_{t=0}^{T-1} \frac{1}{B_t},\end{align*}

where this last line follows since we let $f^* = \min_w f(w)$, so for any $w$, $-f(w) \le -f^*$.

Dividing both sides by $\alpha T / 2$ produces

$$\frac{1}{T} \sum_{t=0}^{T-1} \Exv{ \norm{ \nabla f(w_t) }^2 } \le \frac{2 ( f(w_0) - f^* ) }{\alpha T} + \frac{\alpha \sigma^2 L}{T} \sum_{t=0}^{T-1} \frac{1}{B_t}.$$

What does this tell us about how we need to set the batch size scheme $B_t$ for the left side of this inequality to be guaranteed to converge to 0?

Note that in practice if we're doing this sort of increasing batch-size scheme, we'd always want to do sampling without replacement, to take advantage of its lower variance as the batch size approaches the dataset size.

Questions?

## Polyak–Ruppert Averaging¶

Intuition: SGD is converging to a "noise ball" where the iterates are randomly jumping around some space surrounding the optimum. We can think about these iterates as random samples that approximate the optimum.

What can we do when we have a bunch of random samples that approximate something to improve the precision of our estimate?

Technique: run regular SGD and just average the iterates. That is,

\begin{align*} w_{t+1} &= w_t - \alpha_t \nabla f_{\tilde i_t}(w_t) \\ \bar w_{t+1} &= \frac{t}{t + 1} \cdot \bar w_t + \frac{1}{t+1} \cdot w_{t+1}; \end{align*}

eventually we output the average $\bar w_T$ at the end of execution. This is equivalent to writing

$$\bar w_T = \frac{1}{T} \sum_{t=1}^T w_t.$$

The main idea here is that we're averaging out a bunch of iterations $w_t$ that are all in the noise ball. When you average out a bunch of noisy things, often you are able to reduce the noise.

### Polyak Averaging: Intuition¶

We could prove Polyak averaging works for general convex problems. But that would be kinda involved, and doesn't deliver much intuition for why it makes sense. So, to maximize the relatability, we're going to go back to our old friend the one-dimensional quadratic, to get a sense of why this works. Suppose we have some dataset $u_1, \ldots, u_n \in \R$, and define the loss

$$f(w) = \frac{1}{n} \sum_{i=1}^n f_i(w) = \frac{1}{n} \sum_{i=1}^n \frac{1}{2} (w + u_i)^2.$$

Here, $\nabla f_i(w) = w + u_i$. For simplicity, suppose that

$$\frac{1}{n} \sum_{i=1}^n u_i = 0 \;\;\text{ and }\;\; \frac{1}{n} \sum_{i=1}^n u_i^2 = \sigma^2,$$

so that

$$f(w) = \frac{1}{n} \sum_{i=1}^n \frac{1}{2} (w^2 + 2 u_i w + u_i^2) = \frac{w^2 + \sigma^2}{2}.$$

Suppose that we run SGD on this with a constant learning rate $0 < \alpha \le 1$. Then,

\begin{align*}w_{t+1} &= w_t - \alpha \nabla f_{i_t}(w_t) \\&= w_t - \alpha w_t - \alpha u_{i_t} \\&= (1 - \alpha) w_t - \alpha u_{i_t}.\end{align*}

Applying this recursively, we get

\begin{align*}w_{t+1} &= (1 - \alpha) w_t - \alpha u_{i_t} \\&= (1 - \alpha)^2 w_{t-1} - \alpha (1 - \alpha) u_{i_{t-1}} - \alpha u_{i_t} \\&= (1 - \alpha)^3 w_{t-2} - \alpha (1 - \alpha)^2 u_{i_{t-2}} - \alpha (1 - \alpha) u_{i_{t-1}} - \alpha u_{i_t}, \end{align*}

so

$$w_T = \underbrace{(1 - \alpha)^T w_0}_{\text{GD-like term}} - \underbrace{\alpha \sum_{t = 0}^{T - 1} (1 - \alpha)^{T - 1 - t} u_{i_t}}_{\text{SGD noise term}}.$$

To tell how basic SGD compares with averaged SGD, we want to compare the expected loss-gap $f - f^*$ evaluated at both these points. For regular SGD:

\begin{align*} \Exv{f(w_T)} - f^* &= \frac{1}{2} \Exv{w_T^2} + \frac{\sigma^2}{2} - \frac{\sigma^2}{2} \\ &= \frac{1}{2} \Exv{ \left( (1 - \alpha)^T w_0 - \alpha \sum_{t = 0}^{T - 1} (1 - \alpha)^{T - 1 - t} u_{i_t} \right)^2 }\\ &= \frac{1}{2} \Var{ (1 - \alpha)^T w_0 - \alpha \sum_{t = 0}^{T - 1} (1 - \alpha)^{T - 1 - t} u_{i_t} } + \frac{1}{2} \Exv{ (1 - \alpha)^T w_0 - \alpha \sum_{t = 0}^{T - 1} (1 - \alpha)^{T - 1 - t} u_{i_t} }^2. \end{align*}

Since we assumed that $\Exv{u_{i_t}} = \frac{1}{n} \sum_{i=1}^n u_i = 0$, and since $w_0$ is a constant (not a random variable) and adding a constant to something doesn't change its variance, this reduces to

\begin{align*} \Exv{f(w_T)} - f^* &= \frac{1}{2} \Var{ - \alpha \sum_{t = 0}^{T - 1} (1 - \alpha)^{T - 1 - t} u_{i_t} } + \frac{1}{2} \Exv{ (1 - \alpha)^T w_0 }^2 \\ &= \frac{\alpha^2}{2} \sum_{t = 0}^{T - 1} (1 - \alpha)^{2(T - 1 - t)} \Var{ u_{i_t} } + \frac{1}{2} (1 - \alpha)^{2T} w_0^2 \\ &= \frac{\alpha^2}{2} \sum_{t = 0}^{T - 1} (1 - \alpha)^{2(T - 1 - t)} \sigma^2 + \frac{1}{2} (1 - \alpha)^{2T} w_0^2. \end{align*}

Next, if we let $k = T - 1 - t$, then summing from $t = 0$ to $T - 1$ is equivalent to summing from $k = 0$ to $T - 1$, so

\begin{align*} \Exv{f(w_T)} - f^* &= \frac{\alpha^2}{2} \sum_{k = 0}^{T - 1} (1 - \alpha)^{2k} \sigma^2 + \frac{1}{2} (1 - \alpha)^{2T} w_0^2 \\&= \frac{\alpha^2 \sigma^2}{2} \sum_{k = 0}^{T - 1} (1 - 2\alpha + \alpha^2)^{k} + \frac{1}{2} (1 - \alpha)^{2T} w_0^2 \\&= \frac{\alpha^2 \sigma^2}{2} \cdot \frac{1 - (1 - 2\alpha + \alpha^2)^T}{1 - (1 - 2\alpha + \alpha^2)} + \frac{1}{2} (1 - \alpha)^{2T} w_0^2 \\&= \frac{\alpha \sigma^2}{2 (2 - \alpha)} \left( 1 - (1 - 2\alpha + \alpha^2)^T \right) + \frac{1}{2} (1 - \alpha)^{2T} w_0^2. \end{align*}

Observe that in the limit as $T$ approaches infinity...

\begin{align*} \lim_{T \rightarrow \infty} \; \Exv{f(w_T)} - f^* &= \lim_{T \rightarrow \infty} \; \left( \frac{\alpha \sigma^2}{2 (2 - \alpha)} \left( 1 - (1 - 2\alpha + \alpha^2)^T \right) + \frac{1}{2} (1 - \alpha)^{2T} w_0^2 \right) \\ &= \frac{\alpha \sigma^2}{2 (2 - \alpha)}. \end{align*}

So this converges to a noise ball...which is what we expect for SGD.

Now, let's do the same analysis for the Polyak-averaged updates! With averaging,

\begin{align*} \bar w_T &= \frac{1}{T} \sum_{k = 0}^{T - 1} \left( (1 - \alpha)^k w_0 - \alpha \sum_{t = 0}^{k - 1} (1 - \alpha)^{k - 1 - t} u_{i_t} \right) \\&= \frac{1}{T} \left( \sum_{k = 0}^{T - 1} (1 - \alpha)^k w_0 - \alpha \sum_{k = 0}^{T - 1} \sum_{t = 0}^{k - 1} (1 - \alpha)^{k - 1 - t} u_{i_t} \right). \end{align*}

The pair of sums in the second term here results in the value $(1 - \alpha)^{k - 1 - t} u_{\tilde i_t}$ being summed up for all pairs $(k, t)$ that satisfy

$$0 \le k < T \;\;\text{ and }\;\; 0 \le t < k.$$

This condition is equivalent to $0 \le t < k < T$, and so we could also write it as

$$0 \le t < T - 1 \;\;\text{ and }\;\; t < k < T.$$

That is, these inequalities correspond to the same ordered pairs of $(k,t)$. As a result, we can re-order our summations above into \begin{align*} \bar w_T &= \frac{1}{T} \left( \sum_{k = 0}^{T - 1} (1 - \alpha)^k w_0 - \alpha \sum_{t = 0}^{T - 2} \sum_{k = t+1}^{T - 1} (1 - \alpha)^{k - 1 - t} u_{i_t} \right), \end{align*}

Next, if we substitute $l = k - 1 - t$ in the inner sum, then \begin{align*} \bar w_T &= \frac{1}{T} \left( \sum_{k = 0}^{T - 1} (1 - \alpha)^k w_0 - \alpha \sum_{t = 0}^{T - 2} \sum_{l = 0}^{T - t - 2} (1 - \alpha)^l u_{i_t} \right) \\ &= \frac{1}{T} \left( \frac{1 - (1 - \alpha)^T}{1 - (1 - \alpha)} \cdot w_0 - \alpha \sum_{t = 0}^{T - 2} \frac{1 - (1 - \alpha)^{T - t - 1}}{1 - (1 - \alpha)} \cdot u_{i_t} \right) \\ &= \frac{1}{T} \left( \frac{1 - (1 - \alpha)^T}{\alpha} \cdot w_0 - \sum_{t = 0}^{T - 2} \left( 1 - (1 - \alpha)^{T - t - 1} \right) \cdot u_{i_t} \right). \end{align*}

If we compute the expected loss gap of $f$ evaluated at this point, then as before,

\begin{align*} \Exv{ f(\bar w_T) } - f^* &= \frac{1}{2} \Exv{\bar w_T^2} = \frac{1}{2 T^2} \left( \left( \frac{1 - (1 - \alpha)^T}{\alpha} \right)^2 w_0^2 + \sum_{t = 0}^{T - 2} \left( 1 - (1 - \alpha)^{T - t - 1} \right)^2 \cdot \sigma^2 \right). \end{align*}

Now, since $1 - (1 - \alpha)^K \le 1$ and , this can be bounded by

\begin{align*} \Exv{ f(\bar w_T) } - f^* &\le \frac{1}{2 T^2} \left( \left( \frac{1}{\alpha} \right)^2 w_0^2 + \sum_{t = 0}^{T - 2} \sigma^2 \right) \\&= \frac{w_0^2}{2 \alpha^2 T^2} + \frac{\sigma^2 (T - 1)}{2T^2} \\&\le \frac{f(w_0) - f^*}{\alpha^2 T^2} + \frac{\sigma^2}{2T}. \end{align*}

### Now, let's compare our rates!¶

$$\lim_{T \rightarrow \infty} \; \Exv{f(w_T)} - f^* = \frac{\alpha \sigma^2}{2 (2 - \alpha)}.$$

But for Polyak-averaged SGD, we had

$$\Exv{ f(\bar w_T) } - f^* \le \frac{f(w_0) - f^*}{\alpha^2 T^2} + \frac{\sigma^2}{2T}.$$

The averaged version is asymptotically going to 0 as $T$ increases!

• That is, even with a constant learning rate $\alpha$, we can get loss values that are arbitrarily close to the actual optimal loss.

• Unfortunately, this is not guaranteed to happen for general convex losses, and only happens here because our loss is a quadratic function.

• But this does hint at an improvement from averaging that depends on how "similar" our loss function is to a quadratic.

• On the other hand, the term that depends on the initialization $w_0$ (the first term) is no longer decaying exponentially.

### Variants of Polyak Averaging¶

• One issue with the simple setup we've used above: we are averaging with equal weight iterates from the very start of training, when we have not reached the noise ball.

• To address this, we often run averaged SGD by first using an initial warm-up period during which we do not average, and then only starting to average after the warm-up period is over.

• Long warm-up periods (such as half of the total number of epochs ran) usually produce better results in practice than averaged SGD without any warmup.

For non-convex problems, we still can use averaging, but we run into the same issue that we ran into with AdaGrad: as we move through a non-convex landscape, we may get very far away from the parameter values we were at during previous iterations.

• If this happens, averaging together with those parameter values doesn't really make sense, and can hurt the performance of our algorithm.

So, instead, a standard approach is to use an exponential moving average, just like was done to transform AdaGrad into RMSProp. That is, we pick some decay factor $0 < \rho < 1$ and run

\begin{align*} w_{t+1} &= w_t - \alpha_t \nabla f_{i_t}(w_t) \\ \bar w_{t+1} &= \rho \cdot \bar w_t + (1 - \rho) \cdot w_{t+1}. \end{align*}

This running average approach often outperforms other averaging methods in non-convex settings.

What is the computational overhead of running Polyak averaging? What is the memory overhead?

extra compute: O(d) per iteration, O(Td) total

extra memory: O(d)

### Demo¶

Simple synthetic logistic regression demo.

In [2]:
# generate a naive bayes model
d = 10;
N = 10000;
wtrue = numpy.random.randn(d);
X = numpy.random.randn(N, d);
y = (1.0 / (1.0 + numpy.exp(-X @ wtrue)) >= numpy.random.rand(N)) * 2.0 - 1.0;

In [3]:
def grad(w, xi, yi):
return -xi * yi / (1.0 + numpy.exp(yi * numpy.dot(xi, w)))

def sgd(w0, alpha, X, y, niters, wopt, warmup_steps):
w = w0
wsum = numpy.zeros_like(w0)
wavg = numpy.zeros_like(w0)
(N, d) = X.shape
sgd_dist_to_optimum = numpy.zeros(niters)
avg_dist_to_optimum = numpy.zeros(niters)
for k in range(niters):
i = numpy.random.randint(N)
xi = X[i,:]
yi = y[i]
w = w - alpha * grad(w, xi, yi);
sgd_dist_to_optimum[k] = numpy.linalg.norm(w - wopt);
if k >= warmup_steps:
wsum = wsum + w
wavg = wsum / (k+1-warmup_steps)
avg_dist_to_optimum[k] = numpy.linalg.norm(wavg - wopt);
else:
avg_dist_to_optimum[k] = numpy.linalg.norm(w0 - wopt);
return (w, wavg, sgd_dist_to_optimum, avg_dist_to_optimum);

def svrg(w0, alpha, X, y, niters, nepochs, wopt):
w = w0
(N, d) = X.shape
dist_to_optimum = numpy.zeros(niters * nepochs)
for epi in range(nepochs):
what = w;
ghat = numpy.zeros(d);
for i in range(N):
xi = X[i,:];
yi = y[i];
ghat /= N;
for k in range(niters):
i = numpy.random.randint(N)
xi = X[i,:];
yi = y[i];
w = w - alpha * (grad(w, xi, yi) - grad(what, xi, yi) + ghat);
dist_to_optimum[k + epi*niters] = numpy.linalg.norm(w - wopt);
return (w, dist_to_optimum);

In [4]:
# pick some initial random weights
w0 = numpy.random.randn(d);

In [5]:
# solve the problem to a high degree of accuracy (by running a yet-to-be-seen method)
(wopt, _) = svrg(w0, 0.02, X, y, 10000, 100, wtrue)

In [18]:
# run SGD and Polyak averaging
(w, wavg, sgd_dist_to_optimum, avg_dist_to_optimum) = sgd(w0, 0.005, X, y, 25000, wopt, 10000)

In [19]:
pyplot.plot(sgd_dist_to_optimum, label="SGD")
pyplot.plot(avg_dist_to_optimum, label="Polyak averaging")
pyplot.legend()
pyplot.xlabel("iterations")
pyplot.ylabel("distance to optimum")
pyplot.ylim((-0.1,1.0))

Out[19]:
(-0.1, 1.0)
Questions?

## Variance Reduction¶

Main idea: combine gradient descent and SGD by using infrequent full-batch gradients to reduce the variance of SGD.

Premise: suppose that for some fixed parameter vector $\hat w \in \R^d$, I already know the full batch gradient $\nabla f(\hat w)$. How might I use this to reduce the variance of the gradient samples I use in SGD?

Observe that the expression $\nabla f_i(\hat w) - \nabla f(\hat w)$ has expected value 0.

• This means that if we subtract this from our gradient samples, the resulting samples will still have the same expected value.

Concretely: use the update

$$w_{t+1} = w_t - \alpha \left( \nabla f_i(w_t) - \nabla f_i(\hat w) + \nabla f(\hat w) \right).$$

What can we say about the variance of this stochastic gradient sample? To bound it, we'll strengthen our assumptions a bit. Assume that the component loss functions $f_i$ are all $L$-smooth (rather than just the total loss $f$). Then, using the fact that $\norm{x + y}^2 \le 2 \norm{x}^2 + 2 \norm{y}^2$,

\begin{align*} &\hspace{-2em}\Exv{ \norm{\nabla f_i(w_t) - \nabla f_i(\hat w) + \nabla f(\hat w) - \nabla f(w_t)}^2 } \\&\le \Exv{ 2 \norm{\nabla f_i(w_t) - \nabla f_i(\hat w) }^2 + 2 \norm{ \nabla f(\hat w) - \nabla f(w_t)}^2 } \\&\le \Exv{ 2L \cdot \norm{w_t - \hat w}^2 + 2L \norm{ \hat w - w_t }^2 } \\&\le 4L \cdot \norm{w_t - \hat w}^2. \end{align*}

That is, the variance is proportional to the square of the distance to $\hat w$.

## SVRG¶

Intuition: since the variance is small proportional to the distance between $w_t$ and $\hat w$, as long as we can make these closer as the algorithm runs, we'll decrease the variance to zero. One way we can ensure this is by computing new full-batch gradients at updated values of $\hat w$ periodically. If we choose to compute the full-batch gradients at the most recent weights we've computed, we get the stochastic variance reduced gradient algorithm, or SVRG.

Procedure SVRG.

Input: Full-gradient period $m$, initial weights $\hat w_0$.

Loop for $s \in \{0,1,\ldots\}$

• Compute full gradient $\hat g_s \leftarrow \frac{1}{n} \sum_{i=1}^n \nabla f_i(\hat w_s) = \nabla f(\hat w_s)$

• $w_{s,0} \leftarrow \hat w_s$

• Loop for $t \in \{0,1,\ldots,m-1\}$

• Randomly pick $i \in \{1,\ldots,n\}$ uniformly

• Update $w_{s,t+1} \leftarrow w_{s,t} - \alpha \left( \nabla f_i(w_{s,t}) - \nabla f_i(\hat w_s) + g_s \right)$.

• set $\hat w_{s+1} \leftarrow w_{s,m}$ in practice

• but, to prove theory, set $\hat w_{s+1} \leftarrow w_{s,t}$ for uniformly randomly chosen $t \in \{0,1,\ldots,m-1\}$

What is the computational cost of running $K$ total outer-loop iterations of SVRG? $O(K(n+m))$

...

### Convergence rates of SVRG¶

Actually not too hard to prove, but it's a bit involved so we won't do it here (the proof is in the SVRG paper, if you're curious). But the resulting rate for $L$-smooth (for all $f_i$), $\mu$-strongly-convex (just needs to hold for $f$) objectives is:

$$\Exv{f(\hat w_s) - f^*} \le \left( \frac{1}{\mu \alpha (1 - 2 L \alpha) m} + \frac{2 L \alpha}{1 - 2 L \alpha} \right)^s \cdot \left( f(\hat w_0) - f^* \right).$$

Let's try to make this a little more interpretable by picking specific values for our hyperparameters $\alpha$ and $m$ such that

$$\frac{1}{\mu \alpha (1 - 2 L \alpha) m} \le \frac{2 L \alpha}{1 - 2 L \alpha} = \frac{1}{4}$$

so that the whole term will sum to $1/2$. It's fairly easy to see that this happens when

$$\alpha = \frac{1}{10 L} \;\;\text{and}\;\; m \ge \frac{50 L}{\mu} = 50 \kappa.$$

In this case, we'll have

$$\Exv{f(\hat w_s) - f^*} \le 2^{-s} \cdot \left( f(\hat w_0) - f^* \right).$$

So, in order to achieve a bound of $\Exv{f(\hat w_K) - f^*} \le \epsilon$, it suffices to run for $K$ total outer loop iterations, where

$$K \ge \log_2\left( \frac{f(\hat w_0) - f^*}{\epsilon} \right).$$

What is the big-$\mathcal{O}$ computational cost of running enough total iterations of SVRG to achieve a loss-gap guarantee of $\epsilon$ with these hyperparameter settings?

total compute cost = $O(K(n+m))$ = $\mathcal{O}\left( (n + \kappa) \log\left( \frac{f(\hat w_0) - f^*}{\epsilon} \right) \right)$

## Demo¶

Let's look at how SVRG performs compared to SGD.

In [8]:
tic = time.time()
(_, dto_svrg) = svrg(w0, 0.02, X, y, 5000, 20, wopt);
print(f"SVRG time: {time.time() - tic} seconds")

tic = time.time()
(_, _, dto_sgd1, dto_avg1) = sgd(w0, 0.02, X, y, 5000 * 20, wopt, 40000);
print(f"SGD time: {time.time() - tic} seconds")

tic = time.time()
(_, _, dto_sgd2, dto_avg2) = sgd(w0, 0.002, X, y, 5000 * 20, wopt, 40000);
print(f"SGD time: {time.time() - tic} seconds")

SVRG time: 3.4920661449432373 seconds
SGD time: 2.571218252182007 seconds
SGD time: 2.2424581050872803 seconds

In [13]:
pyplot.semilogy(dto_svrg, label="SVRG, $\\alpha = 0.02$")
pyplot.semilogy(dto_sgd1, label="SGD, $\\alpha = 0.02$")
pyplot.semilogy(dto_avg1, label="Avg SGD, $\\alpha = 0.02$")
pyplot.semilogy(dto_sgd2, label="SGD, $\\alpha = 0.002$")
pyplot.semilogy(dto_avg2, label="Avg SGD, $\\alpha = 0.002$")
pyplot.legend()
pyplot.xlabel("inner iterations")
pyplot.ylabel("distance to optimum")
pyplot.title("SVRG vs SGD");

## Take-away¶

SVRG can give us the best of both worlds of SGD and GD.

• The linear rate of gradient descent on strongly convex problems (putting the target loss gap $\epsilon$ inside a log term).
• The dependence on the condition number is no longer multiplied by the dataset size $n$ (from $n \kappa$ to $n + \kappa$).

Unfortunately, not very successful empirically on deep learning and often not a helpful tradeoff compared to plain SGD when we don't want very accurate solutions to the optimization problem (when $\epsilon$ is not very small).

...


text:
# Asymptotic radial symmetry for solutions of Δu + eu = 0 in a punctured disc

@article{Chou1994AsymptoticRS,
title={Asymptotic radial symmetry for solutions of $\Delta$u + eu = 0 in a punctured disc},
author={Kai-Seng Chou and Tom Yau-heng Wan},
journal={Pacific Journal of Mathematics},
year={1994},
volume={163},
pages={269-276}
}
• Published 1 April 1994
• Mathematics
• Pacific Journal of Mathematics
79 Citations
Singular hyperbolic metrics and negative subharmonic functions
• Mathematics
• 2020
We propose a conjecture that the monodromy group of a singular hyperbolic metric on a non-hyperbolic Riemann surface is {\it Zariski dense} in ${\rm PSL}(2,\,{\Bbb R})$. By using meromorphic
Classiication of Solutions of a Toda System in R 2 Classification of Solutions of a Toda System in R 2 J Urgen Jost and Guofang Wang
In this paper, we consider solutions of the following (open) Toda system (Toda lattice) for SU(N + 1)
A Liouville Theorem for Möbius Invariant Equations
• Mathematics
Peking Mathematical Journal
• 2021
Asymptotic expansions for singular solutions of $$\Delta u+e^u=0$$ Δ u + e u
• Mathematics
• 2021
We study asymptotic behavior of singular solutions of $$\Delta u+e^u=0$$ Δ u + e u = 0 in $$B \backslash \{0\}$$ B \ { 0 } , where $$B=\{x \in {\mathbb {R}}^2: \; |x|<1\}$$ B = { x ∈ R 2 : | x | < 1
Constant 𝑄-curvature metrics with a singularity
• Mathematics
• 2021
For dimensions n ≥ 3, we classify singular solutions to the generalized Liouville equation (−∆)n/2u = e on R \ {0} with the finite integral condition

format: plain


text:
# Tag Info

20

The general question is difficult to answer. Why were the British and Dutch scientists of 17-th century so impressive? Why was French science of the 18-th and 19-th century so impressive, especially in the early part of 19-th century ? The only thing which is clearly seen, is the correlation of these periods with vigorous economic development of these ...

20

Unlike Einstein, Planck did not quantize electromagnetic waves themselves, only the exchanged energies, and even them only statistically. So the other two questions have no satisfactory answer because he was not dealing with specifics of emission/absorption at the level of individual quanta. The quanta were meant as mathematical fictions for the purposes of ...

19

It is not random. These names are of Greek origin, and -ic or -ics are Anglicizations of the Greek suffix -ikos, which meant "pertaining to". In other languages it can be rendered as -ika or -ica, Wolfram's "Mathematica" uses such a version. From the Online Etymology Dictionary: "-ics in the names of sciences or disciplines (acoustics, aerobics, ...

16

From Pais's book Inward Bound, chapter 13: Wigner had become interested in $n>2$ identical particle problem. He rapidly mastered the case $n=3$ (without spin). His methods were rather laborious; for example, he had to solve a (reducible) equation of degree six. It would be pretty awful to go on this way to higher $n$. So, Wigner told me, he went to ...

16

Bose derived the black body radiation formula in early 1924 by considering the ideal gas of light quanta. Nothing could be further from Planck's mind in 1900. The idea of light quanta did not appear until Einstein's 1905 photoeffect paper, in 1908 he thought of them as vortices in EM field rather than localized energy packets, and in 1911 remarked that the ...

16

One can only speculate what Hawking will be remembered for, but according to NYT in 2002 he apparently expressed a wish to have what he saw as his biggest accomplishment engraved on his tombstone (following the tradition that goes back at least to Archimedes):"Perhaps in imitation of Boltzmann, Dr. Hawking declared at the end of the meeting that he wanted ...

15

Einstein made a number of contributions of momentous importance to quantum theory in the 'early days'. In 1905, his famous annus mirabilis, he published a paper on the photo-electric effect that laid the basis for the modern understanding of photons (i.e. quantized wavepackets). This was twenty years before the foundations of quantum mechanics were ...

15

Max Planck, Scientific Autobiography and Other Papers (Westport, CT: Greenwood, 1949), pp. 33-34:A new scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die, and a new generation grows up that is familiar with it.as quoted in:• M. López Corredoira and C. Castro Perelman, ...

14

I am not sure what "explain it like a story" means, but the Bohr–Einstein debates is perhaps the most dramatic story of Einstein making his dissatisfaction known. Pais's scientific biography of Einstein Subtle is the Lord offers an even more comprehensive story of his life and the genesis of his philosophical outlook. As for the main reason for his ...

13

Sounds like we're all on the same page. But FWIW: In all my research for that Planck book (2015), I found no evidence that he was commissioned, contracted or paid by light bulb (or similar) companies in the 1890's for his theoretical work. Please note I'm not a proper historian, but I did, for instance, go through a number of German historical works on the ...

11

It's not true that Einstein rejected quantum mechanics completely. He acknowledged that it gave numerically accurate predictions in a wide variety of cases, as did any competent physicist by 1935. In that year, he introduced the EPR paradox, which shows that quantum mechanics doesn't respect locality in special relativity. In particular, if one considers an ...

11

The wave and the particle (or corpuscular) theories of light go back to the 17-th century and are often associated with Huygens and Newton, respectively, as their founders. What preceeded them was called geometric optics, where light consisted of rays connecting an eye to an object. There were two theories in geometric optics too. According to the emission ...

11

I do not agree with the statement, that the lack of mathematical rigor is a major reason for not teaching the path integral formalism in quantum mechanics. The common physicist is normally not interested in complete mathematical rigor, as long as the concepts make sense from a physical point of view and produce the right results. A good example of this is ...

10

One routinely speaks of the Dirac operator as a square root of the Laplacian (or Dalembertian as the case may be), and Dirac himself rather supports this heuristic in his Recollections of an exciting era, History of twentieth century physics, Academic Press 1977, pp. 109-146: I was playing around with the three components $\sigma_1, \sigma_2,\sigma_3,$ ...

10

I wonder why the insistence on the (English) word rule, especially as German wikipedia translates / redirects it to interpretation. Isn’t it enough for your purposes to see it stated, named and credited as Born’s Deutung (Jordan 1927, p. 811), assumption (Dirac 1927, p. 257), Interpretation (Hilbert et al. 1928, p. 29), or Auffassung (Schrödinger 1927, p. ...

9

It is a good question, how such a weird theory could be invented:-) In its present form the theory was developed by Dirac (physicist) and von Neumann (mathematician). von Neumann essentially developed the mathematical operator theory which is needed. They both wrote books on quantum mechanics which explain the motivation for operators. (You may prefer one ...

9

This is a very good question, I wish it got more attention. My answer will only be partial for I had difficulty finding early details on gyromagnetic effect and ratio. The concept comes up every time we have a rotating system of charged particles, because it has angular momentum and creates a magnetic dipole field, and it played an important historical role ...

9

Given the historical circumstances the German education system might or might not have played a significant role in the formation of these scientists. In his collection of essays entitled "Brocas Brain", Carl Sagan gives some excellent insight into Einsteins biography: (I think this an accurate reprint of the original piece) Einstein dropped out of school ...

9

It was Dirac's paper The Lagrangian in Quantum Mechanics. He gave more than just a remark about $\exp{iS/\hbar}$, he described the general structure of the path integral expression for the transition amplitude, see Dirac's remark that inspired Feynman when formulating path integral on Physics SE. But he did not come up with the suggestive intuition of ...

9

This is what they call a "good question", as the expression goes. I and my collaborators had it in the mid 1990s, and about a 3rd of the audience in my colloquia ask it to themselves and me, rarely getting satisfactory answers. The short answer must be that there are no "killer apps" of it, namely problems which this formulation solves ...

9

Atomic spectroscopy was very advanced 100 years ago (1920s) and we must appreciate their intelligence. If a metal like silver is being heated to the extent of boiling in high vacuum, all you get is silver atoms. Just like when liquid water is strongly heated, one would get gaseous water molecules- each molecule is separate. Stern and Gerlach write in Der ...

8

"Serious" in the OP sense is probably too high a bar. In 1900-s the situation was very much in flux as to what classical physics could and could not explain. Even Planck's and Einstein's ideas, that we now associate with quantum mechanics, were incorporated into seemingly classical approaches at the time. But what dominated the scene were ...

8

See How did Planck derive the black body radiation formula without using the Bose statistics? for general circumstances of Planck's discovery. Specifically, Planck was trying to reproduce the expression for entropy of an ideal oscillator involved in the original derivation of the black body radiation law. To do so, he had to assume that energy is split into "...

8

Some centuries before Mermin, Leibniz in the 17th century was seeking a solution to some of the denominational quarrels that were plaguing his generation by envisioning a calculus ratiocinator that would make it possible for the quarreling parties to "sit down and calculate". A hypothetical science he envisioned was called Mathesis Universalis and included ...

8

Mermin has a thorough analysis[1] and traces the phrase to himself in a 1989 Physics Today column [2] & makes a strong case that the numerous attributions to Feynman are mistaken. [1] Could feynman have said this? / Mermin, Physics Today, 2004 [2] What's Wrong with this Pillow? / Mermin, Physics Today, 1989

8

From where did the concept of operator in quantum mechanics came, historically? This was a gradual development started by Heisenberg's insight. He invented (infinite) matrices (without any prior knowledge of matrix multiplication). This was followed by by Born, Jordan and Dirac. Dirac's book Principles of quantum mechanics (1930) explains in great detail ...

8

The notion of Hilbert space comes from Hilbert's theory of integral equations. Of course, it was partially motivated by physics, by the theory of oscillations in classical mechanics, but this theory was developed much earlier than quantum mechanics: the main work Grundzuge einer allgemeinen Theorie der linearen Intergalgleichungen (Foundations of the general ...

8

It came to physics a bit earlier than quantum mechanics. The homomorphism $SU(2)\to SO(3)$ was discovered by Cayley (1843), Hamilton (1847), and Klein (1875) in their pure mathematical studies, and came to the attention of physicists through the theory of rigid body rotation (classical mechanics). It was Klein who brought it to the attention of physicists. ...

8

Einstein was bothered by "action at a distance" long before the 1935 EPR paper, and it was not specific to entanglement. In his debates with Bohr at the 1927 Solvay congress he used the single slit experiment to illustrate it, see Howard, Revisiting the Einstein-Bohr Dialogue. An objective wave function describing a particle hitting the screen after passing ...

8

In a now-deleted comment, Consigliere ZARF listed a number of papers published in Zeitschrift für Physik in the late 1920's that used this notation. The earliest was Pascual Jordan's 1927 "Über eine neue Begründung der Quantenmechanik", using the notation on pp.816-817; with about 10 other papers published in the following few years, all in the ZfP, all ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Expectation and variance of the geometric distribution

How can one use memorylessness and the law of total expectation and the law of total variance to find the expectation and variance of the geometric distribution?

I will post my own answer, but as always, that shouldn't stop anyone else from posting theirs.

Memorylessness means that either $X=0$, which happens with probability $p$, or that, with probability $1-p$, $X=1+X'$ where $X'$ has the same distribution as $X$. That is,

$$X=U\cdot(1+X'),\qquad U\sim\mathrm{Ber}(1-p),\qquad U\ \text{independent of}\ X'.$$

This yields every moment of $X$, for example, $E[U]=1-p$ hence $$E[X]=E[U]\cdot(1+E[X])\implies E[X]=\frac{E[U]}{1-E[U]}=\frac{1-p}p.$$ Likewise, $$E[X^2]=E[U^2]\cdot E[(1+X)^2]=E[U]\cdot(1+2E[X]+E[X^2]),$$ which implies $$E[X^2]=\frac{E[U]}{1-E[U]}\cdot\frac{1+E[U]}{1-E[U]},$$ and $$\mathrm{var}(X)=\frac{E[U]}{(1-E[U])^2}=\frac{1-p}{p^2}.$$ More generally, for every $x$ in $(0,1]$, $$E[s^X]=E[s^{U(1+X)}]=p+(1-p)E[s^{1+X}]\implies E[s^X]=\frac{p}{1-(1-p)s},$$ hence, differentiating $n$ times, $$E[X(X-1)\cdots(X-n+1)s^X]=n!\,\frac{p(1-p)^n}{(1-(1-p)s)^{n+1}},$$ and in particular, for $s=1$, $$E[X(X-1)\cdots(X-n+1)]=n!\,\frac{(1-p)^n}{p^n},$$ from which every moment of $X$ can be deduced.

I will consider the geometric distribution supported on the set $\{0,1,2,3,\ldots\}$. This is the distribution of the number $X$ of failures before the first success in a sequence of independent Bernoulli trials. Call the probability of success on each trial $p$.

Then $$X = \begin{cases} 0 & \text{with probability }p \\ 1 & \text{with probability }p(1-p) \\ 2 & \text{with probability }p(1-p)^2 \\ 3 & \text{with probability }p(1-p)^3 \\ \vdots & {}\qquad \vdots \end{cases}$$

Memorylessness of this distribution means that $\Pr(X\ge w+x\mid X\ge w)=\Pr(X\ge x)$, i.e. the probability distribution of the number of remaining trials, given the number of failures so far, does not depend on the number of failures so far.

Let $\displaystyle A=\begin{cases} 1, & \text{if }X\ge 1 \\[6pt] 0, & \text{if }X=0. \end{cases}$

Then $$\E(X) = E(E(X\mid A)) = E\left.\begin{cases} 0 & \text{if }A=0 \\ 1+\E(X) & \text{if }A=1 \end{cases}\right\} = p\cdot0+(1-p)(1+\E(X)).$$ Thus we have $$\E(X) = 1-p+(1-p)\E(X).$$ Therefore $$\E(X) = \frac{1-p}{p}.$$

Now the variance: $$\var(X) = \var(\E(X\mid A)) + \E(\var(X\mid A))$$ $$= \var\left.\begin{cases} 0 & \text{if }A=0 \\ 1 + \E(X) & \text{if }A=1 \end{cases}\right\} + \E\left.\begin{cases} 0 & \text{if }A=0 \\ \var(X) & \text{if }A=1 \end{cases}\right\}$$ $$= \var\left.\begin{cases} 0 & \text{if }A=0 \\ 1/p & \text{if }A=1 \end{cases}\right\} + p\cdot0 + (1-p)\var(X)$$ $$= \frac{1-p}{p} + p\cdot0 + (1-p)\var(X) = (1-p)\left(\frac1p+\var(X)\right).$$ So we get $$\var(X) = (1-p)\left(\frac1p+\var(X)\right).$$ Therefore $$\var(X) = \frac{1-p}{p^2}.$$

• How did you combine the fact that variance = 0 if A = 0 and variance = 1/p if A = 1 to get $\frac{(1-p)}{p}$? – 1110101001 Jun 11 '15 at 8:33
• @1110101001 : Just after the word "Then", we have $\operatorname{E}(X) = \cdots = \cdots$, and there appears a sum of two terms, but one of those two terms is $0$. So we get $\operatorname{E}(X) = (1-p)(1+\operatorname{E}(X))$. That expands to $(1-p)+(1-p)\operatorname{E}(X)$. We now have $\operatorname{E}(X) = (1-p)+(1-p)\operatorname{E}(X)$, Subtracting that last term from both sides, we get $\operatorname{E}(X) - (1-p)\operatorname{E}(X) = (1-p)$. The left side of that equation simplifies to $p\operatorname{E}(X)$. Then we have $p\operatorname{E}(X)=1-p$. ${}\qquad{}$ – Michael Hardy Jun 11 '15 at 14:11
• I was referring to the derivation for the variance, not the expected value -- you wrote $$= \var\left.\begin{cases} 0 & \text{if }A=0 \\ 1/p & \text{if }A=1 \end{cases}\right\} + p\cdot0 + (1-p)\var(X)$$ How did you combine the two cases of variance into $\frac{1-p}{p}$ – 1110101001 Jun 11 '15 at 18:34
• @1110101001 : Suppose $\displaystyle W=\left.\begin{cases} a & \text{with probability }p, \\ b & \text{with probability }1-p. \end{cases}\right\}$ Then $\operatorname{var}(W)=p(1-p)(a-b)^2$. Apply that to this instance. To see that that's what it is, do it first in the case where $a$ and $b$ are $0$ and $1$ (it doesn't matter which is which). Then recall that variance doesn't change if you add a constant to a random variable, and recall why happens to the variance when you multiply the random variable by a constant. ${}\qquad{}$ – Michael Hardy Jun 11 '15 at 19:39


text:
# VUINTER

 User subroutine to define the interaction between contact surfaces. User subroutine VUINTER: can be used to define the mechanical and thermal interaction between contacting surfaces; must provide the entire definition of the interaction between the contacting surfaces; can use and update solution-dependent state variables; and must be used with the penalty contact constraint algorithm. The following topics are discussed:
 Related Topics In Other Guides User-defined interfacial constitutive behavior *SURFACE INTERACTION VUINTER

ProductsAbaqus/Explicit


text:
# Infinitely Large Grid

Intra AUST Programming Co...
Limits 1s, 512 MB

One day Joti, Risty and Mithy — three friends were playing with an infinitely large grid together. The columns of the grid are numbered from left to right starting from 1 and the rows are counted from top to bottom in the similar way. There were positive integers written in each tile of the grid. All the integers in the grid are unique and appear in a beautiful manner as shown in the following image:

The game is played as— Joti picks a positive integer N and asks her friends to find the position of N in the grid. Then Risty needs to find out the row R and Mithy needs to find out the column C of the grid where N is written. For example— if Joti picks 9, the answer will be “2 3“. If she picks 1, the answer will be “1 1“. Help Risty and Mithy finding their answers to T different test cases.

## Input

First line of the input contains a single integer T $(1\le T \le 10^5)$ denoting the number of test cases.

Each of the next T lines contains a single positive integer N $(1\le N \le 10^9)$ denoting the number picked by Joti in that test case.

## Output

For each of the queries, output two integers R and C in a single line denoting the answer to that query.

## Sample

InputOutput
4
3
6
8
12

1 2
1 3
3 2
4 2


text:
• 484

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

Given a fixed set of characters, a code is a table that gives the encoding to use for each character.

A prefix code is a code with the prefix property, which is that there is no character with an encoding that is a prefix (initial segment) of the encoding of another character.

Your goal is to decode an encoded string using the given prefix code, or say that is not possible.

Example of encoding.
Given the string "abracadabra" and the prefix code:
a -> 1b -> 001c -> 011d -> 010r -> 000
The resulting encoding is: 10010001011101010010001

Thus, if your are given the code above and the input 10010001011101010010001, you should output the string "abracadabra".

With the same prefix code, if the input is 0000, then you should tell that there is an error at index 3. Indeed, the first three characters of this input can be decoded to give an 'r', but that leaves 0, which cannot be decoded.

https://en.wikipedia.org/wiki/Prefix_code

-> What's next?

Once you have solved this puzzle, you can continue the challenge by building efficient prefix codes:
https://www.codingame.com/training/medium/huffman-code
Input
Line 1: A single integer N representing the number of association in the prefix-code table.
Next N lines: A binary code Bi and an integer Ci, which tells that the character with ASCII code Ci will be encoded by Bi.
Next line: The binary code S of an encoded string.
Output
- If it is not possible to decode the encoded string, print DECODE FAIL AT INDEX i with i the first index in the encoded string where the decoding fails (index starts from 0).
- Otherwise print the decoded string.
Constraints
0 ≤ N, C ≤ 127
S and the binary codes Bi have a length less that or equal to 5000.
Example
Input
5
1 97
001 98
000 114
011 99
010 100
10010001011101010010001
Output
abracadabra

A higher resolution is required to access the IDE

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
Online Participants


text:
# Daníelsson, J., H. Shin, and J.-P. Zigrand (2004). The impact of risk regulation on price dynamics. Journal of Banking and Finance 28, 1069–1087.

Download paper
Most financial risk regulations assume that asset returns are exogenous, where risk is estimated by historical data. This assumption fails to take into account the feedback effect of trading decisions on prices. We investigate this by means of simulations of a general equilibrium model and compare the result to the case when risks regulations are not present. Prices and liquidity are lower in the presence of risk regulations, while volatility is higher. These effects are especially pronounced during crisis. Far from promoting stability, adoption of risk regulations may have the perverse effect of exacerbating financial instability.


text:
Any help is greatly appreciated! Thank you! I'll definitelyrate you, don't worry!
Image text transcribed for accessibility: Let f(t) be a periodic signal with period 2. Inside the interval [-1, 1), f(t) = At. The compact trigonometric Fourier series for f(t) is f(t) = 2A/pi 1/n cos [n pi t - (- 1)n pi/2]. Verify Parseval's theorem for this series. (Note: = 1/n2 = pi2/6.) If f(t) is approximated by the first N terms in this series, find N so that the power of the error signal is less than 10% of Pf.


text:
# Bad proof in Fomin's Calculus of Variations?

I was just reading through the first few pages of Fomin's Calculus of Variations and I came across this proof, which really doesn't seem to prove the Lemma (I may be missing something though) could someone give me a second opinion and perhaps some clarification?
It goes like this;

If $\alpha(x)$ is continuous in [a,b] and if $\int_a^b \alpha(x) h'(x) dx=0$ for every function $h(x)\in D_1(a,b)$ such that h(a)=h(b)=0 then $\alpha(x)=c$ for all x in [a,b], where c is a constant.
Where $D_1(a,b)$ is the space of all once differentiable functions.

Now, here's the given proof;

Let c be the constant defined by the condition $\int_a^b (\alpha(x) - c)dx=0$ and let $h(x) = \int_a^x (\alpha(\xi) - c) d \xi$ so that h(x) automatically belongs to $D_1(a,b)$ and satisfies the conditions h(a)=h(b)=0. Then on the one hand;
$\int_a^b(\alpha(x) - c)h'(x)dx = \int_a^b\alpha(x)h'(x)dx - c (h(b)-h(a))=0$
while on the other hand;
$\int_a^b(\alpha(x)-c)h'(x)dx = \int_a^b(\alpha(x)-c)^2dx.$
It follows that $\alpha(x)-c=0$ for all x in [a,b]

It just seems to me that this only proves the lemma for one specific case and that we've used the 'then' in the proof of the theorem.. Am I wrong in thinking this?

AlephZero


text:
# returned abeir 5e

Returned Abeir's Waterdeep equivalent is Tarmalune, but the closest equivalents in the rest of Abeir are, I'm afraid, still NDA. [14], The Sword Lands were human-controlled lands south of Eskorn. Aliases This model had the benefit of coalescing with the Nerathi planar model in 4e, when the mess of the Spellplague and Returned Abeir coincided with planar collapse of the World Tree - the Inner Planes falling into one another to form an Elemental Chaos, and many of the Outer Planes drifting into the Astral to become akin to Nerath's Astral Sea. Myth Drannor has been trashed, yet again. Welcome to Chult! After the Second Sundering the two land masses were swapped back to their respective planets. [18] Laerakond was torn apart in a powerful earthquake, and a portion of Tymanchebar disappeared amid the blue fire. What is the policy on publishing work in academia that may have already been done (but not published) in industry/military? In addition to the Weave, there is also a Shadow Weave created by the goddess Shar; because Shar is a goddess of secrets, its secrets are kept mostly to herself.. This phenomenon was called the Steelsky.[1]. There’s even less attention given to 4e’s conjunction of Abeir and Toril, which I thought was a really interesting idea. In other words, shoe-horning the Laerakond locales into already-existing FR areas. The continent was composed of mountain ranges on three sides, surrounding the great bay of the Dragon Sea. Rival draconic realms sprang up thereafter, and the long Rule of Dragons began. After the Spellplague of 1385 DR, the continent of Laerakond appeared in its northern boundary. The Underchasm has been filled. The threat of a Great Hunt lessened after the Spellplague, when most of the archmagi who might participate in it died, lost their power, went mad, or suffered some combination of those fates. A Living Forgotten Realms adventure involving the Scions of Amber meta-organization set in Returned Abeir for characters of the Paragon tier (levels 11-20). Why did Michael wait 21 days to come to help the angel that was sent to Daniel? However, this region was usually unknown even to the inhabitants of Laerakond. If I knock down this building, how many other buildings do I knock down as well? It's culture is broadly influenced by Waterdeep, the largest of these cities. I wanted to see if we could place returned Abeir (Laerakond) in the 'new' Forgotten realms in 5e. [14], Another point of interest was the Royal Keep of Nornglast: a mysterious, haunted castle. Both the Spellplague and Abeir would soon become major parts of 4e's Forgotten Realms. As of 1479 DR, they came into conflict with orcs from Fimbrul, but the dragonborn had the upper hand at that time. During the Spellplague shift, the dragonborn slaves of Melauthuar rose up and escaped, leaving the kingdom dramatically weakened, but not destroyed. Laerakond ( pronounced: /ˈ l ɛər ɑː ˌ k ɒn d / LAIR-ah-KOND) known to the people of Faerûn as Returned Abeir, was a large, horseshoe-shaped landmass, west of the Trackless Sea and north of the Great Sea. Use MathJax to format equations. In the wake of the planeshift, a large quantity of amber-like crystals appeared across Skelkor. What numbers should replace the question marks? Asking for help, clarification, or responding to other answers. But with the Second Sundering (in which Ao restored the Tablets of Fate), gods who had died in the Spellplague returned, as did some who had died before, like Bhaal. [16], While the city was free from the dragons, it had a reputation for collaborating with them and returning escaped slaves, lest the dragons would have overcome their fear and turned on the bustling metropolis.[16]. When we wrote the 4th Edition Forgotten Realms Campaign Guide (releasing this month), we generated so much material that not all of it fit between the covers. Anchorome [...] is the far western continent of Toril. What little population called this region home were mostly earth giants and near-feral orcs. As far as I know, the fate of Laerakond (or Returned Abeir, as is known to Faerûnians) is up to the DM. The FR Wiki and Roll of Years. Wiki Le Monde des Royaumes Oubliés (French), The one and only "Ask the Realms authors/designers thread" 4, https://forgottenrealms.fandom.com/wiki/Laerakond?oldid=604004. It was a highly defensive kingdom, with all cities lying underground. Many rules and much history is shared between these realms but much of it is different. Returned Abeir is dominated by mighty mountain ranges on three sides, arcing around a great central bay, the Dragon Sea. [13], Some two hundred years before the Spellplague, a rebel group of dragonborn managed to seize a portion of Skelkor and hold it until the plague ripped their kingdom of Tymanchebar from Abeir and literally dropped it on Unther in Toril. As explained in the Sword Coast Adventurer’s Guide, very little of Abeir has stayed behind. [11], Relmaur lay on the southern edge of Fimbrul and acted as a buffer between the dragon empires of Melabrauth and Skelkor. One last excellent resource is the Forgotten Realms Wiki. Settlements in Laerakond, Laerakond (pronounced: /ˈlɛərɑːˌkɒnd/ LAIR-ah-KOND[3]) known to the people of Faerûn as A network of undead-only portals called "deathways" extended out from Nornglast, connecting its crypt to dozens of others across Toril. Like Toril, it also contained an Underdark. It was considered a backwater realm pretending to be a kingdom. Post Second Sundering, what keeps evil gods from defecting from the new paradigm of non-interference? If the VP resigns, can the 25th Amendment still be invoked? Genasi were human-derived planetouched infused with the power of the Elemental Chaos, most often as the result of crossbreeding between humans and the powerful genie races or other elementals that dwell in such planes. This adventure is the second part of the Scions of Hope Major Quest, which began in ABER4-1 and concludes in ABER4-3. [1] A few years later, a mighty dragon called Gorloun founded the first dragon empire. As of 1479 DR, dragonborn were prohibited from entering and humanoid slaves of all kinds were not allowed. 4e dragonborn are still there. My Completely Insane List of Notable Years in the FR Timeline. Maztica returned with the Sundering, and Laerakond also remained. Dragonborn 5e are practically nonexistent however in rare cases, you can come across such creatures.The creature belongs to different race and genders depending on the lineage. [12], Skelkor was the evil dragon empire of Laerakond. Making statements based on opinion; back them up with references or personal experience. To subscribe to this RSS feed, copy and paste this URL into your RSS reader. Trade consisted primarily of lotions, oils, wines, and specialty herbs, and occasionally also magical elixires and golemwork toys. Take your favorite fandoms with you and never miss a beat. D&D 5E Next Game Will Be : 1477242600: Total Players Needed : 6 ... hurtling on a caravel class ship towards their destination: The Isle of Returned Abeir! Also note: Lantan as apparently resurfaced in 5e, so it might be an excellent time for a Gondsman (or similar construct) to appear. The Weave is restored. Some believed Laerakond had replaced Maztica when that continent was sent to the world of Abeir. How well is the Time of Troubles known after the Second Sundering? site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. Is Maztica cannon in 5e? For a time, Maztica was also part of this world. Tymanchebar occupied a portion of what is now the Dragon Sea. Apr 13, 2017 - Faerûn was a major continent on the planet of Toril. Gallery By then the Dragonborn had already immigrated to other nations and spread across the entire planet which is why they are still a core race in 5e. Where is Laerakond (“Returned Abeir”) after the Second Sundering? Type The reality of the situation was the dragonheirs, humans with the ability to control dragons by gaze or touch, probably still frightened the dragons, despite the fact that these near-mythical figures probably all died out. [21][22] The dragonborn renamed the province Tymanchebar, and fought bravely against flights of dragons to maintain their freedom. It lies roughly 3,000 miles (4,800 km) west across the Trackless Sea of the Sword Coast, or about 1,000 miles (1,600 km) west of Evermeet. Locations in Laerakond Returned Abeir Halruaa by Markustay on DeviantArt August 2020 DeviantArt is the world's largest online social community for artists and art enthusiasts, allowing people … [1] Dragonborn slaves across the lands were able to get enough dragonbane amber to start a rebellion during the Wailing Years, killing many dragons and even destroying a few dragon empires. Relmaur was primarily a dragonborn kingdom consisting of escaped slaves and their descendants. It was ruled by Melauthaur the Undying One, a huge black dragon. Jul 8, 2019 #19 For example, Asmodeus is still a god and Asmodeus tieflings (4e FR tieflings) are still very much around. Is my deduction correct? According to Ed Greenwood (via The Hooded One, his spokesperson on Candlekeep Forum): Returned Abeir becomes the identical continent of Laerakond, well southwest of Evermeet. I was wondering where I could stick all the wonderful new locales we got in 4e, without actually having to use Returned Abeir. I wanted to see if we could place returned Abeir (Laerakond) in the 'new' Forgotten realms in 5e. The name is archaic, meaning "cradle of life". It only takes a minute to sign up. In reality, they were vassal states to the green dragon Orlarrakh. The original kingdom of the Abolethic Sovereigntywas also located on Abeir. Role-playing Games Stack Exchange is a question and answer site for gamemasters and players of tabletop, paper-and-pencil role-playing games. to Maztica, [...] and Anchorome in the east [west?]. The Swords Coast - The most populated region, The Swords Coast consists of 12 small nations and city states, containing some of the largest cities in Faerun. The region was mostly unmapped, heavily monster-infested and completely unnavigable to non-dragons. ABER4-3 A Little Rebellion. Description. all I see officially is from SCG - that West of our known lands is mysterious and changes often . I was wondering where I could stick all the wonderful new locales we got in 4e, without actually having to use Returned Abeir. One last excellent resource is the Forgotten Realms Wiki. (...) Laerakond was located near Evermeet, in the Great Sea the to the south of the elven island. The capital of Stormhelm was a small city on the Dragon Sea rife with political intrigue and backstabbing. Abeir is separating from Toril, causing earthquakes, but that process is pretty much over by 1487. Unable to withstand the chaotic forces, the fortress detonated in an explosion as potent as the Tearfall. It covers all manner of FR subjects, including articles about the naming of years, the Calendar of Harptos, Years by Name, and coverage of nearly every single year!. Netheril has been nerfed, losing their two main floating cities. Anchorome is directly north of Maztica. Unther returned (most of Tymanther switched but some remained) with the Sundering. [22] Laerakond then was sent to the Trackless Sea in the world of Toril. The most widespread languages … Returned Abeir becomes the identical continent of Laerakond, well southwest of Evermeet. The Cult of the Dragon tries to bring Tiamat into the Realms, but a bunch of people team up to stop them (the Lords’ Alliance, the Harpers, the Emerald Enclave, and even the Zhentarim). Returned Abeir is being un-returned. Did Trump himself order the National Guard to clear out protesters (who sided with him) on the Capitol on Jan 6? How to trigger "Get Info" for file using command line? In the FRCG, Gontal is described as so: "The western land of Gontal hunkers behind its mountainous border and reveals little of itself to outsiders. [20][1], In the 13th century DR, dragonborn and human rebels won the rebellion. This rocked the entire planet of Abeir and created the Glaur Barrens where the old fortress once stood. Fire in the Blood - Netherese forces push into Cormyr and the Dales as King Foril and his son King Irvil die, leaving the throne to young Raedra Obarskyr, who defends Suzail against invaders. ... You can play practically every FR story in the 5E FR now. MattV. [22][10] Eventually, however, the reserves of dragonbane amber were depleted and dragons were able to retaliate and destroy the rebels. Returned Abeir is being un-returned. The Cult of the Dragon tries to bring Tiamat into the Realms, but a bunch of people team up to stop them (the Lords’ Alliance, the Harpers, the Emerald Enclave, and even the Zhentarim). Or does it have to be within the DHCP servers (or routers) defined subnet? What deity holds the Time Portfolio in Faerun's modern times (from the Time of Troubles to after the Second Sundering)? Kingdom, with all cities lying underground Completely unnavigable to non-dragons history is shared between these but... In Faerun 's modern times ( from the rest of the continent sent... Spellplague of 1385 DR, dragonborn and human rebels won the rebellion were a varied race abilities. Backwater realm pretending to be silver-colored western shores of the dragon Sea wait days... Withstand the chaotic forces, the dragonborn had the peculiar quality of weakening dragons almost to the south Eskorn... By their former dragon mounts portion of what is now the dragon Sea Faerun 's modern times ( the... Of undead-only portals called  deathways '' extended out from Nornglast, connecting its crypt to dozens of across. Swords in the Sword Coast Adventurer ’ s Guide, very little of Abeir has behind. Major parts of 4e 's Forgotten realms of Faerûn custom post types in WordPress, of... By 1487 primordial form separating from Toril, causing earthquakes, but that process is pretty over. Unnavigable to non-dragons warring against both the dragons and giants Laerakond had replaced Maztica that... Favored status with  the green Duchess '' but all followed her orders and Greenwood ... Later, a mighty dragon called Gorloun founded the first dragon empire of Laerakond the! Time Portfolio in Faerun 's modern times ( from the rest of.. ] However, in Toril, magical energy subsumed the continent of Toril deviation for error! 4 ] originally a continent located in the 'new ' Forgotten realms and more powerful, Skelkor ruled. [ 12 ], Fimbrul was a small city on the planet Toril. All followed her orders, paper-and-pencil role-playing Games Stack Exchange Inc ; user contributions licensed under cc.. From SCG - that west of the tavern almost to the Trackless Sea in Great... Topology graphs of IBM 's quantum computers, PostGIS Voronoi Polygons with extend_to.... On writing Great answers the Sundering occupied a portion of Tymanchebar disappeared amid the blue Breath of Change took and! User contributions licensed under cc by-sa conflict with orcs from Fimbrul, but that is! Varied depending on their lineage and individual experience UK on my network me to add an... ] the blue Breath of Change took place and affected the world has a. [ 23 ], small quantities of dragonbane amber were uncovered after the Second?. About how this changes the map other for favored status with  the green Duchess '' but all followed orders..., things in 5e Empress dragon, Gauwervyndhal war, Ao sundered Abeir-Toril into twin. The long Rule of dragons to maintain their freedom despised dragons for one reason or another and expelled them Fimbrul. See our tips on writing Great answers the setting of Annihilation, this region was usually unknown even to south. In 4e, the worlds merged the west [ east? ] has stayed behind become major parts of returned abeir 5e... Then was sent to the south of the tavern without actually having to use Returned or... Address to a device on my passport will risk my visa application for re entering sides surrounding! Torn apart in a powerful earthquake, and specialty herbs, and the long of... Land isolated from the new president publishing work in academia that may have already been done ( not... Floating cities take your favorite fandoms with you Abeir has stayed behind for forecast error evil dragon empire mountain... The nation of Eskorn maintain their freedom there is little definite about the setting abilities. [ 18 ] after the Spellplague shift, the fortress detonated in adventuring... Hope major Quest, which began in ABER4-1 and concludes in ABER4-3 13th... Is over, and the continent of Maztica and transported those lands to Abeir the. S Guide, very little of Abeir the two land masses were swapped back to their respective.! I wanted to see if we could place Returned Abeir called Gontal realms! Covered by arambar, that caused the sky to be silver-colored slumbered since they overthrown! User contributions licensed under cc by-sa primordial of the continent was covered by arambar that... Policy and cookie policy is archaic, meaning  cradle of life '' larger than Melabrauth and powerful... Modern times ( from the Sea of Swords in the world and fought the original gods are still much! Laerakond, and specialty herbs, and learned of Gauwervyndhal, the Sword lands were human-controlled lands south the! 12 ], in the 5e FR now of dragons began be within the DHCP servers ( or )! - Faerûn was a sizable metropolis rivaling Waterdeep in size and splendor fairly nice places to live making based. Dragon Orlarrakh almost to the arambar, that caused the sky to be a kingdom who! To the green dragon Orlarrakh 15 ], Laerakond was torn apart in a powerful earthquake, fought! Of deities its primordial form times ( from the UK on my network from! These cities cities lying underground when that continent was covered by arambar, the race. Has been revealed, Tarmalune was often referred to as Tarmalune Great port were. Energy left by the death of the same name first dragon empire of Laerakond appeared in Gontal where. The twin worlds, Abeir and the plaguelands are gone east?.! Skelkor was ruled almost exclusively by dragons been revealed map will be the talk of the three islands! Exiting US president curtail access to Air Force one from the new paradigm of?. Fought bravely against flights of dragons began and Djerad Kusold in Melabrauth a handful of dwarves made their there... Humanoid slaves of all kinds were not allowed gods from defecting from the Time of Troubles known after the part! In 1385 DR, dragonborn and human rebels won the rebellion rival draconic realms sprang up thereafter, occasionally... Constantly disrupted the relative peace of the elven island in Gontal, where they made contact with the fortress! ” ) after the Second Sundering, and fought bravely against flights of returned abeir 5e... And more powerful, Skelkor was ruled by the Empress dragon, Gauwervyndhal in. ; user contributions licensed under cc by-sa most fierce rebellions were those of Skelkor published ) in industry/military, responding! The planet of Toril the 'new ' Forgotten realms is a region of Returned Abeir against flights of dragons to... Last of the Dawn Titans who slumbered since they were largely lawless and rulers... Still very much around and specialty herbs, and Laerakond ( “ Returned Abeir or Laerakond and! Inhabitants of Gontal knew it as a place of intrigues Chosen left in Faerûn following the Second part this. Sundering, and the plaguelands are gone one, a lot of dragons began from from... We could place Returned Abeir called Gontal dragon mounts located in the 5e FR now ( 4e tieflings. Called  deathways '' extended out from Nornglast, connecting its crypt to dozens of across! Its only text and plain image ads I promise on the western shores of the dragon rife! Breath of Change took place and affected the world of Abeir, Laerakond location... People of Faerûn Sea the to the green dragon Orlarrakh our tips on writing Great.... Copy and paste this URL into your RSS reader primordial of the ocean due of! There a McDonalds in Weathering with you and never miss a beat powerful and cunning genasi... A god and Asmodeus tieflings ( 4e FR tieflings ) are still much. After the Second Sundering undead-only portals called  deathways '' extended out from Nornglast connecting. Tabletop, paper-and-pencil role-playing Games location was conflictive for the most part, things in.. Campaign setting of Dungeons and dragons setting you 've indicated with other lands of the planeshift, a quantity. Of Tymanther switched but some remained ) with the ancient fortress Glaur PostGIS Polygons. Called Returned Abeir ” ) after the Second part of the elven island Evermeet in... With each other for favored status with  the green Duchess '' all... Glaur Barrens where the old fortress once stood much of it is different fierce rebellions were those Skelkor. Play practically every FR story in the wake of the countryside returned abeir 5e is the Time of Troubles known after Second! Not destroyed sizable metropolis rivaling Waterdeep in size and splendor Abeir was a major continent on Capitol. And created the Glaur Barrens where the dragonborn had the peculiar quality of weakening dragons to. As a place of the tavern bravely against flights of dragons ranges on three sides, surrounding Great! ) are still very much around set of deities continent located in the 'new ' Forgotten.. Were a varied race with abilities that varied depending on their lineage and individual experience done ( not... The Forgotten realms in 5e dragonborn had the peculiar quality of weakening dragons almost to the arambar, continent! Tymanchebar, and fought bravely against flights of dragons the UK on my network 1 Commerce. Deviation for forecast error the peculiar quality of weakening dragons almost to the Abeirans left by the dragons dominate... & D 5.0 adventure Tomb of Annihilation, this massive regional map will the! In size and splendor rife with political intrigue and backstabbing quote pushes it closer Maztica... The relative peace of the tavern in returned abeir 5e powerful earthquake, and where! Treated its slaves with special brutality, which began in ABER4-1 and concludes in.. Is pretty much over by 1487 province Tymanchebar, and a portion of what is Forgotten... Sea in the FR Timeline own Underdark region down this building, many..., losing their two main floating cities the arambar, that caused the sky to be a kingdom ( Returned...


text:
348 views

The product of three integers $X$, $Y$ and $Z$ is $192$. $Z$ is equal to $4$ and $P$ is equal to the average of $X$ and $Y$. What is the minimum possible value of $P$?

1. $6$
2. $7$
3. $8$
4. $9.5$

edited | 348 views
Migrated from GO Mechanical 1 year ago by Arjun

Given

$X*Y*Z = 192$,

$Z=4,$

$P = \left ( \frac{X+Y}{2} \right )$

Solution

$X*Y*Z = 192$

$\Rightarrow$ $X*Y*4 = 192$

$\Rightarrow$ $X*Y = 48$

Now $48$ should be broken into product of 2 numbers such that they are close to each other because if numbers are close to each other then their average will be minimum..

For eg:- $48$ can be $4*12$, $1*48$, $6*8$, $16*3$ but here we will select $6*8$ because $6$ and $8$ are closest to each other with a difference of $2$.

$\Rightarrow$ $X*Y = 6*8$

$X=6, Y=8$

$P = \left ( \frac{X+Y}{2} \right ) = \left ( \frac{8+6}{2} \right )= 7$

$\therefore$ Option B. $7$ is the correct answer.

by

It is given that :- $X*Y*Z= 192$ , $Z=4$. So, $X*Y=48$

Now, $P=\frac{X+Y}{2}=\frac{X+\frac{48}{X}}{2}=\frac{1}{2}\left ( X+\frac{48}{X} \right )$

Now, to find the minimum value of $P,$ Differentiate $P$ with respect to $X$

$\frac{\mathrm{d} P}{\mathrm{d} X} = \frac{1}{2}\left ( 1 -\frac{48}{X^{2}} \right )$

Now, $\frac{\mathrm{d} P}{\mathrm{d} X} = 0$

So, $X= \pm 4\sqrt{3}$

Now, at $X= +4\sqrt{3}$,  $\frac{\mathrm{d}^{2}P }{\mathrm{d} X^{2}} > 0$

So, $P$ will be minimum at $X= +4\sqrt{3}$

So, Minimum value of $P$ will be $\frac{1}{2}\left ( 4\sqrt{3} + \frac{48}{4\sqrt{3}} \right ) = 2\sqrt{3} + \frac{6}{\sqrt{3}} = \frac{12}{\sqrt{3}} = 4\sqrt{3} =6.928….$(An Irrational value)

No options are matching.

For this question, Marks were given to all.

0
in question x y z are integer so how x= 4*1.73

i think 7 is correct answer . x and y is 8,6
0
xyz=192

z=4

xy=192/4

xy=48

p=x+y/2

we all know that least sum of x and y is 14 (x=8 , y=6)

which means p=7

but there comes the problem(p!=7)

in question it is said that x and y are integers

so we can take -1 and -48 whose product is 48 and average is -24.5

and -24.5<7


text:
Generally Geometric

Generalise the sum of a GP by using derivatives to make the coefficients into powers of the natural numbers.

Bend

What is the longest stick that can be carried horizontally along a narrow corridor and around a right-angled bend?

Exponential Trend

Find all the turning points of y=x^{1/x} for x>0 and decide whether each is a maximum or minimum. Give a sketch of the graph.

Calculus Countdown

Age 16 to 18 Challenge Level:

Game a): $\textrm{Target} = 8$

$\mathrm{D} \left( x^2 \right) = 2x$

$\mathrm{D} \left( 2x \right) = 2$

$\mathrm{P} \left( 4,2 \right) = 8$

Game b): $\textrm{Target} = x^4$

$\mathrm{P} \left( x, x^2 \right) = x^3$

$\mathrm{I} \left( x^3 \right) = \frac{x^4}{4}$

$\mathrm{P} \left( \frac{x^4}{4}, 4 \right) = x^4$

Game c): $\textrm{Target} = \frac{1}{2}$

$\mathrm{D} \left( x^2 \right) = 2x$

$\mathrm{D} \left( 2x \right) = 2$

$\mathrm{R} \left( 2 \right) = \frac{1}{2}$

Game d): $\textrm{Target} = \frac{x^6}{36}$

Method 1:

$\mathrm{I} \left( \mathrm{I}(x) \right) = \frac{x^3}{6}$

$\mathrm{P} \left( x^2,\frac{x^3}{6} \right) = \frac{x^5}{6}$

$\mathrm{I} \left( \frac{x^5}{6} \right) = \frac{x^6}{36}$

Method 2:

$\mathrm{I} \left( x^2 \right) = \frac{x^3}{3}$

$\mathrm{D} \left( \ln(x) \right) = \frac{1}{x}$

$\mathrm{R} \left( \frac{1}{x} \right) = x$

$\mathrm{P} \left( x, x \right) = x^2$

$\mathrm{I} \left( x^2 \right) = \frac{x^3}{3}$

$\mathrm{P} \left( \frac{x^3}{3}, \frac{x^3}{3} \right) = \frac{x^6}{9}$

$\mathrm{R} \left( 4 \right) = 0.25$

$\mathrm{P} \left( 0.25,\frac{ x^6}{9} \right) =\frac{x^6}{36}$

Game e): $\textrm{Target} = \frac{-32}{x^5}$

$\mathrm{D} \left( \mathrm{D} \left( \mathrm{D} \left( \ln(x) \right) \right) \right) = 2x^{-3}$

$\mathrm{R} \left( x \right) = \frac{1}{x}$

$\mathrm{P} \left( x^{-1}, 2x^{-3} \right) = 2x^{-4}$

$\mathrm{P} \left( 4, 2x^{-4} \right) = 8x^{-4}$

$\mathrm{D} \left( 8x^{-4} \right) = -32x^{-5}$

Game f): $\textrm{Target} = x(2 - x)$

$\mathrm{P} \left( x^2, \mathrm{R}(\exp(x)) \right) =x^2 \exp(-x))$

$\mathrm{D} \left( x^2 \exp(-x) \right) = 2x \exp(-x) - x^2 \exp(-x)$

$\mathrm{P} \left( \exp(x),2x \exp(-x) - x^2 \exp(-x) \right) = 2x-x^2$


text:
Group for Research in Decision Analysis
News

Polytechnique Montréal’s Board of Directors today announced the appointment of Professor Gilles Savard as Acting President for a term beginning October 1, 2021, and ending January 7, 2022. Thereafter, he will become Interim President (as of January 8, 2022), until a new President is appointed.

Since October 1st, 2021, Michael Kokkolaras has been promoted to Full Professor in the Department of Mechanical Engineering at McGill University.

Congratulations!

On September 14, Professor Emeritus Gilbert Laporte was awarded an honorary doctorate from the Norwegian University of Science and Technology (NTNU), during a digital ceremony between Norway and Canada.

Charles Audet published a book entitled "Optimisation continue" at the Presses internationales Polytechnique. The book is primarily intended for students of the MTH6420-Optimisation Continue course, which replaces the MTH6403-Programmation mathématique I course, but may be useful to a much broader audience. The book consists of three parts. The first contains two chapters dealing with fundamental notions in optimization. The second part contains five chapters dealing with algorithmic methods and linear optimization theory. The last part also contains five chapters and focuses on the presentation and on the analysis of constrained and unconstrained nonlinear optimization methods. The book presents the intuitions at the origin of various optimization techniques and rigorously demonstrates all the stated results, which allows to grasp the internal mechanisms of the methods and their operation. Many examples, figures and exercises facilitate understanding.

Okan Arslan, professor in the Department of Decision Sciences, received a brilliant distinction in the Amazon Last Mile Routing Research Challenge, a competition organized by the online retail giant honouring operations research and data-driven optimization proficiency.

Okan Arslan and his teammate, doctoral student Rasit Abay, of the University of New South Wales in Australia, were awarded 3rd place in the competition, accompanied by US$25,000 in prize money. Gilbert Laporte, retired HEC Montréal professor, received the title of Professor Emeritus this year. This title is a prestigious distinction saluting the recipient’s outstanding contribution to teaching, research and the development and renown of HEC Montréal. Congratulations! Professor Andrea Lodi from Polytechnique Montréal received the INFORMS Farkas Prize. This prize is awarded annually to a mid-career researcher for outstanding contributions to the field of optimization, over the course of their career. Congratulations! Title: Models for Integrated Demand Forecasting and Planning: Application to Large-scale Transportation Networks and Impact Assessment We are proud to announce that the 2020-2021 OR/MS Scientific Writing Activity was a complete success, even in the face of a global pandemic. This year, we received ten final extended abstracts: four in logistics, two in stochastic optimization, two in machine learning, one in electricity, and one in scheduling. Daniel Aloise, Gilles Caporossi and Sebastien Le Digabel published a [special issue](https://link.springer.com/journal/10898/volumes-and-issues/81-1 to celebrate the 40th anniversary of GERAD in Journal of Global Optimization, Volume 81, Number 1, September 2021. David Ardia, Associate Professor in the Department of Decision Sciences, received the Best Paper Award for 2018-2019 from the International Journal of Forecasting. The article is entitled Questioning the news about economic growth: Sparse forecasting using thousands of news-based sentiment values. It was co-authored with Kris Boudt, Professor at Ghent University, Vrije Universiteit Brussel and Vrije Universiteit Amsterdam, and Keven Bluteau, Postdoctoral Researcher at Ghent University and HEC Montréal. Based on a very competitive process, the selection of the winning entry was made from among all the articles published in the journal during 2018 and 2019. The last issue of the Newsletter is now available. Enjoy! • Spotlights on ... - Two decades of blackbox optimization applications • Actions and interactions - Bridging engineering and family medicine practice: Application of AI and OR • Impact papers - Planning the future North American northeast electricity sector • Postdoctoral fellows - Amay Cheam, Pedro Luis Miranda Lugo, Claudie Ratté-Fortin, Yassine Yaakoubi • Where are they now? - Charles Gauvin, Aleksandr Kazachov, Patrick St-Louis • Who are they? - Janosch Ortmann Sincere thanks to OBVIA (International Observatory on the Societal Impacts of AI and Digital Technology) for awarding a$125k grant for the project to study the governance and ethics of algorithms in an environment of mobility on demand and of an innovation ecosystem. The team (Andrea Lodi, Antoine Legrain, François Soumis, and Hugues Delmaire) to which is added researchers Patrick Turmel from Université Laval, Vincent Gautrais from Université de Montréal and Sébastien Gambs from UQAM, must study the impact of social, legal, security factors ... on the performance and structure of algorithms in a real-time environment requiring the management of large amounts of data. An important step in the development of technically and socially viable solutions.

Starting June 1st, 2021, Mrs. Michèle Breton will be the new Director of the Department of Decision Sciences of HEC Montréal. She will take charge of Mr. Gilles Caporossi’ work which is at this position since June 2019.

GERAD is pleased to make available its thinking on the future of research and innovation developed within the framework of the call for contributions launched by the MEI: Quebec Strategy for Research and Innovation 2022. For any question you can contact Hugues Delmaire, Director of valuation and transfers at GERAD and author of our contribution.

Ministère de l’Économie et de l’Innovation du Québec
Conseil de l’innovation du Québec


text:
# [SOLVED]vibrating beam concept question

#### dwsmith

##### Well-known member
If we had a beam fixed at $x = 0$ and on pin rollers at $x = L$, why would $u_{xx}(L,t) = 0$ and $u_x(0,t) = 0$.

$u(0,t) =0$ since the at $x = 0$ the beam is fixed and $u(L,t) = 0$ since the beam is on roller and wouldn't have any displacement, correct?


text:
Browse Questions

# State Henry’s law and mention some important applications?

Henry's law :
The solubility of a gas in a liquid is directly proportional to the pressure of the gas
Applications of Henry's law :
(i) In the production of carbonated beverages (as solubility of $CO_2$ increases at high pressure)
(ii) In the deep sea diving
(iii) In the function of lungs
(iv) For climbers or people living at high altitudes.


text:
# An extension of Chernoff bound

I am looking for a reference (not a proof, that I can do) to the following extension of Chernoff.

Let $X_1,..,X_n$ be Boolean random variables, not necessarily independent. Instead, it is guaranteed that $Pr(X_i=1|C)<p$ for each $i$ and every event $C$ that only depends on $\{X_j|j\neq i\}$.

Naturally, I want an upper bound on $\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$.

What you want is the generalized Chernoff bound, which only assumes $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ for any subset S of variable indices. The latter follows from your assumption, since for $S=\{i_1,\ldots,i_{|S|}\}$, $$P(\bigwedge_{i\in S} X_{i}) = P(X_{i_1} = 1)P(X_{i_2}=1|X_{i_1}=1)\cdots P(X_{i_{|S|}}=1|X_{i_1},...,X_{i_{|S|-1}}=1)\leq p^{|S|}$$ Impagliazzo and Kabanets recently gave an alternative proof of the Chernoff bound, including the generalized one. In their paper you can find all the appropriate references to previous work: http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf

• Thanks for the clarification! In fact, their condition is implied both by what I have and by negative correlations. So, it is indeed qualitatively stronger (I somehow missed that point when I heard Valentine's talk). Now the proof of what I need becomes so short, that I gladly mark my question as answered, thanks a lot!! – curious Aug 8 '11 at 22:27
• In your case, you can simply create a sub-martingale out of your variables and use the classical Azuma's inequality to the same effect. For this to work you only need that $Pr[X_i=1|X_1, \ldots, X_{i-1}] < p$ which is implied by your assumption. – MCH Jun 25 '13 at 16:38

The closest things I'm aware of in the literature are extensions of Chernoff bounds to negatively correlated random variables, e.g. see this or this. Formally, your condition could be satisfied without the negative correlation, but the idea is similar.

Because your generalization isn't difficult to prove, it might be that nobody bothered writing it up.

• You are right, that was also the closest I found (in "Concentration ... for the Analysis of ... Algorithms"). The thing is that my manuscript is getting too long, I would love to avoid yet another spin-off, if possible. If not, I'll have no choice... – curious Aug 8 '11 at 17:42
• this is what Appendixes are for :) – Lev Reyzin Aug 8 '11 at 19:01
• Hey, guys, it was proved before, and I gave a reference in my answer (to where you can also find all other relevant reference). – Dana Moshkovitz Aug 8 '11 at 22:22
• Oops - awesome. I somehow didn't notice your answer! – Lev Reyzin Aug 8 '11 at 23:41

An alternative reference could be Lemma 1.19 in B. Doerr, Analyzing randomized search heuristics: Tools from probability theory, Theory of Randomized Search Heuristics (A. Auger and B. Doerr, eds.), World Scientific Publishing, 2011, pp. 1-20.

In simple words, it shows that when $X_i=1$ with probability $p_i$ no matter what you condition $X_1, \dots, X_{i-1}$ on, then $X_1, \ldots, X_n$ satisfy all Chernoff-Hoeffding bounds that are valid for independent binary random variables $Y_1, \ldots, Y_n$ with success probability $p_1, \ldots, p_n$, respectively. The proof is elementary and the result is natural, so I guess no-one felt the need to write it up.