論文の概要: Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

• arxiv url: http://arxiv.org/abs/2601.21243v1
• Date: Thu, 29 Jan 2026 04:04:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.564154
• Title: Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
• Title（参考訳）: 非滑らかな部分モジュラー・コンケーブ関数のオフラインとオンラインMin-Max問題の解法:ゼロ階法
• Authors: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames,
• Abstract要約: 我々は、ミニミザーに関して非滑らかで、サブモジュラーであり、最大値に関して凹凸であるような目的関数の問題を考察する。 この問題に適用したゼロ階法の性能について検討する。
• 参考スコア（独自算出の注目度）: 1.220074067604011
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider max-min and min-max problems with objective functions that are possibly non-smooth, submodular with respect to the minimiser and concave with respect to the maximiser. We investigate the performance of a zeroth-order method applied to this problem. The method is based on the subgradient of the Lovász extension of the objective function with respect to the minimiser and based on Gaussian smoothing to estimate the smoothed function gradient with respect to the maximiser. In expectation sense, we prove the convergence of the algorithm to an $ε$-saddle point in the offline case. Moreover, we show that, in the expectation sense, in the online setting, the algorithm achieves $O(\sqrt{N\bar{P}_N})$ online duality gap, where $N$ is the number of iterations and $\bar{P}_N$ is the path length of the sequence of optimal decisions. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.
• Abstract（参考訳）: 目的関数の最大値と最小値の問題は、最小値に対して非滑らかで、極値に関して劣モジュラーであり、極値に関して凹凸であると考えられる。 この問題に適用したゼロ階法の性能について検討する。 この方法は、最小値に関する目的関数のロヴァース拡大の次数に基づいており、最大値に関する滑らかな関数勾配を推定するためにガウス滑らか化に基づいている。 期待できる意味では、オフラインの場合の$ε$-saddle 点へのアルゴリズムの収束を証明する。 さらに,オンライン設定では,$O(\sqrt{N\bar{P}_N})$オンライン双対性ギャップが得られ,$N$は反復数であり,$\bar{P}_N$は最適決定の列のパス長であることを示す。 複雑性解析とハイパーパラメータ選択は、すべてのケースに対して提示される。 理論的結果は数値的な例を通して説明される。

関連論文リスト

• Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles [1.220074067604011]
  オフラインの場合、このアルゴリズムのグローバルな$epsilon$-approximateソリューションへの収束性を証明する。 オンラインの場合,静的な後悔に関して,アルゴリズムは漢南一致であることを示す。
  論文  参考訳（メタデータ） (2025-10-17T02:36:46Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• The Complexity of Constrained Min-Max Optimization [29.57458485068705]
  十分大きな局所点 min-max が存在することが保証されていることを示す。 さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。 この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
  論文  参考訳（メタデータ） (2020-09-21T05:54:12Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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