論文の概要: Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean
Proximal Sampler
- arxiv url: http://arxiv.org/abs/2302.06085v1
- Date: Mon, 13 Feb 2023 04:08:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 16:44:32.119254
- Title: Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean
Proximal Sampler
- Title（参考訳）: 対数ラプラス変換と非ユークリッド近位サンプリングのアルゴリズム的側面
- Authors: Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian
- Abstract要約: 我々は、密度の対数ラプラス変換(LLT)と呼ばれる物体によって自然に正則化を誘導する、最近の[LST21]の近位サンプルの非ユークリッドアナログを開発する。
本稿では,Euclidean 設定 [GLL22] に適合させるため,$ell_p$ と $p in [1, 2]$ のSchatten-$p$ノルムの差分プライベート凸最適化の値オラクル複雑性を改善するとともに,最先端の余剰リスク境界を維持した。
- 参考スコア（独自算出の注目度）: 23.166642097170545
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The development of efficient sampling algorithms catering to non-Euclidean
geometries has been a challenging endeavor, as discretization techniques which
succeed in the Euclidean setting do not readily carry over to more general
settings. We develop a non-Euclidean analog of the recent proximal sampler of
[LST21], which naturally induces regularization by an object known as the
log-Laplace transform (LLT) of a density. We prove new mathematical properties
(with an algorithmic flavor) of the LLT, such as strong convexity-smoothness
duality and an isoperimetric inequality, which are used to prove a mixing time
on our proximal sampler matching [LST21] under a warm start. As our main
application, we show our warm-started sampler improves the value oracle
complexity of differentially private convex optimization in $\ell_p$ and
Schatten-$p$ norms for $p \in [1, 2]$ to match the Euclidean setting [GLL22],
while retaining state-of-the-art excess risk bounds [GLLST23]. We find our
investigation of the LLT to be a promising proof-of-concept of its utility as a
tool for designing samplers, and outline directions for future exploration.
- Abstract（参考訳）: 非ユークリッドジオメトリーに適応する効率的なサンプリングアルゴリズムの開発は、ユークリッド設定に成功する離散化技術がより一般的な設定に容易に継承できないため、難しい課題となっている。
我々は、密度の対数ラプラス変換(LLT)と呼ばれる物体によって自然に正規化を誘導する、最近の[LST21]の近位サンプルの非ユークリッドアナログを開発する。
我々は,LLTの厳密な凸性-平滑性双対性や等長不等式など,LLTの新たな数学的特性(アルゴリズム的フレーバー付き)を証明し,温暖開始時の近位サンプルラーマッチング [LST21] の混合時間を証明する。
メインのアプリケーションとして、wwarm-started samplerは、oracleのプライベートな凸最適化の複雑さを$\ell_p$ と schatten-$p$ で改善し、euclidean設定 [gll22] にマッチさせながら、最先端の過剰なリスク境界 [gllst23] を保持する。
我々は,LLTについて,サンプルを設計するためのツールとしての有用性を実証し,今後の探索の方向性を概説する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - Generative Modelling of L\'{e}vy Area for High Order SDE Simulation [5.9535699822923]
L'evyGANはブラウン増分に基づくL'evy領域の近似サンプルを生成するディープラーニングモデルである。
L'evyGANは関節分布と辺縁分布の両方を測定するいくつかの指標で最先端のパフォーマンスを示す。
論文 参考訳（メタデータ） (2023-08-04T16:38:37Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。
既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
論文 参考訳（メタデータ） (2022-09-01T11:05:26Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。