論文の概要: Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization
- arxiv url: http://arxiv.org/abs/2607.20769v1
- Date: Wed, 22 Jul 2026 22:36:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-24 18:26:25.229374
- Title: Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization
- Title（参考訳）: 半減算パラメトリック最適化におけるメモリ計算トレードオフ
- Authors: Shijie Pan, Agustin Castellano, Zeyu Shen, Enrique Mallada,
- Abstract要約: 学習可能な意思決定システムは、オンライン計算コストを削減するためにオフラインデータや計算を使用することが多い。
固定されたオンライン計算予算の下で、所望の精度を達成するためにオフライン情報がどれだけ必要かを検討する。
- 参考スコア（独自算出の注目度）: 3.470927020824476
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning-enabled decision systems often use offline data or computation to reduce online compute cost. Despite the empirical success of such approaches, there is limited general understanding of how much offline information is needed to achieve a desired accuracy under a fixed online computation budget. We study this question through the lens of amortized parametric optimization: an offline phase stores a finite memory of solved problem instances, and an online phase produces a solution to a new instance by retrieving a warm start and applying $K$ steps of projected gradient descent. We analyze this setup for smooth convex parametric optimization over a compact domain, using a nonparametric predictor built from the stored offline solutions. For $μ$-strongly convex objectives, we establish matching upper and lower bounds on the memory required to guarantee $\varepsilon$-accuracy under a fixed online iteration budget $K$. For convex objectives satisfying a $β$-growth condition ($β>2$), we obtain near-matching bounds and identify a phase transition in $K$ beyond which additional memory provides no benefit. We further provide a general proof framework that (i) explicitly quantifies the memory cost of acceleration---how much offline memory is required to achieve a prescribed speedup over the unaided online optimizer---and (ii) identifies two key quantities driving this cost: the convergence rate of the online optimizer and the Lipschitz sensitivity of the solution map to the problem parameter. Experiments on parameterized ridge regression confirm the predicted memory--computation--accuracy tradeoffs.
- Abstract（参考訳）: 学習可能な意思決定システムは、オンライン計算コストを削減するためにオフラインデータや計算を使用することが多い。
このような手法の実証的な成功にもかかわらず、固定されたオンライン計算予算の下では、望ましい精度を達成するためにオフライン情報がどれだけ必要かという一般的な理解は限られている。
オフラインフェーズは、解決された問題インスタンスの有限メモリを格納し、オンラインフェーズは、ウォームスタートを取得して、投影された勾配降下のK$ステップを適用して、新しいインスタンスの解を生成する。
保存されたオフラインソリューションから構築された非パラメトリック予測器を用いて、コンパクトな領域上での凸パラメトリック最適化のためのこの設定を解析する。
$μ$-strongly convexの目的に対して、固定されたオンラインイテレーション予算$K$の下で、$\varepsilon$-accuracyを保証するために必要なメモリ上の上限と下位境界を一致させる。
凸目標が$β$-growth条件(β>2$)を満たす場合、ニアマッチング境界を取得し、追加メモリが役に立たない$K$以上の相転移を識別する。
さらに、一般的な証明フレームワークを提供します。
(i) アクセラレーションのメモリコストを明示的に定量化し、オンラインオプティマイザに対する所定のスピードアップを達成するためにオフラインメモリがどれだけ必要か。
(2) オンラインオプティマイザの収束率と問題パラメータに対する解写像のリプシッツ感度の2つの重要な量を特定する。
パラメータ化されたリッジ回帰の実験は、予測されたメモリ-計算-精度トレードオフを確認する。
関連論文リスト
- Online Learning with Gradient-Variation Interval Regret [54.59204826681113]
そこで本研究では,勾配変動を伴う時間間隔のリフレッシュなスケーリングを実現するオンライン学習アルゴリズムを提案する。
提案手法では, よりシンプルで効率的な2層オンラインアンサンブル構造を用いて, 高い理論的保証を実現する。
論文 参考訳（メタデータ） (2026-06-02T16:16:45Z) - Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts [19.540758462427878]
最適性と最悪の保証を維持しつつ、正確な代入解決を高速化する学習強化フレームワークを提案する。
グラフベースのモデルのメモリボトルネックを$mathcalO(N2)$で回避する軽量な行独立アーキテクチャであるRowDualNetを紹介します。
論文 参考訳（メタデータ） (2026-05-10T07:15:49Z) - Mild Over-Parameterization Benefits Asymmetric Tensor PCA [12.923414933046574]
非対称PCA(ATPCA)は、サンプル複雑性、計算、メモリ間のトレードオフを研究するための原型モデルである。
私たちは$overlinek geq 4$が偶数であるような設定にフォーカスし、限られたメモリ予算の下で降下アルゴリズムを検討する。
論文 参考訳（メタデータ） (2026-04-11T13:34:48Z) - Learning Algorithm Hyperparameters for Fast Parametric Convex Optimization [2.0403774954994858]
本稿では,一階法のハイパーパラメータ列を学習するための機械学習フレームワークを提案する。
いくつかのアルゴリズムのハイパーパラメータの学習方法を示す。
本稿では,制御,信号処理,機械学習など,多くの例を用いて本手法の有効性を示す。
論文 参考訳（メタデータ） (2024-11-24T04:58:36Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Sketchy: Memory-efficient Adaptive Regularization with Frequent
Directions [22.09320263962004]
ディープラーニング(DL)学習タスクにおけるKronecker-factored gradient covariance matrixのスペクトルは、小さなリード固有空間に集中している。
本稿では,行列プレコンディショナを維持するためのメモリと計算要求を低減させる汎用的手法について述べる。
ShampooやAdamと競合する手法で、第2の瞬間を追跡するにはサブ線形メモリしか必要ありません。
論文 参考訳（メタデータ） (2023-02-07T21:50:06Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳（メタデータ） (2022-12-12T18:58:59Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳（メタデータ） (2020-10-22T22:54:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。