論文の概要: Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles

• arxiv url: http://arxiv.org/abs/2510.15257v1
• Date: Fri, 17 Oct 2025 02:36:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-20 20:17:34.444781
• Title: Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles
• Title（参考訳）: ガウス零次ランダムオラクルを用いた部分モジュラ函数の最小化
• Authors: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames,
• Abstract要約: オフラインの場合、このアルゴリズムのグローバルな$epsilon$-approximateソリューションへの収束性を証明する。 オンラインの場合,静的な後悔に関して,アルゴリズムは漢南一致であることを示す。
• 参考スコア（独自算出の注目度）: 1.220074067604011
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider the minimisation problem of submodular functions and investigate the application of a zeroth-order method to this problem. The method is based on exploiting a Gaussian smoothing random oracle to estimate the smoothed function gradient. We prove the convergence of the algorithm to a global $\epsilon$-approximate solution in the offline case and show that the algorithm is Hannan-consistent in the online case with respect to static regret. Moreover, we show that the algorithm achieves $O(\sqrt{NP_N^\ast})$ dynamic regret, where $N$ is the number of iterations and $P_N^\ast$ is the path length. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.
• Abstract（参考訳）: 部分モジュラ函数の最小化問題を考察し、この問題に対するゼロ階法の適用について検討する。 この手法はガウスの滑らかなランダムオラクルを利用して滑らかな関数勾配を推定する。 オフラインの場合のグローバル$\epsilon$-approximateソリューションへのアルゴリズムの収束を証明し、静的な後悔に関して、アルゴリズムがオンラインの場合においてハンナン整合であることを示す。 さらに,アルゴリズムが$O(\sqrt{NP_N^\ast})$ dynamic regretを達成し,$N$を反復数,$P_N^\ast$を経路長とすることを示す。 複雑性解析とハイパーパラメータ選択は、すべてのケースに対して提示される。 理論的結果は数値的な例を通して説明される。

関連論文リスト

• Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach [1.220074067604011]
  我々は、ミニミザーに関して非滑らかで、サブモジュラーであり、最大値に関して凹凸であるような目的関数の問題を考察する。 この問題に適用したゼロ階法の性能について検討する。
  論文  参考訳（メタデータ） (2026-01-29T04:04:27Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
  本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。 また,非コンケーブミニマックス問題に対処できることを示す。
  論文  参考訳（メタデータ） (2021-08-01T15:23:49Z)
• 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)

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

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