論文の概要: Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective

• arxiv url: http://arxiv.org/abs/2403.16317v2
• Date: Mon, 04 Nov 2024 17:44:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 21:25:44.849420
• Title: Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective
• Title（参考訳）: 有限スケールの最適化:境界局所次変分視点
• Authors: Jelena Diakonikolas, Cristóbal Guzmán,
• Abstract要約: 局所的な局所次変分の下での非滑らかな最適化問題について検討する。 得られた目的のクラスは、定義されたクラスに基づいて目的のクラスをカプセル化する。
• 参考スコア（独自算出の注目度）: 17.5796206457693
• License:
• Abstract: We initiate the study of nonsmooth optimization problems under bounded local subgradient variation, which postulates bounded difference between (sub)gradients in small local regions around points, in either average or maximum sense. The resulting class of objective functions encapsulates the classes of objective functions traditionally studied in optimization, which are defined based on either Lipschitz continuity of the objective or H\"{o}lder/Lipschitz continuity of its gradient. Further, the defined class contains functions that are neither Lipschitz continuous nor have a H\"{o}lder continuous gradient. When restricted to the traditional classes of optimization problems, the parameters defining the studied classes lead to more fine-grained complexity bounds, recovering traditional oracle complexity bounds in the worst case but generally leading to lower oracle complexity for functions that are not ``worst case.'' Some highlights of our results are that: (i) it is possible to obtain complexity results for both convex and nonconvex problems with the (local or global) Lipschitz constant being replaced by a constant of local subgradient variation and (ii) mean width of the subdifferential set around the optima plays a role in the complexity of nonsmooth optimization, particularly in parallel settings. A consequence of (ii) is that for any error parameter $\epsilon > 0$, parallel oracle complexity of nonsmooth Lipschitz convex optimization is lower than its sequential oracle complexity by a factor $\tilde{\Omega}\big(\frac{1}{\epsilon}\big)$ whenever the objective function is piecewise linear with polynomially many pieces in the input size. This is particularly surprising as existing parallel complexity lower bounds are based on such classes of functions. The seeming contradiction is resolved by considering the region in which the algorithm is allowed to query the objective.
• Abstract（参考訳）: 本研究は,局所的な局所次変分に基づく非滑らかな最適化問題の研究を開始し,点周辺の小さな局所領域における(部分)次数間の有界差を,平均的あるいは最大的な意味で仮定する。 得られた目的関数のクラスは、最適化において伝統的に研究されてきた対象関数のクラスをカプセル化しており、これは目的関数のリプシッツ連続性またはその勾配のH\"{o}lder/Lipschitz連続性に基づいて定義される。 さらに、定義されるクラスは、リプシッツ連続でもなく、H\"{o}lder continuous gradient も持たない函数を含む。 従来の最適化問題のクラスに制限された場合、研究されたクラスを定義するパラメータはよりきめ細かな複雑性境界を導き、最悪の場合は伝統的なオラクルの複雑性境界を回復するが、一般に ``worst case' でない関数のオラクルの複雑さを低くする。 「''結果のハイライトは以下のとおりである。 i)(局所的あるいは大域的)リプシッツ定数を局所的な下次変動の定数に置き換えた凸問題と非凸問題の両方の複雑性結果を得ることが可能である。 (ii)オプティマ周りの部分微分集合の平均幅は、非滑らかな最適化の複雑さ、特に平行な設定において重要な役割を果たしている。 結果 (ii) 任意の誤差パラメータ $\epsilon > 0$ に対して、非滑らかなリプシッツ凸最適化の並列オラクル複雑性は、入力サイズの多項式的に多くの部分を持つ目的関数が多項式線型であるときに、その逐次オラクル複雑性よりも$\tilde{\Omega}\big(\frac{1}{\epsilon}\big)$ より低い。 既存の並列複雑性の低い境界はそのような関数のクラスに基づいているため、これは特に驚くべきことである。 アルゴリズムが目的を問うことができる領域を考慮して、一見矛盾を解消する。

関連論文リスト

• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
  論文  参考訳（メタデータ） (2022-06-30T02:17:11Z)
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning [87.60600646105696]
  内部最適化問題が凸であるが非滑らかである場合の一階法を研究する。 本研究では, ヤコビアンの近位勾配降下と近位座標降下収率列の前方モード微分が, 正確なヤコビアンに向かって収束していることを示す。
  論文  参考訳（メタデータ） (2021-05-04T17:31:28Z)
• Cyclic Coordinate Dual Averaging with Extrapolation [22.234715500748074]
  単調作用素を用いた変分不等式(VI)問題の一般クラスに適用可能な新しいブロック座標法を提案する。 得られた収束境界は、全勾配法の最適収束境界と一致する。 座標ブロックが$m$の場合、我々の境界における勾配リプシッツ定数は、従来のユークリッドのリプシッツ定数と比較して$sqrtm$よりも大きくなることはない。
  論文  参考訳（メタデータ） (2021-02-26T00:28:58Z)
• Global Convergence of Model Function Based Bregman Proximal Minimization Algorithms [17.740376367999705]
  連続微分可能関数のリプシッツ写像は様々な最適化アルゴリズムにおいて重要な役割を果たす。 モデル$L$madプロパティと呼ばれるグローバル収束アルゴリズムを提案します。
  論文  参考訳（メタデータ） (2020-12-24T08:09:22Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization [21.435973899949285]
  SAG, SAGA, SVRG, SARAHを含むランダム化漸進勾配法では, 有限和最適化の典型的な2つの場合において, 厳密に低い複雑性境界を導出する。 結果は,各成分関数が強凸で滑らかな場合のKatyushaやVRADAの上部複雑性と密に一致し,有限サム関数が強凸で成分関数が平均滑らかな場合のKatyushaXとSDCAの上部複雑性と密に一致した。
  論文  参考訳（メタデータ） (2020-10-17T11:19:07Z)

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

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