論文の概要: Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple,
and Practical
- arxiv url: http://arxiv.org/abs/2209.01147v1
- Date: Fri, 2 Sep 2022 15:59:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-05 12:22:52.497055
- Title: Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple,
and Practical
- Title（参考訳）: 離散性、マッチング、近似のためのアルゴリズム:高速、シンプル、実用的
- Authors: M\'onika Csik\'os and Nabil H. Mustafa
- Abstract要約: 有限集合系 $(X,mathcal S)$ が与えられたとき、2色の $chi:Xto-1,1$ は数学的な S|chi(S)|$ において $max_S として定義される。
我々は、任意の$d>0$と$(X,mathcal S)$に対して、二重シャッター関数 $pi*(k)=O(kd)$ のランダム化アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.2183405753834562
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study one of the key tools in data approximation and optimization:
low-discrepancy colorings. Formally, given a finite set system $(X,\mathcal
S)$, the \emph{discrepancy} of a two-coloring $\chi:X\to\{-1,1\}$ is defined as
$\max_{S \in \mathcal S}|{\chi(S)}|$, where $\chi(S)=\sum\limits_{x \in
S}\chi(x)$.
We propose a randomized algorithm which, for any $d>0$ and $(X,\mathcal S)$
with dual shatter function $\pi^*(k)=O(k^d)$, returns a coloring with expected
discrepancy $O\left({\sqrt{|X|^{1-1/d}\log|\mathcal S|}}\right)$ (this bound is
tight) in time $\tilde O\left({|\mathcal S|\cdot|X|^{1/d}+|X|^{2+1/d}}\right)$,
improving upon the previous-best time of $O\left(|\mathcal S|\cdot|X|^3\right)$
by at least a factor of $|X|^{2-1/d}$ when $|\mathcal S|\geq|X|$. This setup
includes many geometric classes, families of bounded dual VC-dimension, and
others. As an immediate consequence, we obtain an improved algorithm to
construct $\varepsilon$-approximations of sub-quadratic size.
Our method uses primal-dual reweighing with an improved analysis of randomly
updated weights and exploits the structural properties of the set system via
matchings with low crossing number -- a fundamental structure in computational
geometry. In particular, we get the same $|X|^{2-1/d}$ factor speed-up on the
construction time of matchings with crossing number
$O\left({|X|^{1-1/d}}\right)$, which is the first improvement since the 1980s.
The proposed algorithms are very simple, which makes it possible, for the
first time, to compute colorings with near-optimal discrepancies and
near-optimal sized approximations for abstract and geometric set systems in
dimensions higher than $2$.
- Abstract（参考訳）: データ近似と最適化における重要なツールの1つについて研究した。
形式的には、有限集合系 $(x,\mathcal s)$ が与えられると、2色付き$\chi:x\to\{-1,1\}$ の \emph{discrepancy} は $\max_{s \in \mathcal s}|{\chi(s)}|$ と定義され、ここで $\chi(s)=\sum\limits_{x \in s}\chi(x)$ となる。
任意の$d>0$と$(X,\mathcal S)$に対して、2重シャッター関数を持つ$\pi^*(k)=O(k^d)$に対して、期待された離散性を持つ色付けを$O\left({\sqrt{|X|^{1-1/d}\log|\mathcal S|}}\right)$(この境界はきつい)$$\tilde O\left({|\mathcal S|\cdot|X|^{1/d}+|X|^{2+1/d}}\right)$$O\left(|\mathcal S|\cdot|X|3\right)$で返します。
このセットアップには、多くの幾何学クラス、有界双対VC次元の族などが含まれる。
即ち、我々は$\varepsilon$-approximations of sub-quadratic sizeを構築するための改良されたアルゴリズムを得る。
提案手法では,ランダムに更新された重みの解析を改良し,低交叉数との整合性(計算幾何学の基本構造)を生かして,集合系の構造特性を利用する。
特に、交差数 $o\left({|x|^{1-1/d}}\right)$ とのマッチングの構成時間において、同じ $|x|^{2-1/d}$ factor speed-up が得られる。
提案したアルゴリズムは非常に単純で、初めて2ドル以上の次元の抽象的および幾何学的集合系に対して、ほぼ最適の相違と近似に近い大きさの彩色を計算することができる。
関連論文リスト
- An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
微分プライベート降下勾配(SGD)アルゴリズムのプライバシーと実用性(一般化)性能について検討する。
点学習には、$mathcalOBigの過剰なリスク境界を確立する。
ペアで学習するために、勾配に基づく単純なプライベートSGDを提案し、これは$(epsilon,delta)$-differential privacyを満たす。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Low Rank Approximation for General Tensor Networks [55.10347821762229]
我々は与えられたテンソルを$q$$Aで近似する問題を研究する。n times ldots times n$ with a arbitrary tensor network of rank $k$ -- すなわち、グラフ$G = (V, E)$。
私たちは、$A$を二分木ネットワーク$T'$と$O(q)$コアで近似し、このネットワークの各エッジの寸法が最大$widetildeO(kO(dt) cdot qとなるようにします。
論文 参考訳（メタデータ） (2022-07-15T11:55:09Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Low-degree learning and the metric entropy of polynomials [68.8204255655161]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Sharper Rates for Separable Minimax and Finite Sum Optimization via
Primal-Dual Extragradient Methods [39.87865197769047]
分離可能なミニマックス最適化問題 $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$。
論文 参考訳（メタデータ） (2022-02-09T18:57:47Z) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳（メタデータ） (2021-06-25T19:14:45Z) - DIPPA: An improved Method for Bilinear Saddle Point Problems [18.65143269806133]
本稿では,min_bfx max_bfy g(fracx) + bfxtop bfbftop fracbfa kappa_x kappa_x (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y)について述べる。
論文 参考訳（メタデータ） (2021-03-15T10:55:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。