論文の概要: Efficient, Anytime Algorithms for Calibration with Isotonic Regression
under Strictly Convex Losses
- arxiv url: http://arxiv.org/abs/2111.00468v1
- Date: Sun, 31 Oct 2021 11:17:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-02 14:26:39.383342
- Title: Efficient, Anytime Algorithms for Calibration with Isotonic Regression
under Strictly Convex Losses
- Title(参考訳): 厳密な凸損失下でのイソトニック回帰による校正アルゴリズム
- Authors: Kaan Gokcesu, Hakan Gokcesu
- Abstract要約: 最適単調変換が一意な階段関数の形をしていることを示す。
それらの最適モノトン変換もまた一意であり、最小損失を達成する単一の階段変換が存在する。
本稿では,特定の損失設定に対して最適な変換を求める線形時間空間アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the calibration of estimations to increase performance with an
optimal monotone transform on the estimator outputs. We start by studying the
traditional square error setting with its weighted variant and show that the
optimal monotone transform is in the form of a unique staircase function. We
further show that this staircase behavior is preserved for general strictly
convex loss functions. Their optimal monotone transforms are also unique, i.e.,
there exist a single staircase transform that achieves the minimum loss. We
propose a linear time and space algorithm that can find such optimal transforms
for specific loss settings. Our algorithm has an online implementation where
the optimal transform for the samples observed so far are found in linear space
and amortized time when the samples arrive in an ordered fashion. We also
extend our results to cases where the functions are not trivial to individually
optimize and propose an anytime algorithm, which has linear space and
pseudo-linearithmic time complexity.
- Abstract(参考訳): 推定器出力の最適単調変換を用いて推定値の校正を行い,性能向上を図る。
まず,従来の二乗誤差設定を重み付き変種を用いて検討し,最適な単音変換が一意な階段関数の形式であることを示す。
さらに, この階段の挙動は, 一般の厳密な凸損失関数に対して保存されることを示した。
それらの最適モノトン変換もまた一意であり、最小損失を達成する単一の階段変換が存在する。
本稿では,特定の損失設定に対して最適な変換を求める線形時間空間アルゴリズムを提案する。
提案アルゴリズムは, これまでに観測されたサンプルの最適変換を線形空間で検出し, サンプルが順に到着する時刻を補正するオンライン実装である。
また、関数が個別に最適化する自明でない場合にも結果を拡張し、線形空間と擬線形時間複雑性を持つ任意のアルゴリズムを提案する。
関連論文リスト
- Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳(メタデータ) (2023-10-26T19:56:52Z) - Fast Screening Rules for Optimal Design via Quadratic Lasso
Reformulation [0.135975510645475]
本研究は, 安全スクリーニングのルールを導出し, インテリジェンスサンプルを廃棄する。
新しいテストは、特に高次元のパラメータ空間に関わる問題に対して、より高速に計算できる。
本稿では,ラッソ法の正規化経路を計算するホモトピーアルゴリズムを,正方形 $ell_$-penalty に対して再パラメータ化する方法を示す。
論文 参考訳(メタデータ) (2023-10-13T08:10:46Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳(メタデータ) (2023-06-28T00:46:58Z) - Sequential Linearithmic Time Optimal Unimodal Fitting When Minimizing
Univariate Linear Losses [0.0]
スコア値と対象領域の最適マッピングは長方形関数であることを示す。
このアプローチは反復ごとに対数的時間的複雑さを持ち、最適に効率的です。
論文 参考訳(メタデータ) (2023-04-04T22:00:40Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳(メタデータ) (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。