論文の概要: 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ドル以上の次元の抽象的および幾何学的集合系に対して、ほぼ最適の相違と近似に近い大きさの彩色を計算することができる。
関連論文リスト
- Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles [38.45952947660789]
本稿では,$(alpha,tau,mathcal)$-projected-dominanceプロパティの下で関数を最小化する一階法の性能限界について検討する。
論文 参考訳（メタデータ） (2024-08-03T18:34:23Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。
それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文 参考訳（メタデータ） (2023-11-17T22:07:18Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - 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) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。