論文の概要: Complementary Composite Minimization, Small Gradients in General Norms,
and Applications to Regression Problems
- arxiv url: http://arxiv.org/abs/2101.11041v1
- Date: Tue, 26 Jan 2021 19:21:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-14 04:47:54.040760
- Title: Complementary Composite Minimization, Small Gradients in General Norms,
and Applications to Regression Problems
- Title（参考訳）: 補複合化の最小化, 一般ノルムの小勾配化, 回帰問題への応用
- Authors: Jelena Diakonikolas and Crist\'obal Guzm\'an
- Abstract要約: 複合最小化は大規模凸最適化における強力なフレームワークである。
補完的複合最小化のための新しいアルゴリズムフレームワークを提案する。
我々は,フレームワークから得られるアルゴリズムが,ほとんどの標準最適化設定においてほぼ最適であることを証明した。
- 参考スコア（独自算出の注目度）: 14.759688428864157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Composite minimization is a powerful framework in large-scale convex
optimization, based on decoupling of the objective function into terms with
structurally different properties and allowing for more flexible algorithmic
design. In this work, we introduce a new algorithmic framework for
complementary composite minimization, where the objective function decouples
into a (weakly) smooth and a uniformly convex term. This particular form of
decoupling is pervasive in statistics and machine learning, due to its link to
regularization.
The main contributions of our work are summarized as follows. First, we
introduce the problem of complementary composite minimization in general normed
spaces; second, we provide a unified accelerated algorithmic framework to
address broad classes of complementary composite minimization problems; and
third, we prove that the algorithms resulting from our framework are
near-optimal in most of the standard optimization settings. Additionally, we
show that our algorithmic framework can be used to address the problem of
making the gradients small in general normed spaces. As a concrete example, we
obtain a nearly-optimal method for the standard $\ell_1$ setup (small gradients
in the $\ell_\infty$ norm), essentially matching the bound of Nesterov (2012)
that was previously known only for the Euclidean setup. Finally, we show that
our composite methods are broadly applicable to a number of regression
problems, leading to complexity bounds that are either new or match the best
existing ones.
- Abstract（参考訳）: コンポジット最小化は、目的関数を構造的に異なる特性と分離し、より柔軟なアルゴリズム設計を可能にする大規模凸最適化の強力なフレームワークである。
本研究では, 対象関数が(弱く)滑らかかつ一様凸な項に分解する, 相補的複合最小化のための新しいアルゴリズムフレームワークを提案する。
分離のこの特定の形態は、正規化へのリンクのために、統計学と機械学習に広がっている。
私たちの仕事の主な貢献は以下のとおりである。
第1に,一般のノルム空間における相補的複合最小化の問題,第2に相補的複合最小化問題の幅広いクラスに対応する統一的高速化アルゴリズムフレームワーク,第3に,標準最適化設定のほとんどにおいて,このフレームワークによるアルゴリズムがほぼ最適であることを示す。
さらに,我々のアルゴリズムフレームワークは,一般のノルム空間において勾配を小さくする問題に対処するために利用できることを示した。
具体例として、標準的な $\ell_1$ セットアップ($\ell_\infty$ ノルムの小さな勾配)の概最適化法が得られ、本質的には、以前はユークリッド集合でのみ知られていた Nesterov (2012) の境界に一致する。
最後に、私たちのコンポジットメソッドは、多くの回帰問題に広く適用され、新しいものや既存のものと一致する複雑さの境界につながることを示しています。
関連論文リスト
- Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of
Newton Method [4.62316736194615]
準自己調和平滑成分を用いた複合凸最適化問題について検討する。
この問題クラスは、古典的な自己調和函数とリプシッツ連続ヘッセン函数の間に自然に補間する。
準自己協和関数を最小化するためには、グラディエント正規化を伴う基本ニュートン法を用いることができる。
論文 参考訳（メタデータ） (2023-08-28T17:43:04Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - SCORE: Approximating Curvature Information under Self-Concordant
Regularization [0.0]
本稿では,新たな入力を受信するたびに最小化速度を更新する自己調和正規化アルゴリズム(GGN-SCORE)を提案する。
提案アルゴリズムはヘッセン行列の2階情報構造を利用して計算オーバーヘッドを削減する。
論文 参考訳（メタデータ） (2021-12-14T13:03:04Z) - On Constraints in First-Order Optimization: A View from Non-Smooth
Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。
提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。
結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文 参考訳（メタデータ） (2021-07-17T11:45:13Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - A Class of Linear Programs Solvable by Coordinate-Wise Minimization [0.0]
座標最小化を正確に解く線形プログラムのクラスを示す。
いくつかのよく知られた最適化問題の2つのLP緩和がこのクラスにあることを示す。
我々の結果は理論的には非自明であり、将来的には新たな大規模最適化アルゴリズムがもたらされる可能性がある。
論文 参考訳（メタデータ） (2020-01-28T17:14:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。