Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard
원문 초록
In this paper we show how to use drift analysis in the case of two random variables $X_1, X_2$, when the drift is approximatively given by $A\cdot (X_1,X_2)^T$ for a matrix $A$. The non-trivial case is that $X_1$ and $X_2$ impede each other's progress, and we give a full characterization of this case. As application, we develop and analyze a minimal example TwoLinear of a dynamic environment that can be hard. The environment consists of two linear function $f_1$ and $f_2$ with positive weights $1$ and $n$, and in each generation selection is based on one of them at random. They only differ in the set of positions that have weight $1$ and $n$. We show that the $(1+1)$-EA with mutation rate $\chi/n$ is efficient for small $\chi$ on TwoLinear, but does not find the shared optimum in polynomial time for large $\chi$.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Quantile-Based Deep Reinforcement Learning using Two-Timescale Policy Gradient Algorithms
Leveraging the two timescale regime to demonstrate convergence of neural networks
Training a Two Layer ReLU Network Analytically
MiniRBT: A Two-stage Distilled Small Chinese Pre-trained Model
FinalMLP: An Enhanced Two-Stream MLP Model for CTR Prediction
Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems
토론
이 논문과 연결된 포럼 글이 아직 없습니다.