論文の概要: Streaming Complexity of SVMs
- arxiv url: http://arxiv.org/abs/2007.03633v1
- Date: Tue, 7 Jul 2020 17:10:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 20:44:04.781092
- Title: Streaming Complexity of SVMs
- Title（参考訳）: SVMのストリーミング複雑性
- Authors: Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P.
Woodruff
- Abstract要約: 本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
- 参考スコア（独自算出の注目度）: 110.63976030971106
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the space complexity of solving the bias-regularized SVM problem in
the streaming model. This is a classic supervised learning problem that has
drawn lots of attention, including for developing fast algorithms for solving
the problem approximately. One of the most widely used algorithms for
approximately optimizing the SVM objective is Stochastic Gradient Descent
(SGD), which requires only $O(\frac{1}{\lambda\epsilon})$ random samples, and
which immediately yields a streaming algorithm that uses
$O(\frac{d}{\lambda\epsilon})$ space. For related problems, better streaming
algorithms are only known for smooth functions, unlike the SVM objective that
we focus on in this work. We initiate an investigation of the space complexity
for both finding an approximate optimum of this objective, and for the related
``point estimation'' problem of sketching the data set to evaluate the function
value $F_\lambda$ on any query $(\theta, b)$. We show that, for both problems,
for dimensions $d=1,2$, one can obtain streaming algorithms with space
polynomially smaller than $\frac{1}{\lambda\epsilon}$, which is the complexity
of SGD for strongly convex functions like the bias-regularized SVM, and which
is known to be tight in general, even for $d=1$. We also prove polynomial lower
bounds for both point estimation and optimization. In particular, for point
estimation we obtain a tight bound of $\Theta(1/\sqrt{\epsilon})$ for $d=1$ and
a nearly tight lower bound of $\widetilde{\Omega}(d/{\epsilon}^2)$ for $d =
\Omega( \log(1/\epsilon))$. Finally, for optimization, we prove a
$\Omega(1/\sqrt{\epsilon})$ lower bound for $d = \Omega( \log(1/\epsilon))$,
and show similar bounds when $d$ is constant.
- Abstract（参考訳）: ストリーミングモデルにおけるバイアス正規化svm問題を解決するための空間複雑性について検討する。
これは古典的な教師付き学習問題であり、この問題を解くための高速アルゴリズムの開発など、多くの注目を集めている。
SVMの目的をほぼ最適化するための最も広く使われているアルゴリズムの1つは、Stochastic Gradient Descent (SGD)であり、これは、$O(\frac{1}{\lambda\epsilon})$ランダムサンプルのみを必要とし、$O(\frac{d}{\lambda\epsilon})$スペースを使用するストリーミングアルゴリズムを直ちに得る。
関連する問題に関しては、より優れたストリーミングアルゴリズムは、我々がこの作業に集中しているsvmの目的とは違って、滑らかな関数でしか知られていない。
我々は、この目的の近似最適性を見つけるための空間複雑性と、任意のクエリ$(\theta, b)$上で関数値$F_\lambda$を評価するためにデータセットをスケッチする ``point Estimation''' 問題の両方について調査を開始する。
両方の問題に対して、$d=1,2$の場合、空間多項式が$\frac{1}{\lambda\epsilon}$より小さいストリーミングアルゴリズムを得ることができ、これはバイアス正規化SVMのような強い凸関数に対するSGDの複雑さであり、一般には$d=1$であっても厳密であることが知られている。
また、点推定と最適化の両方において多項式下限を証明できる。
特に、点推定には、$d=1$ に対して $\theta(1/\sqrt{\epsilon})$ と$d = \omega( \log(1/\epsilon))$ に対して$\widetilde{\omega}(d/{\epsilon}^2)$ という厳密な下限が得られる。
最後に、最適化のために$\Omega(1/\sqrt{\epsilon})$ lower bound for $d = \Omega( \log(1/\epsilon))$を証明する。
関連論文リスト
- Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Lower Bounds on the Worst-Case Complexity of Efficient Global
Optimization [11.523746174066702]
我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。
この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
論文 参考訳（メタデータ） (2022-09-20T11:57:13Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。