論文の概要: Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with
Error Certificates
- arxiv url: http://arxiv.org/abs/2102.01977v5
- Date: Wed, 22 Mar 2023 09:17:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 08:40:36.617275
- Title: Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with
Error Certificates
- Title（参考訳）: 誤り証明書を用いたゼロ階リプシッツ最適化のためのインスタンス依存境界
- Authors: Fran\c{c}ois Bachoc (IMT, GdR MASCOT-NUM), Tommaso R Cesari (TSE-R),
S\'ebastien Gerchinovitz (IMT)
- Abstract要約: コンパクト部分集合 $mathcal X$ of $mathbb Rd$ 上で定義されるリプシッツ関数 $f$ のゼロ次(ブラックボックス)最適化の問題を研究する。
我々は、任意のリプシッツ関数 $f$ の評価の最適な個数を特徴付け、精度$varepsilon$ で$f$ の近似器を見つけて証明する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of zeroth-order (black-box) optimization of a Lipschitz
function $f$ defined on a compact subset $\mathcal X$ of $\mathbb R^d$, with
the additional constraint that algorithms must certify the accuracy of their
recommendations. We characterize the optimal number of evaluations of any
Lipschitz function $f$ to find and certify an approximate maximizer of $f$ at
accuracy $\varepsilon$. Under a weak assumption on $\mathcal X$, this optimal
sample complexity is shown to be nearly proportional to the integral
$\int_{\mathcal X} \mathrm{d}\boldsymbol x/( \max(f) - f(\boldsymbol x) +
\varepsilon )^d$. This result, which was only (and partially) known in
dimension $d=1$, solves an open problem dating back to 1991. In terms of
techniques, our upper bound relies on a packing bound by Bouttier al. (2020)
for the Piyavskii-Shubert algorithm that we link to the above integral. We also
show that a certified version of the computationally tractable DOO algorithm
matches these packing and integral bounds. Our instance-dependent lower bound
differs from traditional worst-case lower bounds in the Lipschitz setting and
relies on a local worst-case analysis that could likely prove useful for other
learning tasks.
- Abstract（参考訳）: コンパクト部分集合 $\mathcal X$ of $\mathbb R^d$ 上で定義されるリプシッツ関数 $f$ のゼロ階最適化(ブラックボックス)の問題を、アルゴリズムが推奨の精度を証明しなければならないという追加の制約で検討する。
我々は、任意のリプシッツ関数の最適評価回数を、精度$\varepsilon$で、近似最大値が$f$であることを示す。
$\mathcal X$ 上の弱い仮定の下で、この最適なサンプル複雑性は積分 $\int_{\mathcal X} \mathrm{d}\boldsymbol x/(\max(f) - f(\boldsymbol x) + \varepsilon )^d$ にほぼ比例する。
この結果は、次元 $d=1$ でしか知られていなかったが、1991年にまでさかのぼる未解決問題を解く。
手法の面では、我々の上界は、上記の積分にリンクする piyavskii-shubert アルゴリズムの bouttier al. (2020) で束縛されたパッキングに依存している。
また,計算抽出可能なDOOアルゴリズムの認定バージョンが,これらのパッキングと積分境界に一致することを示す。
インスタンス依存の下限は、リプシッツ設定の従来の最悪ケース下限と異なり、ローカルな最悪のケース分析に依存しており、他の学習タスクに有用である可能性が高い。
関連論文リスト
- Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - 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) - Greedy Adversarial Equilibrium: An Efficient Alternative to
Nonconvex-Nonconcave Min-Max Optimization [28.431572772564518]
リプシッツの$varepsilon$-greedy逆数モデルは任意の出発点から$max_z f(x, z)$に収束することを示す。
また、リプシッツの$nabla_y f(x,y)$が$d$, $1/varepsilon$であり、$nabla2_y f(x,y)$上の境界は$nabla2_yであることを示す。
論文 参考訳（メタデータ） (2020-06-22T16:03:41Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。