Exercises

Up to constants, $\lambda_{\text{stat}}^2 = k \log(d) / n$ and $\lambda_{\text{comp}}^2 = k^2 / n$.

With $d=1000$, $\log d \approx 6.91$. Then $\lambda_{\text{stat}}^2 = 10 \cdot 6.91 / 500 \approx 0.138$ and $\lambda_{\text{comp}}^2 = 100 / 500 = 0.200$. Ratio $\lambda_{\text{comp}}^2 / \lambda_{\text{stat}}^2 = k / \log d \approx 1.45$.

A polynomial-time algorithm needs roughly $45\%$ more signal strength than the information-theoretic minimum in this regime.

$\min_i L_T^i = L_T^2 = 45$.

$R_T = 64 - 45 = 19$.

$\mathbf{W} = \frac{1}{4}\begin{bmatrix} 2 & 1 & 0 & 1\\ 1 & 2 & 1 & 0\\ 0 & 1 & 2 & 1\\ 1 & 0 & 1 & 2 \end{bmatrix}.$$

Symmetric by inspection. Each row sums to $4/4 = 1$; by symmetry so does each column. Then $\mathbf{W}\mathbf{1} = \mathbf{1}$ because every row-sum is $1$, so $\mathbf{1}$ is an eigenvector with eigenvalue $1$.

Bonus = $\sqrt{2 \cdot \ln 100 / 4} = \sqrt{\ln 100 / 2} = \sqrt{4.605 / 2} \approx 1.517$. Index $\approx 2.117$.

$\Delta = 1/n = 1/200 = 0.005$.

$b = 0.005 / 0.5 = 0.01$. The MSE added is $2 b^2 = 2 \times 10^{-4}$, which is comparable to the sampling variance $1/(12n) \approx 4.2 \times 10^{-4}$.

Let $\Phi_t = \sum_i w_t^i$ with $w_1^i = 1$. The update $w_{t+1}^i = w_t^i e^{-\eta \ell_t^i}$ gives $\ln(\Phi_{t+1}/\Phi_t) = \ln \mathbb{E}_{i \sim p_t} [e^{-\eta \ell_t^i}]$.

Applying $e^{-\eta x} \le 1 - \eta x + \eta^2 x^2 / 2$ and then $\ln(1+y) \le y$, $$\ln(\Phi_{t+1}/\Phi_t) \le -\eta \langle p_t, \ell_t\rangle + \eta^2 / 2.$$

Summing: $\ln \Phi_{T+1} \le \ln N - \eta L_T^{\text{alg}} + T\eta^2/2$. Also $\ln \Phi_{T+1} \ge -\eta L_T^\star$. Combine and set $\eta = \sqrt{2 \ln N / T}$ to get $L_T^{\text{alg}} - L_T^\star \le \sqrt{2T \ln N}$.

$\sum_{t=1}^T f_t(\theta_t) - \min_\theta \sum_t f_t(\theta) \le R_T$ where $f_t$ is the loss on sample $t$.

For iid data $\mathbb{E}[f_t(\theta)] = f(\theta)$, and the comparator $\min_\theta$ dominates $f(\theta^\star)$, so $\sum_t \mathbb{E}[f(\theta_t)] - T f(\theta^\star) \le R_T$.

By convexity, $f(\bar\theta_T) \le \frac{1}{T}\sum_t f(\theta_t)$. Taking expectations and dividing by $T$: $\mathbb{E}[f(\bar\theta_T)] - f(\theta^\star) \le R_T / T \le C / \sqrt{T}$.

Write $\mathbf{x}^{(0)} = \bar x \mathbf{1} + \mathbf{e}^{(0)}$ where $\mathbf{1}^T \mathbf{e}^{(0)} = 0$.

$\mathbf{x}^{(t)} = \mathbf{W}^t \mathbf{x}^{(0)} = \bar x \mathbf{1} + \mathbf{W}^t \mathbf{e}^{(0)}$ since $\mathbf{W}\mathbf{1} = \mathbf{1}$.

Restricted to $\mathbf{1}^\perp$, the spectral radius of $\mathbf{W}$ is $\lambda_2(\mathbf{W})$. Thus $\|\mathbf{W}^t \mathbf{e}^{(0)}\|_2 \le \lambda_2^t \|\mathbf{e}^{(0)}\|_2$.

Arm $a$ is pulled at round $t$ only if $\hat\mu_a + \sqrt{2\ln t / n_a} \ge \hat\mu_\star + \sqrt{2\ln t / n_\star}$.

This requires at least one of: (i) $\hat\mu_\star < \mu_\star - \sqrt{2\ln t / n_\star}$, (ii) $\hat\mu_a > \mu_a + \sqrt{2\ln t / n_a}$, or (iii) $n_a < 8\ln t / \Delta_a^2$.

Each of (i),(ii) has probability at most $t^{-4}$, summed gives $\mathcal{O}(1)$ contribution. Event (iii) gives $\mathbb{E}[n_a(T)] \le 8\ln T / \Delta_a^2 + \mathcal{O}(1)$, so regret contribution is $\mathcal{O}(\ln T / \Delta_a)$.

$e_{t+1} = e_t - \gamma_t (e_t - w_t) = (1-\gamma_t) e_t + \gamma_t w_t$.

