論文の概要: Characterizing Parametric and Convergence Stability in Nonconvex and Nonsmooth Optimizations: A Geometric Approach

• arxiv url: http://arxiv.org/abs/2204.01643v1
• Date: Mon, 4 Apr 2022 16:46:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-05 14:07:47.318364
• Title: Characterizing Parametric and Convergence Stability in Nonconvex and Nonsmooth Optimizations: A Geometric Approach
• Title（参考訳）: 非凸および非滑らか最適化におけるパラメトリックおよび収束安定性の特徴:幾何学的アプローチ
• Authors: Xiaotie Deng, Hanyu Li, Ningyuan Li
• Abstract要約: 連続パラメータ化非平滑関数点f$f$の最小化における安定性の問題を考える。 定常安定性の2つの概念:パラメトリック安定性と分割安定性を示す。 これらの概念が幾何学理論と深く結びついていることが示される。
• 参考スコア（独自算出の注目度）: 6.605210585717247
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider stability issues in minimizing a continuous (probably parameterized, nonconvex and nonsmooth) real-valued function $f$. We call a point stationary if all its possible directional derivatives are nonnegative. In this work, we focus on two notions of stability on stationary points of $f$: parametric stability and convergence stability. Parametric considerations are widely studied in various fields, including smoothed analysis, numerical stability, condition numbers and sensitivity analysis for linear programming. Parametric stability asks whether minor perturbations on parameters lead to dramatic changes in the position and $f$ value of a stationary point. Meanwhile, convergence stability indicates a non-escapable solution: Any point sequence iteratively produced by an optimization algorithm cannot escape from a neighborhood of a stationary point but gets close to it in the sense that such stationary points are stable to the precision parameter and algorithmic numerical errors. It turns out that these notions have deep connections to geometry theory. We show that parametric stability is linked to deformations of graphs of functions. On the other hand, convergence stability is concerned with area partitioning of the function domain. Utilizing these connections, we prove quite tight conditions of these two stability notions for a wide range of functions and optimization algorithms with small enough step sizes and precision parameters. These conditions are subtle in the sense that a slightly weaker function requirement goes to the opposite of primitive intuitions and leads to wrong conclusions. We present three applications of this theory. These applications reveal some understanding on Nash equilibrium computation, nonconvex and nonsmooth optimization, as well as the new optimization methodology of deep neural networks.
• Abstract（参考訳）: 連続(パラメータ化、非凸、非滑らか)の実数値関数 $f$ を最小化するときの安定性の問題を考える。 すべての方向微分が非負であれば、点を定常と呼ぶ。 本研究は,パラメータ安定性と収束安定性という,固定点における安定性の2つの概念に焦点をあてる。 パラメトリックな考察は、滑らかな解析、数値安定性、条件数、線形計画の感度解析など様々な分野で広く研究されている。 パラメトリック安定性は、パラメータの小さな摂動が位置の劇的な変化と静止点の$f$値をもたらすかどうかを問う。 最適化アルゴリズムによって反復的に生成される任意の点列は、定常点の近傍から逃れることはできないが、そのような定常点が精度パラメータとアルゴリズムの数値誤差に対して安定であるという意味で、それに近い。 これらの概念は幾何学理論と深い関係を持つことが判明した。 パラメトリック安定性は関数グラフの変形と関連していることを示す。 一方、収束安定性は関数領域の領域分割に関係している。 これらの接続を利用することで、この2つの安定性の概念の極めて厳密な条件を幅広い関数と最適化アルゴリズムに対して証明する。 これらの条件は、わずかに弱い函数要件が原始直観の反対に進み、間違った結論に至るという意味で微妙である。 この理論の応用は3つある。 これらの応用により、nash平衡計算、非凸および非滑らか最適化、およびディープニューラルネットワークの新しい最適化手法に関するいくつかの理解が明らかになった。

関連論文リスト

• ADMM for Structured Fractional Minimization [7.9047096855236125]
  我々は、数値化器が微分可能な関数を含むような、構造化された分数問題のクラスを考える。 本稿では,このクラスの問題に対して,最初の乗算器の交換法であるsf FADMMを紹介する。
  論文  参考訳（メタデータ） (2024-11-12T02:50:12Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  本研究では,2次損失を持つ1層多変量ReLUネットワークをトレーニングする際に,勾配勾配勾配が収束する解のタイプについて検討する。 我々は、浅いReLUネットワークが普遍近似器であるにもかかわらず、安定した浅層ネットワークは存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-06-30T09:17:39Z)
• Exact Mean Square Linear Stability Analysis for SGD [28.65663421598186]
  勾配降下(SGD)の線形安定性に必要かつ十分なステップサイズを明示的条件として提示する。 SGDの安定性閾値は、全バッチ勾配ステップw.p.$-p$と1サンプル勾配ステップw.p.$p$の混合プロセスと等価であることを示す。
  論文  参考訳（メタデータ） (2023-06-13T15:29:23Z)
• Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
  我々は分散環境でスティーフェル多様体に焦点をあて、$nMn log-1)$のエージェントの連結ネットワークをテストする。 そこで本研究では,nMn log-1 以下の自然ステーションを強制的に強制する分散下位段階法 (DRSM)$ という手法を提案する。
  論文  参考訳（メタデータ） (2023-03-31T02:56:23Z)
• Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees [57.67528738886731]
  誘導点に基づくスケーラブルスパース近似の数値安定性について検討する。 地理空間モデリングなどの低次元タスクに対しては,これらの条件を満たす点を自動計算する手法を提案する。
  論文  参考訳（メタデータ） (2022-10-14T15:20:17Z)
• Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
  有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。 本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
  論文  参考訳（メタデータ） (2021-02-09T05:35:53Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  我々は,SGDの反復的リスクによって制御される新しい境界を開発する,平均モデル安定性と呼ばれる新しい安定性尺度を導入する。 これにより、最良のモデルの振舞いによって一般化境界が得られ、低雑音環境における最初の既知の高速境界が導かれる。 我々の知る限りでは、このことはSGDの微分不能な損失関数でさえも初めて知られている安定性と一般化を与える。
  論文  参考訳（メタデータ） (2020-06-15T06:30:19Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization [73.38702974136102]
  アルゴリズムの高速化のために,パラメータ再起動方式が提案されている。 本論文では,非滑らかな問題を解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:06:27Z)

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

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