論文の概要: Coordinate Linear Variance Reduction for Generalized Linear Programming

• arxiv url: http://arxiv.org/abs/2111.01842v4
• Date: Thu, 6 Apr 2023 21:55:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-10 15:52:07.096092
• Title: Coordinate Linear Variance Reduction for Generalized Linear Programming
• Title（参考訳）: 一般化線形計画法における座標線形分散低減
• Authors: Chaobing Song, Cheuk Yin Lin, Stephen J. Wright, Jelena Diakonikolas
• Abstract要約: この問題における線形構造は、効率的でスケーラブルな1次アルゴリズムの設計に利用できることを示す。 textscclvr はスペクトルノルムではなく、線形制約行列 (GLP) の最大行ノルムに依存する(GLP) に対して、より複雑な結果をもたらす。
• 参考スコア（独自算出の注目度）: 27.365677554732304
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a class of generalized linear programs (GLP) in a large-scale setting, which includes simple, possibly nonsmooth convex regularizer and simple convex set constraints. By reformulating (GLP) as an equivalent convex-concave min-max problem, we show that the linear structure in the problem can be used to design an efficient, scalable first-order algorithm, to which we give the name \emph{Coordinate Linear Variance Reduction} (\textsc{clvr}; pronounced "clever"). \textsc{clvr} yields improved complexity results for (GLP) that depend on the max row norm of the linear constraint matrix in (GLP) rather than the spectral norm. When the regularization terms and constraints are separable, \textsc{clvr} admits an efficient lazy update strategy that makes its complexity bounds scale with the number of nonzero elements of the linear constraint matrix in (GLP) rather than the matrix dimensions. On the other hand, for the special case of linear programs, by exploiting sharpness, we propose a restart scheme for \textsc{clvr} to obtain empirical linear convergence. Then we show that Distributionally Robust Optimization (DRO) problems with ambiguity sets based on both $f$-divergence and Wasserstein metrics can be reformulated as (GLPs) by introducing sparsely connected auxiliary variables. We complement our theoretical guarantees with numerical experiments that verify our algorithm's practical effectiveness, in terms of wall-clock time and number of data passes.
• Abstract（参考訳）: 一般化線形プログラム (glp) のクラスを, 単純かつ非滑らかな凸正規化子と単純凸集合制約を含む大規模構成で検討した。 GLP を等価凸凹 min-max 問題として再構成することにより、この問題の線形構造を用いて効率よくスケーラブルな一階述語アルゴリズムを設計できることを示し、これを「emph{Coordinate Linear Variance Reduction} (\textsc{clvr}; クレーバー」と発音する) と呼ぶ。 \textsc{clvr} はスペクトルノルムではなく、線形制約行列(GLP)の最大行ノルムに依存する(GLP)に対して、より複雑な結果をもたらす。 正規化項と制約が分離可能であるとき、 \textsc{clvr} は、その複雑性を行列次元ではなく (GLP) における線形制約行列の 0 個の非零要素の数に制限する効率的な遅延更新戦略を認める。 一方,線形プログラムの特別な場合には,シャープネスを利用して,経験的線形収束を得るために, \textsc{clvr} のリスタートスキームを提案する。 次に,$f$-divergence と wasserstein メトリクスの両方に基づく曖昧性集合を持つ分布的ロバスト最適化(dro)問題を,疎結合な補助変数を導入することで (glps) に再構成できることを示す。 理論的保証は、ウォールクロック時間とデータパス数の観点からアルゴリズムの実用性を検証する数値実験で補う。

関連論文リスト

• Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares [0.8702432681310401]
  線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。 IRLS法は,低/複合状態の計測に好適であることを示す。
  論文  参考訳（メタデータ） (2023-06-08T06:35:47Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
  本稿では,複合最適化問題のクラスについて述べる。 合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
  論文  参考訳（メタデータ） (2023-03-29T16:15:34Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Smooth Bilevel Programming for Sparse Regularization [5.177947445379688]
  反復再重み付き最小二乗法(IRLS)は、機械学習における空間的回帰問題を解くための一般的な手法である。 両レベルスキームが組み合わさって、IRLSの驚くほど再パラメータ化が、いかにスパーシティの上位化を実現するかを示す。
  論文  参考訳（メタデータ） (2021-06-02T19:18:22Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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