論文の概要: $γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions

• arxiv url: http://arxiv.org/abs/2602.13506v1
• Date: Fri, 13 Feb 2026 22:34:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 14:17:28.120486
• Title: $γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions
• Title（参考訳）: $γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with application to DR-Submodular and OSS Functions
• Authors: Mohammad Pedramfar, Vaneet Aggarwal,
• Abstract要約: このような関数の広範な近似を特徴付ける新しい一階述語条件である$-weakly $-up-concavityを導入する。 本フレームワークは,DR-サブモジュラークラスに対する最適係数を復元し,既存の近似係数を大幅に改善する。
• 参考スコア（独自算出の注目度）: 52.031993908548294
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimizing monotone non-convex functions is a fundamental challenge across machine learning and combinatorial optimization. We introduce and study $γ$-weakly $θ$-up-concavity, a novel first-order condition that characterizes a broad class of such functions. This condition provides a powerful unifying framework, strictly generalizing both DR-submodular functions and One-Sided Smooth (OSS) functions. Our central theoretical contribution demonstrates that $γ$-weakly $θ$-up-concave functions are upper-linearizable: for any feasible point, we can construct a linear surrogate whose gains provably approximate the original non-linear objective. This approximation holds up to a constant factor, namely the approximation coefficient, dependent solely on $γ$, $θ$, and the geometry of the feasible set. This linearizability yields immediate and unified approximation guarantees for a wide range of problems. Specifically, we obtain unified approximation guarantees for offline optimization as well as static and dynamic regret bounds in online settings via standard reductions to linear optimization. Moreover, our framework recovers the optimal approximation coefficient for DR-submodular maximization and significantly improves existing approximation coefficients for OSS optimization, particularly over matroid constraints.
• Abstract（参考訳）: モノトン非凸関数の最適化は、機械学習と組合せ最適化における根本的な課題である。 そのような関数の幅広いクラスを特徴付ける新しい一階条件である$γ$-weakly $θ$-up-concavityを導入して研究する。 この条件は強力な統一フレームワークを提供し、DR-部分モジュラ関数とOne-Sided Smooth (OSS)関数を厳密に一般化する。 我々の中心的な理論的な寄与は、$γ$-weakly $θ$-up-concave 関数が上線可算であることを示し、任意の実現可能な点に対して、ゲインが元の非線形目的を確実に近似する線形サロゲートを構築することができる。 この近似は定数係数、すなわち近似係数、すなわち$γ$、$θ$、および実現可能な集合の幾何学にのみ依存する。 この線形化性は、幅広い問題に対して即時かつ統一的な近似を保証する。 具体的には、オフライン最適化のための統一的な近似保証と、オンライン設定における静的および動的後悔境界を、線形最適化への標準的還元により取得する。 さらに,我々のフレームワークは,DR-サブモジュラー最大化のための最適近似係数を復元し,OSS最適化のための既存の近似係数,特にマトロイド制約よりも大幅に改善する。

関連論文リスト

• Gradient-free stochastic optimization for additive models [50.57026826740147]
  本稿では,Polyak-Lojasiewicz あるいは強凸条件を満たす目的関数に対する雑音観測によるゼロ次最適化の問題に対処する。 対象関数は加法的構造を持ち、H"古い関数族によって特徴づけられる高次滑らか性特性を満たすと仮定する。
  論文  参考訳（メタデータ） (2025-03-03T23:39:08Z)
• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  非最適化は機械学習の中心であるが、一般の非凸性は弱い収束を保証するため、他方に比べて悲観的すぎる。 非凸アルゴリズムに新しい統一仮定を導入する。
  論文  参考訳（メタデータ） (2025-02-17T21:25:31Z)
• Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization [29.705337940879705]
  分散プロジェクションフリー最適化のための新しいフレームワークを提案する。 我々は、高次線形化可能な関数フレームワークの柔軟性で分散最適化手法を活用する。
  論文  参考訳（メタデータ） (2025-01-30T07:28:34Z)
• From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization [33.38582292895673]
  本稿では,モノトーン非線型やDR-サブモジュラリティなど,様々な環境での凹凸とDR-サブモジュラリティの概念を紹介する。 一般的なメタアルゴリズムは、線形/四進関数を上線形/四進関数を最適化するものに変換する。
  論文  参考訳（メタデータ） (2024-04-27T06:19:30Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Non-local Optimization: Imposing Structure on Optimization Problems by Relaxation [0.0]
  進化的計算と強化学習において、関数 $f: Omega to mathbbR$ の最適化はしばしば、Theta mapto mathbbE_theta(f)$ of $f$ の緩和 $theta を最適化することで解決される。 測度理論とフーリエ解析を用いてそのような緩和構造を考察し、多くの関連する最適化手法の成功に光を当てることを可能にした。
  論文  参考訳（メタデータ） (2020-11-11T20:45:47Z)
• Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions [73.33961743410876]
  ソフトマックス関数は近似と滑らかさの2つの主要な効率尺度を持つ。 近似と滑らか性の異なる尺度に対する最適近似-滑らか性トレードオフを同定する。 これにより、新しいソフトマックス関数が生まれ、それぞれ異なる用途に最適である。
  論文  参考訳（メタデータ） (2020-10-22T05:19:58Z)
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization [16.0251555430107]
  凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。 最適精度制御と結果の順序-最適後悔性能を確立する。 提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
  論文  参考訳（メタデータ） (2020-03-11T18:42:40Z)

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

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