論文の概要: Optimal Scalarizations for Sublinear Hypervolume Regret

• arxiv url: http://arxiv.org/abs/2307.03288v4
• Date: Mon, 04 Nov 2024 22:09:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:55:29.322386
• Title: Optimal Scalarizations for Sublinear Hypervolume Regret
• Title（参考訳）: サブ線形ハイパーボリュームレグレットの最適スカラー化
• Authors: Qiuyi Zhang,
• Abstract要約: 均一にランダムな重みを持つ超体積スカラー化は、O(T-1/k)$の最適サブボリューム超体積後悔境界が得られることを示す。 多目的線型包帯の設定のために、不必要な$textpoly(k)$依存を取り除くために$tildeO(d T-1/2 + T-1/k)$の後悔境界を得る新しい非ユークリッド解析を導出する。
• 参考スコア（独自算出の注目度）: 2.703970154550017
• License:
• Abstract: Scalarization is a general, parallizable technique that can be deployed in any multiobjective setting to reduce multiple objectives into one, yet some have dismissed this versatile approach because linear scalarizations cannot explore concave regions of the Pareto frontier. To that end, we aim to find simple non-linear scalarizations that provably explore a diverse set of $k$ objectives on the Pareto frontier, as measured by the dominated hypervolume. We show that hypervolume scalarizations with uniformly random weights achieves an optimal sublinear hypervolume regret bound of $O(T^{-1/k})$, with matching lower bounds that preclude any algorithm from doing better asymptotically. For the setting of multiobjective stochastic linear bandits, we utilize properties of hypervolume scalarizations to derive a novel non-Euclidean analysis to get regret bounds of $\tilde{O}( d T^{-1/2} + T^{-1/k})$, removing unnecessary $\text{poly}(k)$ dependencies. We support our theory with strong empirical performance of using non-linear scalarizations that outperforms both their linear counterparts and other standard multiobjective algorithms in a variety of natural settings.
• Abstract（参考訳）: スケーラビリティは、複数の目的を1つに減らすため、任意の多目的設定に展開できる一般的なパラライズ可能な手法であるが、線形スカラー化はパレートフロンティアの凹凸領域を探索できないため、この汎用的アプローチを否定する者もいる。 その目的は、支配的な超体積によって測定されるように、パレートフロンティア上の様々な$k$の目的の集合を確実に探索する単純な非線形スカラー化を見つけることである。 均一にランダムな重みを持つ超体積スカラー化は、任意のアルゴリズムが漸近的により良い処理をすることを妨げる下界と一致する$O(T^{-1/k})$の最適線形超体積後悔境界を達成することを示す。 多目的確率線型包帯の設定には、超体積スカラー化の特性を利用して、新しい非ユークリッド解析を導出し、$\tilde{O}(d T^{-1/2} + T^{-1/k})$の後悔境界を求め、不要な$\text{poly}(k)$依存を取り除く。 我々は,非線形スキャラライゼーションを多種多様な自然条件下で,線形なスキャラライゼーションと他の標準多目的アルゴリズムより優れているという,強い経験的性能で理論を支援した。

関連論文リスト

• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models [0.2741266294612776]
  我々は高次元ランダム最小二乗問題に対して運動量を持つ勾配アルゴリズムのクラスを解析する。 固定運動量パラメータを持つ(小バッチ)運動量では,ステップサイズを正確に調整した場合,SGDよりも実際の性能向上は得られないことを示す。 非強凸条件では、運動量を用いてSGDよりも大きな改善が得られる。
  論文  参考訳（メタデータ） (2021-06-07T15:08:24Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• Adaptive Online Estimation of Piecewise Polynomial Trends [23.91519151164528]
  我々は,2乗誤差損失と雑音勾配フィードバックを伴う非定常最適化の枠組みを考察する。 非パラメトリック回帰理論から動機づけられた新しい変分制約を導入する。 我々は、同じ方針が、他のいくつかの非パラメトリックな関心の族に最適であることを示す。
  論文  参考訳（メタデータ） (2020-09-30T19:30:28Z)
• Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization [8.90548944387431]
  本稿では、$f(x)$が競合する可能性のある目的のベクトルを出力する多目的最適化について考察する。 証明可能な収束保証を伴う多目的最適化プロセスに、任意の証明可能な収束単目的最適化プロセスが、強制的に変換可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-08T15:00:30Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)

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

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