論文の概要: Subgradient Selection Convergence Implies Uniform Subdifferential Set Convergence: And Other Tight Convergences Rates in Stochastic Convex Composite Minimization
- arxiv url: http://arxiv.org/abs/2405.10289v4
- Date: Sun, 22 Dec 2024 17:33:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:51:31.906803
- Title: Subgradient Selection Convergence Implies Uniform Subdifferential Set Convergence: And Other Tight Convergences Rates in Stochastic Convex Composite Minimization
- Title(参考訳): 半次選択収束が一様部分微分集合収束に影響を及ぼす:確率凸コンポジット最小化におけるその他のタイト収束速度
- Authors: Feng Ruan,
- Abstract要約: 非滑らかな近似最適化の非平均化では、部分微分写像の均一収束を理解することが重要である。
この研究は、部分微分写像の一様収束と下次写像の集団を結びつける。
偏微分凸複合目的に対する一様収束率を導出する。
- 参考スコア(独自算出の注目度): 2.719510212909501
- License:
- Abstract: In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the population risk. Yet, characterizing this convergence remains a fundamental challenge. This work introduces a novel perspective by connecting the uniform convergence of subdifferential mappings to that of subgradient mappings as empirical risk converges to the population risk. We prove that, for stochastic weakly-convex objectives, and within any open set, a uniform bound on the convergence of subgradients -- chosen arbitrarily from the corresponding subdifferential sets -- translates to a uniform bound on the convergence of the subdifferential sets themselves, measured by the Hausdorff metric. Using this technique, we derive uniform convergence rates for subdifferential sets of stochastic convex-composite objectives. Our results do not rely on key distributional assumptions in the literature, such as the continuous differentiability of the population objective, yet still provide tight convergence rates. These guarantees lead to new insights into the nonsmooth landscapes of such objectives within finite samples.
- Abstract(参考訳): 非平滑で非凸確率最適化では、集団リスクにアプローチする際のサンプル平均推定値の定常点を解析するために、部分微分写像の均一収束を理解することが重要である。
しかし、この収束を特徴づけることは依然として根本的な課題である。
この研究は、経験的リスクが集団リスクに収束するにつれて、部分微分写像の均一収束と下次写像の均一収束を結びつけることによって、新しい視点を導入する。
確率的弱凸対象に対しては、任意の開集合において、級数(対応する部分微分集合から任意に選択される)の収束に関する一様有界は、ハウスドルフ計量によって測られる部分微分集合自体の収束に関する一様有界となることを証明している。
この手法を用いて,確率凸合成対象の偏微分集合に対する一様収束率を導出する。
我々の結果は、人口目標の連続的な微分可能性のような文献における主要な分布仮定には依存していないが、それでも厳密な収束率を提供している。
これらの保証は、有限サンプル内のそのような目的の非滑らかな風景に対する新たな洞察をもたらす。
関連論文リスト
- A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Set [20.166217494056916]
制約的な仮定を課さずに共分散推定器を構築するための原理的手法を提案する。
頑健な推定器は効率的に計算可能で一貫したものであることを示す。
合成および実データに基づく数値実験により、我々の頑健な推定器は最先端の推定器と競合していることが示された。
論文 参考訳(メタデータ) (2024-05-30T15:01:18Z) - A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。
本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文 参考訳(メタデータ) (2024-05-24T21:09:19Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - Stochastic Saddle Point Problems with Decision-Dependent Distributions [0.6091702876917279]
本稿では,静的設定と時間変化設定の両方において決定に依存するサドル点問題に焦点をあてる。
定常ミニマックス問題に対するサドル点である平衡点の概念を導入する。
原始双対アルゴリズムは、同様の方法でサドル点に収束することを示す。
論文 参考訳(メタデータ) (2022-01-07T03:36:41Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳(メタデータ) (2021-06-30T18:32:46Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Sequential Estimation of Convex Divergences using Reverse Submartingales
and Exchangeable Filtrations [31.088836418378534]
本稿では,分布間の凸発散の逐次推定手法を提案する。
我々のアプローチの技術的基盤は、経験的凸の発散が(部分的に順序づけられた)逆潜水星であることの観察にある。
これらの技術は、信頼配列と凸発散の両方に関する既存の文献に強力な追加であるように見える。
論文 参考訳(メタデータ) (2021-03-16T18:22:14Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳(メタデータ) (2020-12-07T19:14:49Z) - Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized
Equations [0.0]
演算子を期待値とする単調な包摂問題を考える。
分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。
本稿では,不確実性に対処する手法を提案する。
論文 参考訳(メタデータ) (2020-08-26T02:33:27Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。
この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文 参考訳(メタデータ) (2020-06-06T19:08:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。