論文の概要: Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes

• arxiv url: http://arxiv.org/abs/2601.20076v1
• Date: Tue, 27 Jan 2026 21:40:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.674376
• Title: Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes
• Title（参考訳）: 適応ステップサイズを考慮した制約付き最適化のためのランダム化フェーザビリティ手法
• Authors: Abhishek Chakraborty, Angelia Nedić,
• Abstract要約: 凸関数の低レベル集合の交叉によって定義される制約を対象関数として最小化することを検討する。 我々は、Polyakのステップと、反復毎にランダムな数のサンプル制約を持つランダム化ファジビリティーアルゴリズムを使用する。 サンプルサイズの成長の特定の選択に対して、最適な速度が達成される。
• 参考スコア（独自算出の注目度）: 0.6363756171493382
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider minimizing an objective function subject to constraints defined by the intersection of lower-level sets of convex functions. We study two cases: (i) strongly convex and Lipschitz-smooth objective function and (ii) convex but possibly nonsmooth objective function. To deal with the constraints that are not easy to project on, we use a randomized feasibility algorithm with Polyak steps and a random number of sampled constraints per iteration, while taking (sub)gradient steps to minimize the objective function. For case (i), we prove linear convergence in expectation of the objective function values to any prescribed tolerance using an adaptive stepsize. For case (ii), we develop a fully problem parameter-free and adaptive stepsize scheme that yields an $O(1/\sqrt{T})$ worst-case rate in expectation. The infeasibility of the iterates decreases geometrically with the number of feasibility updates almost surely, while for the averaged iterates, we establish an expected lower bound on the function values relative to the optimal value that depends on the distribution for the random number of sampled constraints. For certain choices of sample-size growth, optimal rates are achieved. Finally, simulations on a Quadratically Constrained Quadratic Programming (QCQP) problem and Support Vector Machines (SVM) demonstrate the computational efficiency of our algorithm compared to other state-of-the-art methods.
• Abstract（参考訳）: 凸関数の低レベル集合の交叉によって定義される制約を対象関数として最小化することを検討する。 私たちは2つのケースを研究します。 (i)強い凸とリプシッツ・滑らかな目的関数 (ii)凸だが、おそらく非滑らかな目的関数。 投影しにくい制約に対処するため、目的関数を最小化するために(サブ)段階的なステップを採りながら、Polyakのステップと反復毎にランダムにサンプルされた制約を列挙したランダム化ファシビリティアルゴリズムを用いる。 例 i) 適応ステップサイズを用いて, 目的関数の値が所定の許容範囲に収まることを期待して線形収束を証明した。 例 (II) パラメータフリーで適応的なステップ化スキームを開発し, 期待値が$O(1/\sqrt{T})=最悪のケースレートとなる。 繰り返しの実施可能性はほぼ確実に更新可能な回数に比例して幾何的に減少するが、平均的な反復に対しては、ランダムな制約数の分布に依存する最適値に対する関数値の期待下限を確立する。 サンプルサイズの成長の特定の選択に対して、最適な速度が達成される。 最後に、擬似制約付き二次計画法(QCQP)問題とサポートベクトルマシン(SVM)に関するシミュレーションにより、他の最先端手法と比較してアルゴリズムの計算効率を実証する。

関連論文リスト

• A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization [18.38962516619021]
  厳密なペナルティモデルを構築するための新しい手法を提案する。 対象関数と関数の次数と各制約関数値を用いる。 その結果,本手法は2人制約問題よりもはるかに高速であることが判明した。
  論文  参考訳（メタデータ） (2025-01-31T15:18:52Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。 本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。 我々は,新しい数値スケール問題の有効性を実証する。
  論文  参考訳（メタデータ） (2020-10-23T05:24:05Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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