論文の概要: Proximal Oracles for Optimization and Sampling
- arxiv url: http://arxiv.org/abs/2404.02239v2
- Date: Wed, 09 Jul 2025 02:24:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-10 17:37:43.185965
- 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 H\"older smooth or in hybrid form as the finite sum of H\"older 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 its iteration-complexity under both H\"older smoothness and hybrid settings using novel convergence analysis, yielding results that are new to the literature. We further propose an adaptive proximal bundle method for non-smooth optimization that employs an aggressive adaptive stepsize strategy, which adjusts stepsizes only when necessary and never rejects iterates. The proposed method is universal since it does not need any problem parameters as input. Additionally, we provide an exact implementation of a proximal sampling oracle, analogous to the proximal map in optimization, along with simple complexity analyses for both the H\"older smooth and hybrid cases, using a novel technique based on 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 H\"older smooth and hybrid settings.
- Abstract（参考訳）: 非平滑な目的関数による凸最適化と非平滑なポテンシャル(負の対数密度)による対数対数対数検定について検討する。
特に、凸目的/ポテンシャル関数が H\"古い滑らかなか、H\"古い滑らかな成分の有限和としてハイブリッド形式の2つの特定の設定について検討する。
非平滑性によって引き起こされる課題を克服するため、我々のアルゴリズムは最適化とサンプリングに2つの強力な近位フレームワーク、すなわち最適化のための近位点フレームワークと、拡張分布上でギブスサンプリングを使用する交互サンプリングフレームワーク(ASF)を採用している。
最適化アルゴリズムとサンプリングアルゴリズムの両方の重要な要素は、正規化切削平面法による近位写像の効率的な実装である。
我々は,H\"古い滑らかさとハイブリット・セッティングの両面において,新たな収束解析を用いて反復複雑性を確立し,文献に新しい結果をもたらす。
さらに,非滑らかな最適化のための適応的近位バンドル法を提案し,適応的適応的段階化戦略を用いて,必要な時にのみ段階化を調整し,繰り返しを拒否しない。
提案手法は入力として問題パラメータを必要としないため普遍的である。
さらに、最適化における近位写像に類似した近位サンプリングオラクルの正確な実装と、修正ガウス積分に基づく新しい手法を用いて、H\"古いスムーズかつハイブリッドなケースの単純な複雑性解析を提供する。
最後に、この近位サンプリングオラクルとASFを組み合わせて、H\"古いスムーズかつハイブリッドな設定でサンプリングするための非漸近的複雑性境界を持つマルコフ連鎖モンテカルロ法を得る。
関連論文リスト
- Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation [2.3342885570554652]
本稿では,プロセスカーネルに対する一括近似と,取得関数に対するMIQP表現を紹介する。
我々は,合成関数,制約付きベンチマーク,ハイパーチューニングタスクに関するフレームワークを実証的に実証した。
論文 参考訳（メタデータ） (2024-10-22T10:56:52Z) - A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
論文 参考訳（メタデータ） (2023-12-04T19:00:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。