論文の概要: Certificate-Guided Pruning for Stochastic Lipschitz Optimization

• arxiv url: http://arxiv.org/abs/2601.20231v1
• Date: Wed, 28 Jan 2026 04:02:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.762973
• Title: Certificate-Guided Pruning for Stochastic Lipschitz Optimization
• Title（参考訳）: 確率リプシッツ最適化のための認証ガイドプルーニング
• Authors: Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma,
• Abstract要約: 雑音評価の下で,リプシッツ関数のブラックボックス最適化について検討した。 既存の適応的な離散化手法は、暗黙的に最適領域を避けるが、最適性や測定可能な進捗保証の明確な証明書は提供していない。 本稿では、アダプティブテキストbf-Guided Pruning (CGP)を導入し、信頼調整リプシッツエンベロープによる潜在的最適点の集合A_t$を明示的に維持する。
• 参考スコア（独自算出の注目度）: 6.908972852063454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study black-box optimization of Lipschitz functions under noisy evaluations. Existing adaptive discretization methods implicitly avoid suboptimal regions but do not provide explicit certificates of optimality or measurable progress guarantees. We introduce \textbf{Certificate-Guided Pruning (CGP)}, which maintains an explicit \emph{active set} $A_t$ of potentially optimal points via confidence-adjusted Lipschitz envelopes. Any point outside $A_t$ is certifiably suboptimal with high probability, and under a margin condition with near-optimality dimension $α$, we prove $\Vol(A_t)$ shrinks at a controlled rate yielding sample complexity $\tildeO(\varepsilon^{-(2+α)})$. We develop three extensions: CGP-Adaptive learns $L$ online with $O(\log T)$ overhead; CGP-TR scales to $d > 50$ via trust regions with local certificates; and CGP-Hybrid switches to GP refinement when local smoothness is detected. Experiments on 12 benchmarks ($d \in [2, 100]$) show CGP variants match or exceed strong baselines while providing principled stopping criteria via certificate volume.
• Abstract（参考訳）: 雑音評価の下で,リプシッツ関数のブラックボックス最適化について検討した。 既存の適応的な離散化手法は、暗黙的に最適領域を避けるが、最適性や測定可能な進捗保証の明確な証明書は提供していない。 信頼調整リプシッツエンベロープによる潜在的最適点の明示的な \emph{active set} $A_t$ を維持した \textbf{Certificate-Guided Pruning (CGP)} を導入する。 A_t$ の外の任意の点は高い確率で正に最適であり、近最適次元 $α$ のマージン条件の下では、サンプル複雑性 $\tildeO(\varepsilon^{-(2+α)})$ を得る制御速度で $\Vol(A_t)$ が縮まることを証明している。 CGP-Adaptiveは、$O(\log T)$オーバーヘッドでオンラインで学習し、CGP-TRは、ローカルな証明書付き信頼領域を介して$d > 50$にスケールし、CGP-Hybridは、局所的な滑らかさが検出されたときにGPリファインメントに切り替える。 12ベンチマーク($d \in [2, 100]$)の実験では、CGPの変種は強力なベースラインと一致しているか、あるいは超えている。

関連論文リスト

• Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation [0.2864713389096699]
  本研究では,スムーズな非デルタ最適化において,厳密なサドル点を回避するための一階法を包括的に理論的に解析する。 我々の主な貢献は、完全に明示的な定数を持ち、勾配とサドル・エスケープ相を厳密に分離したパーチャベッド・エスケープ・ダイアンス (PSD) アルゴリズムである。 我々は、合成機能と実用的な機械学習タスクの両方の実験を通して、理論的予測を検証する。
  論文  参考訳（メタデータ） (2025-08-22T17:06:28Z)
• Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation [52.772454746132276]
  問題依存量のモデル化における近似誤差は,アルゴリズムのグローバル収束とは無関係であることを示す。 我々は,任意の定値学習率を持つ$textttLin-SPG$が,最適ポリシーへのグローバル収束を保証することを証明した。
  論文  参考訳（メタデータ） (2025-05-06T04:03:06Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Private Convex Optimization in General Norms [23.166642097170545]
  任意のノルム$normxcdot$におけるリプシッツである凸関数の微分プライベート最適化のための新しいフレームワークを提案する。 本稿では,このメカニズムが差分プライバシーを満足し,DP-ERM(経験的リスク最小化)とDP-SCO(確率的凸最適化)の両方を解決することを示す。 我々のフレームワークは、一般ノルム空間におけるプライベート凸最適化に初めて適用され、ミラー降下によって達成された非プライベートSCOレートを直接回復する。
  論文  参考訳（メタデータ） (2022-07-18T02:02:22Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• 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)
• Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates [0.0]
  コンパクト部分集合 $mathcal X$ of $mathbb Rd$ 上で定義されるリプシッツ関数 $f$ のゼロ次(ブラックボックス)最適化の問題を研究する。 我々は、任意のリプシッツ関数 $f$ の評価の最適な個数を特徴付け、精度$varepsilon$ で$f$ の近似器を見つけて証明する。
  論文  参考訳（メタデータ） (2021-02-03T09:51:03Z)

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

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