論文の概要: Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs

• arxiv url: http://arxiv.org/abs/2008.01724v2
• Date: Tue, 13 Jul 2021 01:56:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-03 00:13:43.083976
• Title: Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Title（参考訳）: 凸と非凸の最適化は無作為設計による無作為なブラインドデコンボリューションの最小最適化である
• Authors: Yuxin Chen, Jianqing Fan, Bingyan Wang, Yuling Yan
• Abstract要約: 両対数ランダムノイズの解法における凸緩和と非最適最適化の有効性について検討する。 その結果、最先端の理論的保証が大幅に改善された。
• 参考スコア（独自算出の注目度）: 12.089409241521185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the effectiveness of convex relaxation and nonconvex optimization in solving bilinear systems of equations under two different designs (i.e.$~$a sort of random Fourier design and Gaussian design). Despite the wide applicability, the theoretical understanding about these two paradigms remains largely inadequate in the presence of random noise. The current paper makes two contributions by demonstrating that: (1) a two-stage nonconvex algorithm attains minimax-optimal accuracy within a logarithmic number of iterations. (2) convex relaxation also achieves minimax-optimal statistical accuracy vis-\`a-vis random noise. Both results significantly improve upon the state-of-the-art theoretical guarantees.
• Abstract（参考訳）: 2つの異なる設計(例えば、$~$aのランダムフーリエ設計とガウス設計)の下で方程式の双線型系の解法における凸緩和と非凸最適化の有効性について検討する。 適用性は広いが、これらの2つのパラダイムに関する理論的理解は、ランダムノイズの存在下ではほとんど不十分である。 本論文は,(1)2段階の非凸アルゴリズムが対数的な反復数で最小最適精度を得ることを示すことによって2つの貢献を行う。 2)凸緩和は,最小値の統計精度 vis-\`a-vis ランダムノイズも達成する。 どちらの結果も最先端の理論的保証を大幅に改善した。

関連論文リスト

• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression [15.389011827844572]
  重み付き雑音や客観的腐敗の下での高テール線形回帰は、どちらも統計的に困難である。 本稿では,ノイズガウスあるいは重度1+エプシロン回帰問題に対するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T14:31:03Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Computationally Efficient and Statistically Optimal Robust Low-rank Matrix and Tensor Estimation [15.389011827844572]
  低ランク線形収縮推定法では, どちらも統計的に困難である。 本稿では,計算効率だけでなく,統計的に最適である新しいサブオリエント(RsGrad)を提案する。
  論文  参考訳（メタデータ） (2022-03-02T09:05:15Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models [41.7567932118769]
  二元モデルにおける高次元推論のための凸実験リスクについて検討する。 ロジスティックモデルとプロビットモデルの下でのバイナリ線形分類では、最小二乗法の性能は0.997倍、0.98倍である。
  論文  参考訳（メタデータ） (2020-02-17T22:32:14Z)

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

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