論文の概要: Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms

• arxiv url: http://arxiv.org/abs/2508.00775v1
• Date: Fri, 01 Aug 2025 16:56:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-04 18:08:53.964317
• Title: Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms
• Title（参考訳）: 保証付き最適化の学習--線形収束アルゴリズムの完全評価
• Authors: Andrea Martin, Ian R. Manchester, Luca Furieri,
• Abstract要約: 高度な工学的応用では、最適化アルゴリズムは数学的に定義された問題のクラスよりも証明可能な証明可能なケースを保証する必要がある。 非滑らかな合成最適化問題のクラスに対して線形収束を実現するアルゴリズムのクラスを記述する。
• 参考スコア（独自算出の注目度）: 1.4747234049753448
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In high-stakes engineering applications, optimization algorithms must come with provable worst-case guarantees over a mathematically defined class of problems. Designing for the worst case, however, inevitably sacrifices performance on the specific problem instances that often occur in practice. We address the problem of augmenting a given linearly convergent algorithm to improve its average-case performance on a restricted set of target problems - for example, tailoring an off-the-shelf solver for model predictive control (MPC) for an application to a specific dynamical system - while preserving its worst-case guarantees across the entire problem class. Toward this goal, we characterize the class of algorithms that achieve linear convergence for classes of nonsmooth composite optimization problems. In particular, starting from a baseline linearly convergent algorithm, we derive all - and only - the modifications to its update rule that maintain its convergence properties. Our results apply to augmenting legacy algorithms such as gradient descent for nonconvex, gradient-dominated functions; Nesterov's accelerated method for strongly convex functions; and projected methods for optimization over polyhedral feasibility sets. We showcase effectiveness of the approach on solving optimization problems with tight iteration budgets in application to ill-conditioned systems of linear equations and MPC for linear systems.
• Abstract（参考訳）: 高度な工学的応用では、最適化アルゴリズムは数学的に定義された問題のクラスに対して証明可能な最悪の保証を伴わなければならない。 しかし、最悪の場合の設計は、必然的に、実行時に頻繁に発生する特定の問題インスタンスのパフォーマンスを犠牲にする。 与えられた線形収束アルゴリズムを拡張して、制約された対象問題(例えば、特定の力学系へのアプリケーションに対するモデル予測制御(MPC)のためのオフザシェルフソルバの調整)における平均ケース性能を向上させるとともに、問題のクラス全体にわたって最悪のケース保証を保った。 この目的に向けて、非滑らかな合成最適化問題のクラスに対して線形収束を達成するアルゴリズムのクラスを特徴付ける。 特に、ベースライン線型収束アルゴリズムから始めると、その収束特性を維持する更新規則のすべての-および唯一の-を導出する。 この結果は,非凸関数の勾配降下,勾配支配関数の勾配降下,強凸関数のネステロフの加速法,多面体実現可能性集合に対する最適化法などのレガシーアルゴリズムの拡張に適用できる。 本稿では,線形方程式の不条件系と線形系に対するMPCの適用において,厳密な反復予算による最適化問題の解法の有効性を示す。

関連論文リスト

• On improving generalization in a class of learning problems with the method of small parameters for weakly-controlled optimal gradient systems [0.0]
  制御入力が非線形項の係数としてシステム力学に入力される弱制御勾配系の変分問題を考える。 摂動理論を用いて、最適化問題の列を解くことができる結果を提供する。 また、そのような近似最適解に対する収束率を推定する。
  論文  参考訳（メタデータ） (2024-12-11T20:50:29Z)
• A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
  伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。 ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
  論文  参考訳（メタデータ） (2024-05-03T10:37:34Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming [10.06803520598035]
  我々は、下流最適化の最適条件によって機械学習損失関数が機能する最大最適マージンと呼ばれる問題に対する新しいアプローチを開発する。
  論文  参考訳（メタデータ） (2023-01-26T17:53:38Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。 我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
  論文  参考訳（メタデータ） (2021-07-23T13:43:34Z)
• A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians [11.03311584463036]
  滑らかな非線形等式制約最適化問題の解法として, 逐次2次最適化アルゴリズムを提案する。 数値実験の結果、このアルゴリズムは一般的な代替品と比較して優れた性能を示すことが示された。
  論文  参考訳（メタデータ） (2021-06-24T13:46:52Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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