检索结果-内蒙古大学图书馆

information-based complexity, Feedback and Dynamics in Convex Programming

IEEE TRANSACTIONS ON information THEORY 2011年第10期57卷 7036-7056页

作者： Raginsky, Maxim Rakhlin, Alexander Duke Univ Dept Elect & Comp Engn Durham NC 27708 USA Univ Penn Wharton Sch Business Dept Stat Philadelphia PA 19104 USA

We study the intrinsic limitations of sequential convex optimization through the lens of feedback information theory. In the oracle model of optimization, an algorithm queries an oracle for noisy information about the unknown objective function and the goal is to (approximately) minimize every function in a given class using as few queries as possible. We show that, in order for a function to be optimized, the algorithm must be able to accumulate enough information about the objective. This, in turn, puts limits on the speed of optimization under specific assumptions on the oracle and the type of feedback. Our techniques are akin to the ones used in statistical literature to obtain minimax lower bounds on the risks of estimation procedures;the notable difference is that, unlike in the case of i.i.d. data, a sequential optimization algorithm can gather observations in a controlled manner, so that the amount of information at each step is allowed to change in time. In particular, we show that optimization algorithms often obey the law of diminishing returns: the signal-to-noise ratio drops as the optimization algorithm approaches the optimum. To underscore the generality of the tools, we use our approach to derive fundamental lower bounds for a certain active learning problem. Overall, the present work connects the intuitive notions of "information" in optimization, experimental design, estimation, and active learning to the quantitative notion of Shannon information.

关键词： Convex optimization Fano's inequality feedback information theory hypothesis testing with controlled observations information-based complexity information-theoretic converse minimax lower bounds sequential optimization algorithms statistical estimation

来源：评论

学校读者我要写书评

暂无评论

The exact information-based complexity of smooth convex minimization

引用

JOURNAL OF complexity 2017年 39卷 1-16页

作者： Drori, Yoel Google Inc 1600 Amphitheatre Pkwy Mountain View CA 94043 USA

We obtain a new lower bound on the information-based complexity of first-order minimization of smooth and convex functions. We show that the bound matches the worst-case performance of the recently introduced Optimized Gradient Method (Drori and Teboulle, 2013;Kim and Fessler, 2015), thereby establishing that the bound is tight and can be realized by an efficient algorithm. The proof is based on a novel construction technique of smooth and convex functions. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Convex optimization complexity Rate of convergence information-based complexity

来源：评论

学校读者我要写书评

暂无评论

ON THE information-based complexity OF OPTIMAL RECONSTRUCTION FOR NONLINEAR-SYSTEMS

引用

SYSTEMS & CONTROL LETTERS 1990年第2期14卷 161-167页

作者： CHEN, GR RICE UNIV DEPT ELECT & COMP ENGNHOUSTONTX 77251

The information-based complexity of optimal reconstruction problems for general nonlinear systems is studied. Both lower and upper bounds for the worst-case reconstruction-error functional are given. The existence of ... 详细信息

关键词： information-based complexity optimal reconstruction nonlinear systems lower and upper error bouns optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Why does information-based complexity use the real number model?

引用

THEORETICAL COMPUTER SCIENCE 1999年第1-2期219卷 451-465页

作者： Wozniakowski, H Columbia Univ Dept Comp Sci New York NY 10027 USA

We explain why information-based complexity uses the real number model. Results in the real number model are essentially the same as in floating point arithmetic with fixed precision modulo two important assumptions, namely . we use only stable algorithms, . the approximation error is not too small, compared to the product of the condition number, the roundoff unit of floating point arithmetic, and the accumulation constant of a stable algorithm. We illustrate this by an example of solving nonlinear equations by bisection. We also indicate the possible tradeoffs between complexity and stability, and the need of using multiple or varying precision for ill-conditioned problems. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： real number model floating point arithmetic information-based complexity nonlinear equations bisection

来源：评论

学校读者我要写书评

暂无评论

The exact order of information-based complexity of weakly singular integral equations with periodic analytic coefficients

引用

MATHEMATICAL NOTES 1997年第5-6期62卷 537-548页

作者： Azizov, M Institute of Mathematics National Academy of Sciences of Ukraine Russia

The exact order of complexity of weakly singular integral equations including logarithmic singularities with periodic and analytic coefficients is found. This class of equations contains the boundary equations of exte... 详细信息

关键词： information-based complexity epsilon-complexity weakly singular equations boundary value problems Helmholtz equation

来源：评论

学校读者我要写书评

暂无评论

On the information-based complexity of stochastic programming

引用

OPERATIONS RESEARCH LETTERS 2013年第6期41卷 622-626页

作者： Tavares, Gabriela Parpas, Panos Univ London Imperial Coll Sci Technol & Med Dept Comp London SW7 2AZ England

Existing complexity results in stochastic linear programming using the Turing model depend only on problem dimensionality. We apply techniques from the information-based complexity literature to show that the smoothness of the recourse function is just as important. We derive approximation error bounds for the recourse function of two-stage stochastic linear programs and show that their worst case is exponential and depends on the solution tolerance, the dimensionality of the uncertain parameters and the smoothness of the recourse function. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Optimization Stochastic programming Uncertainty complexity information-based complexity

