論文の概要: Optimal Restart Strategies for Parameter-dependent Optimization Algorithms
- arxiv url: http://arxiv.org/abs/2501.10173v1
- Date: Fri, 17 Jan 2025 13:14:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-20 14:00:06.076588
- Title: Optimal Restart Strategies for Parameter-dependent Optimization Algorithms
- Title（参考訳）: パラメータ依存最適化アルゴリズムのための最適再スタート戦略
- Authors: Lisa Schönenberger, Hans-Georg Beyer,
- Abstract要約: 本稿では,未知パラメータ$lambda$に依存するアルゴリズムの再起動戦略について検討する。
$lambda$のユニークな、未知の、最適な値が存在すると仮定される。
アルゴリズムが正常に動作するためには、この値を到達または超越する必要がある。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: This paper examines restart strategies for algorithms whose successful termination depends on an unknown parameter $\lambda$. After each restart, $\lambda$ is increased, until the algorithm terminates successfully. It is assumed that there is a unique, unknown, optimal value for $\lambda$. For the algorithm to run successfully, this value must be reached or surpassed. The key question is whether there exists an optimal strategy for selecting $\lambda$ after each restart taking into account that the computational costs (runtime) increases with $\lambda$. In this work, potential restart strategies are classified into parameter-dependent strategy types. A loss function is introduced to quantify the wasted computational cost relative to the optimal strategy. A crucial requirement for any efficient restart strategy is that its loss, relative to the optimal $\lambda$, remains bounded. To this end, upper and lower bounds of the loss are derived. Using these bounds it will be shown that not all strategy types are bounded. However, for a particular strategy type, where $\lambda$ is increased multiplicatively by a constant factor $\lambda$, the relative loss function is bounded. Furthermore, it will be demonstrated that within this strategy type, there exists an optimal value for $\lambda$ that minimizes the maximum relative loss. In the asymptotic limit, this optimal choice of $\lambda$ does not depend on the unknown optimal $\lambda$.
- Abstract（参考訳）: 本稿では,未知パラメータである$\lambda$に依存するアルゴリズムの再起動戦略について検討する。
再起動すると、$\lambda$はアルゴリズムが正常に終了するまで増加する。
$\lambda$のユニークな、未知の、最適な値が存在すると仮定される。
アルゴリズムが正常に動作するためには、この値を到達または超越する必要がある。
重要な問題は、計算コスト(ランタイム)が$\lambda$で増加することを考慮し、再起動した後に$\lambda$を選択するための最適な戦略が存在するかどうかである。
この研究では、潜在的再起動戦略をパラメータ依存戦略タイプに分類する。
最適戦略に対して無駄な計算コストを定量化するために損失関数を導入する。
効率的な再起動戦略にとって重要な要件は、その損失が、最適な$\lambda$に対してバウンドであることである。
この目的のために、損失の上下の境界が導出される。
これらの境界を用いて、全ての戦略型が有界であるとは限らないことが示される。
しかし、$\lambda$ が定数係数 $\lambda$ によって乗法的に増加する特定の戦略タイプでは、相対損失関数は有界である。
さらに、この戦略タイプでは、最大相対損失を最小限に抑える$\lambda$に対して最適な値が存在することが示される。
漸近的な制限では、$\lambda$のこの最適な選択は未知の$\lambda$に依存しない。
関連論文リスト
- Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
本稿では,次数$tildemathcalO(mathrmpoly(H)sqrtSAT)$の残差を求めるアルゴリズムを提案する。
提案したアルゴリズムと分析は、占有対策によって与えられる典型的なツールを完全に回避する。
論文 参考訳（メタデータ） (2024-07-08T08:06:45Z) - Plus Strategies are Exponentially Slower for Planted Optima of Random Height [0.0]
局所オプティマの高さの小さなランダムな変動でさえプラス戦略に破壊的な効果を示し、超ポリノミアルランタイムに繋がることを示した。
以上の結果から,コンマ戦略ではなくプラス戦略が,スムーズな景観の緩やかな非構造的ゆらぎによって認知されることが示唆された。
論文 参考訳（メタデータ） (2024-04-15T11:37:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Iterative Hard Thresholding with Adaptive Regularization: Sparser
Solutions Without Sacrificing Runtime [17.60502131429094]
本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。
提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。
我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
論文 参考訳（メタデータ） (2022-04-11T19:33:15Z) - Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳（メタデータ） (2021-12-21T01:54:17Z) - Regret Bounds for Stochastic Shortest Path Problems with Linear Function
Approximation [29.549633678730054]
線形関数近似を用いたエピソディック最短経路問題に対する2つのアルゴリズムを提案する。
1つは計算コストが高いが、$tildeo (sqrtb_star3 d3 k/cmin )$ regret が得られる。
2つ目は実際は計算的に効率的であり、同じ後悔境界が得られると推測する。
論文 参考訳（メタデータ） (2021-05-04T16:05:08Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Sparse Convex Optimization via Adaptively Regularized Hard Thresholding [17.60502131429094]
本稿では,適応正規化ハードThresholding (ARHT) アルゴリズムを提案する。
また、OMP with Replacement (OMPR) for general $f$, under the condition $s > s* frackappa24$。
論文 参考訳（メタデータ） (2020-06-25T17:16:21Z) - Provably Efficient Exploration in Policy Optimization [117.09887790160406]
本稿では,最適化アルゴリズム(OPPO)の最適変種を提案する。
OPPO は $tildeO(sqrtd2 H3 T )$ regret を達成する。
我々の知る限りでは、OPPOは、探索する最初の証明可能な効率的なポリシー最適化アルゴリズムである。
論文 参考訳（メタデータ） (2019-12-12T08:40:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。