论文标题
最大程度地降低高维多维数据集的低维凸功能
Minimizing a low-dimensional convex function over a high-dimensional cube
论文作者
论文摘要
对于矩阵$ w \ in \ mathbb {z}^{m \ times n} $，$ m \ leq n $和convex函数$ g：\ mathbb {r}^m \ rightArrow \ rightArrow \ mathbb {r} $，我们对最小化$ f（x）= g（w x）$ nsemimpect我们将研究可分离的凸功能和尖锐的凸功能$ g $。此外，矩阵$ w $对我们来说是未知的。仅显示行$ m \ leq n $和$ \ | w \ | _ {\ infty} $的数量。复合函数$ f（x）$仅由Zeroth和一阶Oracle呈现。我们的主要结果是一个接近定理，该定理可确保可分离凸和尖锐凸功能的整体最小值和连续最小值始终“接近”。这将是开发用于检测整数最小值的算法的关键要素，该整数最小值大约是$（m \ | w \ | _ {\ infty}）^{\ Mathcal {o} {o}（m^3）} \ cdot \ cdot \ cd text {poly}（poly}（poly}（n）$。在特殊情况下，当$（i）$ $ w $明确给出$（ii）$ $ g $的$（ii）$ g $是可分离的凸，也可以调整hochbaum和shanthikumar的算法。此改编算法的运行时间与我们的一般算法的运行时间相匹配。
For a matrix $W \in \mathbb{Z}^{m \times n}$, $m \leq n$, and a convex function $g: \mathbb{R}^m \rightarrow \mathbb{R}$, we are interested in minimizing $f(x) = g(Wx)$ over the set $\{0,1\}^n$. We will study separable convex functions and sharp convex functions $g$. Moreover, the matrix $W$ is unknown to us. Only the number of rows $m \leq n$ and $\|W\|_{\infty}$ is revealed. The composite function $f(x)$ is presented by a zeroth and first order oracle only. Our main result is a proximity theorem that ensures that an integral minimum and a continuous minimum for separable convex and sharp convex functions are always "close" by. This will be a key ingredient to develop an algorithm for detecting an integer minimum that achieves a running time of roughly $(m \| W \|_{\infty})^{\mathcal{O}(m^3)} \cdot \text{poly}(n)$. In the special case when $(i)$ $W$ is given explicitly and $(ii)$ $g$ is separable convex one can also adapt an algorithm of Hochbaum and Shanthikumar. The running time of this adapted algorithm matches with the running time of our general algorithm.
