論文の概要: Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces

• arxiv url: http://arxiv.org/abs/2507.19465v1
• Date: Fri, 25 Jul 2025 17:50:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-28 16:16:49.056638
• Title: Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces
• Title（参考訳）: 未知の平板を有する非平板問題に対する線形収束アルゴリズム
• Authors: Zhe Zhang, Suvrit Sra,
• Abstract要約: 本研究では,ドメインを滑らかな部分へ分割する関数を高速に最適化するアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 38.01989268269625
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop efficient algorithms for optimizing piecewise smooth (PWS) functions where the underlying partition of the domain into smooth pieces is \emph{unknown}. For PWS functions satisfying a quadratic growth (QG) condition, we propose a bundle-level (BL) type method that achieves global linear convergence -- to our knowledge, the first such result for any algorithm for this problem class. We extend this method to handle approximately PWS functions and to solve weakly-convex PWS problems, improving the state-of-the-art complexity to match the benchmark for smooth non-convex optimization. Furthermore, we introduce the first verifiable and accurate termination criterion for PWS optimization. Similar to the gradient norm in smooth optimization, this certificate tightly characterizes the optimality gap under the QG condition, and can moreover be evaluated without knowledge of any problem parameters. We develop a search subroutine for this certificate and embed it within a guess-and-check framework, resulting in an almost parameter-free algorithm for both the convex QG and weakly-convex settings.
• Abstract（参考訳）: 我々は,ドメインを滑らかな部分へ分割する関数を最適化する効率的なアルゴリズムを開発した。 二次成長(QG)条件を満たすPWS関数に対して,この問題クラスのアルゴリズムとして初めて,大域的線形収束を実現するバンドルレベル(BL)型手法を提案する。 本手法は, ほぼPWS関数を扱うために拡張され, 弱凸なPWS問題を解くために, 平滑な非凸最適化のためのベンチマークに適合するように, 最先端の複雑さを改善した。 さらに、PWS最適化のための検証可能かつ正確な終了基準についても紹介する。 滑らかな最適化における勾配ノルムと同様に、この証明はQG条件下での最適性ギャップを厳しく特徴づけ、さらに問題パラメータの知識なしに評価することができる。 我々は,この証明の検索サブルーチンを開発し,推測と検証のフレームワークに組み込むことにより,凸QGと弱凸設定の両方に対してほぼパラメータフリーなアルゴリズムを実現する。

関連論文リスト

• Adam assisted Fully informed Particle Swarm Optimzation ( Adam-FIPSO ) based Parameter Prediction for the Quantum Approximate Optimization Algorithm (QAOA) [1.024113475677323]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、マックス・カット問題などの最適化問題の解法として用いられる顕著な変分アルゴリズムである。 QAOAの重要な課題は、高品質なソリューションにつながる適切なパラメータを効率的に特定することである。
  論文  参考訳（メタデータ） (2025-06-07T13:14:41Z)
• Extended convexity and smoothness and their applications in deep learning [5.281849820329249]
  本稿では,ディープラーニングにおける非滑らかな最適化のメカニズムを明らかにすることを目的とする。 解析の結果、勾配降下法(SGD)アルゴリズムは経験的リスクを効果的に最小化できることが示された。
  論文  参考訳（メタデータ） (2024-10-08T08:40:07Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• 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)
• A simple uniformly optimal method without line search for convex optimization [9.280355951055865]
  パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。 滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-16T05:26:03Z)
• 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)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• 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)
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems [12.010310883787911]
  我々は、弱凸(おそらく非滑らかな)最適化問題の重要なクラスを解くための、適応的な段階的な新しい手法の族を解析する。 実験結果から,提案アルゴリズムが0次勾配降下と設計変動を経験的に上回ることを示す。
  論文  参考訳（メタデータ） (2020-05-19T07:44:52Z)

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

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