論文の概要: Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms

• arxiv url: http://arxiv.org/abs/2306.12383v3
• Date: Mon, 25 Dec 2023 06:41:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-27 22:33:44.526633
• Title: Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms
• Title（参考訳）: 二次バンドのサンプル複雑性:ヘッセン依存境界と最適アルゴリズム
• Authors: Qian Yu, Yining Wang, Baihe Huang, Qi Lei, Jason D. Lee
• Abstract要約: 最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
• 参考スコア（独自算出の注目度）: 64.10576998630981
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In stochastic zeroth-order optimization, a problem of practical relevance is understanding how to fully exploit the local geometry of the underlying objective function. We consider a fundamental setting in which the objective function is quadratic, and provide the first tight characterization of the optimal Hessian-dependent sample complexity. Our contribution is twofold. First, from an information-theoretic point of view, we prove tight lower bounds on Hessian-dependent complexities by introducing a concept called energy allocation, which captures the interaction between the searching algorithm and the geometry of objective functions. A matching upper bound is obtained by solving the optimal energy spectrum. Then, algorithmically, we show the existence of a Hessian-independent algorithm that universally achieves the asymptotic optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions, which are enabled by a truncation method.
• Abstract（参考訳）: 確率的ゼロ次最適化において、実用的妥当性の問題は、対象関数の局所幾何を完全に活用する方法を理解することである。 目的関数が二次的となる基本的な設定を考察し、最適なヘッセン依存サンプルの複雑性を初めて厳密に評価する。 私たちの貢献は2倍です。 まず,情報理論的な観点から,探索アルゴリズムと対象関数の幾何との相互作用を捉えたエネルギー割当という概念を導入することで,ヘッセン依存複素性に対する厳密な下界を証明した。 最適エネルギースペクトルを解くことにより、一致する上界を得る。 そして,アルゴリズムにより,全ヘッセンインスタンスの漸近的最適サンプル複雑性を普遍的に達成するヘッセン独立アルゴリズムの存在を示す。 提案アルゴリズムは, トランケーション法により実現された重み付き雑音分布に対して, 最適なサンプル複素量を示す。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Proximal Oracles for Optimization and Sampling [18.77973093341588]
  非滑らかな目的関数による凸最適化と非滑らかなポテンシャルによる対数凹型サンプリングについて検討する。 非滑らか性による課題を克服するため、アルゴリズムは最適化とサンプリングに2つの強力な近位フレームワークを用いる。
  論文  参考訳（メタデータ） (2024-04-02T18:52:28Z)
• Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization [20.11028799145883]
  複合凸最適化のための外挿法 (A-CODER) を用いた加速サイクル座標二元平均化法を提案する。 A-CODERは,前処理よりもブロック数に依存して最適な収束率が得られることを示す。 目的関数の滑らかな成分が有限和形式で表現できるような設定では、A-CODERの分散還元変種であるVR-A-CODERを導入し、最先端の複雑性を保証する。
  論文  参考訳（メタデータ） (2023-03-28T19:46:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization [14.336473214524663]
  アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。 アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。 アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
  論文  参考訳（メタデータ） (2022-04-12T16:27:49Z)
• A Granular Sieving Algorithm for Deterministic Global Optimization [6.01919376499018]
  リプシッツ連続関数に対する大域的最適化問題を解くために、勾配のない決定論的手法を開発した。 この方法は、目的関数の領域と範囲の両方で同期解析を行うグラニュラーシービングとみなすことができる。
  論文  参考訳（メタデータ） (2021-07-14T10:03:03Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds [9.632674803757475]
  距離における凸問題と非最適化問題の解法を提案する。 提案アルゴリズムは,目的関数における複雑性のレベルに適応する。
  論文  参考訳（メタデータ） (2020-10-18T02:48:22Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  本アルゴリズムは,実験者のガウス過程から引き出された一組の引き数で区切られた関数空間の有限次元ランダム部分空間列を生成する。 標準ベイズ最適化は各部分空間に適用され、次の部分空間の出発点(オリジン)として用いられる最良の解である。 シミュレーションおよび実世界の実験,すなわちブラインド関数マッチング,アルミニウム合金の最適析出強化関数の探索,深層ネットワークの学習速度スケジュール最適化において,本アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2020-09-08T06:54:11Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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