This paper studies the problem of distributed stochastic optimization in an
adversarial setting where, out of the $m$ machines which allegedly compute
stochastic gradients every iteration, an $\alpha$-fraction are Byzantine, and
can behave arbitrarily and adversarially. Our main result is a variant of
stochastic gradient descent (SGD) which finds $\varepsilon$-approximate
minimizers of convex functions in $T = \tilde{O}\big( \frac{1}{\varepsilon^2 m}
+ \frac{\alpha^2}{\varepsilon^2} \big)$ iterations. In contrast, traditional
mini-batch SGD needs $T = O\big( \frac{1}{\varepsilon^2 m} \big)$ iterations,
but cannot tolerate Byzantine failures. Further, we provide a lower bound
showing that, up to logarithmic factors, our algorithm is
information-theoretically optimal both in terms of sampling complexity and time
complexity.

本文研究了在对抗性环境下分布式随机优化问题，其中包括部分机器为拜占庭故障，提出了解决方案并证明了算法的采样和时间复杂度均达到信息上界。

拜占庭随机梯度下降

Byzantine Stochastic Gradient Descent

Reconstruction of structure and parameters of an Ising model from binary
samples is a problem of practical importance in a variety of disciplines,
ranging from statistical physics and computational biology to image processing
and machine learning. The focus of the research community shifted towards
developing universal reconstruction algorithms which are both computationally
efficient and require the minimal amount of expensive data. We introduce a new
method, Interaction Screening, which accurately estimates the model parameters
using local optimization problems. The algorithm provably achieves perfect
graph structure recovery with an information-theoretically optimal number of
samples, notably in the low-temperature regime which is known to be the hardest
for learning. The efficacy of Interaction Screening is assessed through
extensive numerical tests on synthetic Ising models of various topologies with
different types of interactions, as well as on a real data produced by a D-Wave
quantum computer. This study shows that the Interaction Screening method is an
exact, tractable and optimal technique universally solving the inverse Ising
problem.

本文介绍一种名为 Interaction Screening 的新方法，使用本地优化问题准确估计模型参数，这个算法在信息论上优化样本数量的条件下可以实现完美的图形结构恢复，证明了 Interaction Screening 方法是一种准确、可行和最优的通用逆向 Ising 问题解决技术。

Ising 模型的最优结构和参数学习

Optimal structure and parameter learning of Ising models

We study the question of identity testing for structured distributions. More
precisely, given samples from a {\em structured} distribution $q$ over $[n]$
and an explicit distribution $p$ over $[n]$, we wish to distinguish whether
$q=p$ versus $q$ is at least $\epsilon$-far from $p$, in $L_1$ distance. In
this work, we present a unified approach that yields new, simple testers, with
sample complexity that is information-theoretically optimal, for broad classes
of structured distributions, including $t$-flat distributions, $t$-modal
distributions, log-concave distributions, monotone hazard rate (MHR)
distributions, and mixtures thereof.

研究了对结构化分布的身份验证问题，提出了具有信息理论最优的样本复杂度的新型简单测试器，并应用于 t - 平面，t - 模态，对数凸，单调危险率（MHR）和它们的混合等广泛类别的结构化分布。

测试结构化分布的身份

Testing Identity of Structured Distributions

A $k$-modal probability distribution over the discrete domain $\{1,...,n\}$
is one whose histogram has at most $k$ "peaks" and "valleys." Such
distributions are natural generalizations of monotone ($k=0$) and unimodal
($k=1$) probability distributions, which have been intensively studied in
probability theory and statistics.
In this paper we consider the problem of \emph{learning} (i.e., performing
density estimation of) an unknown $k$-modal distribution with respect to the
$L_1$ distance. The learning algorithm is given access to independent samples
drawn from an unknown $k$-modal distribution $p$, and it must output a
hypothesis distribution $\widehat{p}$ such that with high probability the total
variation distance between $p$ and $\widehat{p}$ is at most $\epsilon.$ Our
main goal is to obtain \emph{computationally efficient} algorithms for this
problem that use (close to) an information-theoretically optimal number of
samples.
We give an efficient algorithm for this problem that runs in time
$\mathrm{poly}(k,\log(n),1/\epsilon)$. For $k \leq \tilde{O}(\log n)$, the
number of samples used by our algorithm is very close (within an
$\tilde{O}(\log(1/\epsilon))$ factor) to being information-theoretically
optimal. Prior to this work computationally efficient algorithms were known
only for the cases $k=0,1$ \cite{Birge:87b,Birge:97}.
A novel feature of our approach is that our learning algorithm crucially uses
a new algorithm for \emph{property testing of probability distributions} as a
key subroutine. The learning algorithm uses the property tester to efficiently
decompose the $k$-modal distribution into $k$ (near-)monotone distributions,
which are easier to learn.

本文针对 $k$- 模态分布，提出了一种密度估计的学习算法，利用性质测试算法实现分布分解，从而实现对不同峰值与谷值情况的分布的有效估计。