論文の概要: Optimal Algorithms for Stochastic Complementary Composite Minimization

• arxiv url: http://arxiv.org/abs/2211.01758v1
• Date: Thu, 3 Nov 2022 12:40:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-04 14:19:07.662542
• Title: Optimal Algorithms for Stochastic Complementary Composite Minimization
• Title（参考訳）: 確率補間合成最小化のための最適アルゴリズム
• Authors: Alexandre d'Aspremont, Crist\'obal Guzm\'an, Cl\'ement Lezane
• Abstract要約: 統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
• 参考スコア（独自算出の注目度）: 76.20428372514958
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization in the stochastic setting. This problem corresponds to the minimization of the sum of a (weakly) smooth function endowed with a stochastic first-order oracle, and a structured uniformly convex (possibly nonsmooth and non-Lipschitz) regularization term. Despite intensive work on closely related settings, prior to our work no complexity bounds for this problem were known. We close this gap by providing novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems. We conclude by providing numerical results comparing our methods to the state of the art.
• Abstract（参考訳）: 統計学と機械学習における正規化手法に着想を得て,確率的設定における相補的複合最小化について検討した。 この問題は、確率的一階神託と構造的一様凸(おそらくは非スムースかつ非リプシッツ)正規化項が与えられた(弱く)滑らかな関数の和の最小化に対応する。 密接に関連する設定で集中的に作業したにも関わらず、私たちの仕事の前には、この問題の複雑さの境界は知られていません。 予測と高い確率で、新たな過剰なリスク境界を提供することで、このギャップを埋めます。 我々のアルゴリズムはほぼ最適であり、このタイプの問題に対する新しい低い複雑性境界によって証明する。 我々は,我々の手法と最先端技術を比較した数値結果を提供することで結論付けた。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Complementary Composite Minimization, Small Gradients in General Norms, and Applications to Regression Problems [14.759688428864157]
  複合最小化は大規模凸最適化における強力なフレームワークである。 補完的複合最小化のための新しいアルゴリズムフレームワークを提案する。 我々は,フレームワークから得られるアルゴリズムが,ほとんどの標準最適化設定においてほぼ最適であることを証明した。
  論文  参考訳（メタデータ） (2021-01-26T19:21:28Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers [0.0]
  核ノルムへの凸緩和を最小化することは、推奨システムと堅牢な主成分分析に重要である。 本研究では, ブイロとルクシロによる核プログラムのランク因数分解のための効率的なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-13T19:04:37Z)
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities [21.13934071954103]
  本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。 SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。 結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
  論文  参考訳（メタデータ） (2020-01-22T00:05:14Z)

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

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