We study succinct approximation of functions that have noisy oracle access. Namely, construction of a succinct representation of a function, given oracle access to an L-approximation of the function, rather than to the function itself. Specifically, we consider the question of the succinct representation of an approximation of a convex function v that cannot be accessed directly, but only via oracle calls to a general (i.e., not necessarily convex) L-approximation v' of v. We efficiently construct such a succinct ((1+epsilon)L^2)-approximation for a univariate convex v, for any epsilon>0. The algorithms designed in this paper can, and are used as subroutines (gadgets) within other approximation algorithms.
Citation
Approximating Convex Functions Via Non-Convex Oracles Under The Relative Noise Model, Discrete Optimization 16, pp. 1-16, 2015.