論文の概要: Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets

• arxiv url: http://arxiv.org/abs/2402.12868v2
• Date: Sun, 16 Feb 2025 19:51:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-18 14:06:20.396724
• Title: Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets
• Title（参考訳）: 確率的オンライン凸最適化における確率集合の曲率の爆発による高速化
• Authors: Taira Tsuchiya, Shinji Ito,
• Abstract要約: オンライン線形最適化では、損失関数の平均勾配が一定の閾値を超えると、実現可能な集合の曲率を利用することができることが知られている。 本研究では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
• 参考スコア（独自算出の注目度）: 35.8717656676532
• License:
• Abstract: In this work, we explore online convex optimization (OCO) and introduce a new condition and analysis that provides fast rates by exploiting the curvature of feasible sets. In online linear optimization, it is known that if the average gradient of loss functions exceeds a certain threshold, the curvature of feasible sets can be exploited by the follow-the-leader (FTL) algorithm to achieve a logarithmic regret. This study reveals that algorithms adaptive to the curvature of loss functions can also leverage the curvature of feasible sets. In particular, we first prove that if an optimal decision is on the boundary of a feasible set and the gradient of an underlying loss function is non-zero, then the algorithm achieves a regret bound of $O(\rho \log T)$ in stochastic environments. Here, $\rho > 0$ is the radius of the smallest sphere that includes the optimal decision and encloses the feasible set. Our approach, unlike existing ones, can work directly with convex loss functions, exploiting the curvature of loss functions simultaneously, and can achieve the logarithmic regret only with a local property of feasible sets. Additionally, the algorithm achieves an $O(\sqrt{T})$ regret even in adversarial environments, in which FTL suffers an $\Omega(T)$ regret, and achieves an $O(\rho \log T + \sqrt{C \rho \log T})$ regret in corrupted stochastic environments with corruption level $C$. Furthermore, by extending our analysis, we establish a matching regret upper bound of $O\Big(T^{\frac{q-2}{2(q-1)}} (\log T)^{\frac{q}{2(q-1)}}\Big)$ for $q$-uniformly convex feasible sets, where uniformly convex sets include strongly convex sets and $\ell_p$-balls for $p \in [2,\infty)$. This bound bridges the gap between the $O(\log T)$ bound for strongly convex sets~($q=2$) and the $O(\sqrt{T})$ bound for non-curved sets~($q\to\infty$).
• Abstract（参考訳）: 本研究では,オンライン凸最適化(OCO)について検討し,実現可能な集合の曲率を利用して高速な速度を提供する新しい条件と解析を導入する。 オンライン線形最適化では、損失関数の平均勾配が一定のしきい値を超えると、その実現可能な集合の曲率をフォロー・ザ・リード(FTL)アルゴリズムで利用し、対数的後悔を達成することが知られている。 本研究では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。 特に、最適決定が実現可能な集合の境界にあり、基礎となる損失関数の勾配がゼロでないことを最初に証明すると、アルゴリズムは確率的環境において$O(\rho \log T)$の後悔境界を達成する。 ここで、$\rho > 0$ は最適決定を含む最小球面の半径であり、実現可能な集合を囲む。 我々のアプローチは、既存のものとは異なり、凸損失関数を直接扱うことができ、損失関数の曲率を同時に利用でき、実現可能な集合の局所的な性質でのみ対数的後悔を実現することができる。 さらに、FTL が $\Omega(T)$ regret を被った場合であっても $O(\sqrt{T})$ regret を達成し、腐敗レベル $C$ の確率環境において $O(\rho \log T + \sqrt{C \rho \log T})$ regret を達成している。 さらに、分析を拡張して、$O\Big(T^{\frac{q-2}{2(q-1)}} (\log T)^{\frac{q}{2(q-1)}}\Big)$ for $q$-一様凸実現可能集合に対して、一様凸集合は強い凸集合と$p \in [2,\infty)$に対する$\ell_p$-ballsを含む。 この境界は、強凸集合~($q=2$)に対する$O(\log T)$boundと非曲線集合~($q\to\infty$)$O(\sqrt{T})$boundの間のギャップを埋める。

関連論文リスト

• Online Convex Optimization with a Separation Oracle [10.225358400539719]
  本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。 我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
  論文  参考訳（メタデータ） (2024-10-03T13:35:08Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
  重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。 簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。 また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
  論文  参考訳（メタデータ） (2023-02-14T00:23:42Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
  論文  参考訳（メタデータ） (2023-02-13T18:13:36Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Nearly Optimal Algorithms for Level Set Estimation [21.83736847203543]
  線形包帯に対する最近の適応的実験設計手法と関連づけることで, レベルセット推定問題に対する新しいアプローチを提案する。 我々は、我々の境界がほぼ最適であることを示す。すなわち、我々の上限は、しきい値線形帯域に対して既存の下限と一致する。
  論文  参考訳（メタデータ） (2021-11-02T17:45:02Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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