論文の概要: Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

• arxiv url: http://arxiv.org/abs/2406.07373v1
• Date: Tue, 11 Jun 2024 15:41:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-12 15:15:04.858594
• Title: Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
• Title（参考訳）: 並列確率凸最適化における計算クエリ深さギャップの閉鎖
• Authors: Arun Jambulapati, Aaron Sidford, Kevin Tian,
• Abstract要約: 我々は,リプシッツ,凸関数を次数次オラクルで最小化するための新しい並列アルゴリズムを開発した。 その結果,最もよく知られた問合せ深度と並列アルゴリズムの最もよく知られた計算深度とのギャップを埋めることができた。
• 参考スコア（独自算出の注目度）: 26.36906884097317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a new parallel algorithm for minimizing Lipschitz, convex functions with a stochastic subgradient oracle. The total number of queries made and the query depth, i.e., the number of parallel rounds of queries, match the prior state-of-the-art, [CJJLLST23], while improving upon the computational depth by a polynomial factor for sufficiently small accuracy. When combined with previous state-of-the-art methods our result closes a gap between the best-known query depth and the best-known computational depth of parallel algorithms. Our method starts with a ball acceleration framework of previous parallel methods, i.e., [CJJJLST20, ACJJS21], which reduce the problem to minimizing a regularized Gaussian convolution of the function constrained to Euclidean balls. By developing and leveraging new stability properties of the Hessian of this induced function, we depart from prior parallel algorithms and reduce these ball-constrained optimization problems to stochastic unconstrained quadratic minimization problems. Although we are unable to prove concentration of the asymmetric matrices that we use to approximate this Hessian, we nevertheless develop an efficient parallel method for solving these quadratics. Interestingly, our algorithms can be improved using fast matrix multiplication and use nearly-linear work if the matrix multiplication exponent is 2.
• Abstract（参考訳）: リプシッツ,凸関数を確率的下次オラクルで最小化するための新しい並列アルゴリズムを開発した。 クエリの総数とクエリ深度、すなわちクエリの並列ラウンドの数は、従来の最先端の[CJJLLST23]と一致し、多項式係数による計算深度を十分に小さくして改善する。 従来の最先端手法と組み合わせることで、最もよく知られたクエリ深度と、最もよく知られた並列アルゴリズムの計算深度とのギャップを埋めることができます。 本手法は,従来の並列手法,すなわち [CJJJLST20, ACJJS21] の球加速フレームワークから始まり, ユークリッド球に制約された関数の正規化ガウス畳み込みを最小化する問題を低減する。 この誘導関数のヘシアンの新しい安定性特性を開発し、活用することにより、先行並列アルゴリズムから離れ、これらのボール制約最適化問題を確率的非制約二次最小化問題に還元する。 我々は、このヘシアンを近似するために使用する非対称行列の濃度を証明できないが、それでもこれらの二次問題を解くための効率的な並列法を開発する。 興味深いことに、我々のアルゴリズムは高速な行列乗法を用いて改善することができ、行列乗法指数が 2 である場合、ほぼ線形な作業を用いることができる。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• Continuation Newton methods with deflation techniques for global optimization problems [3.705839280172101]
  最適化問題のグローバルな最小点はエンジニアリングである。 本稿では,この非線形大規模問題に対する新しいメメティックアルゴリズムについて考察する。 我々の数値実験によると、新しいアルゴリズムは制約のない未制約問題に対してうまく機能する。
  論文  参考訳（メタデータ） (2021-07-29T09:53:49Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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