論文の概要: Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle

• arxiv url: http://arxiv.org/abs/2605.08850v1
• Date: Sat, 09 May 2026 10:03:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:49.929456
• Title: Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle
• Title（参考訳）: Local LMO: 局所線形最小化による制約付き勾配最適化
• Authors: Peter Richtárik, Kaja Gruntkowska, Hanmin Li,
• Abstract要約: Local Lは制約付き最適化のための新しいプロジェクションフリー型である。 局所LMOはGD(Gradient Descent)のオラクルと見なされる。
• 参考スコア（独自算出の注目度）: 51.714334316332476
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We design Local LMO - a new projection-free gradient-type method for constrained optimization. The key algorithmic idea is to replace the global linear minimization oracle over the constraint set used by Frank-Wolfe (FW) with a local linear minimization oracle over the intersection of the constraint set and a "small" ball centered at the current iterate. In particular, when minimizing $f:\mathbb{R}^d\to \mathbb{R}$ over a constraint $\emptyset\neq\mathcal{X}\subseteq\mathbb{R}^d$, Local LMO performs the iteration \[x_{k+1}\in \arg\min_{z\in\mathcal{X}\cap\mathcal{B}(x_{k},t_k)}\langle\nabla f(x_{k}), z \rangle,\] where $x_0\in\mathcal{X}$, and $t_k>0$ is a suitably chosen radius which can be interpreted as an effective stepsize. While designed as an alternative to FW, Local LMO is perhaps best viewed as a generalization of Gradient Descent (GD) rather than a modification of FW. Indeed, it is easy to see that Local LMO reduces to GD in the unconstrained setting and, more generally, to GD restricted to an affine subspace if the constraint $\mathcal{X}$ is affine. We prove that this simple algorithmic scheme transfers the known (unaccelerated) convergence rates of Projected Gradient Descent (PGD) to the projection-free world in several important regimes, some of which are beyond the reach of FW. In contrast to FW theory, i) our guarantees hold without requiring the feasible set $\mathcal{X}$ to be bounded, ii) our theory does not require the "curvature" assumption, which allows us to establish a standard sublinear rate for convex functions with bounded gradients, iii) we obtain a linear rate in the smooth strongly convex regime. Furthermore, we obtain sharp sublinear rates in the smooth convex and non-convex regimes, in the $(L_0,L_1)$-smooth convex regime, and in stochastic and non-differentiable settings.
• Abstract（参考訳）: 制約付き最適化のための新しいプロジェクションフリー勾配型手法であるLocal LMOを設計する。 鍵となるアルゴリズムのアイデアは、FW(Frank-Wolfe)が使用する制約集合上の大域線型最小化オラクルを、制約集合の交叉上の局所線型最小化オラクルと、現在のイテレートを中心とする「小さい」ボールに置き換えることである。 特に、$f:\mathbb{R}^d\to \mathbb{R}$ over a constraint $\emptyset\neq\mathcal{X}\subseteq\mathbb{R}^d$ を最小化するとき、局所 LMO は反復 \[x_{k+1}\in \arg\min_{z\in\mathcal{X}\cap\mathcal{B}(x_{k},t_k)}\langle\nabla f(x_{k}), z \rangle,\] を最小化する。 FWの代替として設計されたが、ローカルLMOはFWの修正ではなく、GD(Gradient Descent)の一般化と見なされている。 実際、局所 LMO が非制約設定において GD に還元され、より一般的には、制約 $\mathcal{X}$ がアフィンであれば、アフィン部分空間に制限される GD に還元されることは容易にわかる。 我々は、この単純なアルゴリズムスキームが、FWの到達範囲を超えているいくつかの重要な状況において、投影されたグラディエントDescent(PGD)の既知の(加速しない)収束速度を射影のない世界へ転送することを証明した。 FW理論とは対照的に。 i) 有界集合 $\mathcal{X}$ を必要とせずに保留する。 i) この理論は「曲率」の仮定を必要としないので、有界勾配を持つ凸函数の標準線型率を確立することができる。 三 円滑な凸系において直線率を得る。 さらに, 滑らかな凸系と非凸系, $(L_0, L_1)$-smooth 凸系, 確率的および非微分的条件において, 鋭いサブ線形速度を得る。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Provably Efficient Model-Free Constrained RL with Linear Function Approximation [4.060731229044571]
  我々は,大規模システムにおいても,サブリニア後悔とサブリニア制約違反を実現するための,最初のモデルフリーシミュレータフリーアルゴリズムを開発した。 本結果は,標準LSVI-UCBアルゴリズムの新たな適応により達成される。
  論文  参考訳（メタデータ） (2022-06-23T17:54:31Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• 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)

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

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