Consider the problem of minimizing an expected logarithmic loss over either
the probability simplex or the set of quantum density matrices. This problem
encompasses tasks such as solving the Poisson inverse problem, computing the
maximum-likelihood estimate for quantum state tomography, and approximating
positive semi-definite matrix permanents with the currently tightest
approximation ratio. Although the optimization problem is convex, standard
iteration complexity guarantees for first-order methods do not directly apply
due to the absence of Lipschitz continuity and smoothness in the loss function.
In this work, we propose a stochastic first-order algorithm named $B$-sample
stochastic dual averaging with the logarithmic barrier. For the Poisson inverse
problem, our algorithm attains an $\varepsilon$-optimal solution in $\tilde{O}
(d^2/\varepsilon^2)$ time, matching the state of the art. When computing the
maximum-likelihood estimate for quantum state tomography, our algorithm yields
an $\varepsilon$-optimal solution in $\tilde{O} (d^3/\varepsilon^2)$ time,
where $d$ denotes the dimension. This improves on the time complexities of
existing stochastic first-order methods by a factor of $d^{\omega-2}$ and those
of batch methods by a factor of $d^2$, where $\omega$ denotes the matrix
multiplication exponent. Numerical experiments demonstrate that empirically,
our algorithm outperforms existing methods with explicit complexity guarantees.

本文介绍了一种用于最小化预期对数损失的随机一阶算法，解决了凸优化问题中由于损失函数的缺乏 Lipschitz 连续性和平滑性而导致标准迭代复杂度保证不直接适用的问题，提出的算法取得了比现有方法更好的复杂度和性能。

基于随机对偶平均的快速期望对数损失最小化

Fast Minimization of Expected Logarithmic Loss via Stochastic Dual  Averaging

We advance the Cohn-Umans framework for developing fast matrix multiplication
algorithms. We introduce, analyze, and search for a new subclass of strong
uniquely solvable puzzles (SUSP), which we call simplifiable SUSPs. We show
that these puzzles are efficiently verifiable, which remains an open question
for general SUSPs. We also show that individual simplifiable SUSPs can achieve
the same strength of bounds on the matrix multiplication exponent $\omega$ that
infinite families of SUSPs can. We report on the construction, by computer
search, of larger SUSPs than previously known for small width. This, combined
with our tighter analysis, strengthens the upper bound on the matrix
multiplication exponent from $2.66$ to $2.505$ obtainable via this
computational approach, and nears the results of the handcrafted constructions
of Cohn et al.

研究了一种解决快速矩阵乘法计算的算法，介绍了高效验证的可简化的独特可解谜题，指出可以通过可简化的 SUSPs 实现和无限个 SUSPs 同样强的矩阵乘法上限，利用电脑搜索构建了比现有更大的 SUSPs 用于提高矩阵乘法上限。

高效可验证的强唯一可解拼图与矩阵乘法

Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix  Multiplication

We further develop the group-theoretic approach to fast matrix multiplication
introduced by Cohn and Umans, and for the first time use it to derive
algorithms asymptotically faster than the standard algorithm. We describe
several families of wreath product groups that achieve matrix multiplication
exponent less than 3, the asymptotically fastest of which achieves exponent
2.41. We present two conjectures regarding specific improvements, one
combinatorial and the other algebraic. Either one would imply that the exponent
of matrix multiplication is 2.

利用群论方法改进矩阵乘法算法，并描述了多个实现矩阵乘法指数小于 3 的交替积群族，最快的指数为 2.41。同时提出了两个关于改进算法的猜想，其一组合学的，其二代数学的，证明其中任意一个即可使得矩阵乘法的指数为 2。