Approximating convex functions via non-convex oracles under the relative noise model

作者：Halman Nir^*

来源：Discrete Optimization, 2015, 16: 1-16.

DOI：10.1016/j.disopt.2014.12.001

• Approximate binary search
• Dynamic programming
• Property preserving reconstruction

We study succinct representations of a convex univariate function phi over a finite domain. We show how to construct a succinct representation, namely a piecewise-linear phi) over bar approximating phi when given a black box access to an L-approximation oracle (phi) over tilde of phi (the oracle value is always within a multiplicative factor L from the true value). The piecewise linear phi) over bar has few breakpoints (poly-logarithmic in the size of the domain and the function values) and approximates the true function phi up to a (1+epsilon)L-2 multiplicative factor point-wise, for any epsilon > 0. This phi) over bar is also convex so it can be used as a replacement for the original function and be plugged in algorithms in a black box fashion. Finally, we give positive and negative results for multivariate convex functions.

• 出版日期2015-5