論文の概要: Proximal Oracles for Optimization and Sampling

• arxiv url: http://arxiv.org/abs/2404.02239v1
• Date: Tue, 2 Apr 2024 18:52:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-04 19:28:46.504255
• Title: Proximal Oracles for Optimization and Sampling
• Title（参考訳）: 最適化とサンプリングのための近位オラクル
• Authors: Jiaming Liang, Yongxin Chen,
• Abstract要約: 非滑らかな目的関数による凸最適化と非滑らかなポテンシャルによる対数凹型サンプリングについて検討する。 非滑らか性による課題を克服するため、アルゴリズムは最適化とサンプリングに2つの強力な近位フレームワークを用いる。
• 参考スコア（独自算出の注目度）: 18.77973093341588
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider convex optimization with non-smooth objective function and log-concave sampling with non-smooth potential (negative log density). In particular, we study two specific settings where the convex objective/potential function is either semi-smooth or in composite form as the finite sum of semi-smooth components. To overcome the challenges caused by non-smoothness, our algorithms employ two powerful proximal frameworks in optimization and sampling: the proximal point framework for optimization and the alternating sampling framework (ASF) that uses Gibbs sampling on an augmented distribution. A key component of both optimization and sampling algorithms is the efficient implementation of the proximal map by the regularized cutting-plane method. We establish the iteration-complexity of the proximal map in both semi-smooth and composite settings. We further propose an adaptive proximal bundle method for non-smooth optimization. The proposed method is universal since it does not need any problem parameters as input. Additionally, we develop a proximal sampling oracle that resembles the proximal map in optimization and establish its complexity using a novel technique (a modified Gaussian integral). Finally, we combine this proximal sampling oracle and ASF to obtain a Markov chain Monte Carlo method with non-asymptotic complexity bounds for sampling in semi-smooth and composite settings.
• Abstract（参考訳）: 非滑らかな目的関数による凸最適化と非滑らかなポテンシャル(負の対数密度)による対数対数検定について検討する。 特に,凸目的/ポテンシャル関数が半滑らかか,あるいは半滑らか成分の有限和として合成形式の2つの具体的設定について検討する。 非平滑性によって引き起こされる課題を克服するため、我々のアルゴリズムは最適化とサンプリングに2つの強力な近位フレームワーク、すなわち最適化のための近位点フレームワークと、拡張分布上でギブスサンプリングを使用する交互サンプリングフレームワーク(ASF)を採用している。 最適化アルゴリズムとサンプリングアルゴリズムの両方の重要な要素は、正規化切削平面法による近位写像の効率的な実装である。 半滑らかな構成と複合的な構成の両方において、近位写像の反復複雑性を確立する。 さらに,非滑らかな最適化のための適応的近位バンドル法を提案する。 提案手法は入力として問題パラメータを必要としないため普遍的である。 さらに、最適化における近位写像に類似した近位サンプリングオラクルを開発し、新しい手法(ガウス積分の修正)を用いてその複雑さを確立する。 最後に、この近位サンプリングオラクルとASFを組み合わせて、半平滑で複合的な設定でサンプリングするための非漸近的複雑性境界を持つマルコフ連鎖モンテカルロ法を得る。

関連論文リスト

• Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation [2.3342885570554652]
  本稿では,プロセスカーネルに対する一括近似と,取得関数に対するMIQP表現を紹介する。 我々は,合成関数,制約付きベンチマーク,ハイパーチューニングタスクに関するフレームワークを実証的に実証した。
  論文  参考訳（メタデータ） (2024-10-22T10:56:52Z)
• Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization [55.115992622028685]
  以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。 最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
  論文  参考訳（メタデータ） (2023-10-26T19:56:52Z)
• Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
  2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。 本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
  論文  参考訳（メタデータ） (2023-09-04T19:47:04Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。 我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。 アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
  論文  参考訳（メタデータ） (2022-10-31T17:59:29Z)
• A Proximal Algorithm for Sampling from Non-convex Potentials [14.909442791255042]
  滑らかさに欠ける非滑らかなポテンシャルの問題を考察する。 滑らかではなく、ポテンシャルは半滑らかあるいは多重多重滑らか関数であると仮定される。 我々は、交互サンプリングフレームワークとして知られるGibbsサンプリングの特殊なケースを開発する。
  論文  参考訳（メタデータ） (2022-05-20T13:58:46Z)
• A Proximal Algorithm for Sampling from Non-smooth Potentials [10.980294435643398]
  非滑らかなポテンシャルからのサンプリングのための新しいMCMCアルゴリズムを提案する。 本手法は, 近似バンドル法と交互サンプリングフレームワークに基づく。 この研究の重要な貢献は、任意の凸非滑らかポテンシャルに対して制限されたガウスオラクルを実現する高速アルゴリズムである。
  論文  参考訳（メタデータ） (2021-10-09T15:26:07Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• 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)

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

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