论文标题
部分可观测时空混沌系统的无模型预测
Private Isotonic Regression
论文作者
论文摘要
在本文中，我们考虑了等渗回归的差异私有（DP）算法的问题。对于最一般的等渗回归问题，在部分有序的集合（POSET）$ \ MATHCAL {X} $以及对于任何Lipschitz损失函数中，我们都会获得纯dp算法，在给定$ n $输入点的情况下，预期过多的经验风险大约是$ $ \ $ \ nathrm {width}（\ mathcal {\ nathcal calcal {x}） \ log | \ Mathcal {x} | / n $，其中$ \ mathrm {width}（\ mathcal {x}）$是poset的宽度。相比之下，我们还获得了大约$（\ mathrm {width}（\ Mathcal {x}） + \ log | \ mathcal {x} |） / n $的近乎匹配的下限，即使对于大致dp算法也是如此。此外，我们表明上述界限本质上是可以在不利用poset的任何进一步结构的情况下获得的最好的。 在完全有序集的特殊情况下，对于$ \ ell_1 $和$ \ ell_2^2 $损失，我们的算法可以在接近线性的运行时间内实现；我们还将该算法扩展到私有等渗回归问题，并在输出函数上具有其他结构性约束。
In this paper, we consider the problem of differentially private (DP) algorithms for isotonic regression. For the most general problem of isotonic regression over a partially ordered set (poset) $\mathcal{X}$ and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given $n$ input points, has an expected excess empirical risk of roughly $\mathrm{width}(\mathcal{X}) \cdot \log|\mathcal{X}| / n$, where $\mathrm{width}(\mathcal{X})$ is the width of the poset. In contrast, we also obtain a near-matching lower bound of roughly $(\mathrm{width}(\mathcal{X}) + \log |\mathcal{X}|) / n$, that holds even for approximate-DP algorithms. Moreover, we show that the above bounds are essentially the best that can be obtained without utilizing any further structure of the poset. In the special case of a totally ordered set and for $\ell_1$ and $\ell_2^2$ losses, our algorithm can be implemented in near-linear running time; we also provide extensions of this algorithm to the problem of private isotonic regression with additional structural constraints on the output function.
