論文の概要: Local Search Algorithms for Rank-Constrained Convex Optimization
- arxiv url: http://arxiv.org/abs/2101.06262v1
- Date: Fri, 15 Jan 2021 18:52:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-28 11:17:32.729214
- Title: Local Search Algorithms for Rank-Constrained Convex Optimization
- Title（参考訳）: ランク付き凸最適化のための局所探索アルゴリズム
- Authors: Kyriakos Axiotis and Maxim Sviridenko
- Abstract要約: 階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。
我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
- 参考スコア（独自算出の注目度）: 7.736462653684946
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose greedy and local search algorithms for rank-constrained convex
optimization, namely solving $\underset{\mathrm{rank}(A)\leq r^*}{\min}\, R(A)$
given a convex function $R:\mathbb{R}^{m\times n}\rightarrow \mathbb{R}$ and a
parameter $r^*$. These algorithms consist of repeating two steps: (a) adding a
new rank-1 matrix to $A$ and (b) enforcing the rank constraint on $A$. We
refine and improve the theoretical analysis of Shalev-Shwartz et al. (2011),
and show that if the rank-restricted condition number of $R$ is $\kappa$, a
solution $A$ with rank $O(r^*\cdot \min\{\kappa \log
\frac{R(\mathbf{0})-R(A^*)}{\epsilon}, \kappa^2\})$ and $R(A) \leq R(A^*) +
\epsilon$ can be recovered, where $A^*$ is the optimal solution. This
significantly generalizes associated results on sparse convex optimization, as
well as rank-constrained convex optimization for smooth functions. We then
introduce new practical variants of these algorithms that have superior runtime
and recover better solutions in practice. We demonstrate the versatility of
these methods on a wide range of applications involving matrix completion and
robust principal component analysis.
- Abstract（参考訳）: 階数制約付き凸最適化のための欲望と局所探索アルゴリズム,すなわち$\underset{\mathrm{rank}(a)\leq r^*}{\min}\, r(a)$ 与えられた凸関数 $r:\mathbb{r}^{m\times n}\rightarrow \mathbb{r}$ とパラメータ $r^*$ の解法を提案する。
これらのアルゴリズムは2つのステップを繰り返す: (a) 新たな rank-1 行列を $a$ に追加し、 (b) ランク制約を $a$ で強制する。
我々はshalev-shwartzらの理論解析を洗練し改善する。
(2011) で、ランク制限された条件数 $r$ が $\kappa$ であれば、ランク $o(r^*\cdot \min\{\kappa \log \frac{r(\mathbf{0})-r(a^*)}{\epsilon}, \kappa^2\})$ と $r(a) \leq r(a^*) + \epsilon$ の解は、$a^*$ が最適解である。
このことはスパース凸最適化とスムーズ関数に対する階数制約付き凸最適化の関連結果を著しく一般化する。
次に,これらのアルゴリズムの実用的変種を新たに導入し,優れた実行環境と,実際に優れた解を回収する。
行列補完とロバストな主成分分析を含む広範囲のアプリケーションにおいて,これらの手法の汎用性を示す。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳（メタデータ） (2023-06-16T17:00:51Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳（メタデータ） (2022-08-07T20:53:42Z) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-11T17:33:07Z) - Iterative Hard Thresholding with Adaptive Regularization: Sparser
Solutions Without Sacrificing Runtime [17.60502131429094]
本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。
提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。
我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
論文 参考訳（メタデータ） (2022-04-11T19:33:15Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Sparse Convex Optimization via Adaptively Regularized Hard Thresholding [17.60502131429094]
本稿では,適応正規化ハードThresholding (ARHT) アルゴリズムを提案する。
また、OMP with Replacement (OMPR) for general $f$, under the condition $s > s* frackappa24$。
論文 参考訳（メタデータ） (2020-06-25T17:16:21Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。