論文の概要: On Rate-Optimal Partitioning Classification from Observable and from Privatised Data

• arxiv url: http://arxiv.org/abs/2312.14889v3
• Date: Fri, 05 Sep 2025 20:05:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-09 14:07:02.598471
• Title: On Rate-Optimal Partitioning Classification from Observable and from Privatised Data
• Title（参考訳）: 観測可能データとプリバタイズデータからのレート最適分割分類について
• Authors: Balázs Csanád Csáji, László Györfi, Ambrus Tamás, Harro Walk,
• Abstract要約: 分割分類の古典的手法を再検討し, 緩和条件下での収束率について検討する。 我々は、$d$次元ユークリッド空間における分類の問題を考える。
• 参考スコア（独自算出の注目度）: 4.2931743492904095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we revisit the classical method of partitioning classification and study its convergence rate under relaxed conditions, both for observable (non-privatised) and for privatised data. We consider the problem of classification in a $d$ dimensional Euclidean space. Previous results on the partitioning classifier worked with the strong density assumption, which is restrictive, as we demonstrate through simple examples. Here, we study the problem under much milder assumptions. We presuppose that the distribution of the inputs is a mixture of an absolutely continuous and a discrete distribution, such that the absolutely continuous component is concentrated to a $d_a$ dimensional subspace. In addition to the standard Lipschitz and margin conditions, a novel characteristic of the absolutely continuous component is introduced, by which the exact convergence rate of the classification error probability is computed, both for the binary and for the multi-label cases. Interestingly, this rate of convergence depends only on the intrinsic dimension of the inputs, $d_a$. The privacy constraints mean that the independent identically distributed data cannot be directly observed, and the classifiers are functions of the randomised outcome of a suitable local differential privacy mechanism. In this paper we add Laplace distributed noises to the discontinuations of all possible locations of the feature vector and to its label. Again, tight upper bounds on the rate of convergence of the classification error probability are derived, without the strong density assumption, such that this rate depends on $2d_a$.
• Abstract（参考訳）: 本稿では,従来の分割分類法を再検討し,その収束率について,可観測(非民営化)と民営化(民営化)の両面から検討する。 我々は、$d$次元ユークリッド空間における分類の問題を考える。 分割分類器の以前の結果は、単純な例で示すように、強い密度の仮定で機能した。 ここでは、この問題をはるかに軽微な仮定で研究する。 入力の分布は絶対連続分布と離散分布の混合であり、絶対連続成分が$d_a$次元部分空間に集中することを仮定する。 標準リプシッツ条件とマージン条件に加えて、絶対連続成分の新たな特性を導入し、二進数と多ラベルの場合の両方において、分類誤差確率の正確な収束率を算出する。 興味深いことに、この収束速度は入力の内在次元、$d_a$にのみ依存する。 プライバシー制約は、独立に分散したデータを直接観察できないことを意味し、分類器は、適切な局所的な差分プライバシー機構のランダムな結果の関数である。 本稿では,特徴ベクトルの可能なすべての位置とラベルの停止にLaplace分散ノイズを付加する。 また、分類誤差確率の収束率に関する強い上限は、強い密度の仮定なしに導出され、この値は2d_a$に依存する。

関連論文リスト

