論文の概要: On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedback

• arxiv url: http://arxiv.org/abs/2210.05584v1
• Date: Tue, 11 Oct 2022 16:16:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-12 14:36:30.250640
• Title: On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedback
• Title（参考訳）: 帯域フィードバックを用いた非定常確率最適化の適応性について
• Authors: Yining Wang
• Abstract要約: 集約された関数の変化が事前認識されている場合、単純な再起動アルゴリズムが最適の動的後悔を達成できることが示される。 また,静止ベンチマークに対して良好な後悔を達成するアルゴリズムを,動的ベンチマークに対して良い後悔を与えるアルゴリズムに自動的に変換できることを示す。
• 参考スコア（独自算出の注目度）: 11.208914594208654
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we study the non-stationary stochastic optimization question with bandit feedback and dynamic regret measures. The seminal work of Besbes et al. (2015) shows that, when aggregated function changes is known a priori, a simple re-starting algorithm attains the optimal dynamic regret. In this work, we designed a stochastic optimization algorithm with fixed step sizes, which combined together with the multi-scale sampling framework of Wei and Luo (2021) achieves the optimal dynamic regret in non-stationary stochastic optimization without requiring prior knowledge of function change budget, thereby closes a question that has been open for a while. We also establish an additional result showing that any algorithm achieving good regret against stationary benchmarks with high probability could be automatically converted to an algorithm that achieves good regret against dynamic benchmarks, which is applicable to a wide class of bandit convex optimization algorithms.
• Abstract（参考訳）: 本稿では,バンディットフィードバックと動的後悔尺度を用いた非定常確率的最適化問題について検討する。 besbes et al. (2015) の独創的な研究は、集約関数の変化が前もって知られているとき、単純な再スタートアルゴリズムが最適な動的後悔を達成することを示している。 本研究では,wei と luo (2021) のマルチスケールサンプリングフレームワークと組み合わせることで,関数変更予算の事前知識を必要とせず,非定常確率的最適化における最適動的後悔を実現する,固定ステップサイズの確率的最適化アルゴリズムを考案した。 また,固定ベンチマークに対して高い確率で良好な後悔を達成できるアルゴリズムを動的ベンチマークに対して良好な後悔を達成できるアルゴリズムに自動的に変換できることが,幅広い帯域幅の凸最適化アルゴリズムに適用できることを示す。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  このアルゴリズムは指数勾配と$p$-normアルゴリズムの組み合わせと解釈できる。 彼らはシーケンス依存の後悔の上界を達成し、スパース目標決定変数の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-08-08T11:29:55Z)
• Latency considerations for stochastic optimizers in variational quantum algorithms [0.02294014185517203]
  ノイズの多い中間雑音の量子スケール設定で顕著になった変分量子アルゴリズムは、ハードウェアの実装を必要とする。 これまでのところ、ほとんどの研究では勾配反復を古典的な反復として用いたアルゴリズムが採用されている。 本研究では,古典的決定論的アルゴリズムの力学をエミュレートするプロセスを生成する最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-01-31T18:51:24Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes [4.355567556995855]
  ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。 標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
  論文  参考訳（メタデータ） (2021-03-23T00:28:15Z)
• Optimizing Optimizers: Regret-optimal gradient descent algorithms [9.89901717499058]
  我々は,後悔最適アルゴリズムの存在,一意性,一貫性について検討する。 制御問題に対する一階最適条件を提供することにより、後悔最適アルゴリズムはそれらの力学において特定の構造を満たす必要があることを示す。 それらを近似する高速な数値法を提案し,長期的後悔を直接最適化する最適化アルゴリズムを生成する。
  論文  参考訳（メタデータ） (2020-12-31T19:13:53Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Stochastic batch size for adaptive regularization in deep network optimization [63.68104397173262]
  ディープラーニングフレームワークにおける機械学習問題に適用可能な適応正規化を取り入れた一階最適化アルゴリズムを提案する。 一般的なベンチマークデータセットに適用した従来のネットワークモデルに基づく画像分類タスクを用いて,提案アルゴリズムの有効性を実証的に実証した。
  論文  参考訳（メタデータ） (2020-04-14T07:54:53Z)

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

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