論文の概要: Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems

• arxiv url: http://arxiv.org/abs/2609.17629v1
• Date: Tue, 15 Sep 2026 09:16:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.461775
• Title: Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems
• Title（参考訳）: Fenchel-Young Duality Gaps:正規化逆問題に対する早期停止認定
• Abstract要約: 正規化逆問題に対して計算可能誤差境界と証明済み早期停止について検討する。 この分析は、$F()+R()$の合計ギャップをデータ学習用語に分割する、正確な双対対ギャップの同一性に依存する。 GBLの正確なサポートリカバリを確立するために、これらのエラー境界の上にコンパニオンペーパーが構築されている。
• 参考スコア（独自算出の注目度）: 4.3686879183724665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study computable error bounds and certified early stopping for regularized inverse problems, where a data-fidelity term is traded against a regularizer. The analysis relies on an exact duality-gap identity that splits the total gap of $F(Φμ)+λR(μ)$ into a data-fidelity Fenchel--Young loss and a regularizer Fenchel--Young loss, $ Δ(μ,h)=L_F(Φμ\parallel h)+λL_R(μ\parallelη),\qquad η=-Φ^\star h/λ, $ valid for any primal point $μ$ and any dual point $h$. The data-fidelity term $F$ is strictly convex, so wherever $F^\star$ is differentiable the loss $L_F(Φμ\parallel h)$ is the Bregman divergence of~$F$ between the prediction $Φμ$ and $\nabla F^\star(h)$, and it vanishes exactly at \emph{Mirror Alignment} $h=\nabla F(Φμ)$. Evaluated at a dual-feasible point $\tilde h$, the gap~$Δ(μ,\tilde h)$ is computable and \emph{oracle-free}, meaning that it uses no knowledge of the solution, and it bounds the suboptimality of $μ$. Under the source condition, the same Fenchel--Young losses give \emph{a priori} bounds on the estimation and prediction errors. Their scale is the irreducible model and noise error $L_F(Φμ^\star\parallel h^\star)$, which vanishes exactly when Mirror Alignment holds at the certificate. This gives an early-stopping rule: run the algorithm until the regularizer Fenchel--Young loss falls below a tolerance $ε$. A constructive version of the Brøndsted--Rockafellar theorem then turns the current pair into an exact \emph{dual-feasible} one, and this proxy lifts to an exact primal certificate. We build the proxy by a proximal step in the geometry of the fidelity, with Bregman kernel $F^\star$ and tilted by the prediction $Φμ$: it recovers the Euclidean step of Carlier when $F$ is the squared error, and it reduces the duality gap by the regularizer Fenchel--Young loss, up to a second-order remainder that vanishes in the quadratic case. Our running example is the Generalized Beurling--Lasso (GBL), where $R$ is the total-variation norm on signed measures. It contains the classical Beurling--Lasso, obtained with the squared error, and also covers robust, logistic, entropic and inverse-optimal-transport losses. The same duality gap certifies deep-learning optimizers such as Lion-K and Muon, in their proximal form, as solvers of the regularized program. A companion paper by the same authors builds on these error bounds to establish exact support recovery for the GBL under a non-degenerate source condition.
• Abstract（参考訳）: 本稿では,正則化逆問題に対して計算可能誤差境界と早期停止の証明を行い,正則化問題に対してデータ忠実度項を交換する。 この分析は、合計ギャップをデータフィデリティFenchel-Young損失と正規化Fenchel-Young損失、$ Δ(μ,h)=L_F(\μ\parallel h)+λL_R(μ\parallelη),\qquad η=-\^\star h/λ、任意の原始点$μ$と任意の双対点$h$に分割する、正確な双対対対ギャップの同一性に依存する。 データ忠実度項 $F$ は厳密な凸であり、$F^\star$ が可微分可能であれば、$L_F(シュμ\parallel h)$ は、予測 $\μ$ と $\nabla F^\star(h)$ の間の 〜$F$ のブレグマン発散であり、ちょうど \emph{Mirror Alignment} $h=\nabla F(シュμ)$ で消える。 双対実現可能な点 $\tilde h$ で評価すると、ギャップ~$Δ(μ,\tilde h)$ は計算可能で \emph{oracle-free} であり、解の知識を使わず、$μ$ の準最適性に縛られる。 ソース条件の下では、同じフェンシェル・ヨンの損失は、推定と予測誤差に "emph{a priori}" 境界を与える。 彼らのスケールは既約モデルであり、ノイズエラーは$L_F(\μ^\star\parallel h^\star)$であり、ミラーアライメントが証明書を保持したときに正確に消滅する。 正規化器 Fenchel-Young の損失が ε$ 以下になるまでアルゴリズムを実行する Brøndsted--Rockafellar の定理の構成版は、現在のペアを正確な 'emph{dual-feasible} に変換する。 我々は、F$が二乗誤差であるときにカルリエのユークリッドステップを復元し、正則化Fenchel-Young損失による双対性ギャップを2階残差まで減少させる。 我々のランニング例はGeneralized Beurling--Lasso (GBL) であり、ここでは$R$は符号付き測度における全変量ノルムである。 古典的なBourling--Lassoは二乗誤差で得られ、ロバスト、ロジスティック、エントロピー、および逆最適化-輸送損失もカバーしている。 同じ双対性ギャップは、正規化プログラムの解法として、Lion-KやMuonのようなディープラーニングオプティマイザをその近位形で証明する。 同じ著者による共用論文は、非退化ソース条件下でのGBLの正確なサポートリカバリを確立するために、これらのエラー境界の上に構築されている。

関連論文リスト

• How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL [8.929322780616545]
  更新写像の間の非有界なギャップは、定常対称ガウス HMM において、固定有限$Kge2$ に対して消滅する予測的 KL と共存することができる。 この構成は$K$で固定されており、圧縮が無害である場合や内部のギャップがタスク損失を発生させる必要がある場合の普遍的な基準を提供していない。
  論文  参考訳（メタデータ） (2026-09-10T06:22:53Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• One Inverse Step is a Convex Program: Bayes-Limit Calibration of Diffusion Inversion [0.0]
  1つの暗黙のDDIM反転ステップは、事前訓練された拡散モデルが局所多様体幾何学を符号化するかどうかの最も安価なプローブである。 フェルミ窓はモデルのトレーニングサポートと3.6$-$5.6times$で対立し、ヘッセン=リプシッツ定数は法が読み取る曲率の2-$12%である。 最後の条件付き天井 $_t_max(mathrmsym,J)le1$, from $mathrmCov(x_0mid x_t)succeq0$
  論文  参考訳（メタデータ） (2026-08-24T11:01:54Z)
• Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
  重畳の非線形観測回数が限られていることから, スパースベクトルの回復を考察する。 本稿では, 一般化畳み込みペナルティとハマー化データ忠実度を組み合わせた正規化に基づくフレームワークを提案する。 仮に局所的な定常点を保った位数$sqrtslog(n)/m$の誤差境界を導出する。
  論文  参考訳（メタデータ） (2026-07-12T07:29:39Z)
• When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
  良性オーバーフィッティングが線形レートで失敗することを示します。 この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
  論文  参考訳（メタデータ） (2026-05-07T14:14:09Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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