論文の概要: Nonsmooth Projection-Free Optimization with Functional Constraints

• arxiv url: http://arxiv.org/abs/2311.11180v1
• Date: Sat, 18 Nov 2023 23:06:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-22 06:51:51.557499
• Title: Nonsmooth Projection-Free Optimization with Functional Constraints
• Title（参考訳）: 関数制約付き非スムース射影自由最適化
• Authors: Kamiar Asgari, Michael J. Neely
• Abstract要約: 本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
• 参考スコア（独自算出の注目度）: 14.413404128420352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents a subgradient-based algorithm for constrained nonsmooth convex optimization that does not require projections onto the feasible set. While the well-established Frank-Wolfe algorithm and its variants already avoid projections, they are primarily designed for smooth objective functions. In contrast, our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. It achieves an $\epsilon$-suboptimal solution in $\mathcal{O}(\epsilon^{-2})$ iterations, with each iteration requiring only a single (potentially inexact) Linear Minimization Oracle (LMO) call and a (possibly inexact) subgradient computation. This performance is consistent with existing lower bounds. Similar performance is observed when deterministic subgradients are replaced with stochastic subgradients. In the special case where there are no functional inequality constraints, our algorithm competes favorably with a recent nonsmooth projection-free method designed for constraint-free problems. Our approach utilizes a simple separation scheme in conjunction with a new Lagrange multiplier update rule.
• Abstract（参考訳）: 本稿では,制約付き非平滑凸最適化のための段階的アルゴリズムを提案する。 確立されたフランク・ウルフアルゴリズムとその変種は射影を既に避けているが、それらは主に滑らかな目的関数のために設計されている。 対照的に,提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 これは$\mathcal{o}(\epsilon^{-2})$イテレーションで$\epsilon$-サブオプティマイズソリューションを実現し、各イテレーションは1つの(潜在的に不正確な)リニア最小化オラクル(lmo)呼び出しと(おそらくは不適格な)サブグレードの計算しか必要としない。 この性能は既存の下限と一致している。 決定論的下位段階を確率的下位段階に置き換える際にも同様のパフォーマンスが観察される。 関数的不等式制約が存在しない特別の場合、このアルゴリズムは制約のない問題のために設計された最近の非滑らかな射影自由法と有利に競合する。 提案手法は,新しいラグランジュ乗算器更新規則と連動して,簡易な分離スキームを用いる。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)
• Block majorization-minimization with diminishing radius for constrained nonconvex optimization [9.907540661545328]
  BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。 凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T07:53:09Z)
• Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
  本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。 このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。 本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
  論文  参考訳（メタデータ） (2020-08-13T08:56:24Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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