Fugu-MT 論文翻訳(概要): PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability

論文の概要: PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability

arxiv url: http://arxiv.org/abs/2011.02320v4
Date: Thu, 24 Mar 2022 02:32:15 GMT
ステータス: 処理完了
システム内更新日: 2022-09-29 22:41:18.016861
Title: PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability
Title（参考訳）: PCP理論、SETHなど:サブ線形時間不適合性の証明を目指して
Authors: Hengzhao Ma, Jianzhong Li
Abstract要約: 分散PCP定理は任意の時間不近似性を証明するために一般化できるが、線形の場合失敗することを示す。線形時間アルゴリズムの研究の進展を考えると、線形時間近似アルゴリズムの研究を導く上では、サブ線形PCP定理が重要である。
参考スコア（独自算出の注目度）: 7.8651861370959955
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper we propose the PCP-like theorem for sub-linear time inapproximability. Abboud et al. have devised the distributed PCP framework for sub-quadratic time inapproximability. We show that the distributed PCP theorem can be generalized for proving arbitrary polynomial time inapproximability, but fails in the linear case. We prove the sub-linear PCP theorem by adapting from an MA-protocol for the Set Containment problem, and show how to use the theorem to prove both existing and new inapproximability results, exhibiting the power of the sub-linear PCP theorem. Considering the emerging research works on sub-linear time algorithms, the sub-linear PCP theorem is important in guiding the research in sub-linear time approximation algorithms.
Abstract（参考訳）: 本稿では,線形時間不近似に対するPCP型定理を提案する。 abboudらはsub-quadratic time inapproximabilityのための分散pcpフレームワークを考案した。分散pcp定理は任意の多項式時間の近似性を証明するために一般化できるが、線形の場合では失敗する。我々は,集合包含問題に対する MA-protocol から適応した部分線型PCP定理を証明し,その定理を用いて既存および新たな不近似性の両方を証明し,部分線形PCP定理のパワーを示す。線形時間アルゴリズムの研究の進展を考えると、線形時間近似アルゴリズムの研究を導く上では、線形PCP定理が重要である。

関連論文リスト

A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文参考訳（メタデータ） (2024-05-24T21:09:19Z)
Proving Theorems Recursively [80.42431358105482]
本稿では、定理をレベル・バイ・レベルで証明するPOETRYを提案する。従来のステップバイステップメソッドとは異なり、POETRYは各レベルで証明のスケッチを検索する。また,POETRYが検出した最大証明長は10～26。
論文参考訳（メタデータ） (2024-05-23T10:35:08Z)
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA [43.106438224356175]
ほぼ最適誤差保証付き頑健なPCAのためのニア線形時間アルゴリズムを開発した。また,メモリ使用量にほぼ線形なロバストPCAのためのシングルパスストリーミングアルゴリズムを開発した。
論文参考訳（メタデータ） (2023-05-04T04:45:16Z)
Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learning [27.8712875561043]
ポイントワイド・ペアワイド・ラーニング(PPL)のいくつかのアルゴリズムは、「ポイントワイド・ロスとペアワイド・ロス」のハイブリッド・エラー・メトリックを用いて定式化されている。本稿では,PPLの一般化特性を解明し,この理論的ギャップを埋めようとしている。
論文参考訳（メタデータ） (2023-02-20T13:25:23Z)
DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization [39.67743321086165]
本稿では,分散凸複合最適化問題に対する新しいDISAを提案する。 DISA は初めて、線型写像のユークリッドノルムに対する収束ステップサイズ範囲の依存を排除した。近似近位写像を持つ DISA の変種を提供し、その大域収束と下線収束率を証明する。
論文参考訳（メタデータ） (2022-09-05T09:16:59Z)
Matching Normalizing Flows and Probability Paths on Manifolds [57.95251557443005]
連続正規化フロー (Continuous Normalizing Flows, CNFs) は、常微分方程式(ODE)を解くことによって、先行分布をモデル分布に変換する生成モデルである。我々は,CNFが生成する確率密度パスと目標確率密度パスとの間に生じる新たな分岐系であるPPDを最小化して,CNFを訓練することを提案する。 PPDの最小化によって得られたCNFは、既存の低次元多様体のベンチマークにおいて、その可能性とサンプル品質が得られることを示す。
論文参考訳（メタデータ） (2022-07-11T08:50:19Z)
Strong posterior contraction rates via Wasserstein dynamics [8.479040075763892]
ベイズ統計学において、後部収縮率(PCR)は、後部分布が真のモデルの任意の小さな近傍に集中する速度を定量化する。我々は,関数のパラメータ空間上での強いノルム距離に関して,PCRに対する新しいアプローチを開発する。
論文参考訳（メタデータ） (2022-03-21T06:53:35Z)
Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity [50.38337893712897]
線形性を仮定しないMDP上の構造条件であるEPW(Effective Planning Window)条件を導入する。 EPW条件は、この条件を満たすMDPを確実に解くアルゴリズムを提供することで、サンプル効率のよいRLを許容することを示した。また, EPW のような条件の必要性も示し, わずかに非線形な単純な MDP を効率的にサンプリングできないことを示した。
論文参考訳（メタデータ） (2021-06-15T00:06:59Z)
Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-23T04:25:36Z)
Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
論文参考訳（メタデータ） (2020-06-18T17:18:02Z)
One-shot Distibuted Algorithm for PCA with RBF Kernels [23.266613551011638]
提案アルゴリズムは,サンプル分散シナリオと特徴分散シナリオの二重関係に着想を得たものである。理論的には,線形カーネルとRBFカーネルの近似誤差を解析する。提案アルゴリズムは,固有値が高速に減衰すると,通信コストの低い高品質な結果が得られることを示す。
論文参考訳（メタデータ） (2020-05-06T09:07:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。