論文の概要: Making Progress Based on False Discoveries
- arxiv url: http://arxiv.org/abs/2204.08809v1
- Date: Tue, 19 Apr 2022 11:17:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-20 13:31:10.202754
- Title: Making Progress Based on False Discoveries
- Title（参考訳）: 偽発見に基づく進歩
- Authors: Roi Livni
- Abstract要約: 本稿では,凸最適化の枠組みにおける適応データ解析の課題について考察する。
一般アナリスト(必ずしも勾配降下ではない)に対して、Omega (1/epsilon3)$サンプルが必要であることを示す。
第二に、オラクル上の特定の仮定の下では、勾配降下$tilde Omega (1/epsilon2.5)$サンプルが必要であることを示す。
- 参考スコア（独自算出の注目度）: 14.505867475659274
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the question of adaptive data analysis within the framework of
convex optimization. We ask how many samples are needed in order to compute
$\epsilon$-accurate estimates of $O(1/\epsilon^2)$ gradients queried by
gradient descent, and we provide two intermediate answers to this question.
First, we show that for a general analyst (not necessarily gradient descent)
$\Omega(1/\epsilon^3)$ samples are required. This rules out the possibility of
a foolproof mechanism. Our construction builds upon a new lower bound (that may
be of interest of its own right) for an analyst that may ask several non
adaptive questions in a batch of fixed and known $T$ rounds of adaptivity and
requires a fraction of true discoveries. We show that for such an analyst
$\Omega (\sqrt{T}/\epsilon^2)$ samples are necessary.
Second, we show that, under certain assumptions on the oracle, in an
interaction with gradient descent $\tilde \Omega(1/\epsilon^{2.5})$ samples are
necessary. Our assumptions are that the oracle has only \emph{first order
access} and is \emph{post-hoc generalizing}. First order access means that it
can only compute the gradients of the sampled function at points queried by the
algorithm. Our assumption of \emph{post-hoc generalization} follows from
existing lower bounds for statistical queries. More generally then, we provide
a generic reduction from the standard setting of statistical queries to the
problem of estimating gradients queried by gradient descent.
These results are in contrast with classical bounds that show that with
$O(1/\epsilon^2)$ samples one can optimize the population risk to accuracy of
$O(\epsilon)$ but, as it turns out, with spurious gradients.
- Abstract（参考訳）: 凸最適化の枠組みにおける適応データ解析の課題について考察する。
我々は、勾配降下によってクエリされた$O(1/\epsilon^2)$勾配の$\epsilon$-正確な推定を計算するために、どのくらいのサンプルが必要なのかを問う。
まず、一般アナリスト(必ずしも勾配降下ではない)に対して、$\Omega(1/\epsilon^3)$サンプルが必要であることを示す。
これにより、防犯機構の可能性を排除できる。
私たちの構築は、いくつかの非適応的な質問を、固定的で既知の1ラウンドの順応性(adaptivity)で実行し、真の発見のほんの一部を必要とするアナリストのために、新しい下限(それ自体が興味を持つかもしれない)に基づいています。
そのようなアナリストに対して、$\Omega (\sqrt{T}/\epsilon^2)$サンプルが必要であることを示す。
第二に、オラクル上の特定の仮定の下では、勾配降下$\tilde \Omega(1/\epsilon^{2.5})$サンプルが必要であることを示す。
我々の仮定では、オラクルは \emph{first order access} のみを持ち、 \emph{post-hoc generalizing} である。
1次アクセスは、アルゴリズムが問い合わせた点におけるサンプル関数の勾配のみを計算できることを意味する。
emph{post-hoc generalization} の仮定は、統計クエリの既存の下限から導かれる。
より一般的には、統計的クエリの標準設定から、勾配降下によって問合せされた勾配を推定する問題への一般的な還元を提供する。
これらの結果は、$O(1/\epsilon^2)$サンプルを用いて、人口リスクを$O(\epsilon)$の精度に最適化できるが、その結果、急激な勾配を持つことを示す古典的境界とは対照的である。
関連論文リスト
- Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Sample-optimal classical shadows for pure states [0.0]
我々は、結合測定と独立測定の両方の設定において、純粋な状態に対する古典的なシャドウタスクを考察する。
独立測定では、$mathcal O(sqrtBd epsilon-1 + epsilon-2)$ sufficeを示す。
論文 参考訳（メタデータ） (2022-11-21T19:24:17Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Quantum tomography using state-preparation unitaries [0.22940141855172028]
ユニタリへのアクセスが与えられると、$d$次元の量子状態の古典的記述を近似的に得るアルゴリズムを記述する。
状態の$varepsilon$-$ell$-approximationを得るには、$widetildeTheta(d/varepsilon)$ Unitaryのアプリケーションが必要です。
我々は、ランク=r$混合状態のシュターテン$q$最適推定値を得るための効率的なアルゴリズムを与える。
論文 参考訳（メタデータ） (2022-07-18T17:56:18Z) - Generalization Bounds for Gradient Methods via Discrete and Continuous
Prior [8.76346911214414]
次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。
また、あるSGDの変種に対する新しい境界を得ることもできる。
論文 参考訳（メタデータ） (2022-05-27T07:23:01Z) - 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) - 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) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。