論文の概要: Learning Lines with Ordinal Constraints
- arxiv url: http://arxiv.org/abs/2004.13202v2
- Date: Mon, 25 May 2020 20:18:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 04:53:05.473918
- Title: Learning Lines with Ordinal Constraints
- Title(参考訳): 規則制約付きラインの学習
- Authors: Bohan Fan, Diego Ihara Centurion, Neshat Mohammadi, Francesco Sgherzi,
Anastasios Sidiropoulos, Mina Valizadeh
- Abstract要約: 3点の点 $(u,v,w)$ に対する順序的制約は、$|f(u)-f(v)|f(u)-f(w)|$ を主張する。
本稿では,この問題の高密度ケースに対する近似アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 3.6047642906482142
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of finding a mapping $f$ from a set of points into the
real line, under ordinal triple constraints. An ordinal constraint for a triple
of points $(u,v,w)$ asserts that $|f(u)-f(v)|<|f(u)-f(w)|$. We present an
approximation algorithm for the dense case of this problem. Given an instance
that admits a solution that satisfies $(1-\varepsilon)$-fraction of all
constraints, our algorithm computes a solution that satisfies
$(1-O(\varepsilon^{1/8}))$-fraction of all constraints, in time $O(n^7) +
(1/\varepsilon)^{O(1/\varepsilon^{1/8})} n$.
- Abstract(参考訳): 直交三重制約の下で、一組の点から実数直線への写像$f$を求める問題について検討する。
点 $(u,v,w)$ の三重項に対する順序的制約は $|f を主張する
(u)-f
(v)|<|f
(u)-f(w)|$ である。
この問題の高密度ケースに対する近似アルゴリズムを提案する。
1-\varepsilon)$-fraction of all constraintsを満足する解を与えられた場合、我々のアルゴリズムは、すべての制約を$(1-O(\varepsilon^{1/8})$-fraction of all constraints, in time $O(n^7) + (1/\varepsilon)^{O(1/\varepsilon^{1/8})} n$を満足する解を計算する。
関連論文リスト
- On the Complexity of First-Order Methods in Stochastic Bilevel
Optimization [9.649991673557167]
両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。
既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。
我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
論文 参考訳(メタデータ) (2024-02-11T04:26:35Z) - The Computational Complexity of Finding Stationary Points in Non-Convex
Optimization [60.53870185393238]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳(メタデータ) (2023-10-13T14:52:46Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳(メタデータ) (2021-09-21T13:19:04Z) - 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) - Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。
非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
論文 参考訳(メタデータ) (2021-05-04T21:49:15Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳(メタデータ) (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。