論文の概要: Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity

• arxiv url: http://arxiv.org/abs/2410.20649v1
• Date: Mon, 28 Oct 2024 01:06:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:16:05.916281
• Title: Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity
• Title（参考訳）: データから変分不等式を学習する:強い単調性の下での高速一般化率
• Authors: Eric Zhao, Tatjana Chavdarova, Michael Jordan,
• Abstract要約: 変分不等式(VIs)は最適化問題の幅広いクラスである。 強い単調性を満たすVIを学習するために、高速な速度を得る方法を示す。 具体的には、凸最小化の標準的な安定性に基づく議論が、ドメインが小さな被覆を許すとき、直接 VI に拡張されることを実証する。
• 参考スコア（独自算出の注目度）: 7.821495984906274
• License:
• Abstract: Variational inequalities (VIs) are a broad class of optimization problems encompassing machine learning problems ranging from standard convex minimization to more complex scenarios like min-max optimization and computing the equilibria of multi-player games. In convex optimization, strong convexity allows for fast statistical learning rates requiring only $\Theta(1/\epsilon)$ stochastic first-order oracle calls to find an $\epsilon$-optimal solution, rather than the standard $\Theta(1/\epsilon^2)$ calls. In this paper, we explain how one can similarly obtain fast $\Theta(1/\epsilon)$ rates for learning VIs that satisfy strong monotonicity, a generalization of strong convexity. Specifically, we demonstrate that standard stability-based generalization arguments for convex minimization extend directly to VIs when the domain admits a small covering, or when the operator is integrable and suboptimality is measured by potential functions; such as when finding equilibria in multi-player games.
• Abstract（参考訳）: 変分不等式(VIs)は、標準的な凸最小化から、min-max最適化やマルチプレイヤーゲームの平衡計算のようなより複雑なシナリオまで、機械学習の問題を含む幅広い最適化問題である。 凸最適化において、強い凸性は、標準的な$\Theta(1/\epsilon)$コールではなく、$\epsilon$-Optimalソリューションを見つけるために、$\Theta(1/\epsilon)$確率的な1次オラクルコールのみを必要とする高速な統計的学習率を可能にする。 本稿では、強い凸性の一般化である強い単調性を満たすVIを学習するために、同様に高速な$\Theta(1/\epsilon)$レートを得る方法を説明する。 具体的には、凸最小化の標準安定性に基づく一般化引数が、ドメインが小さな被覆を許す場合や、演算子が可積分であり、潜在的関数によって準最適性が測定される場合、例えばマルチプレイヤーゲームにおいて平衡を求めるときなど、直接 VI に拡張されることを実証する。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。 解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
  論文  参考訳（メタデータ） (2024-02-07T18:22:41Z)
• The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
  実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。 さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
  論文  参考訳（メタデータ） (2023-11-09T14:29:25Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization [37.177329562964765]
  我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。 この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。 しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
  論文  参考訳（メタデータ） (2022-02-27T09:41:43Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Higher-order methods for convex-concave min-max optimization and monotone variational inequalities [7.645449711892907]
  制約付き凸凹 min-max 問題に対する収束率の改善と高次滑らかな単調変分不等式を提供する。 p>2$の場合、ネミロフスキーの1階ミラープロキシ法の反復複雑性を改善する。 さらに、制約のない$p=2$ケースでアルゴリズム全体をインスタンス化する。
  論文  参考訳（メタデータ） (2020-07-09T03:12:33Z)

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

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