来源：评论

学校读者我要写书评

暂无评论

A parallel information-based complexity approach to visual surface reconstruction

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1998年第2期70卷 165-177页

作者： Jiang, TZ Univ New S Wales Sch Math Sydney NSW 2052 Australia

In this paper, we give a novel insight into studying the low level vision. We attack low level problems by parallel information-based complexity techniques. Here we only study the visual surface reconstruction. We obtain tight bounds on the complexity, considered as a function of two variables simultaneously: the number of processors, the required precision. This result seems to be new even in serial case. Our results will provide a benchmark for the intrinsic difficulty of visual surface reconstruction. With this, one can compare its computational complexity with the cost any algorithm that solves the problem to tell how well the given algorithm measures up. To the best of our knowledge, it is the first attempt to introduce parallel information-based complexity techniques into studying low level vision.

关键词： low level vision algebraic complexity parallel complexity information-based complexity visual surface reconstruction

来源：评论

学校读者我要写书评

暂无评论

Compressed sensing

引用

IEEE TRANSACTIONS ON information THEORY 2006年第4期52卷 1289-1306页

作者： Donoho, DL Stanford Univ Dept Stat Stanford CA 94305 USA

Suppose x is an unknown vector in R-m (a digital image or signal);we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible by transform coding with a known transform, and we reconstruct via the nonlinear procedure defined here, the number of measurements n can be dramatically smaller than the size m. Thus, certain natural classes of images with m pixels need only n = O(m(1/4) log(5/2)(m)) nonadaptive nonpixel samples for faithful recovery, as opposed to the usual m pixel samples. More specifically, suppose x has a sparse representation in some orthonormal basis (e.g., wavelet, Fourier) or tight frame (e.g., curvelet, Gabor)-so the coefficients belong to an l(p), ball for O < p <= 1. The N most important coefficients in that expansion allow reconstruction with l(2) error O(N1/2-1/p). It is possible to design n = O (N log (m)) nonadaptive measurements allowing reconstruction with accuracy comparable to that attainable with direct knowledge of the N most important coefficients. Moreover, a good approximation to those N important coefficients is extracted from the n measurements by solving a linear program-Basis Pursuit in signal processing. The nonadaptive measurements have the character of "random" linear combinations of basis/frame elements. Our results use the notions of optimal recovery, of n-widths, and information-based complexity. We estimate the Gel'fand n-widths of l(p) balls in high-dimensional Euclidean space in the case 0 < p <= 1, and give a criterion identifying near-optimal subspaces for Gel'fand n-widths. We show that "most" subspaces are near-optimal, and show that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces.

关键词： adaptive sampling almost-spherical sections of Banach spaces Basis Pursuit eigenvalues of random matrices Gel'fand n-widths information-based complexity integrated sensing and processing minimum l(1)-norm decomposition optimal recovery Quotient-of-a-Subspace theorem sparse solution of linear equations

来源：评论

学校读者我要写书评

暂无评论

complexity of parametric initial value problems for systems of ODEs

引用

MATHEMATICS AND COMPUTERS IN SIMULATION 2017年 135卷 72-85页

作者： Daun, Thomas Heinrich, Stefan Univ Kaiserslautern Dept Comp Sci D-67653 Kaiserslautern Germany

We study the approximate solution of initial value problems for parameter dependent finite or infinite systems of scalar ordinary differential equations (ODEs). Both the deterministic and the randomized setting is considered, with input data from various smoothness classes. We study deterministic and Monte Carlo multilevel algorithms and derive convergence rates. Moreover, we prove their optimality by showing matching (in some limit cases up to logarithmic factors) lower bounds and settle this way the complexity. Comparisons between the deterministic and randomized setting are given, as well. (C) 2015 International Association for Mathematics and Computers in Simulation (IMACS). Published by Elsevier B.V. All rights reserved.

关键词： Ordinary differential equation Initial value problem Parametric problem Multilevel Monte Carlo information-based complexity

来源：评论

学校读者我要写书评

暂无评论

No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期208卷 51-74页

作者： Tian, Lai So, Anthony Man-Cho Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

We consider the oracle complexity of computing an approximate stationary point of a Lipschitz function. When the function is smooth, it is well known that the simple deterministic gradient method has finite dimension-free oracle complexity. However, when the function can be nonsmooth, it is only recently that a randomized algorithm with finite dimension-free oracle complexity has been developed. In this paper, we show that no deterministic algorithm can do the same. Moreover, even without the dimension-free requirement, we show that any finite-time deterministic method cannot be general zero-respecting. In particular, this implies that a natural derandomization of the aforementioned randomized algorithm cannot have finite-time complexity. Our results reveal a fundamental hurdle in modern large-scale nonconvex nonsmooth optimization.

关键词： Stationary points Black-box optimization information-based complexity Dimension-free rates Lower bounds

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：