It is well-known that plug-in statistical estimation of optimal transport suffers from the curse of dimension. Despite recent efforts to improve the rate of estimation with the smoothness of the problem, the computational complexities of these recently proposed methods still degrade exponentially with the dimension. In this paper, thanks to a representation theorem, we derive a statistical estimator of smooth optimal transport which achieves in average a precision $\epsilon$ for a computational cost of $\tilde{\mathcal{O}}(\epsilon^{-2\gamma})$, where $\gamma$ is the complexity of a semidefinite program mixed with a second order cone program, hence yielding a dimension free rate. Even though our result is theoretical in nature due to the large constants involved in our estimation, it settles the question of whether the smoothness of optimal solutions can be taken advantage of from a computational and statistical point of view.
翻译：众所周知,对最佳运输的插头统计估计受到维度的诅咒。尽管最近努力提高估算率,使问题更加顺利,但最近提出的这些方法的计算复杂性仍然随着维度而成倍下降。 在本文中,由于一个代表理论,我们得出了一个对平稳最佳运输的统计估计,平均能达到精确的美元,以计算成本为美元=%(( ⁇ )( ⁇ )( ⁇ ( ⁇ )-2\gamma})美元。 美元是半固定方案的复杂性,与二阶锥体方案混合,因此产生了一个无维率。 尽管我们的结果是理论性的,但由于我们估算中涉及的大型常数,它解决了从计算和统计角度能否利用最佳解决办法的顺利性的问题。
相关内容
微信扫码咨询专知VIP会员