論文の概要: Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard

• arxiv url: http://arxiv.org/abs/2203.14547v2
• Date: Wed, 10 May 2023 07:47:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-11 17:55:15.857265
• Title: Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard
• Title（参考訳）: 2次元ドリフト解析:2つの関数を同時に最適化することは難しい
• Authors: Duri Janett, Johannes Lengler
• Abstract要約: 2つの確率変数の場合、ドリフト解析の使い方を示す。 難易度の高い動的環境の2つの最小例を分析します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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$.
• Abstract（参考訳）: 本稿では,2つの確率変数$X_1,X_2$のとき,行列$A$に対して$A\cdot (X_1,X_2)^T$で近似的にドリフトが与えられるとき,ドリフト解析の使い方を示す。 非自明な場合、$X_1$と$X_2$は互いの進行を妨げ、この場合の完全な特徴を与える。 適用例として、困難である動的環境の最小例であるTwoLinearを開発し、分析する。 環境は2つの線形関数 $f_1$ と $f_2$ で構成され、正の重みは $$ と $n$ である。 それらは、重さが1ドルと$n$の位置にのみ異なる。 突然変異率$\chi/n$の$(1+1)$-EAはTwoLinear上の小さな$\chi$に対して効率的であるが、大きな$\chi$の多項式時間における共有最適化は見つからない。

関連論文リスト

• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
  1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。 目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
  論文  参考訳（メタデータ） (2024-03-14T15:04:45Z)
• A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions [44.655316553524855]
  我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。 それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
  論文  参考訳（メタデータ） (2023-11-17T22:07:18Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone Functions [7.111443975103329]
  突然変異率$c/n$ for $cle 1$で、1:s+1)$-successルールで集団サイズを適応的に制御する。 この$c=1$のセットアップは1maxで$s1$で効率的であるが、$s ge 18$で非効率的であることを示す。
  論文  参考訳（メタデータ） (2022-04-01T15:46:12Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Mediated Uncoupled Learning: Learning Functions without Direct Input-output Correspondences [80.95776331769899]
  ペア化されたデータがない場合、$X$から$Y$を予測するタスクを考えます。 単純なアプローチは、$S_X$で$U$から$U$を予測し、$S_Y$で$U$から$Y$を予測することである。 我々は$U$を予測しない新しい方法を提案するが、$f(X)$と$S_X$をトレーニングすることで$Y = f(X)$を直接学習し、$h(U)$を予測する。
  論文  参考訳（メタデータ） (2021-07-16T22:13:29Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
  標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。 これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
  論文  参考訳（メタデータ） (2020-04-13T08:06:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。