論文の概要: Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2305.18730v2
- Date: Fri, 2 Jun 2023 04:16:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-05 18:49:19.506276
- Title: Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization
- Title（参考訳）: マルチクロックバイレベル最適化のための並列高速化を用いたブロックワイズ確率分散法
- Authors: Quanqi Hu, Zi-Hao Qiu, Zhishuai Guo, Lijun Zhang, Tianbao Yang
- Abstract要約: 非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。
a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
- 参考スコア（独自算出の注目度）: 43.74656748515853
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we consider non-convex multi-block bilevel optimization (MBBO)
problems, which involve $m\gg 1$ lower level problems and have important
applications in machine learning. Designing a stochastic gradient and
controlling its variance is more intricate due to the hierarchical sampling of
blocks and data and the unique challenge of estimating hyper-gradient. We aim
to achieve three nice properties for our algorithm: (a) matching the
state-of-the-art complexity of standard BO problems with a single block; (b)
achieving parallel speedup by sampling $I$ blocks and sampling $B$ samples for
each sampled block per-iteration; (c) avoiding the computation of the inverse
of a high-dimensional Hessian matrix estimator. However, it is non-trivial to
achieve all of these by observing that existing works only achieve one or two
of these properties. To address the involved challenges for achieving (a, b,
c), we propose two stochastic algorithms by using advanced blockwise
variance-reduction techniques for tracking the Hessian matrices (for
low-dimensional problems) or the Hessian-vector products (for high-dimensional
problems), and prove an iteration complexity of
$O(\frac{m\epsilon^{-3}\mathbb{I}(I<m)}{I\sqrt{I}} +
\frac{m\epsilon^{-3}}{I\sqrt{B}})$ for finding an $\epsilon$-stationary point
under appropriate conditions. We also conduct experiments to verify the
effectiveness of the proposed algorithms comparing with existing MBBO
algorithms.
- Abstract（参考訳）: 本稿では,m\gg 1$低レベル問題を含む非凸型マルチブロック2レベル最適化(mbbo)問題について考察する。
確率的勾配の設計と分散の制御は、ブロックやデータの階層的サンプリングと、超勾配を推定するユニークな課題のためにより複雑である。
アルゴリズムの3つの優れた特性を 達成することを目指しています
(a)標準bo問題の最先端の複雑さと単一ブロックとのマッチング
(b)$i$ブロックをサンプリングし、各イテレーション毎に$b$サンプルをサンプリングして並列スピードアップを達成すること。
(c)高次元ヘッセン行列推定器の逆計算を避けること。
しかし、既存の作品がこれらの性質の1つまたは2つしか達成できないことを観察することで、これらすべてを達成することは非自明である。
a,b)を達成するための課題に対処する
c) ヘッセン行列 (低次元問題) やヘッセンベクトル積 (高次元問題) の追跡に先進的ブロックワイド分散還元法を用いて2つの確率的アルゴリズムを提案し、適切な条件下での$O(\frac{m\epsilon^{-3}\mathbb{I}(I<m)}{I\sqrt{I}} + \frac{m\epsilon^{-3}}{I\sqrt{B}})$の反復複雑性を証明した。
また,既存のMBBOアルゴリズムと比較して提案アルゴリズムの有効性を検証する実験を行った。
関連論文リスト
- Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。
我々のアルゴリズムは距離を使って複雑さを見積もることができる。
MathO (log d) / EuM4。
DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
論文 参考訳（メタデータ） (2024-06-27T18:38:42Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Multi-block Min-max Bilevel Optimization with Applications in Multi-task
Deep AUC Maximization [36.743632418094]
マルチブロックのmin-max双レベル最適化問題に対処するシングルループアルゴリズムを提案する。
我々のアルゴリズムは数百のタスクで問題に取り組むのに利用できることを示す。
論文 参考訳（メタデータ） (2022-06-01T06:42:36Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Block majorization-minimization with diminishing radius for constrained
nonconvex optimization [9.907540661545328]
BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。
凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
論文 参考訳（メタデータ） (2020-12-07T07:53:09Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。