論文の概要: Performance of $\ell_1$ Regularization for Sparse Convex Optimization

• arxiv url: http://arxiv.org/abs/2307.07405v1
• Date: Fri, 14 Jul 2023 15:31:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-17 13:34:33.775890
• Title: Performance of $\ell_1$ Regularization for Sparse Convex Optimization
• Title（参考訳）: スパース凸最適化のための$\ell_1$正規化の性能
• Authors: Kyriakos Axiotis, Taisuke Yasuda
• Abstract要約: ベクトル値特徴を持つスパース凸最適化のためのグループLASSOの最初のリカバリ保証を与える。 この結果は、一般入力インスタンス下での凸関数に対するグループLASSOの経験的成功を理論的に説明する最初のものである。 この問題に対する一般損失関数の第一結果は、強い凸性や滑らかさに制限されるだけである。
• 参考スコア（独自算出の注目度）: 10.37112414795167
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Despite widespread adoption in practice, guarantees for the LASSO and Group LASSO are strikingly lacking in settings beyond statistical problems, and these algorithms are usually considered to be a heuristic in the context of sparse convex optimization on deterministic inputs. We give the first recovery guarantees for the Group LASSO for sparse convex optimization with vector-valued features. We show that if a sufficiently large Group LASSO regularization is applied when minimizing a strictly convex function $l$, then the minimizer is a sparse vector supported on vector-valued features with the largest $\ell_2$ norm of the gradient. Thus, repeating this procedure selects the same set of features as the Orthogonal Matching Pursuit algorithm, which admits recovery guarantees for any function $l$ with restricted strong convexity and smoothness via weak submodularity arguments. This answers open questions of Tibshirani et al. and Yasuda et al. Our result is the first to theoretically explain the empirical success of the Group LASSO for convex functions under general input instances assuming only restricted strong convexity and smoothness. Our result also generalizes provable guarantees for the Sequential Attention algorithm, which is a feature selection algorithm inspired by the attention mechanism proposed by Yasuda et al. As an application of our result, we give new results for the column subset selection problem, which is well-studied when the loss is the Frobenius norm or other entrywise matrix losses. We give the first result for general loss functions for this problem that requires only restricted strong convexity and smoothness.
• Abstract（参考訳）: 実際に広く採用されているにもかかわらず、LASSO と Group LASSO の保証は統計的問題以外の設定に著しく欠けており、これらのアルゴリズムは通常、決定論的入力に対するスパース凸最適化の文脈においてヒューリスティックであると考えられている。 ベクトル値特徴を持つスパース凸最適化のためのグループLASSOの最初のリカバリ保証を与える。 厳密な凸関数 $l$ を最小化するとき、十分に大きな Group LASSO 正規化が適用されるなら、最小化子は勾配の最大$\ell_2$ノルムを持つベクトル値の特徴で支えられるスパースベクトルである。 したがって、この手順を繰り返すと直交マッチング追従アルゴリズムと同じ特徴が選択され、弱い部分モジュラリティの引数によって制限された強い凸性と滑らかさを持つ任意の関数に対して回復保証が与えられる。 tibshirani et al. and yasuda et al.の疑問に答える。 その結果、一般入力条件下での凸関数に対するラッソ群の経験的成功を理論上初めて説明し、強い凸性と滑らかさのみを仮定した。 また,安田らによって提案された注意機構にインスパイアされた特徴選択アルゴリズムであるSequential Attentionアルゴリズムの証明保証を一般化した。 この結果の適用例として、損失がフロベニウスノルムあるいは他のエントリーワイズ行列損失であるときによく研究されるカラム部分集合選択問題に対する新しい結果を与える。 この問題に対する一般損失関数の第一結果は、強い凸性や滑らか性のみを必要とするものである。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.667453772837954]
  強い凸関数制約を受ける凸関数を最小化する方法を示す。 有限個の結果に独立な意味を持つような空間パターンを同定する。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle [16.290192687098383]
  本稿では,アフィン制約を伴う凸複合最適化問題について考察する。 正確なプロジェクション/近距離計算が難解な高次元アプリケーションにより,テキスト投影のないラグランジアン型拡張手法を提案する。
  論文  参考訳（メタデータ） (2022-10-25T12:51:43Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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