論文の概要: De-singularity Subgradient for the $q$-th-Powered $\ell_p$-Norm Weber Location Problem
- arxiv url: http://arxiv.org/abs/2412.15546v2
- Date: Mon, 03 Feb 2025 10:20:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-04 16:03:29.006811
- Title: De-singularity Subgradient for the $q$-th-Powered $\ell_p$-Norm Weber Location Problem
- Title（参考訳）: $q$-th- Powered $\ell_p$-Norm Weber ロケーション問題に対する非特異性次数
- Authors: Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen, Cheng Li,
- Abstract要約: 目的の勾配は特異点のかなりの集合には存在しない。
本稿では, 1leqslant p$ と $1leqslant p2$ の$q$-th-powered $ell_p$-norm の場合のデ・シンギュラリティ(de-singularity)を定式化する。
この問題に対して,Singularityのない$q$-th-powered $ell_p$-norm Weiszfeldアルゴリズム($q$P$p$NWAWS)を開発した。
- 参考スコア（独自算出の注目度）: 14.506533458989853
- License:
- Abstract: The Weber location problem is widely used in several artificial intelligence scenarios. However, the gradient of the objective does not exist at a considerable set of singular points. Recently, a de-singularity subgradient method has been proposed to fix this problem, but it can only handle the $q$-th-powered $\ell_2$-norm case ($1\leqslant q<2$), which has only finite singular points. In this paper, we further establish the de-singularity subgradient for the $q$-th-powered $\ell_p$-norm case with $1\leqslant q\leqslant p$ and $1\leqslant p<2$, which includes all the rest unsolved situations in this problem. This is a challenging task because the singular set is a continuum. The geometry of the objective function is also complicated so that the characterizations of the subgradients, minimum and descent direction are very difficult. We develop a $q$-th-powered $\ell_p$-norm Weiszfeld Algorithm without Singularity ($q$P$p$NWAWS) for this problem, which ensures convergence and the descent property of the objective function. Extensive experiments on six real-world data sets demonstrate that $q$P$p$NWAWS successfully solves the singularity problem and achieves a linear computational convergence rate in practical scenarios.
- Abstract（参考訳）: Weberの位置問題は、いくつかの人工知能のシナリオで広く使われている。
しかし、目的の勾配は特異点のかなりの集合には存在しない。
近年、この問題を解決するために非特異性劣次法が提案されているが、有限特異点しか持たない$q$-th-powered $\ell_2$-norm case(1\leqslant q<2$)しか扱えない。
本稿では,$q$-th-powered $\ell_p$-norm case with $1\leqslant q\leqslant p$ および $1\leqslant p<2$ について,この問題の他のすべての未解決状況を含むデシンギュラリティ(de-singularity)を更に確立する。
特異集合が連続体であるため、これは難しい問題である。
目的関数の幾何学も複雑であり、下位次数、最小値、降下方向の特徴づけは非常に困難である。
この問題に対して,Singularityのない$q$-th-powered $\ell_p$-norm Weiszfeldアルゴリズム($q$P$p$NWAWS)を開発した。
6つの実世界のデータセットに対する大規模な実験により、$q$P$p$NWAWS は特異性問題の解決に成功し、実用シナリオにおける線形計算収束率を達成することを示した。
関連論文リスト
- Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry [20.068722738606287]
我々は、$(epsilon,delta)$-differential privacy(DP)の制約の下で、サドル点問題(SSP)と変分不等式(SVI)を研究する。
強いSPギャップ上の$tildeObig(frac1sqrtn + fracsqrtdnepsilonbig)$のバウンドを得る。
我々は、$の強いVI-ギャップ上の有界値を得る最初の解析を提供する。
論文 参考訳（メタデータ） (2024-11-07T21:45:05Z) - A De-singularity Subgradient Approach for the Extended Weber Location Problem [12.263117303066831]
拡張Weber ロケーション問題に対する非特異な下位段階のアプローチを確立する。
提案手法はこの問題を解き、非特異性の場合と同じ結果を示し、線形収束の合理的な速度を示す。
論文 参考訳（メタデータ） (2024-05-11T09:22:44Z) - Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。
解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
論文 参考訳（メタデータ） (2024-02-07T18:22:41Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - 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) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - An $L^2$ Analysis of Reinforcement Learning in High Dimensions with
Kernel and Neural Network Approximation [9.088303226909277]
本稿では,カーネル法や2層ニューラルネットワークモデルを用いて関数近似を行う状況について考察する。
私たちは$tildeO(H3|mathcal A|frac14n-frac14)$を$Hn$サンプルで最適なポリシーにバインドします。
この結果はまだ有限次元の作用空間を必要とするが、誤差境界は状態空間の次元とは独立である。
論文 参考訳（メタデータ） (2021-04-15T21:59:03Z) - Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文 参考訳（メタデータ） (2020-10-16T08:10:02Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。