論文の概要: Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging
- arxiv url: http://arxiv.org/abs/2311.02557v1
- Date: Sun, 5 Nov 2023 03:33:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-07 17:06:30.600238
- Title: Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging
- Title（参考訳）: 確率的双対平均化による対数損失の高速最小化
- Authors: Chung-En Tsai and Hao-Chung Cheng and Yen-Huan Li
- Abstract要約: 確率の単純さや量子行列の集合よりも期待される対数損失を最小化する問題を解く。
Poisson逆問題に対して、我々のアルゴリズムは$tildeO (d3/varepsilon2)$時間で$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $tildeO (d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
- 参考スコア（独自算出の注目度）: 8.990961435218544
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the problem of minimizing an expected logarithmic loss over either
the probability simplex or the set of quantum density matrices. This problem
encompasses tasks such as solving the Poisson inverse problem, computing the
maximum-likelihood estimate for quantum state tomography, and approximating
positive semi-definite matrix permanents with the currently tightest
approximation ratio. Although the optimization problem is convex, standard
iteration complexity guarantees for first-order methods do not directly apply
due to the absence of Lipschitz continuity and smoothness in the loss function.
In this work, we propose a stochastic first-order algorithm named $B$-sample
stochastic dual averaging with the logarithmic barrier. For the Poisson inverse
problem, our algorithm attains an $\varepsilon$-optimal solution in $\tilde{O}
(d^2/\varepsilon^2)$ time, matching the state of the art. When computing the
maximum-likelihood estimate for quantum state tomography, our algorithm yields
an $\varepsilon$-optimal solution in $\tilde{O} (d^3/\varepsilon^2)$ time,
where $d$ denotes the dimension. This improves on the time complexities of
existing stochastic first-order methods by a factor of $d^{\omega-2}$ and those
of batch methods by a factor of $d^2$, where $\omega$ denotes the matrix
multiplication exponent. Numerical experiments demonstrate that empirically,
our algorithm outperforms existing methods with explicit complexity guarantees.
- Abstract（参考訳）: 確率的単純性または量子密度行列の集合よりも期待される対数損失を最小化する問題を考える。
この問題は、ポアソン逆問題の解法、量子状態トモグラフィーの最大様推定値の計算、正の半定値行列の近似、現在最も厳密な近似比などのタスクを含む。
最適化問題は凸であるが、一階法の標準的な反復複雑性は、損失関数のリプシッツ連続性や滑らかさの欠如により直接適用されない。
本研究では,対数障壁を持つ確率的一階アルゴリズムである$b$-sample確率的双対平均法を提案する。
ポアソン逆問題に対して、我々のアルゴリズムは、芸術の状態を一致させて、$\tilde{O} (d^2/\varepsilon^2) の最適解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは$\tilde{O} (d^3/\varepsilon^2)$時間で$\varepsilon$-optimal Solutionを得る。
これにより、既存の確率的一階法の時間的複雑さを、$d^{\omega-2}$で、バッチ法を$d^2$で、$\omega$は行列の乗法指数を表す。
数値実験により,提案手法は従来の手法よりも明示的な複雑性を保証できることを示した。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean
Estimation and Linear Regression [44.13655983242414]
最適誤差保証付きニア・ニア・ニア・リニア時間アルゴリズムの最初のサンプルを設計する。
堅牢な線形回帰のために、サンプル複雑性$n = tildeO(d/epsilon2)$と、ターゲット回帰器を$ell$-$O(epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。
これは、文献のオープンな疑問に答え、最適なエラー保証を達成するための最初のサンプルとタイムアルゴリズムである。
論文 参考訳（メタデータ） (2023-12-04T00:31:16Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Faster Stochastic First-Order Method for Maximum-Likelihood Quantum
State Tomography [10.758021887982782]
量子状態トモグラフィーでは、サンプルサイズと寸法は量子ビットの数とともに指数関数的に増加する。
本稿では,バーグ様エントロピーを用いたミラー降下法を提案する。
我々の知る限りでは、これは現在、最大形量子状態トモグラフィーの高速で一階法である。
論文 参考訳（メタデータ） (2022-11-23T11:35:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳（メタデータ） (2021-06-22T07:24:17Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。