論文の概要: Convex Optimization Is Free When Accuracy Is Expensive
- arxiv url: http://arxiv.org/abs/2609.35418v1
- Date: Mon, 28 Sep 2026 15:30:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-02 05:40:48.481866
- Title: Convex Optimization Is Free When Accuracy Is Expensive
- Title（参考訳）: コンベックスの最適化は、精度が大きければ無料
- Abstract要約: 我々は、勾配を正確に評価できないときに凸最適化を研究するが、精度$$$で$-$のように計算が成長するアルゴリズムの階層によってのみ近似される。
損失関数の最小化に要するコストは,問題要求の精度での勾配の1つの評価よりも,$のみに依存する。
- 参考スコア（独自算出の注目度）: 18.56538898519597
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like $δ^{-γ}$ in the accuracy $δ$. When $γ>2$, falling into the Harder-Than-Monte-Carlo (HTMC) regime, the price of accuracy outruns the variance reduction that Monte Carlo would buy and we show that minimizing a loss function costs no more, up to a factor depending only on $γ$, than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy $δ$ by an unbiased estimator of it, whose variance $σ^2$ becomes a second, independently priced dial: the cost of one call drops from $δ^{-γ}$ to $δ^{2-γ}σ^{-2}$. Plain inexact gradient descent driven by that oracle reaches loss $\varepsilon$ at expected compute $Θ(\varepsilon^{-γ})$ in the convex case, against $Θ(\varepsilon^{-(γ+1)})$ for the same method run at a fixed accuracy: randomization buys a full power of $\varepsilon$. Under $μ$-strong convexity the exponent halves, to $\varepsilon^{-γ/2}$, because the iterates settle at a noise floor and the bias budget relaxes accordingly. Both bounds are independent of the step size, and hence of the smoothness constant, and we show that the cost is a functional of the underlying gradient flow rather than of any discretization of it.
- Abstract（参考訳）: 本稿では、勾配を正確に評価できない場合の凸最適化について検討するが、精度$δ$の計算で$δ^{-γ}$のように成長するアルゴリズムの階層によってのみ近似する。
ハルダー・タン・モンテ・カルロ(HTMC)体制に該当する$γ>2$の場合には,モンテカルロが購入する分散化よりも精度が優れており,損失関数の最小化に要するコストは,問題要求の精度での勾配の単一評価よりも,最大で1ドル程度に抑えられる。
ランダム化された多重レベルオラクルは、精度の決定論的近似に$δ$を非バイアス推定器で置き換え、その分散$σ^2$は第2の独立価格ダイヤルとなる: 1つの呼び出しのコストは$δ^{-γ}$から$δ^{2-γ}σ^{-2}$に低下する。
そのオラクルによって引き起こされる通常の不正確な勾配降下は、期待された計算で$\varepsilon$(\varepsilon^{-γ})$(\varepsilon^{-(γ+1)})$(\varepsilon$)$(\varepsilon^{-(γ+1)})$(\varepsilon$)$(\varepsilon$)$(\varepsilon$)$(\varepsilon$)$(\varepsilon$)$)$(\varepsilon$)$(\vare psilon$)$(\varepsilon$)$(\varepsilon$)$(\varepsilon$)$)$(\varepsilon$)$(\varepsilon$)$(\varepsilon$) $(\varepsilon$)$)$(\varepsilon$)$)$(\varepsilon$)$(\varepsilon$)$(\varepsilon$).
μ$-strong convexityの下では、指数半減期は$\varepsilon^{-γ/2}$となる。
どちらの境界もステップサイズとは独立であり、従って滑らかさ定数は独立であり、そのコストは、その離散化よりも基礎となる勾配流の関数であることが示される。
関連論文リスト
- Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise [7.692336118507715]
我々は,Blum-Gladyshev(mathsfBG$-0)ノイズモデルの下での非線形最適化について検討した。
モーメント付き正規化勾配降下は、勾配毎のパラメータを1つだけ使い、複雑さが$O(varepsilon-6)$で$mathsfBG$-0ノイズの下に収束することを示す。
論文 参考訳（メタデータ） (2026-05-14T18:27:49Z) - Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization [0.0]
後悔の定量化はアルゴリズムによる意思決定の不確実性のコストである。
本稿では,任意の最適化問題における期待された後悔が,正確な分解を許容することを示す。
論文 参考訳（メタデータ） (2026-05-13T18:32:44Z) - Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization [0.6015898117103067]
我々は,条件付き予測を共同で推定し,外的目的を最適化する同時学習最適化アルゴリズムを解析する。
我々は,この手法が次数$mathcalObig (1/sqrtNbig)$の収束率を達成することを証明した。
論文 参考訳（メタデータ） (2026-03-13T14:53:35Z) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。
ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。
PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
論文 参考訳（メタデータ） (2022-11-29T18:43:22Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳（メタデータ） (2022-11-29T18:38:40Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。