論文の概要: Beyond Log-Concavity: Theory and Algorithm for Sum-Log-Concave
Optimization
- arxiv url: http://arxiv.org/abs/2309.15298v1
- Date: Tue, 26 Sep 2023 22:22:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-28 17:29:13.322735
- Title: Beyond Log-Concavity: Theory and Algorithm for Sum-Log-Concave
Optimization
- Title(参考訳): log-concavityを超えて:sum-log-concave最適化の理論とアルゴリズム
- Authors: Mastane Achab
- Abstract要約: 一般に凸ではないが、一般凸不等式を満たすことが示される。
本稿では,クロスグラディエントDescent (XGD)アルゴリズムを提案する。
本稿では,要約-log-concave関数に依存するいわゆるチェッカーレグレッション手法を提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper extends the classic theory of convex optimization to the
minimization of functions that are equal to the negated logarithm of what we
term as a sum-log-concave function, i.e., a sum of log-concave functions. In
particular, we show that such functions are in general not convex but still
satisfy generalized convexity inequalities. These inequalities unveil the key
importance of a certain vector that we call the cross-gradient and that is, in
general, distinct from the usual gradient. Thus, we propose the Cross Gradient
Descent (XGD) algorithm moving in the opposite direction of the cross-gradient
and derive a convergence analysis. As an application of our sum-log-concave
framework, we introduce the so-called checkered regression method relying on a
sum-log-concave function. This classifier extends (multiclass) logistic
regression to non-linearly separable problems since it is capable of
tessellating the feature space by using any given number of hyperplanes,
creating a checkerboard-like pattern of decision regions.
- Abstract(参考訳): 本稿では、凸最適化の古典的な理論を、我々がsum-log-concave関数、すなわちlog-concave関数の和と呼ぶものの否定対数に等しい関数の最小化に拡張する。
特に、そのような函数は一般に凸ではないが、一般凸不等式を満たすことを示す。
これらの不等式は、私たちがクロスグラディエント(cross-gradient)と呼び、一般に通常の勾配とは異なるあるベクトルの重要な重要性を浮き彫りにする。
そこで,我々はクロスグレードの反対方向に移動するクロスグレード降下 (xgd) アルゴリズムを提案し,収束解析を導出する。
本稿では,sum-log-concave フレームワークの適用として,sum-log-concave 関数に依存するいわゆる Checkered regression 手法を提案する。
この分類器は、任意の数の超平面を用いて特徴空間を計算し、チェッカーボードのような決定領域のパターンを作成することができるので、(複数のクラス)ロジスティック回帰を非線形に分離できない問題に拡張する。
関連論文リスト
- Optimal lower bounds for logistic log-likelihoods [1.3124513975412255]
ロジット変換は、おそらく線形設定を超えて最も広く採用されているリンク関数である。
2次よりも鋭い接する下界が、結果として生じるマイノライザーのトラクタビリティを損なうことなく導出できるかどうかはまだ分かっていない。
本稿は、新しい2次下界の設計と研究を通じて、このような挑戦的な問題に対処する。
論文 参考訳(メタデータ) (2024-10-14T09:09:33Z) - Non-asymptotic convergence bounds for Sinkhorn iterates and their
gradients: a coupling approach [10.568851068989972]
本稿では,アルゴリズムの効率的な解法を実現するために,元のOT問題であるエントロピックOT問題の緩和に焦点をあてる。
この定式化はSchr"odinger Bridge問題としても知られ、特に最適制御(SOC)と結びつき、人気のあるシンクホーンアルゴリズムで解くことができる。
論文 参考訳(メタデータ) (2023-04-13T13:58:25Z) - Universal coding, intrinsic volumes, and metric complexity [3.4392739159262145]
ガウス的設定における逐次確率の割り当てについて検討し、ゴールは実数値観測の列を予測または等価に予測することである。
解析の一環として、一般集合のミニマックスについても記述し、情報理論の古典的な結果と最終的に関連づける。
論文 参考訳(メタデータ) (2023-03-13T16:54:04Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Linear Convergence of ISTA and FISTA [8.261388753972234]
疎表現を用いた線形逆問題の解法として,反復縮小保持アルゴリズム (ISTA) のクラスを再検討する。
滑らかな部分を凸とする以前の仮定は最小二乗モデルを弱める。
目的値と2乗近位下次ノルムの両方において、線形収束を合成最適化に一般化する。
論文 参考訳(メタデータ) (2022-12-13T02:02:50Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳(メタデータ) (2022-03-30T11:39:00Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。
分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
論文 参考訳(メタデータ) (2022-02-28T13:01:04Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳(メタデータ) (2021-09-17T17:46:12Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。