論文の概要: Improved Bounds for Swap Multicalibration and Swap Omniprediction
- arxiv url: http://arxiv.org/abs/2505.20885v1
- Date: Tue, 27 May 2025 08:29:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-28 17:05:58.515483
- Title: Improved Bounds for Swap Multicalibration and Swap Omniprediction
- Title（参考訳）: Swap Multicalibration と Swap Omniprediction のための改善された境界
- Authors: Haipeng Luo, Spandan Senapati, Vatsal Sharan,
- Abstract要約: 我々は,有界線型関数に対する$O(sqrtT)$ $ell_2$-swap多重校正誤差を効率よく実現できることを示す。
また、凸関数とリプシッツ関数のクラスに対して、$varepsilon$-swap omnipredictorを効率的に学習する、$O(varepsilon -3)$サンプル複雑性も確立する。
- 参考スコア（独自算出の注目度）: 31.959887895880765
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we consider the related problems of multicalibration -- a multigroup fairness notion and omniprediction -- a simultaneous loss minimization paradigm, both in the distributional and online settings. The recent work of Garg et al. (2024) raised the open problem of whether it is possible to efficiently achieve $O(\sqrt{T})$ $\ell_{2}$-multicalibration error against bounded linear functions. In this paper, we answer this question in a strongly affirmative sense. We propose an efficient algorithm that achieves $O(T^{\frac{1}{3}})$ $\ell_{2}$-swap multicalibration error (both in high probability and expectation). On propagating this bound onward, we obtain significantly improved rates for $\ell_{1}$-swap multicalibration and swap omniprediction for a loss class of convex Lipschitz functions. In particular, we show that our algorithm achieves $O(T^{\frac{2}{3}})$ $\ell_{1}$-swap multicalibration and swap omniprediction errors, thereby improving upon the previous best-known bound of $O(T^{\frac{7}{8}})$. As a consequence of our improved online results, we further obtain several improved sample complexity rates in the distributional setting. In particular, we establish a $O(\varepsilon ^ {-3})$ sample complexity of efficiently learning an $\varepsilon$-swap omnipredictor for the class of convex and Lipschitz functions, $O(\varepsilon ^{-2.5})$ sample complexity of efficiently learning an $\varepsilon$-swap agnostic learner for the squared loss, and $O(\varepsilon ^ {-5}), O(\varepsilon ^ {-2.5})$ sample complexities of learning $\ell_{1}, \ell_{2}$-swap multicalibrated predictors against linear functions, all of which significantly improve on the previous best-known bounds.
- Abstract（参考訳）: 本稿では,マルチグループフェアネスの概念であるマルチキャリブレーションと,同時損失最小化パラダイムであるOmnipredictionの関連問題を,分散およびオンライン設定の両方において検討する。
Garg et al (2024) の最近の研究は、有界線型関数に対する$O(\sqrt{T})$$$\ell_{2}$-multicalibration誤差を効率的に達成できるかどうかというオープンな問題を提起した。
本稿では,この疑問に強く肯定的な意味で答える。
本稿では,O(T^{\frac{1}{3}})$$\ell_{2}$-swap多重校正誤差(高い確率と期待の両方で)を実現するアルゴリズムを提案する。
この境界を伝播すると、$\ell_{1}$-swapの多重校正と、凸リプシッツ函数の損失クラスに対する全予測のスワップが大幅に改善される。
特に、我々のアルゴリズムは、$O(T^{\frac{2}{3}})$$\ell_{1}$-swapマルチキャリブレーションを達成し、O(T^{\frac{7}{8}})$の既知バウンダリを改良することを示した。
改善されたオンライン結果の結果,さらに分散環境でのサンプルの複雑性率の改善が得られた。
特に、$O(\varepsilon ^ {-3}),$O(\varepsilon ^ {-3}),$O(\varepsilon ^ {-3}),$O(\varepsilon ^ {-2.5}),$O(\varepsilon ^{-2.5}),$O(\varepsilon ^ {-5}), O(\varepsilon ^ {-2.5}), $O(\varepsilon ^ {-2.5}), $O(\varepsilon ^ {-2.5}), $O(\varepsilon ^ {-5}), $O(\varepsilon ^ {-2.5}), $O(\varepsilon ^ {-2.5}), $\ell_{1}, \ell_{2}$-swap multicalibrated predictor for the class of convex and Lipschitz function, $O(\varepsilon ^{-2.5}), $O(\varepsilon )$ agnostic learner for the squared loss, $O(\varepsilon ^ {-5}), $O(\varepsilon ^ {-2.5}), $O(\varepsilon ^ {-2.5}), $O(\varepsilon ^ {-2.5}), $O(\varepsilon は、よりよく知られている。
関連論文リスト
- Robust learning of halfspaces under log-concave marginals [6.852292115526837]
線形しきい値関数を学習し、境界体積$O(r+varepsilon)$の分類子を半径摂動$r$で返すアルゴリズムを与える。
dtildeO(1/varepsilon2)$の時間とサンプルの複雑さはブール回帰の複雑さと一致する。
論文 参考訳（メタデータ） (2025-05-19T20:12:16Z) - Full Swap Regret and Discretized Calibration [18.944031222413294]
構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。
我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する
また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
論文 参考訳（メタデータ） (2025-02-13T13:49:52Z) - Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。
2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文 参考訳（メタデータ） (2024-10-31T13:51:59Z) - Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳（メタデータ） (2020-10-05T08:16:56Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。