論文の概要: An efficient nonconvex reformulation of stagewise convex optimization problems

• arxiv url: http://arxiv.org/abs/2010.14322v1
• Date: Tue, 27 Oct 2020 14:30:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 10:56:12.571755
• Title: An efficient nonconvex reformulation of stagewise convex optimization problems
• Title（参考訳）: 段階的凸最適化問題の効率的非凸再構成法
• Authors: Rudy Bunel, Oliver Hinder, Srinadh Bhojanapalli, Krishnamurthy (Dj) Dvijotham
• Abstract要約: 我々は、段階的構造問題を活用するために設計された非改革を開発する。 ニューラルネットワーク検証のアプローチでは、わずか数ステップで急激な局所的なギャップが得られます。 棚から取り出した問題や特殊な解法よりも早く解決できる。
• 参考スコア（独自算出の注目度）: 21.61123565780424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-shelf solvers can solve these problems but may scale poorly. We develop a nonconvex reformulation designed to exploit this staged structure. Our reformulation has only simple bound constraints, enabling solution via projected gradient methods and their accelerated variants. The method automatically generates a sequence of primal and dual feasible solutions to the original convex problem, making optimality certification easy. We establish theoretical properties of the nonconvex formulation, showing that it is (almost) free of spurious local minima and has the same global optimum as the convex problem. We modify PGD to avoid spurious local minimizers so it always converges to the global minimizer. For neural network verification, our approach obtains small duality gaps in only a few gradient steps. Consequently, it can quickly solve large-scale verification problems faster than both off-the-shelf and specialized solvers.
• Abstract（参考訳）: ステージ構造を持つ凸最適化問題は、最適制御、ディープニューラルネットワークの検証、等張回帰など、いくつかの文脈で現れる。 オフ・ザ・シェルフ・ソルバはこれらの問題を解決することができるが、スケールが悪くなる可能性がある。 我々は、このステージ構造を利用するために設計された非凸改質を開発する。 我々の再構成は単純な境界制約しか持たず、射影勾配法およびそれらの加速変量による解が可能である。 本手法は,元凸問題に対する一次および二重実現可能な解列を自動的に生成し,最適性証明を容易にする。 非凸定式化の理論的性質を確立し、(ほとんど)急激な局所ミニマを伴わず、凸問題と同じ大域的最適性を持つことを示す。 pgdは局所的最小化を回避するため、常に大域的最小化に収束するように修正する。 ニューラルネットワークの検証には,ほんの数段階の勾配ステップで小さな双対性ギャップを求める。 これにより、オフザシェルフおよび特殊解法よりも高速に大規模な検証問題を解くことができる。

関連論文リスト

• Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization [55.115992622028685]
  以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。 最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
  論文  参考訳（メタデータ） (2023-10-26T19:56:52Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems [7.5573375809946395]
  定常的非平滑項の両方にフォーカスできるNCSCミニマックス問題を解くための最初の試みを行う。 提案アルゴリズムは,ミニマックス問題の新たな再構成に基づいて設計されている。
  論文  参考訳（メタデータ） (2023-04-05T13:54:43Z)
• Smooth over-parameterized solvers for non-smooth structured optimization [3.756550107432323]
  非滑らか性 (non-smoothness) は、空間性、群空間性、低ランクエッジ、鋭いエッジなどの解の構造的制約を符号化する。 我々は、基礎となる非滑らかな最適化問題の非重み付きだが滑らかな過度パラメータ化を運用する。 我々の主な貢献は変数の一部を明示的に最小化することで新しい定式化を定義する変数射影(VarPro)を適用することです。
  論文  参考訳（メタデータ） (2022-05-03T09:23:07Z)
• Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions [41.337814204665364]
  ReLUアクティベーション機能を持つ2層ニューラルネットワークの凸最適化アルゴリズムを開発した。 凸ゲート型ReLUモデルでは,ReLUトレーニング問題に対するデータ依存の近似バウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2022-02-02T23:50:53Z)
• A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [21.67411847762289]
  双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。 本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。 我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAが$O(frac1T)$収束率を持つことを示す。
  論文  参考訳（メタデータ） (2022-01-31T18:17:25Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• 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)
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions [51.60996023961886]
  コーン制約のある凸最適化プログラムを解くことにより,グローバルな2層ReLUニューラルネットワークの探索が可能であることを示す。 我々の分析は新しく、全ての最適解を特徴づけ、最近、ニューラルネットワークのトレーニングを凸空間に持ち上げるために使われた双対性に基づく分析を活用できない。
  論文  参考訳（メタデータ） (2020-06-10T15:38:30Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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