• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Approximating convex functions via non-convex oracles under the relative noise model
【24h】

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

机译：相对噪声模型下通过非凸预言逼近凸函数

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 function (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 function (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 function (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. (C) 2014 Elsevier B.V. All rights reserved.
机译：我们研究有限域上凸单变量函数phi的简洁表示。我们展示了如何构造简洁的表示形式，即在给定黑线访问phi代数上的L近似值oracle（phi）时，条形近似phi上的分段线性函数（phi）（oracle值始终在可乘范围内因子L的真实值）。条形上的分段线性函数（phi）具有很少的断点（域大小和函数值的对数），并按点近似将真实函数phi逼近为（1 +ε）L-2乘积因子，对于任何大于0的epsilon。此函数（phi）也是凸形的，因此可以用作原始函数的替代，并以黑盒的方式插入算法中。最后，我们给出了多元凸函数的正负结果。 （C）2014 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号