Approximating Convex Functions By Non-Convex Oracles Under The Relative Noise Model
Nir Halman (halmanhuji.ac.il)
Abstract: 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.
Keywords: Approximation schemes, discrete convexity
Category 1: Combinatorial Optimization (Approximation Algorithms )
Citation: Approximating Convex Functions Via Non-Convex Oracles Under The Relative Noise Model, Discrete Optimization 16, pp. 1-16, 2015.
Entry Submitted: 02/02/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|