論文の概要: Project and Forget: Solving Large-Scale Metric Constrained Problems
- arxiv url: http://arxiv.org/abs/2005.03853v2
- Date: Mon, 26 Sep 2022 21:27:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-05 12:06:48.733606
- Title: Project and Forget: Solving Large-Scale Metric Constrained Problems
- Title（参考訳）: プロジェクトと目標:大規模メトリクス制約問題の解決
- Authors: Rishi Sonthalia, Anna C. Gilbert
- Abstract要約: データポイント間で異なる測定値のセットが与えられた場合、入力された測定値と最も「一致」したメトリック表現を決定することは、多くの機械学習アルゴリズムにおいて重要なステップである。
既存の手法は、そのような問題に大量のメートル法制約があるため、特定の種類のメトリクスや小さな問題のサイズに制限される。
本稿では,多くの(指数関数的に)不等式制約を持つ計量制約問題の解法として,ブレグマン射影を用いたプロジェクト・アンド・フォーゲット(Project and Forget)を提案する。
- 参考スコア（独自算出の注目度）: 7.381113319198104
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a set of dissimilarity measurements amongst data points, determining
what metric representation is most "consistent" with the input measurements or
the metric that best captures the relevant geometric features of the data is a
key step in many machine learning algorithms. Existing methods are restricted
to specific kinds of metrics or small problem sizes because of the large number
of metric constraints in such problems. In this paper, we provide an active set
algorithm, Project and Forget, that uses Bregman projections, to solve metric
constrained problems with many (possibly exponentially) inequality constraints.
We provide a theoretical analysis of \textsc{Project and Forget} and prove that
our algorithm converges to the global optimal solution and that the $L_2$
distance of the current iterate to the optimal solution decays asymptotically
at an exponential rate. We demonstrate that using our method we can solve large
problem instances of three types of metric constrained problems: general weight
correlation clustering, metric nearness, and metric learning; in each case,
out-performing the state of the art methods with respect to CPU times and
problem sizes.
- Abstract（参考訳）: データポイント間の不均一性測定のセットが与えられると、どのメトリック表現が入力測定値と最も"一貫性"があるかを決定することは、多くの機械学習アルゴリズムにおいて重要なステップとなる。
既存の手法は、そのような問題に大量のメートル法制約があるため、特定の種類のメトリクスや小さな問題のサイズに制限される。
本稿では,多くの(指数関数的に)不等式制約を持つ計量制約問題の解法として,ブレグマン射影を用いた能動集合アルゴリズムProject and Forgetを提案する。
我々は、textsc{Project and Forget} の理論解析を行い、我々のアルゴリズムが大域最適解に収束し、電流と最適解との$L_2$距離が指数率で漸近的に崩壊することを証明する。
また,本手法を用いて,一般重量相関クラスタリング,距離近接性,距離学習という3種類の制約付き問題の大規模問題インスタンスを解決できることを実証した。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - A General Online Algorithm for Optimizing Complex Performance Metrics [5.726378955570775]
我々は,バイナリ,マルチクラス,マルチラベルの分類問題において,様々な複雑なパフォーマンス指標を用いて,直接的に使用可能な汎用オンラインアルゴリズムを導入,分析する。
アルゴリズムの更新と予測のルールは、過去のデータを保存することなく、非常にシンプルで計算的に効率的である。
論文 参考訳（メタデータ） (2024-06-20T21:24:47Z) - A cutting plane algorithm for globally solving low dimensional k-means
clustering problems [4.5594982923247995]
我々は、低次元データを持つインスタンスのk-means問題を考え、これを構造的凹面割り当て問題として定式化する。
これにより、低次元構造を利用して、妥当な時間で大域的最適性に問題を解くことができる。
本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,数値的な結果を提供する。
論文 参考訳（メタデータ） (2024-02-21T07:55:33Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Tight Cram\'{e}r-Rao type bounds for multiparameter quantum metrology
through conic programming [61.98670278625053]
最適な精度で不整合パラメータを推定できる実用的な測定戦略が最重要である。
ここでは、最適精度で非相関な測定方法を見つけるための具体的な方法を示す。
従来の計算可能境界と最終的な精度境界との間には厳密なギャップがあることを数値的に示す。
論文 参考訳（メタデータ） (2022-09-12T13:06:48Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳（メタデータ） (2022-08-23T18:56:05Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳（メタデータ） (2022-06-22T23:57:40Z) - Dimensionally Consistent Learning with Buckingham Pi [4.446017969073817]
支配方程式がない場合、次元解析は物理系における洞察を抽出し対称性を見つけるための堅牢な手法である。
本研究では,非次元群を検出するために,可観測データの対称構造と自己相似構造を用いる自動手法を提案する。
我々はバッキンガム・パイの定理を制約として利用する3つのデータ駆動手法を開発した。
論文 参考訳（メタデータ） (2022-02-09T17:58:00Z) - New Methods for Detecting Concentric Objects With High Accuracy [0.0]
デジタルデータに幾何学的オブジェクトを適合させることは、虹彩検出、自律ナビゲーション、産業ロボット操作など、多くの分野において重要な問題である。
データに幾何学的形状を合わせるには、幾何学的(定形)アプローチと代数的(非定形)アプローチの2つの一般的なアプローチがある。
他の反復的手法の信頼性の高い初期推定として使用できる新しい推定器を開発した。
論文 参考訳（メタデータ） (2021-02-16T08:19:18Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - Towards Certified Robustness of Distance Metric Learning [53.96113074344632]
我々は,距離学習アルゴリズムの一般化とロバスト性を改善するために,入力空間に逆のマージンを付与することを提唱する。
アルゴリズム的ロバスト性の理論手法を用いることにより,拡張マージンは一般化能力に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-10T16:51:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。