論文の概要: Maximizing Determinants under Matroid Constraints

• arxiv url: http://arxiv.org/abs/2004.07886v1
• Date: Thu, 16 Apr 2020 19:16:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-12 22:12:52.081683
• Title: Maximizing Determinants under Matroid Constraints
• Title（参考訳）: マトロイド制約下での行列式最大化
• Authors: Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat
• Abstract要約: 我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
• 参考スコア（独自算出の注目度）: 69.25768526213689
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given vectors $v_1,\dots,v_n\in\mathbb{R}^d$ and a matroid $M=([n],I)$, we study the problem of finding a basis $S$ of $M$ such that $\det(\sum_{i \in S}v_i v_i^\top)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning. The current best results include an $e^{2k}$-estimation for any matroid of rank $k$ and a $(1+\epsilon)^d$-approximation for a uniform matroid of rank $k\ge d+\frac d\epsilon$, where the rank $k\ge d$ denotes the desired size of the optimal set. Our main result is a new approximation algorithm with an approximation guarantee that depends only on the dimension $d$ of the vectors and not on the size $k$ of the output set. In particular, we show an $(O(d))^{d}$-estimation and an $(O(d))^{d^3}$-approximation for any matroid, giving a significant improvement over prior work when $k\gg d$. Our result relies on the existence of an optimal solution to a convex programming relaxation for the problem which has sparse support; in particular, no more than $O(d^2)$ variables of the solution have fractional values. The sparsity results rely on the interplay between the first-order optimality conditions for the convex program and matroid theory. We believe that the techniques introduced to show sparsity of optimal solutions to convex programs will be of independent interest. We also give a randomized algorithm that rounds a sparse fractional solution to a feasible integral solution to the original problem. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials and show new relationships between different convex programs studied for the problem. Finally, we use the estimation algorithm and sparsity results to give an efficient deterministic approximation algorithm with an approximation guarantee that depends solely on the dimension $d$.
• Abstract（参考訳）: 与えられたベクトル $v_1,\dots,v_n\in\mathbb{r}^d$ とマトロイド $m=([n],i)$ が与えられたとき、$\det(\sum_{i \in s}v_i v_i^\top)$ が最大化される基底 $m$ を求める問題を調べる。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。 現在の最良の結果には、ランク $k$の任意のマトロイドに対する$e^{2k}$-推定と、ランク $k\ge d+\frac d\epsilon$の統一マトロイドに対する$(1+\epsilon)^d$近似が含まれる。 我々の主な結果は、ベクトルの次元$d$にのみ依存し、出力集合のサイズ$k$には依存しない近似を保証する新しい近似アルゴリズムである。 特に、任意のマトロイドに対して$(O(d))^{d}$-estimationと$(O(d))^{d^3}$-approximationを示す。 我々の結果は、疎サポートを持つ問題に対する凸プログラミング緩和に対する最適解の存在に依存し、特に、解の$O(d^2)$変数は分数値を持つ。 スパーシリティの結果は、凸プログラムの1階最適条件とマトロイド理論の間の相互作用に依存する。 凸プログラムに対する最適解のスパース性を示すために導入された技法は、独立した関心を持つだろうと信じている。 また、元の問題に対する実現可能な積分解に対してスパース分数解を丸めるランダム化アルゴリズムを与える。 近似保証を示すために, 強対数凸多項式に関する最近の研究を利用して, 異なる凸プログラム間の新たな関係を示す。 最後に、推定アルゴリズムとスパーシティ結果を用いて、次元$d$のみに依存する近似保証付き効率的な決定論的近似アルゴリズムを提供する。

関連論文リスト

• Combinatorial optimization of the coefficient of determination [0.0]
  決定係数が最も高い平面上の$n$点の$k$-部分集合を選択するための効率的なアルゴリズムを開発する。 誤差のない$n=30$までの試行で,提案手法の最適性を実験的に実証した。
  論文  参考訳（メタデータ） (2024-10-12T00:53:25Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Dueling Optimization with a Monotone Adversary [35.850072415395395]
  凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。 目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-11-18T23:55:59Z)
• Composable Coresets for Determinant Maximization: Greedy is Almost Optimal [2.849878266188877]
  a set of $n$ in $mathbbRd$, the emphdeterminant problem of the emphdeterminant problem to pick $k$ vectors with the maximum volume。 広く使われているGreedyアルゴリズムは、O(k)3k$の近似係数がほぼ最適である構成可能なコアセットも提供する。
  論文  参考訳（メタデータ） (2023-09-26T21:46:44Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• 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)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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