論文の概要: A Query-Optimal Algorithm for Finding Counterfactuals

• arxiv url: http://arxiv.org/abs/2207.07072v1
• Date: Thu, 14 Jul 2022 17:21:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-15 15:49:02.366181
• Title: A Query-Optimal Algorithm for Finding Counterfactuals
• Title（参考訳）: 対物探索のためのクエリ-最適アルゴリズム
• Authors: Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan
• Abstract要約: 我々は,その性能に関する理論的保証が強い反事実を見つけるアルゴリズムを設計する。 [ S(f)O(Delta_f(xstar))cdot log d]クエリを$f$にし、xstar$でslの最適カウンターファクトを返します。
• 参考スコア（独自算出の注目度）: 14.934032347716995
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model $f : X^d \to \{0,1\}$ and instance $x^\star$, our algorithm makes \[ {S(f)^{O(\Delta_f(x^\star))}\cdot \log d}\] queries to $f$ and returns {an {\sl optimal}} counterfactual for $x^\star$: a nearest instance $x'$ to $x^\star$ for which $f(x')\ne f(x^\star)$. Here $S(f)$ is the sensitivity of $f$, a discrete analogue of the Lipschitz constant, and $\Delta_f(x^\star)$ is the distance from $x^\star$ to its nearest counterfactuals. The previous best known query complexity was $d^{\,O(\Delta_f(x^\star))}$, achievable by brute-force local search. We further prove a lower bound of $S(f)^{\Omega(\Delta_f(x^\star))} + \Omega(\log d)$ on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.
• Abstract（参考訳）: 我々は,その性能に関する理論的保証が強い反事実を見つけるアルゴリズムを設計する。 任意の単調モデル $f : x^d \to \{0,1\}$ とインスタンス $x^\star$ に対して、我々のアルゴリズムは \[ {s(f)^{o(\delta_f(x^\star))}\cdot \log d}\] クエリを$f$ とし、$x^\star$: 最寄りのインスタンス $x'$ to $x^\star$ に対して$f(x')\ne f(x^\star)$ を返す。 ここで $s(f)$ はリプシッツ定数の離散的類似である $f$ の感度であり、$\delta_f(x^\star)$ は $x^\star$ から最も近い反事実までの距離である。 以前の最もよく知られたクエリの複雑さは$d^{\,O(\Delta_f(x^\star))}$で、ブルートフォースローカルサーチによって達成できる。 さらに、任意のアルゴリズムのクエリ複雑性に対して、$S(f)^{\Omega(\Delta_f(x^\star))} + \Omega(\log d)$の低い境界を証明し、アルゴリズムの保証が本質的に最適であることを示す。

関連論文リスト

• Dueling Optimization with a Monotone Adversary [35.850072415395395]
  凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。 目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-11-18T23:55:59Z)
• Faster Stochastic Algorithms for Minimax Optimization under Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
  我々は、$min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$という形の有限サム問題を解くためのSPIDER-GDAを提案する。 SPIDER-GDA は $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon) の中で $epsilon$-optimal Solution を見つけることができる。
  論文  参考訳（メタデータ） (2023-07-29T02:26:31Z)
• An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
  既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。 我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
  論文  参考訳（メタデータ） (2022-12-29T19:26:12Z)
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
  双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。 Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
  論文  参考訳（メタデータ） (2022-01-19T05:56:19Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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