論文の概要: Local LMO is Secretly a Projection Method!

• arxiv url: http://arxiv.org/abs/2609.33383v1
• Date: Sun, 27 Sep 2026 09:03:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:29:37.666759
• Title: Local LMO is Secretly a Projection Method!
• Title（参考訳）: ローカルLMOは秘密裏にプロジェクションメソッドです!
• Abstract要約: 局所線型オラクル (Local LMO) は射影を計算することなく制約付き凸問題を解く。 局所LMOは、半空間の局所化の深さによってインデックス付けされるような、より広い射影法に属することを示す。
• 参考スコア（独自算出の注目度）: 51.56484100374058
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The local linear minimization oracle (Ferris and Zavriev, 1996; arXiv:2605.08850), or Local LMO, solves constrained convex problems without having to compute a projection: it minimizes a linear model over the intersection of the feasible set with a ball around the current iterate. We show that, whenever the ball radius does not exceed the Polyak radius, the Local LMO step is the Euclidean projection of the current iterate onto the intersection of the feasible set with a half-space that separates the iterate from the solution set; this projection is nonetheless computable by a linear oracle alone. We demonstrate that Local LMO belongs to a broader family of projection methods which may be indexed by the depth of the localizing half-space. For objectives with $\vartheta$-Hölder continuous gradient, every method from this family whose half-space lies sufficiently deep drives the best of its first $K$ iterates to optimality at the universal rate $\mathcal{O}(K^{-(1+\vartheta)/2})$, matching the non-accelerated universal gradient method of Nesterov (2015). Run at the Polyak radius, Local LMO attains the same rate when the constrained optima are also unconstrained ($\|\nabla f(x_\star)\| = 0$), and the rate $\mathcal{O}(K^{-1/(2-\vartheta)})$ otherwise.
• Abstract（参考訳）: 局所線型最小化オラクル (Ferris and Zavriev, 1996; arXiv:2605.08850) または局所LMO (Local LMO) は、射影を計算することなく制約付き凸問題を解く。 球半径がポリアック半径を超えないとき、局所LMOステップは、イテレートを解集合から分離する半空間を持つファシブル集合の交差点への電流のユークリッド射影であり、この射影は線型オラクルだけで計算可能である。 局所LMOは、半空間の局所化の深さによってインデックス付けされるような、より広い射影法に属することを実証する。 $\vartheta$-Hölder 連続勾配を持つ目的に対して、この族から得られるハーフ空間が十分深いすべてのメソッドは、その最初の$K$のベストを、普遍速度 $\mathcal{O}(K^{-(1+\vartheta)/2})$ で最適に反復し、ネステロフの非加速的普遍勾配法(2015年)と一致する。 ポリアック半径で走るとき、局所 LMO は制約されたオプティマが非制約であるときにも同じ速度を得る(\|\nabla f(x_\star)\| = 0$)し、それ以外は$\mathcal{O}(K^{-1/(2-\vartheta)})$である。

関連論文リスト

• Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle [51.714334316332476]
  Local Lは制約付き最適化のための新しいプロジェクションフリー型である。 局所LMOはGD(Gradient Descent)のオラクルと見なされる。
  論文  参考訳（メタデータ） (2026-05-09T10:03:24Z)
• Trust Region Masking for Long-Horizon LLM Reinforcement Learning [20.589897184824878]
  大規模言語モデルのポリシー勾配法は、ロールアウトポリシーのサンプルから計算された代理目的を最適化する。 $_textroll ne _$ の場合、サロゲートと真の目的の間に近似誤差がある。 本稿では,トークンが信頼領域に違反した場合に,全シーケンスを勾配計算から除外するトラスト領域マスキング(TRM)を提案する。
  論文  参考訳（メタデータ） (2025-12-28T20:41:59Z)
• 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)
• The Local Landscape of Phase Retrieval Under Limited Samples [12.366532279123359]
  我々は,地球規模のミニマを囲む良質な景観を高次元で確保するために必要となる最小限のサンプルサイズを確認することを目的としている。 まず、 whenn=odlog d の局所凸性について調べる。
  論文  参考訳（メタデータ） (2023-11-26T07:22:35Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。 特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
  論文  参考訳（メタデータ） (2020-07-22T18:18:28Z)

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

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