論文の概要: Optimal Scalarizations for Sublinear Hypervolume Regret
- arxiv url: http://arxiv.org/abs/2307.03288v3
- Date: Wed, 14 Aug 2024 22:42:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-16 19:24:40.552972
- 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: http://creativecommons.org/licenses/by-nc-sa/4.0/
- 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)$依存を取り除く。
我々は,非線形スキャラライゼーションを多種多様な自然条件下で,線形なスキャラライゼーションと他の標準多目的アルゴリズムより優れているという,強い経験的性能で理論を支援した。
関連論文リスト
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity [16.779513676120096]
我々は、最適化の経路に沿った目的の条件付けに依存する勾配降下に対する新しい準最適境界を開発する。
我々の証明の鍵となるのは方向の滑らかさであり、これは、目的の上のバウンドを開発するために使用する勾配変動の尺度である。
我々は,方向の滑らかさの知識を使わずとも,ポリアクのステップサイズと正規化GDが高速で経路依存の速度を得ることを示した。
論文 参考訳(メタデータ) (2024-03-06T22:24:05Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳(メタデータ) (2023-05-28T06:33:37Z) - Robust Implicit Regularization via Weight Normalization [6.042206709451915]
重み正規化は、重みが実質的に大規模であっても持続する頑健なバイアスを可能にすることを示す。
実験により, 暗黙バイアスの収束速度とロバスト性の両方の利得は, 重み正規化を用いて劇的に改善されることが示唆された。
論文 参考訳(メタデータ) (2023-05-09T13:38:55Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-28T08:25:26Z) - 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) - The Role of Momentum Parameters in the Optimal Convergence of Adaptive
Polyak's Heavy-ball Methods [12.93796690939018]
適応型Polyak's Heavy-ball (HB) 法は最適な個人収束率を$O(frac1sqrtt)$とする。
新しい解析では,hb運動量とその時間的変動が凸最適化の高速化にどのように役立つかを示す。
論文 参考訳(メタデータ) (2021-02-15T02:57:14Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z) - Random Hypervolume Scalarizations for Provable Multi-Objective Black Box
Optimization [8.90548944387431]
本稿では、$f(x)$が競合する可能性のある目的のベクトルを出力する多目的最適化について考察する。
証明可能な収束保証を伴う多目的最適化プロセスに、任意の証明可能な収束単目的最適化プロセスが、強制的に変換可能であることを示す。
論文 参考訳(メタデータ) (2020-06-08T15:00:30Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳(メタデータ) (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。