• Mean-square and linear convergence of a stochastic proximal point algorithm in metric spaces of nonpositive curvature [0.0]
  単調ベクトル場の平均の零点を近似する非線形(分離可能な)アダマール空間の一般設定において、近点アルゴリズムの変種を定義する。 摂動空間上の確率的独立仮定と分離性仮定とともに、その収束性を適切な強い単調性仮定の下で証明する。
  論文  参考訳（メタデータ） (2025-10-12T16:54:04Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• A Connection Between Learning to Reject and Bhattacharyya Divergences [57.942664964198286]
  インプットとラベルの両面で共同理想分布を学習することを検討する。 我々は、拒絶と統計的相違の閾値付けを関連づける。 一般に、バタチャリアの発散による拒絶は、Chowのルールよりも攻撃的でないことが分かる。
  論文  参考訳（メタデータ） (2025-05-08T14:18:42Z)
• Benign Overfitting and the Geometry of the Ridge Regression Solution in Binary Classification [75.01389991485098]
  リッジ回帰はクラスタ平均ベクトルのスケールによって定性的に異なる挙動を示す。 スケールが非常に大きいレジームでは、良心過剰を許容する条件は回帰タスクと同一であることが判明した。
  論文  参考訳（メタデータ） (2025-03-11T01:45:42Z)
• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  本稿では、多様体制約データ分布のクラスにおける段階的領域適応の課題に対処する。 本稿では,適応的なワッサースタイン半径を持つ分布ロバスト最適化(DRO)を基礎とした手法を提案する。 我々のバウンダリは、新たに導入されたそれとの互換性尺度に依存しており、シーケンスに沿ったエラー伝搬のダイナミクスを完全に特徴付けています。
  論文  参考訳（メタデータ） (2024-10-17T22:07:25Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
  異種データを用いた因果推論のための協調的逆確率スコア推定器を提案する。 異質性の増加に伴うメタアナリシスに基づく手法に対して,本手法は有意な改善を示した。
  論文  参考訳（メタデータ） (2024-04-24T09:04:36Z)
• Gaussian-Smoothed Sliced Probability Divergences [15.123608776470077]
  滑らか化とスライシングが計量特性と弱位相を保存することを示す。 また、滑らかなパラメータに関して異なる発散の連続性を含む他の性質も導出する。
  論文  参考訳（メタデータ） (2024-04-04T07:55:46Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Revisiting Non-separable Binary Classification and its Applications in Anomaly Detection [10.031370250511207]
  XOR の線形分類が可能であることを示す。 我々は、SVMの目的に適合し、マージン内または外にあるデータを識別する等分性分離を提案する。 分類器はスムーズな近似でニューラルネットワークパイプラインに統合できる。
  論文  参考訳（メタデータ） (2023-12-03T23:59:03Z)
• Generalized equivalences between subsampling and ridge regularization [3.1346887720803505]
  アンサンブルリッジ推定器におけるサブサンプリングとリッジ正則化の間の構造的およびリスク等価性を証明した。 我々の同値性の間接的な意味は、最適に調整されたリッジ回帰は、データアスペクト比において単調な予測リスクを示すことである。
  論文  参考訳（メタデータ） (2023-05-29T14:05:51Z)
• Classification Tree Pruning Under Covariate Shift [7.982668978293684]
  分類木,すなわち,バイアスと分散のバランスをとるのに適した部分木を選択するという問題を考える。 このような状況下では、クロスバリデーションや他のペナル化変種が著しく不十分である場合に、最適なプルーニングを行うための最初の効率的な手順を提示する。
  論文  参考訳（メタデータ） (2023-05-07T17:08:21Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions [9.953088581242845]
  2次モーメントを持つ任意のデータ分布に対して,コンバージェンス保証と複雑性を提供する。 我々の結果は、対数共空性や機能的不等式を前提としない。 我々の理論解析は、異なる離散近似の比較を提供し、実際の離散化点の選択を導くかもしれない。
  論文  参考訳（メタデータ） (2022-11-03T15:51:00Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  本論文は,最適化が容易なjmmdの統一形式を理論的に導出する。 統合JMMDから、JMMDは分類に有利な特徴ラベル依存を低下させることを示す。 本稿では,その依存を促進する新たなmmd行列を提案し,ラベル分布シフトにロバストな新しいラベルカーネルを考案する。
  論文  参考訳（メタデータ） (2021-01-25T09:46:14Z)
• Strongly universally consistent nonparametric regression and classification with privatised data [2.879036956042183]
  非パラメトリック回帰の古典的問題を再考するが、局所的な差分プライバシー制約を課す。 我々は回帰関数の新しい推定器を設計し、よく研究された分割回帰推定器の民営版とみなすことができる。
  論文  参考訳（メタデータ） (2020-10-31T09:00:43Z)
• Predictive Value Generalization Bounds [27.434419027831044]
  本稿では,二項分類の文脈におけるスコアリング関数の評価のためのビクテリオンフレームワークについて検討する。 本研究では,新しい分布自由な大偏差と一様収束境界を導出することにより,予測値に関するスコアリング関数の特性について検討する。
  論文  参考訳（メタデータ） (2020-07-09T21:23:28Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)
• Distribution-free binary classification: prediction sets, confidence intervals and calibration [106.50279469344937]
  分布自由条件における二項分類のための不確実性定量化(キャリブレーション、信頼区間、予測セット)の3つの概念について検討する。 固定幅と一様質量の両双対の双対確率に対する信頼区間を導出する。 我々の「三脚」定理の結果として、双有理確率に対するこれらの信頼区間は分布自由キャリブレーションに繋がる。
  論文  参考訳（メタデータ） (2020-06-18T14:17:29Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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