論文の概要: Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging
- arxiv url: http://arxiv.org/abs/2311.02557v2
- Date: Mon, 11 Mar 2024 10:44:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 15:29:39.368130
- 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要約: 本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(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
includes 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
$\smash{\tilde{O}}(d^2/\varepsilon^2)$ time, matching the state of the art,
where $d$ denotes the dimension. When computing the maximum-likelihood estimate
for quantum state tomography, our algorithm yields an $\varepsilon$-optimal
solution in $\smash{\tilde{O}}(d^3/\varepsilon^2)$ time. 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確率的双対平均法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$\varepsilon$-optimal solution in $\smash{\tilde{O}}(d^2/\varepsilon^2)$ time, with the state of the art, where $d$ represent the dimension。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは、$\smash{\tilde{O}}(d^3/\varepsilon^2)$ timeで$\varepsilon$-optimal Solutionを得る。
これにより、既存の確率的一階法の時間的複雑さを、$d^{\omega-2}$で、バッチ法を$d^2$で、$\omega$は行列の乗法指数を表す。
数値実験により,提案手法は従来の手法よりも明示的な複雑性を保証できることを示した。
関連論文リスト
- 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) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。