論文の概要: On the Correctness of the Generalized Isotonic Recursive Partitioning
Algorithm
- arxiv url: http://arxiv.org/abs/2401.04847v2
- Date: Thu, 11 Jan 2024 01:40:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-12 11:18:46.531074
- Title: On the Correctness of the Generalized Isotonic Recursive Partitioning
Algorithm
- Title(参考訳): 一般化等張再帰的分割アルゴリズムの正しさについて
- Authors: Joong-Ho Won and Jihan Jung
- Abstract要約: 本稿では, 一般等速再帰分割法 (GIRP) アルゴリズムを, 分離凸損失下での等速モデルの適合性について詳細に解析する。
GIRPアルゴリズムは、アルゴリズムの各ステップにおいて、中間解が等調性制約を満たすような魅力的な特徴を示す。
GIRP の小さな修正は正しい解を得るのに十分であり、すべての中間解が等方性であることの望ましい性質を保っている。
- 参考スコア(独自算出の注目度): 9.482025609011123
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: This paper presents an in-depth analysis of the generalized isotonic
recursive partitioning (GIRP) algorithm for fitting isotonic models under
separable convex losses, proposed by Luss and Rosset [J. Comput. Graph.
Statist., 23 (2014), pp. 192--201] for differentiable losses and extended by
Painsky and Rosset [IEEE Trans. Pattern Anal. Mach. Intell., 38 (2016), pp.
308-321] for nondifferentiable losses. The GIRP algorithm poseses an attractive
feature that in each step of the algorithm, the intermediate solution satisfies
the isotonicity constraint. The paper begins with an example showing that the
GIRP algorithm as described in the literature may fail to produce an isotonic
model, suggesting that the existence and uniqueness of the solution to the
isotonic regression problem must be carefully addressed. It proceeds with
showing that, among possibly many solutions, there indeed exists a solution
that can be found by recursive binary partitioning of the set of observed data.
A small modification of the GIRP algorithm suffices to obtain a correct
solution and preserve the desired property that all the intermediate solutions
are isotonic. This proposed modification includes a proper choice of
intermediate solutions and a simplification of the partitioning step from
ternary to binary.
- Abstract(参考訳): 本稿では,Luss and Rosset [J. Comput. Graph. Statist., 23 (2014), pp. 192--201] によって提案され,Painsky and Rosset [IEEE Trans. Pattern Anal. Mach. Intell., 38 (2016), pp. 308-321] によって拡張された,分離凸損失下でのイソトニックモデル適合のための一般化イソトニック再帰分割(GIRP)アルゴリズムの詳細な解析を行う。
GIRPアルゴリズムはアルゴリズムの各ステップにおいて、中間解が等調性制約を満たすような魅力的な特徴を示す。
論文は、文献に記述されているガープアルゴリズムが等張的モデルの作成に失敗していることを示す例から始まり、等張的回帰問題に対する解の存在と一意性について慎重に取り組まなければならないことを示唆する。
これは、おそらく多くの解のうち、観測されたデータの再帰的なバイナリ分割によって見つかる解が存在することを示すことから始まる。
GIRPアルゴリズムの小さな修正は正しい解を得るのに十分であり、すべての中間解が等方性であることの望ましい性質を保存する。
この修正は、中間解の適切な選択と、3次から2次への分割ステップの単純化を含む。
関連論文リスト
- ADMM-MM Algorithm for General Tensor Decomposition [7.0326155922512275]
提案アルゴリズムは3つの基本損失関数(ell$-loss, $ell$-loss, KL divergence)と様々な低ランクテンソル分解モデル(CP, Tucker, TT, TR)をサポートする。
提案したアルゴリズムにより広帯域のアプリケーションを解くことができ、プラグイン・アンド・プレイ方式で既存のテンソル分解モデルに容易に拡張できることを示す。
論文 参考訳(メタデータ) (2023-12-19T00:17:34Z) - On permutation symmetries in Bayesian neural network posteriors: a
variational perspective [8.310462710943971]
勾配降下の局所解には本質的に損失障壁がないことを示す。
これにより、ベイズニューラルネットワークにおける近似推論に関する疑問が提起される。
線形接続された解を探索するマッチングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-16T08:26:50Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Decentralized Inexact Proximal Gradient Method With Network-Independent
Stepsizes for Convex Composite Optimization [39.352542703876104]
本稿では,非方向および接続ネットワーク上での分散凸複合最適化について考察する。
CTA(Combine-Then-Adapt)に基づく新しい分散アルゴリズムは、非協調的なネットワーク非依存の定数ステップサイズの下で提案される。
論文 参考訳(メタデータ) (2023-02-07T03:50:38Z) - Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。
適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。
決定集合の低次元構造を高次元問題に活用する。
論文 参考訳(メタデータ) (2022-11-21T18:31:43Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。
我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。
これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文 参考訳(メタデータ) (2022-04-07T00:11:05Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳(メタデータ) (2021-06-09T08:05:36Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳(メタデータ) (2021-05-27T23:41:01Z) - Partition-based formulations for mixed-integer optimization of trained
ReLU neural networks [66.88252321870085]
本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。
1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
論文 参考訳(メタデータ) (2021-02-08T17:27:34Z) - Efficient Consensus Model based on Proximal Gradient Method applied to
Convolutional Sparse Problems [2.335152769484957]
我々は、勾配近似(PG)アプローチに基づく効率的なコンセンサスアルゴリズムの理論解析を導出し、詳述する。
提案アルゴリズムは、異常検出タスクに対する別の特別な畳み込み問題にも適用できる。
論文 参考訳(メタデータ) (2020-11-19T20:52:48Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳(メタデータ) (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。