論文の概要: Budget Constraints as Riemannian Manifolds

• arxiv url: http://arxiv.org/abs/2605.00649v1
• Date: Fri, 01 May 2026 13:30:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-04 17:43:28.96822
• Title: Budget Constraints as Riemannian Manifolds
• Title（参考訳）: リーマン多様体としての予算制約
• Authors: Michael Helcig, Dan Alistarh,
• Abstract要約: 機械学習における繰り返し発生する問題は、全コスト予算の下で各NグループにKオプションの1つを割り当てることである。 本稿では, 予算の厳格な実施の下で, 真の目的の1次最適化を可能にする新しい制約を提案する。 既知のオプティマによる合成クナプサック問題では、多様体ベースの制約処理が最適解を回復するのに対し、ペナルティ法は最適の83%である。
• 参考スコア（独自算出の注目度）: 39.54576236079211
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Assigning one of K options to each of N groups under a total cost budget is a recurring problem in machine learning, appearing in mixed-precision quantization, non-uniform pruning, and expert selection. The objective (model loss) depends jointly on all assignments and does not decompose across groups, which prevents combinatorial solvers from optimizing the true objective directly and limits them to proxy objectives. Evolutionary search evaluates the actual loss but lacks gradient information, while penalty-based methods provide gradients but enforce the budget only approximately and require sensitive hyperparameter tuning. We observe that under softmax relaxation, the budget constraint defines a smooth Riemannian manifold in logit space with particularly simple geometry: the normal vector is available in closed form, shifting logits along the cost vector changes expected cost monotonically, allowing binary-search retraction, and vector transport reduces to a single inner product. Building on this structure, we propose Riemannian Constrained Optimization (RCO), which augments a standard Adam update with tangent projection, binary-search retraction, and momentum transport. Combined with Gumbel straight-through estimation and budget-constrained dynamic programming for discrete feasibility, RCO enables first-order optimization of the true objective under exact budget enforcement, without introducing constraint hyperparameters. On synthetic knapsack problems with known optima, the manifold-based constraint handling recovers optimal solutions, whereas penalty methods plateau at 83% of optimal. On LLM compression tasks, including mixed-precision quantization and MoE expert pruning, RCO matches or exceeds evolutionary search methods while requiring 3x to 16x lower wall-clock cost on the evaluated configurations.
• Abstract（参考訳）: 総コスト予算の下で各NグループにKオプションの1つを割り当てることは、混合精度の量子化、非一様プルーニング、専門家の選択に現れる機械学習の繰り返しの問題である。 目的(モデル損失)は、すべての割り当てに共同で依存し、グループ間で分解しないため、組合せ的解法が真の目的を直接最適化し、それらをプロキシ目的に制限するのを防ぐ。 進化的探索は実際の損失を評価するが、勾配情報を欠く。 我々は、ソフトマックス緩和の下で、予算制約はロジット空間における滑らかなリーマン多様体を特に単純な幾何学で定義する:正規ベクトルは閉形式で利用可能であり、コストベクトルの変化に伴うロジットを単調にシフトし、二項探索の取り消しを可能にし、ベクトル輸送は単一の内部積に還元される。 この構造の上に構築されたRiemannian Constrained Optimization (RCO) は、標準的なAdam更新をタンジェントプロジェクション、バイナリ検索リトラクション、モーメントトランスポートで強化する。 離散実現性のためのGumbelストレートスルー推定と予算制約付き動的プログラミングを組み合わせることで、RCOは制約ハイパーパラメータを導入することなく、厳密な予算執行の下で真の目標の1次最適化を可能にする。 既知のオプティマによる合成クナプサック問題では、多様体ベースの制約処理が最適解を回復するのに対し、ペナルティ法は最適の83%である。 混合精度量子化とMoEエキスパートプルーニングを含むLLM圧縮タスクでは、RCOは、評価された構成に対して3倍から16倍の低コストで、進化的探索手法に適合または超過する。

関連論文リスト

• Cost-Aware Learning [72.31444819326795]
  本稿では,異なるコンポーネント関数をサンプリングするコスト認識学習の問題点について考察する。 凸関数に対するコスト・アウェア・Descentアルゴリズムを提案し、そのコスト複雑性を導出し誤差を$$$とする。 本稿では,性能を保ちつつポリシー最適化のコストを削減するアルゴリズムであるCost-Aware GRPOを紹介する。
  論文  参考訳（メタデータ） (2026-04-30T15:39:09Z)
• DRAFTO: Decoupled Reduced-space and Adaptive Feasibility-repair Trajectory Optimization for Robotic Manipulators [4.0407133618465005]
  本稿では、トラジェクトリ最適化のための新しいアルゴリズム、Decoupled Reduced-spaceとAdaptive Feasibility-Repair Trajectory Optimization (DRAFTO)を提案する。 連立限界実現性を扱いながら繰り返し制約された最適化の回数を減らすため、最適化を低空間ガウスニュートン(Gass-Newton, GN)降下に分離する。 CHOMP, TrajOpt, GPMP2, FACTOなどの最適化型プランナに対するベンチマークテストの結果, 様々なシナリオやタスクにおいて高い効率性と信頼性が検証された。
  論文  参考訳（メタデータ） (2026-03-10T20:24:42Z)
• First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints [9.141425189503794]
  フェデレート学習に適した1次ソフトマックス重み付きスイッチング勾配法を提案する。 完全なクライアント参加の下で、我々のアルゴリズムは標準的な $mathcalO(-4)$ Oracle complexity を達成する。 我々は、統一されたエラー分解を提供し、シャープな$mathcalO(logfrac1)$高確率収束保証を確立する。
  論文  参考訳（メタデータ） (2026-03-06T00:14:46Z)
• Residual subspace evolution strategies for nonlinear inverse problems [1.14219428942199]
  逆の問題は工学や科学に及ぼし、騒々しく、微分不可能で、高価な残効評価は、ヤコビアンベースの解法を日常的に破る。 本稿では、ガウスプローブを現在の勾配付近に描画する微分自由解法である残留部分空間進化戦略(RSES)を導入し、それらの方向に沿って残差がどのように変化するかを記録し、最小二乗法でプローブを再結合して最適な更新を生成する。
  論文  参考訳（メタデータ） (2025-12-11T06:20:13Z)
• Two-Timescale Optimization Framework for Sparse-Feedback Linear-Quadratic Optimal Control [3.746304628644379]
  The $mathcalHfeedback$-guaranteed sparse-feedback linear-quadratic (LQ) optimal control with convex parameterization and convex-bounded uncertainty。
  論文  参考訳（メタデータ） (2024-06-17T03:17:33Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。 本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。 この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
  論文  参考訳（メタデータ） (2022-09-16T09:38:38Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)

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

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