論文の概要: Private optimization in the interpolation regime: faster rates and
hardness results
- arxiv url: http://arxiv.org/abs/2210.17070v1
- Date: Mon, 31 Oct 2022 05:18:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 16:34:47.663835
- Title: Private optimization in the interpolation regime: faster rates and
hardness results
- Title（参考訳）: 補間法におけるプライベート最適化:高速なレートとハードネス結果
- Authors: Hilal Asi, Karan Chadha, Gary Cheng, John Duchi
- Abstract要約: プライベートでない凸最適化では、勾配法は非補間法よりも、全てのサンプル損失を同時に最小化する解が存在するという問題にはるかに早く収束する。
プライベートサンプルの複雑さは指数関数的に改善した(近辺)。
- 参考スコア（独自算出の注目度）: 9.405458160620533
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In non-private stochastic convex optimization, stochastic gradient methods
converge much faster on interpolation problems -- problems where there exists a
solution that simultaneously minimizes all of the sample losses -- than on
non-interpolating ones; we show that generally similar improvements are
impossible in the private setting. However, when the functions exhibit
quadratic growth around the optimum, we show (near) exponential improvements in
the private sample complexity. In particular, we propose an adaptive algorithm
that improves the sample complexity to achieve expected error $\alpha$ from
$\frac{d}{\varepsilon \sqrt{\alpha}}$ to $\frac{1}{\alpha^\rho} +
\frac{d}{\varepsilon} \log\left(\frac{1}{\alpha}\right)$ for any fixed $\rho
>0$, while retaining the standard minimax-optimal sample complexity for
non-interpolation problems. We prove a lower bound that shows the
dimension-dependent term is tight. Furthermore, we provide a superefficiency
result which demonstrates the necessity of the polynomial term for adaptive
algorithms: any algorithm that has a polylogarithmic sample complexity for
interpolation problems cannot achieve the minimax-optimal rates for the family
of non-interpolation problems.
- Abstract（参考訳）: 非私的確率的凸最適化では、確率的勾配法は補間問題(全てのサンプル損失を同時に最小化する解が存在する場合)に、非補間問題よりもはるかに早く収束する。
しかし、関数が最適値の周りに二次成長を示すと、プライベートサンプルの複雑性が(ほぼ)指数関数的に向上する。
特に、任意の固定された $\rho >0$ に対して$\frac{d}{\varepsilon \sqrt{\alpha}}$ から$\frac{1}{\alpha^\rho} + \frac{d}{\varepsilon} \log\left(\frac{1}{\alpha}\right)$ への期待誤差を達成するためにサンプル複雑性を改善する適応アルゴリズムを提案する。
次元依存項がタイトであることを示す下界を証明できる。
さらに,適応アルゴリズムの多項式項の必要性を示す超効率な結果を与える。補間問題に対する多対数的なサンプル複雑性を持つアルゴリズムは,非補間問題の族に対する最小最適速度を達成できない。
関連論文リスト
- Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Accelerated Gradient Algorithms with Adaptive Subspace Search for
Instance-Faster Optimization [6.896308995955336]
グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。
本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
論文 参考訳（メタデータ） (2023-12-06T01:16:10Z) - Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳（メタデータ） (2023-10-26T19:56:52Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。
また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
論文 参考訳（メタデータ） (2022-02-15T16:02:32Z) - Distributed Stochastic Consensus Optimization with Momentum for
Nonconvex Nonsmooth Problems [45.88640334610308]
本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。
提案アルゴリズムは,過度な通信を実現することができることを示す。
提案アルゴリズムの有効性を示す実験を行った。
論文 参考訳（メタデータ） (2020-11-10T13:12:21Z) - SGD with shuffling: optimal rates without component convexity and large
epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。
我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。
我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文 参考訳（メタデータ） (2020-06-12T05:00:44Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。