論文の概要: Coordinate Methods for Matrix Games
- arxiv url: http://arxiv.org/abs/2009.08447v1
- Date: Thu, 17 Sep 2020 17:55:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-17 12:24:53.422120
- Title: Coordinate Methods for Matrix Games
- Title（参考訳）: マトリックスゲームのための座標法
- Authors: Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
- Abstract要約: 我々は,MathcalX max_yinmathY ytop A x$ の $min_x 形式の双線形サドル点問題を解くための主対座標法を開発した。
提案手法は,既存のサブ線形手法を,各項目の複雑性とサンプルの複雑さの観点から限界に推し進める。
- 参考スコア（独自算出の注目度）: 41.821881312775496
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop primal-dual coordinate methods for solving bilinear saddle-point
problems of the form $\min_{x \in \mathcal{X}} \max_{y\in\mathcal{Y}} y^\top A
x$ which contain linear programming, classification, and regression as special
cases. Our methods push existing fully stochastic sublinear methods and
variance-reduced methods towards their limits in terms of per-iteration
complexity and sample complexity. We obtain nearly-constant per-iteration
complexity by designing efficient data structures leveraging Taylor
approximations to the exponential and a binomial heap. We improve sample
complexity via low-variance gradient estimators using dynamic sampling
distributions that depend on both the iterates and the magnitude of the matrix
entries.
Our runtime bounds improve upon those of existing primal-dual methods by a
factor depending on sparsity measures of the $m$ by $n$ matrix $A$. For
example, when rows and columns have constant $\ell_1/\ell_2$ norm ratios, we
offer improvements by a factor of $m+n$ in the fully stochastic setting and
$\sqrt{m+n}$ in the variance-reduced setting. We apply our methods to
computational geometry problems, i.e. minimum enclosing ball, maximum inscribed
ball, and linear regression, and obtain improved complexity bounds. For linear
regression with an elementwise nonnegative matrix, our guarantees improve on
exact gradient methods by a factor of $\sqrt{\mathrm{nnz}(A)/(m+n)}$.
- Abstract（参考訳）: 我々は, 線形プログラミング, 分類, 回帰を含む, $\min_{x \in \mathcal{X}} \max_{y\in\mathcal{Y}} y^\top A x$ という形の双線型サドル点問題を解くための原始双対座標法を開発した。
提案手法は, 既存の全確率部分線形法と分散還元法を, 単体間複雑性とサンプル複雑性の観点から限界に推し進める。
テイラー近似を指数関数と二項ヒープに応用した効率的なデータ構造を設計し, ほぼ一点当たりの複雑性を求める。
我々は,行列成分の反復と等級に依存する動的サンプリング分布を用いて,低分散勾配推定器を用いて試料の複雑性を向上する。
私たちのランタイム境界は、m$ by $n$ matrix $a$のスパーシティ測度に依存する係数によって、既存のプリミティブメソッドのそれを改善する。
例えば、行と列が定数 $\ell_1/\ell_2$ のノルム比を持つ場合、完全確率的な設定では $m+n$ 、分散縮小設定では $\sqrt{m+n}$ の改善を提供する。
本手法を計算幾何学問題、すなわち最小囲い球、最大打ち込み球、線形回帰に適用し、改良された複雑性境界を求める。
要素的に非負行列を持つ線型回帰に対して、我々は$\sqrt{\mathrm{nnz}(A)/(m+n)}$ の係数で正確な勾配法を改善する。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39: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) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳（メタデータ） (2022-06-29T01:40:38Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Fast and Near-Optimal Diagonal Preconditioning [46.240079312553796]
左か右の対角線再スケーリングにより$mathbfA$の条件数を改善する方法を示す。
構造化混合パッキングと半定値プログラムを対象とし,$widetildeO(textnnz(mathbfA) cdot textpoly(kappastar))$ timeに対して,$mathbfA$の定数係数最適スケーリングを計算する。
論文 参考訳（メタデータ） (2020-08-04T17:53:28Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。