論文の概要: Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses

• arxiv url: http://arxiv.org/abs/2010.12033v2
• Date: Mon, 28 Dec 2020 22:02:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 08:20:49.787853
• Title: Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses
• Title（参考訳）: Lipschitzの継続性のないRegret境界: 相対的Lipschitz損失によるオンライン学習
• Authors: Yihan Zhou, Victor S. Portella, Mark Schmidt, Nicholas J. A. Harvey
• Abstract要約: オンライン凸最適化 (OCO) において、関数のリプシッツ連続性は、サブ線形後悔を得るために一般的に仮定される。 本研究では,相対リプシッツ関数と相対凸関数のOCOを考える。 以下に示すように、正規化されたリーダーアルゴリズムとオンラインミラー降下の変種について、残念な点を示す。
• 参考スコア（独自算出の注目度）: 19.554559253046225
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In online convex optimization (OCO), Lipschitz continuity of the functions is commonly assumed in order to obtain sublinear regret. Moreover, many algorithms have only logarithmic regret when these functions are also strongly convex. Recently, researchers from convex optimization proposed the notions of "relative Lipschitz continuity" and "relative strong convexity". Both of the notions are generalizations of their classical counterparts. It has been shown that subgradient methods in the relative setting have performance analogous to their performance in the classical setting. In this work, we consider OCO for relative Lipschitz and relative strongly convex functions. We extend the known regret bounds for classical OCO algorithms to the relative setting. Specifically, we show regret bounds for the follow the regularized leader algorithms and a variant of online mirror descent. Due to the generality of these methods, these results yield regret bounds for a wide variety of OCO algorithms. Furthermore, we further extend the results to algorithms with extra regularization such as regularized dual averaging.
• Abstract（参考訳）: オンライン凸最適化 (OCO) において、関数のリプシッツ連続性は、サブ線形後悔を得るために一般的に仮定される。 さらに、多くのアルゴリズムは、これらの関数が強い凸であるときにのみ対数的後悔を持つ。 近年、凸最適化の研究者は「相対的リプシッツ連続性」と「相対的強い凸性」の概念を提案した。 どちらの概念も古典的概念の一般化である。 相対的な設定における下位段階の手法は、古典的な設定における性能に類似した性能を有することが示されている。 本研究では,相対リプシッツ関数と相対強凸関数に対するocoを考える。 古典的ocoアルゴリズムの既知の後悔の限界を相対的な設定に拡張する。 具体的には、正規化リーダアルゴリズムとオンラインミラー降下の変種に従うことに対する後悔の限界を示す。 これらの手法の一般化により、これらの結果は様々なOCOアルゴリズムに対する後悔の限界をもたらす。 さらに、正規化双対平均化のような余分な正規化を伴うアルゴリズムに結果をさらに拡張する。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective [17.5796206457693]
  局所的な局所次変分の下での非滑らかな最適化問題について検討する。 得られた目的のクラスは、定義されたクラスに基づいて目的のクラスをカプセル化する。
  論文  参考訳（メタデータ） (2024-03-24T22:42:40Z)
• Second Order Methods for Bandit Optimization and Control [34.51425758864638]
  我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。 また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
  論文  参考訳（メタデータ） (2024-02-14T04:03:38Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Convergence rate of the (1+1)-evolution strategy on locally strongly convex functions with lipschitz continuous gradient and their monotonic transformations [20.666734673282498]
  進化戦略(ES)は、ブラックボックス連続最適化のための有望なアルゴリズムの1つである。 本研究では,局所$L$-強凸関数上の (1+1)-ES の線型収束率の上界と下界を$U$-Lipschitz連続勾配で導出した。
  論文  参考訳（メタデータ） (2022-09-26T07:16:50Z)
• Generalization in Supervised Learning Through Riemannian Contraction [4.3604518673788135]
  教師付き学習環境では、計量 0 がアセシアンレート $lambda で収縮している場合、それは一様に$math であることを示す。 結果は、連続および安定な $-time において、勾配と決定論的損失曲面を保っている。 それらは、Descent$凸面や強い凸損失面など、ある種の線形な設定で最適であることを示すことができる。
  論文  参考訳（メタデータ） (2022-01-17T23:08:47Z)
• Cyclic Coordinate Dual Averaging with Extrapolation [22.234715500748074]
  単調作用素を用いた変分不等式(VI)問題の一般クラスに適用可能な新しいブロック座標法を提案する。 得られた収束境界は、全勾配法の最適収束境界と一致する。 座標ブロックが$m$の場合、我々の境界における勾配リプシッツ定数は、従来のユークリッドのリプシッツ定数と比較して$sqrtm$よりも大きくなることはない。
  論文  参考訳（メタデータ） (2021-02-26T00:28:58Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Exactly Computing the Local Lipschitz Constant of ReLU Networks [98.43114280459271]
  ニューラルネットワークの局所リプシッツ定数は、堅牢性、一般化、公正性評価に有用な指標である。 ReLUネットワークのリプシッツ定数を推定するために, 強い不適合性を示す。 このアルゴリズムを用いて、競合するリプシッツ推定器の密度と正規化トレーニングがリプシッツ定数に与える影響を評価する。
  論文  参考訳（メタデータ） (2020-03-02T22:15:54Z)

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

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