論文の概要: A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
- arxiv url: http://arxiv.org/abs/2002.07003v1
- Date: Mon, 17 Feb 2020 15:28:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 12:37:26.007318
- Title: A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
- Title（参考訳）: 制約付き自己調和最小化のためのNewton Frank-Wolfe法
- Authors: Deyi Liu, Volkan Cevher, Quoc Tran-Dinh
- Abstract要約: 本稿では,制約集合上の線形最小化オラクル(LMO)を用いて,制約付き自己調和最小化問題のクラスをカラフルに解く方法を示す。
L-smoothの場合、我々の手法のLMO呼び出し数はFrank-Wolfe法とほぼ同じであることを示す。
- 参考スコア（独自算出の注目度）: 60.90222082871258
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We demonstrate how to scalably solve a class of constrained self-concordant
minimization problems using linear minimization oracles (LMO) over the
constraint set. We prove that the number of LMO calls of our method is nearly
the same as that of the Frank-Wolfe method in the L-smooth case. Specifically,
our Newton Frank-Wolfe method uses $\mathcal{O}(\epsilon^{-\nu})$ LMO's, where
$\epsilon$ is the desired accuracy and $\nu:= 1 + o(1)$. In addition, we
demonstrate how our algorithm can exploit the improved variants of the
LMO-based schemes, including away-steps, to attain linear convergence rates. We
also provide numerical evidence with portfolio design with the competitive
ratio, D-optimal experimental design, and logistic regression with the elastic
net where Newton Frank-Wolfe outperforms the state-of-the-art.
- Abstract（参考訳）: 我々は,制約集合上の線形最小化オラクル(lmo)を用いた制約付き自己一致最小化問題のクラスをスカラブ的に解く方法を示す。
L-smoothの場合、我々の手法のLMO呼び出し数はFrank-Wolfe法とほぼ同じであることを示す。
具体的には、Newton Frank-Wolfe 法は $\mathcal{O}(\epsilon^{-\nu})$ LMO's を使い、$\epsilon$ は所望の精度であり、$\nu:= 1 + o(1)$ である。
さらに, このアルゴリズムは, アウトステップを含む改良されたLMOベースのスキームを有効活用し, 線形収束率を達成できることを示す。
また,競争比,d-最適実験設計,およびニュートン・フランク=ウルフが最先端技術を上回る弾性ネットを用いたロジスティック回帰によるポートフォリオ設計についても,数値的な証拠を提供する。
関連論文リスト
- Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - A Multistep Frank-Wolfe Method [2.806911268410107]
フランク=ウルフ法におけるジグザグ現象を離散化の成果物として検討した。
多重ステップのフランク・ウルフ変種は、トラニケート誤差が$O(Deltap)$として崩壊し、$p$はメソッドの順序である。
論文 参考訳（メタデータ） (2022-10-14T21:12:01Z) - Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method
for Empirical Risk Minimization [1.4504054468850665]
In Empirical Minimization -- Minimization -- We present a novel computer step-size approach to we have compute guarantees。
提案手法は実世界のバイナリデータセットに非常に重要な問題を示す。
また、計算の保証を得るための新しい適応的なステップサイズアプローチを提案する。
論文 参考訳（メタデータ） (2022-08-30T00:08:37Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps [66.88729048402082]
一般化自己一致は、多くの学習問題の目的関数に存在する重要な特性である。
検討対象の領域が一様凸あるいは多面体である場合など,様々な症例に対する収束率の改善を示す。
論文 参考訳（メタデータ） (2021-05-28T15:26:36Z) - RNN Training along Locally Optimal Trajectories via Frank-Wolfe
Algorithm [50.76576946099215]
小領域の損失面に局所的なミニマを反復的に求めることにより,RNNの新規かつ効率的なトレーニング手法を提案する。
新たなRNNトレーニング手法を開発し,追加コストを伴っても,全体のトレーニングコストがバックプロパゲーションよりも低いことを実証的に観察した。
論文 参考訳（メタデータ） (2020-10-12T01:59:18Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳（メタデータ） (2020-10-05T08:16:56Z) - Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization [30.980431848476925]
線形予測・構造を一般化した制約付き有限滑らかサム最小化アルゴリズムを提案する。
提案手法は実装が簡単で,ステップサイズチューニングを必要としない。
オープンソースパッケージで検討されたすべてのメソッドの実装を提供する。
論文 参考訳（メタデータ） (2020-02-27T00:47:21Z) - Self-Concordant Analysis of Frank-Wolfe Algorithms [3.3598755777055374]
ポアソン逆問題 (Poisson inverse problem) や量子状態トモグラフィー (quantum state tomography) など、多くの応用において、損失は非有界曲率を持つ自己協和関数 (SC) によって与えられる。
SC関数の理論を用いて、FW法の新たな適応ステップサイズを提供し、k反復後の大域収束率 O(1/k) を証明する。
論文 参考訳（メタデータ） (2020-02-11T11:30:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。