論文の概要: Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures
- arxiv url: http://arxiv.org/abs/2111.15139v1
- Date: Tue, 30 Nov 2021 05:40:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-01 15:55:48.280985
- Title: Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures
- Title(参考訳): maxipデータ構造を用いた条件勾配法における線形反復コスト障壁の破却
- Authors: Anshumali Shrivastava, Zhao Song and Zhaozhuo Xu
- Abstract要約: 条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
- 参考スコア(独自算出の注目度): 49.73889315176884
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Conditional gradient methods (CGM) are widely used in modern machine
learning. CGM's overall running time usually consists of two parts: the number
of iterations and the cost of each iteration. Most efforts focus on reducing
the number of iterations as a means to reduce the overall running time. In this
work, we focus on improving the per iteration cost of CGM. The bottleneck step
in most CGM is maximum inner product search (MaxIP), which requires a linear
scan over the parameters. In practice, approximate MaxIP data-structures are
found to be helpful heuristics. However, theoretically, nothing is known about
the combination of approximate MaxIP data-structures and CGM. In this work, we
answer this question positively by providing a formal framework to combine the
locality sensitive hashing type approximate MaxIP data-structures with CGM
algorithms. As a result, we show the first algorithm, where the cost per
iteration is sublinear in the number of parameters, for many fundamental
optimization algorithms, e.g., Frank-Wolfe, Herding algorithm, and policy
gradient.
- Abstract(参考訳): 条件勾配法(CGM)は現代の機械学習で広く使われている。
CGMの全体の実行時間は、通常、イテレーションの数と各イテレーションのコストの2つの部分で構成される。
ほとんどの取り組みは、全体の実行時間を削減する手段として、イテレーションの数を減らすことに重点を置いている。
本稿では,CGMのイテレーション毎のコスト改善に焦点を当てる。
ほとんどのccmにおけるボトルネックステップは最大内積探索(maxip)であり、パラメータの線形スキャンを必要とする。
実際には、近似MaxIPデータ構造は役に立つヒューリスティックである。
しかし理論的には、近似MaxIPデータ構造とCGMの組み合わせについては何も分かっていない。
本研究では,局所性に敏感なハッシュ型近似 maxip データ構造と cgm アルゴリズムを組み合わせた形式的フレームワークを提供することで,この疑問に正の答えを得る。
その結果、Frank-Wolfeアルゴリズム、Herdingアルゴリズム、ポリシー勾配など、多くの基本的な最適化アルゴリズムに対して、イテレーション当たりのコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Improving Time and Memory Efficiency of Genetic Algorithms by Storing
Populations as Minimum Spanning Trees of Patches [0.0]
進化的アルゴリズムでは、演算子を適用し、人口を保存する計算コストは、適合性評価のコストに匹敵する。
個体群を最小のスパンニングツリーとして保存することは、頂点が個体に対応するが、それらのメタ情報しか含まない場合において、簡単な実装の代替として実現可能であることを示す。
我々の実験は、メモリ使用量と計算コストの両方の観点から、大幅な改善(クロスオーバー演算子の実行を含む)が達成可能であることを示唆している。
論文 参考訳(メタデータ) (2023-06-29T05:12:14Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Alternating Mahalanobis Distance Minimization for Stable and Accurate CP
Decomposition [4.847980206213335]
本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。
このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。
すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
論文 参考訳(メタデータ) (2022-04-14T19:56:36Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic
Algorithm for Constrained Markov Decision Processes [22.07834608976826]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳(メタデータ) (2021-10-21T18:05:40Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Non-approximate Inference for Collective Graphical Models on Path Graphs
via Discrete Difference of Convex Algorithm [19.987509826212115]
本稿では,パスグラフ上の集合的グラフィカルモデル(CGM)に対するMAP推論の新しい手法を提案する。
まず、MAP推論問題を(非線形)最小コストフロー問題として定式化できることを示す。
提案手法では,dcaの重要なサブルーチンを最小凸コストフローアルゴリズムにより効率的に計算できる。
論文 参考訳(メタデータ) (2021-02-18T07:28:18Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - A new heuristic algorithm for fast k-segmentation [0.0]
文献には$k$-segmentationの厳密で近似的な方法が存在する。
本稿では,既存の手法を改善するために,新しいアルゴリズムを提案する。
計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
論文 参考訳(メタデータ) (2020-09-02T04:50:17Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳(メタデータ) (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。