論文の概要: Fixed Point Computation: Beating Brute Force with Smoothed Analysis

• arxiv url: http://arxiv.org/abs/2501.10884v1
• Date: Sat, 18 Jan 2025 21:32:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:19:40.761156
• Title: Fixed Point Computation: Beating Brute Force with Smoothed Analysis
• Title（参考訳）: 固定点計算:スムース解析によるブルート力の打ち消し
• Authors: Idan Attias, Yuval Dagan, Constantinos Daskalakis, Rui Yao, Manolis Zampetakis,
• Abstract要約: 本稿では,$varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $ell$ unit ball to itself。 アルゴリズムのランタイムは、スムーズな分析フレームワークの下で、$eO(n)/varepsilon$でバウンドされる。
• 参考スコア（独自算出の注目度）: 28.978340288565118
• License:
• Abstract: We propose a new algorithm that finds an $\varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $\ell_2$ unit ball to itself. We use the general framework of finding approximate solutions to a variational inequality, a problem that subsumes fixed point computation and the computation of a Nash Equilibrium. The algorithm's runtime is bounded by $e^{O(n)}/\varepsilon$, under the smoothed-analysis framework. This is the first known algorithm in such a generality whose runtime is faster than $(1/\varepsilon)^{O(n)}$, which is a time that suffices for an exhaustive search. We complement this result with a lower bound of $e^{\Omega(n)}$ on the query complexity for finding an $O(1)$-approximate fixed point on the unit ball, which holds even in the smoothed-analysis model, yet without the assumption that the function is smooth. Existing lower bounds are only known for the hypercube, and adapting them to the ball does not give non-trivial results even for finding $O(1/\sqrt{n})$-approximate fixed points.
• Abstract（参考訳）: 我々は,$\varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $\ell_2$ unit ball to itself.というアルゴリズムを提案する。 我々は,定点計算とナッシュ平衡の計算を仮定する問題である変分不等式に対する近似解を求める一般的な枠組みを用いる。 アルゴリズムのランタイムは、スムーズな分析フレームワークの下で、$e^{O(n)}/\varepsilon$でバウンドされる。 これは、ランタイムが$(1/\varepsilon)^{O(n)}$より高速であるような一般性において、初めて知られているアルゴリズムである。 この結果は、単球上の$O(1)$-approximateの不動点を見つけるためのクエリの複雑さに対して$e^{\Omega(n)}$の低い境界で補う。 既存の下界はハイパーキューブでしか知られておらず、ボールにそれらを適用することは、$O(1/\sqrt{n})$-approximate fixed point を見つけることさえも、非自明な結果を与えない。

関連論文リスト

• 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)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• 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)
• 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)
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness [26.71898403195793]
  非常に滑らかな凸関数を最適化する複雑性について検討する。 正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。 我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
  論文  参考訳（メタデータ） (2021-12-02T10:51:43Z)
• 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)
• No quantum speedup over gradient descent for non-smooth convex optimization [22.16973542453584]
  ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。 私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。 下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
  論文  参考訳（メタデータ） (2020-10-05T06:32:47Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。