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

Existing private synthetic data generation algorithms are agnostic to
downstream tasks. However, end users may have specific requirements that the
synthetic data must satisfy. Failure to meet these requirements could
significantly reduce the utility of the data for downstream use. We introduce a
post-processing technique that improves the utility of the synthetic data with
respect to measures selected by the end user, while preserving strong privacy
guarantees and dataset quality. Our technique involves resampling from the
synthetic data to filter out samples that do not meet the selected utility
measures, using an efficient stochastic first-order algorithm to find optimal
resampling weights. Through comprehensive numerical experiments, we demonstrate
that our approach consistently improves the utility of synthetic data across
multiple benchmark datasets and state-of-the-art synthetic data generation
algorithms.

本研究介绍了一种后处理技术，使用有效的随机一阶算法从合成数据中进行重新采样，以过滤不符合选定效用度量标准的样本，提高了合成数据的效用，并保持强大的隐私保护和数据集质量。

为提高选定度量的效用而后处理私有合成数据

Post-processing Private Synthetic Data for Improving Utility on Selected  Measures

We propose a new stochastic first-order algorithmic framework to solve
stochastic composite nonconvex optimization problems that covers both
finite-sum and expectation settings. Our algorithms rely on the SARAH estimator
introduced in (Nguyen et al, 2017) and consist of two steps: a proximal
gradient and an averaging step making them different from existing nonconvex
proximal-type algorithms. The algorithms only require an average smoothness
assumption of the nonconvex objective term and additional bounded variance
assumption if applied to expectation problems. They work with both constant and
adaptive step-sizes, while allowing single sample and mini-batches. In all
these cases, we prove that our algorithms can achieve the best-known complexity
bounds. One key step of our methods is new constant and adaptive step-sizes
that help to achieve desired complexity bounds while improving practical
performance. Our constant step-size is much larger than existing methods
including proximal SVRG schemes in the single sample case. We also specify the
algorithm to the non-composite case that covers existing state-of-the-arts in
terms of complexity bounds. Our update also allows one to trade-off between
step-sizes and mini-batch sizes to improve performance. We test the proposed
algorithms on two composite nonconvex problems and neural networks using
several well-known datasets.

提出了一种新的随机一阶算法框架来解决随机复合非凸优化问题，该算法覆盖了有限和期望设置，其中算法仅需要非凸目标项的平均光滑性假设和附加的有界方差假设，并证明了算法可以实现最佳复杂度界限。