論文の概要: Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

• arxiv url: http://arxiv.org/abs/2605.26373v1
• Date: Mon, 25 May 2026 22:45:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-27 17:51:41.49452
• Title: Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
• Title（参考訳）: アルゴリズム等価性による隠れ凸損失のオンライン学習:最適回帰,幾何バリア,帯域フィードバック
• Authors: Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos, Ioannis Panageas, Antonios Varvitsiotis,
• Abstract要約: 私たちはGhai-Jacobianの損失を隠したオンライン学習に対抗しています。 対角-ヤコビ条件を必要な--ヘッセン幾何学に置き換える。
• 参考スコア（独自算出の注目度）: 19.63303297174247
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding $\mathcal{O}(T^{2/3})$ regret. They left open whether the optimal $Θ(\sqrt{T})$ regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves $\mathcal{O}(\sqrt{T})$ regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers $Ω(T)$ regret. Finally, we extend our analysis to one-point bandit feedback and prove a $\mathcal{O}(T^{3/4})$ expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.
• Abstract（参考訳）: 本研究では,非凸損失(非凸損失)を非線形再パラメータ化後に凸になるような非凸損失(非凸損失)を用いて,敵対的オンライン学習を研究する。 Ghai, Lu and Hazan (2022) は、幾何学的および滑らかな仮定の下で、そのような非凸損失に対するオンライン勾配降下(OGD)は、適切な正則化器を用いて、下層の凸損失に対するオンラインミラー降下(OMD)を概ねシミュレートし、$\mathcal{O}(T^{2/3})を後悔することを示した。 彼らは、この隠された凸設定において、オンライン凸最適化からの最適の$(\sqrt{T})$後悔が回復できるかどうかを公表した。 私たちはこの質問に答える。 より具体的には、よりシャープな離散時間アルゴリズム同値論により、OGD が同じ仮定の下で $\mathcal{O}(\sqrt{T})$ regret を達成することを証明し、対向的オンライン凸最適化における最適最悪のケースレートと一致する。 我々はまた、このアルゴリズムの同値性に必要な幾何を明確にすることによって、Ghai, Lu and Hazan (2022) の別のオープンな問題にも対処する。 対角的・ヤコビ的十分条件を必要十分ヘッセン整合条件に置き換え、許容パラメータ化のクラスを拡大する。 我々は、ヘッセン整合仮定が OGD にとって不可欠であることを示す下界との厳密な後悔を補完し、失敗すると滑らかなパラメータ化と OGD が $Ω(T)$ の後悔に苦しむ隠れ凸損失の逆列を構築する。 最後に、解析結果を1点の帯域幅フィードバックに拡張し、球面スムージングを伴う帯域幅 OGD に対する $\mathcal{O}(T^{3/4})$ expected regret bound を証明し、その古典的な速度を凸損失に合わせる。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Revisiting Projection-Free Online Learning with Time-Varying Constraints [35.573654458435854]
  我々は制約付きオンライン凸最適化について検討し、そこでは決定は固定的で典型的には複雑な領域に属する必要がある。 いくつかのプロジェクションフリーな手法が$mathcalO(T3/4 sqrtlog T)$ regret boundと$mathcalO(T3/4 sqrtlog T)$ cumulative constraint violation (CCV) bound for general convex lossで提案されている。 本稿では,損失関数が強凸である場合に,この結果を改善し,さらにテクスチノーベルの後悔とCCV境界を確立する。
  論文  参考訳（メタデータ） (2025-01-27T13:38:51Z)
• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。 我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-12T17:08:31Z)
• 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)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
  我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。 一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2020-10-16T05:42:50Z)

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

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