$e_{t+1} = \prod_{s=1}^{t}(1-1/s) e_1 + \sum_{s=1}^{t}\prod_{r=s+1}^{t}(1-1/r) \frac{w_s}{s}$. The product $\prod_{s=1}^{t}(1-1/s) = 0$, and $\prod_{r=s+1}^{t}(1-1/r) = s/t$, so $e_{t+1} = \frac{1}{t}\sum_{s=1}^{t} w_s$.

$\mathbb{E}[e_{t+1}^2] = \sigma^2 / t$ by independence.

Synchronous: $\Theta(N^2)$ rounds $\times$ $2N$ messages = $\Theta(N^3)$. Gossip: $\Theta(N^2)$ pair exchanges $\times$ 2 messages = $\Theta(N^2)$. Gossip wins by factor $N$.

Synchronous converges in $\Theta(1)$ rounds (spectral gap is $1$), using $\Theta(N^2)$ messages. Gossip still takes $\Theta(N^2)$ pair exchanges. They match up to constants.

Gossip wins when the spectral gap is small; synchronous wins when the graph is dense and each round is globally useful.

The minimax rate for pointwise estimation of a Lipschitz density is $n^{-2/3}$. A $1/n^2$ rate is faster than the parametric rate $1/n$, which is suspicious.

(i) Is the claim in MSE or squared-bias-plus-variance correctly accounted? (ii) Does the proof implicitly restrict to a parametric sub-family (smoother than Lipschitz)? (iii) Is the constant allowed to depend on $n$? (iv) Are boundary and tuning effects absorbed?

Either the class is stronger than claimed, the estimator uses side information, or the analysis has a bug. Request clarified assumptions and a simulation against the Le Cam lower bound.

Set $w_{ij} = 1/(1 + \max(d_i, d_j))$ for edges, $0$ elsewhere. Symmetric by construction.

$w_{ii} = 1 - \sum_{j \sim i} w_{ij}$. Since $w_{ij} \le 1/(1+d_i)$ and there are $d_i$ neighbours, $w_{ii} \ge 1 - d_i/(1+d_i) = 1/(1+d_i) > 0$.

Rows sum to $1$ by construction; symmetry gives column sums.

Given a graph $G$ with adjacency $\mathbf{A}$, form samples whose covariance is $\mathbf{I} + \lambda \mathbf{v}\mathbf{v}^T$ where $\mathbf{v}$ is the clique indicator (sparsity $k$). Under the null (no clique) there is no spike.

If a poly-time sparse-PCA estimator achieves detection below $\sqrt{k^2/n}$, applying it to the reduction detects planted cliques with $k = o(\sqrt{N})$, which contradicts the planted clique conjecture.

Beating the computational rate is therefore at least as hard as refuting a widely-believed average-case complexity assumption.

For $f_0 = R/\eta$ and iterates $\theta_t$ minimizing $\sum_{s \le t-1} f_s$, telescoping gives $\sum_t f_t(\theta_t) - \sum_t f_t(\theta^\star) \le f_0(\theta^\star) - f_0(\theta_1) + \sum_t [f_t(\theta_t) - f_t(\theta_{t+1})]$.

Strong convexity of $R$ implies $\|\theta_t - \theta_{t+1}\| \le \eta \|\nabla f_t(\theta_t)\|_\star$; convexity of $f_t$ gives $f_t(\theta_t) - f_t(\theta_{t+1}) \le \|\nabla f_t(\theta_t)\|_\star \|\theta_t - \theta_{t+1}\|$.

Plugging in, $R_T \le R(\theta^\star)/\eta + \eta \sum_t \|\nabla f_t(\theta_t)\|_\star^2$. The factor $1/2$ comes from a tighter version of the stability step.

Summing over $i$ and using double stochasticity of $\mathbf{W}$: $\bar\theta^{(t+1)} = \bar\theta^{(t)} + \frac{\alpha_t}{N} \sum_i h_i(y_i - h_i\bar\theta^{(t)}) + \text{disagreement}$. This is a stochastic approximation toward $\theta^\star_{\text{ML}} = (\sum_i h_i^2)^{-1}\sum_i h_i y_i$.

Consensus contracts the disagreement at rate $\lambda_2^t$, while innovation injects noise of order $\alpha_t$. With $\alpha_t \to 0$, disagreement shrinks to $0$ in mean-square.

Standard stochastic approximation arguments (under $\sum \alpha_t = \infty, \sum \alpha_t^2 < \infty$) yield $\theta_i^{(t)} \to \theta^\star_{\text{ML}}$ almost surely.

Empirical mean has variance $\sigma^2/n \le 1/(4n)$.

Adding Laplace noise with scale $1/(n\varepsilon)$ adds MSE $2/(n\varepsilon)^2$.

Total $\asymp 1/n + 1/(n\varepsilon)^2$. Privacy is free when $1/(n\varepsilon)^2 \lesssim 1/n$, i.e. $n \gtrsim 1/\varepsilon^2$.

Angular-domain channel is $k$-sparse in $d$ directions with $n$ pilots. Information-theoretic minimax rate is $k \log(d/k)/n$; LASSO achieves $k \log d / n$; thresholding after matched filter $k^2/n$.

Orthogonal matching pursuit or LASSO with $\ell_1$ penalty; analysis in Ch.14-15 shows mutual-incoherence rates.

A reduction from planted dense submatrix would give conditional lower bounds at $k^2/n$ — the widely-believed barrier for poly-time sparse PCA/CCA. Write up as a research note.