有效的全球优化无声最坏情况复杂性的下界
Wenjie Xu1,2, Yuning Jiang1, Emilio T Maddalena1
1Automatic Control Laboratory, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland.
概括
这项研究为高效的全球优化建立了统一的下界,这对于昂贵的黑子功能至关重要. 调查结果表明,这种约束与常见内核的现有上限密切匹配,表明近乎最佳的性能.
科学领域:
- 机器学习 机器学习
- 优化理论 优化理论
背景情况:
- 高效的全球优化 (EGO) 对昂贵的黑子功能至关重要.
- 现有的研究经常提供内核特定的复杂性边界.
研究的目的:
- 为 EGO 预言复杂性推导一个统一的下限.
- 为了比较这个下限与现有的普通核的上限.
主要方法:
- 对EGO最坏情况下的Oracle复杂性的分析.
- 在复制内核希尔伯特空间时,使用米度来导出统一的下界.
主要成果:
- 确定了EGO预言复杂性的统一下限.
- 这个边界几乎与二次指数和马特恩核的上限相匹配.
- 匹配在维度 (d) 和对数数值的因子内.
结论:
- 导出的下界对于常用的内核来说几乎是最佳的.
- 这种统一的方法简化了EGO的复杂性分析.
- 结果提供了对EGO算法的效率的理论见解.
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
51
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
51
Propagation of Uncertainty from Random Error
681
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
681
Statically Indeterminate Problem Solving
376
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
376
Entropy Change in Reversible Processes
2.5K
In the Carnot engine, which achieves the maximum efficiency between two reservoirs of fixed temperatures, the total change in entropy is zero. The observation can be generalized by considering any reversible cyclic process consisting of many Carnot cycles. Thus, it can be stated that the total entropy change of any ideal reversible cycle is zero.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
2.5K
Linear Approximation in Time Domain
81
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
81
Routh-Hurwitz Criterion II
229
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
229


