summaries: This paper studies how regularization affects the robust population risk in the overparameterization regime. The authors study the behavior of linear regression and logistic regression under sufficient statistical settings. In particular, even in the noiseless regime, the population robust risk benefits from the regularization, but not the population test risk. The argument is empirically verified.

summaries: The authors analyze the generalization performance of regularized adversarial linear regression and classification models for standard Gaussian data in the overparameterized setting.  The analysis allows for l^2 weight decay as well as l^\infty perturbation of the inputs.  Using similar methods to Hastie, Montanari, Rosset, and Tibshirani [18] and Javanmard and Soltanolkotabi [19], they are able to develop precise formula for the generalization error in the limit as n/d -> constant as n,d -> infinity.  They demonstrate that non-zero regularization has strictly better generalization in the robust setting.

summaries: The paper studies the benefits of non-vanishing regularization for improving generalization in overparameterized classification and regression problems. In this setting, previous works studied the implicit bias effect. Particularly, it was shown that training models *without* explicit regularization can still yield good generalization performance. In contrast, in this paper, the authors show that explicit regularization can further improve generalization, especially w.r.t. the adversarial robust risk.

summaries: This paper compares the effect of interpolation and regularization on robust generalization. It shows that in the case of regression under squared loss and classification under the log loss when the ground truth is a linear model robust generalization error is smaller for regularized estimators. The robust generalization error is defined as the error under consistent adversarial perturbations.

abstractText: Numerous recent works show that overparameterization implicitly reduces variance for min-norm interpolators and max-margin classifiers. These findings suggest that ridge regularization has vanishing benefits in high dimensions. We challenge this narrative by showing that, even in the absence of noise, avoiding interpolation through ridge regularization can significantly improve generalization. We prove this phenomenon for the robust risk of both linear regression and classification, and hence provide the first theoretical result on robust overfitting.

authors:
A. Ali
J.Z. Kolter
R.J. Tibshirani

title: A continuous-time view of early stopping for least squares regression

venue: In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
A. Ali
E. Dobriban
R. Tibshirani

title: The implicit regularization of stochastic gradient flow for least squares

venue: In Proceedings of the International Conference on Machine Learning (ICML),

authors:
Z. Bai
J.W. Silverstein

title: Spectral analysis of large dimensional random matrices, volume 20

authors:
Z.D. Bai
Y.Q. Yin

title: Limit of the smallest eigenvalue of a large dimensional sample covariance matrix

venue: The Annals of Probability,

authors:
P. Bartlett
Y. Freund
W.S. Lee
R.E. Schapire

title: Boosting the margin: A new explanation for the effectiveness of voting methods

venue: The Annals of Statistics,

authors:
P.L. Bartlett
P.M. Long
G. Lugosi
A. Tsigler

title: Benign overfitting in linear regression

venue: In Proceedings of the National Academy of Sciences,

authors:
M. Belkin
D. Hsu
S. Ma
S. Mandal

title: Reconciling modern machine-learning practice and the classical bias–variance trade-off

title: Training with noise is equivalent to Tikhonov regularization

venue: Neural Computation,

authors:
P. Bühlmann
S. Van De Geer

title: Statistics for high-dimensional data: Methods, theory and applications

venue: Springer Science & Business Media,

title: Invariance, causality and robustness

venue: Statistical Science,

authors:
Y. Chen
P. Bühlmann

title: Domain adaptation under structural causal models

venue: arXiv preprint arXiv:2010.15764,

authors:
L. Chizat
F. Bach

title: On the global convergence of gradient descent for over-parameterized models using optimal transport

venue: In Advances in Neural Information Processing Systems (NeurIPS),

title: Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss

venue: In Proceedings of the Conference on Learning Theory (COLT),

authors:
Z. Deng
A. Kammoun
C. Thrampoulidis

title: A model of double descent for high-dimensional binary linear classification

venue: In Information and Inference: A Journal of the IMA,

authors:
E. Dobriban
S. Wager

title: High-dimensional asymptotics of prediction: Ridge regression and classification

authors:
C. Dong
L. Liu
J. Shang

title: Data profiling for adversarial training: On the ruin of problematic data

venue: arXiv preprint arXiv:2102.07437,

authors:
W. Gao
Z.-H. Zhou

title: On the doubt about margin explanation of boosting

venue: Artificial Intelligence,

authors:
B. Ghorbani
S. Mei
T. Misiakiewicz
A. Montanari

title: Linearized two-layers neural networks in high dimension

authors:
I. Goodfellow
J. Shlens
C. Szegedy

title: Explaining and harnessing adversarial examples

venue: In Proceedings of the International Conference on Learning Representations (ICLR),

title: On Milman’s inequality and random subspaces which escape through a mesh in R

venue: In Geometric aspects of functional analysis,

authors:
P. Grother
G. Quinn
P. Phillips

title: Report on the evaluation of 2D still-image face recognition

authors:
S. Gunasekar
J.D. Lee
D. Soudry
N. Srebro

title: Implicit bias of gradient descent on linear convolutional networks

authors:
T. Hastie
A. Montanari
S. Rosset
R.J. Tibshirani

title: Surprises in high-dimensional ridgeless least squares interpolation

venue: arXiv preprint arXiv:1903.08560,

authors:
A. Javanmard
M. Soltanolkotabi

title: Precise statistical analysis of classification accuracies for adversarial training

venue: arXiv preprint arXiv:2010.11213,

authors:
A. Javanmard
M. Soltanolkotabi
H. Hassani

title: Precise tradeoffs in adversarial training for linear regression

authors:
Z. Ji
M. Telgarsky

title: Gradient descent aligns the layers of deep linear networks

title: The implicit bias of gradient descent on nonseparable data

authors:
A. Knowles
J. Yin

title: Anisotropic local laws for random matrices

venue: Probability Theory and Related Fields,

authors:
D. Kobak
J. Lomond
B. Sanchez

title: The optimal ridge penalty for real-world highdimensional data can be zero or negative due to the implicit ridge regularization

venue: Journal of Machine Learning Research,

authors:
Y. Lee
R.F. Barber

title: Binary classification with corrupted labels

venue: arXiv preprint arXiv:2106.09136,

authors:
Y. Li
E.X.Fang
H. Xu
T. Zhao

title: Implicit bias of gradient descent based adversarial training on separable data

authors:
K. Lyu
J. Li

title: Gradient descent maximizes the margin of homogeneous neural networks

authors:
S. Mei
A. Montanari

title: The generalization error of random features regression: Precise asymptotics and double descent curve

authors:
V. Muthukumar
A. Narang
V. Subramanian
M. Belkin
D. Hsu
A. Sahai

title: Classification vs regression in overparameterized regimes: Does the loss function matter

authors:
V. Muthukumar
K. Vodrahalli
V. Subramanian
A. Sahai

title: Harmless interpolation of noisy data in regression

venue: IEEE Journal on Selected Areas in Information Theory,

authors:
P. Nakkiran
G. Kaplun
Y. Bansal
T. Yang
B. Barak
I. Sutskever

title: Deep double descent: Where bigger models and more data hurt

authors:
P. Nakkiran
P. Venkat
S.M. Kakade
T. Ma

title: Optimal regularization can mitigate double descent

authors:
P. Patil
Y. Wei
A. Rinaldo
R. Tibshirani

title: Uniform consistency of cross-validation estimators for high-dimensional ridge regression

authors:
Y. Plan
R. Vershynin

title: Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach

venue: In IEEE Transactions on Information Theory,

authors:
J. Quionero-Candela
M. Sugiyama
A. Schwaighofer
N.D. Lawrence

title: Dataset Shift in Machine Learning

authors:
A. Raghunathan
S.M. Xie
F. Yang
J. Duchi
P. Liang

title: Understanding and mitigating the tradeoff between robustness and accuracy

authors:
L. Rice
E. Wong
Z. Kolter

title: Overfitting in adversarially robust deep learning

authors:
D. Richards
J. Mourtada
L. Rosasco

title: Asymptotics of ridge (less) regression under general source condition

authors:
S. Rosset
J. Zhu
T. Hastie

title: Margin maximizing loss functions

authors:
S. Sagawa
P.W. Koh
T.B. Hashimoto
P. Liang

title: Distributionally robust neural networks

authors:
F. Salehi
E. Abbasi
B. Hassibi

title: The impact of regularization on high-dimensional logistic regression

authors:
A. Sanyal
P.K. Dokania
V. Kanade
P. Torr

title: How benign is benign overfitting

authors:
A. Sinha
H. Namkoong
J. Duchi

title: Certifying some distributional robustness with principled adversarial training

authors:
D. Soudry
E. Hoffer
M.S. Nacson
S. Gunasekar
N. Srebro

title: The implicit bias of gradient descent on separable data

authors:
P. Sur
E.J. Candès

title: A modern maximum-likelihood theory for high-dimensional logistic regression

authors:
C. Thrampoulidis
S. Oymak
B. Hassibi

title: Regularized linear regression: A precise analysis of the estimation error

title: High-Dimensional Statistics: A Non-Asymptotic Viewpoint

authors:
B. Wu
J. Chen
D. Cai
X. He
Q. Gu

title: Do wider neural networks really help adversarial robustness

venue: arXiv preprint arXiv:2010.01279,

authors:
D. Wu
J. Xu

title: On the optimal weighted `2 regularization in overparameterized linear regression

venue: arXiv preprint arXiv:2006.05800,

title: Learning and evaluating classifiers under sample selection bias

authors:
D. Zou
S. Frei
Q. Gu

title: Provable robustness of adversarial training for learning halfspaces with noise

heading: 1 Introduction

text:
Conventional statistical wisdom cautions the user who trains a model by minimizing a loss L(θ): if a global minimizer achieves zero or near-zero training loss (i.e., it interpolates), we run the risk of overfitting (i.e., high variance) and thus suboptimal prediction performance. Instead, regularization is commonly used to reduce the effect of noise and to obtain an estimator with better generalization. Specifically, regularization limits model complexity and induces worse data fit, for example via an explicit penalty term R(θ). The resulting penalized loss L(θ) + λR(θ) explicitly imposes certain structural properties on the minimizer. This classical rationale, however, does seemingly not apply to overparameterized models: for example, large neural networks in practice exhibit good generalization performance on i.i.d. samples even if L(θ) vanishes and label noise is present [36]. Since interpolators are not unique in the overparameterized regime, it is crucial to study the specific implicit biases of interpolating estimators. In particular, for common losses, a large body of recent work analyzes the properties of the solutions found via gradient descent at convergence (see e.g. [44, 12, 13, 22, 26, 27, 49, 31]). For example, for linear and logistic regression, it is well-known that gradient descent converges to the min-`2-norm and max-`2-margin solutions, respectively [22, 27, 32, 49]. These interpolating estimators also minimize the respective penalized loss L(θ) + λ‖θ‖22 in the limit of λ→ 0 [44]. A plethora of recent papers explicitly study generalization properties on min-`2-norm interpolators [15, 18, 23, 6, 33, 34, 35] and max-`2-margin solutions [14, 34, 46], and show that the variance decreases as the overparameterization ratio increases beyond the interpolation threshold. While regularization with λ > 0 is commonly known to reduce the risk at the interpolation threshold [23, 37], many of these works are motivated by the second descent of the double descent phenomenon [7] which suggests that regularization becomes redundant with sufficient overparameterization. Hence, previous papers focus on highly overparameterized settings where the optimal regularization parameter satisfies λopt ≤ 0 [29, 54, 43], implying that for large d/n, explicit regularization with λ > 0 is redundant or even detrimental for generalization.
∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Taking a step back, this narrative originated from theoretical and experimental findings that consider the standard test risk with identically distributed training and test data. However, this measure cannot reflect the robust risk of models when the test data has a shifted distribution, is attacked by adversaries, or contains many samples from minority groups [19, 21, 40, 55]. In fact, mounting empirical evidence suggests that regularization is indeed helpful for robust generalization, even in highly overparameterized regimes where the benefits for the standard risk are negligible [42]. This phenomenon is sometimes referred to as robust overfitting.
In the presence of noise, the following intuition holds true: since the robust risk amplifies estimation errors, its variance is larger and hence regularization – such as early stopping – can be beneficial for generalization [47]. However, we observe that even when estimating entirely noiseless signals, robust overfitting persists! We observe this phenomenon in experiments with shallow neural networks on sanitized image data depicted in Figure 1a and, in fact, even for linear models trained on highdimensional synthetic noiseless data. In particular, Figures 1b,1c show that min-`2-norm and robust max-`2-margin interpolators (minimizers of the training loss for λ → 0), achieve a higher robust risk than the corresponding regularized estimators that do not interpolate noiseless observations (minimizers for λ > 0).
To date, our observations in the noiseless case cannot be explained by prior work. On the contrary, they seem to contradict a simple intuition: if the min-`2-norm and robust max-`2-margin interpolators exhibit large risks as λ → 0, the induced bias for a small `2-norm is potentially suboptimal and a larger penalty weight λ > 0 should only degrade performance. In this paper, we provide possible explanations that debunk this intuition in the high-dimensional overparameterized regime. We prove for isotropic Gaussian covariates that a strictly positive regularization parameter λ systematically improves robust generalization for linear and robust logistic regression. Empirically, we show that early stopping and other factors that lead to a non-interpolating estimator achieve a similar effect. Our results provide the first rigorous explanation of robust overfitting even in the absence of noise.
In Section 2, we formally define the setting that we use throughout our analysis. We then first present precise asymptotic expressions for the robust risk for linear regression in Section 3 that explicitly explain robust overfitting. Furthermore, in Section 4, we consider classification with logistic regression and derive asymptotic results.

heading: 2 Risk minimization framework

text: In this section, we introduce the data generating process that we assume throughout our analysis, and define the standard and robust risks that we use as evaluation metrics.

heading: 2.1 Problem setting

text:
This paper considers the supervised learning problem of estimating a mapping from d-dimensional real-valued features x ∈ Rd to a target y ∈ Y ⊆ R given a training set of labeled samples D = {(xi, yi)}ni=1. We assume that the feature vectors xi are drawn i.i.d. from the marginal distribution P that we assume to be an isotropic Gaussian. We further focus on noiseless observations yi = 〈θ?, xi〉 for regression tasks and yi = sgn(〈θ?, xi〉) for classification tasks, respectively. However, the main results are more general and apply to noisy observations as well. For regression, we assume additive Gaussian noise with zero mean and σ2 variance, while for classification we flip a certain percentage of the training labels.
This paper studies the high-dimensional asymptotic regime where d/n→ γ as both the dimensionality d and the number of samples n tend to infinity. This high-dimensional setting is widely studied as it can often – as in our experiments – yield precise predictions for the risk of the estimator when both the input dimension and the data set size are large [9, 52]. It is also the predominant setting considered in previous theoretical works that discuss overparameterized linear models [2, 14, 15, 23, 25, 24, 50].

heading: 2.2 Standard and robust risk

text:
We now introduce the standard and robust evaluation metrics for regression and classification. Given a pointwise test loss `test : R× R→ R, we define the standard (population) risk of an estimator θ̂ as
R(θ̂) := EX∼P`test ( 〈θ̂, X〉, 〈θ?, X〉 ) , (1)
where the expectation is taken over the marginal feature distribution P. Note that for any datadependent estimator θ̂, this risk is fixed if conditioned on the training data. Our asymptotic bounds hold almost surely over draws of the training set. As standard in the literature, we choose the square loss `test(u, v) = (u − v)2 for regression and the 0-1 loss `test(u, v) = 1sgn(u) 6=sgn(v) for classification.
The broad application of ML models in real-world decision-making processes increases requirements on their generalization abilities beyond i.i.d. test sets. For example, in the image domain, classifiers should be robust and output the same prediction for perturbations of an image that do not change the ground truth label (e.g., imperceptible `p-perturbations [19]). In this case, we say the perturbations are consistent and the estimator that achieves zero robust population risk also has zero standard population risk. For linear models in particular, one way to enforce consistency is to restrict perturbations to the space orthogonal to the ground truth, as proposed in [41].
Motivated by the imperceptibility assumption and `p-adversarial attacks widely studied in the image domain, we consider the adversarially robust risk of a parameter θ with respect to consistent `pperturbations
R (θ̂) := EX∼P max δ∈Up( ) `test(〈θ̂, X + δ〉, 〈θ?, X〉) , (2)
with the perturbation set Up( ) := {δ ∈ Rd : ‖δ‖p ≤ and 〈θ?, δ〉 = 0}. In many scientific applications, security against adversarial attacks may not be the dominating concern; one may instead require estimators to be robust against small distribution shifts. Earlier work [48] has pointed out that distribution shift robustness and adversarial robustness are equivalent for losses that are convex in the parameter θ. Similarly, in our setting, adversarial robustness against consistent `p-perturbations implies distributional robustness against `p-bounded mean shifts in the covariate distribution P (see Appendix A.3).
3 Min-`2-norm interpolation in robust linear regression
In the context of regression, we illustrate overfitting of the robust risk in Equation (2) with the set of consistent `2-perturbations U2( ). More precisely, we show that preventing min-`2-norm interpolation on noiseless samples via ridge regularization improves the robust risk. We refer the reader to Appendix C.1 for an intuitive explanation. Lastly, we note that due to the rotational invariance of the problem, our results hold for sparse and dense ground truths θ? alike.

heading: 3.1 Interpolating and regularized estimator

text:
We study linear ridge regression estimates defined as
θ̂λ = arg min θ
1
n n∑ i=0 (yi − 〈θ, xi〉)2 + λ‖θ‖22. (3)
The min-`2-norm interpolator is the limit of the linear ridge regression estimate with λ→ 0 and is given by
θ̂0 = arg min θ ‖θ‖2 such that 〈θ, xi〉 = yi for all i. (4)
Note that the min-`2-norm interpolator is also the estimator that gradient descent on the unregularized loss converges to, while ridge regression with λ > 0 corresponds to early-stopped estimators [1, 2]. Therefore, by proving that a ridge regularized estimator with λ > 0 significantly outperforms the min-`2-norm interpolator with λ→ 0, we also show that early stopping benefits robust generalization. Whenever the goal is to achieve a low robust risk, a popular alternative to using the standard linear regression estimate in Equations (3),(4) is to consider adversarially trained estimators [19, 25]. However, `2-adversarial training in its usual form (i.e., with inconsistent perturbations) prevents regression estimators from interpolating, and hence, has a similar effect to `2-regularization as we discuss in more detail in Appendix C.2. On the other hand, training with consistent perturbations as defined in the robust risk is equivalent to full knowledge of the direction of θ? and hence simply recovers the ground truth in the noiseless case. Since our goal is to reveal the shortcomings of interpolators compared to regularized estimators, we only analyze ridge estimators trained without perturbations.

heading: 3.2 Robust overfitting in noiseless linear regression

text:
The following theorem provides a precise asymptotic expression of the robust risk under consistent `2-perturbations for the ridge regression estimate in Equation (3). The proof extends techniques from previous works [23, 15] based on results from random matrix theory [3, 28] and can be found in Appendix E. Without loss of generality, we can assume that ‖θ?‖2 = 1. Theorem 3.1. Assuming the marginal input distribution P = N (0, Id), the robust risk (2) of the estimator θ̂λ for λ > 0 (defined in (3)) with respect to consistent `2-perturbations U2( ) asymptotically converges to
R (θ̂λ) a.s.−→ Rλ + 2Pλ +
√ 8 2
π PλRλ =: R ,λ (5)
as d, n → ∞ with d/n → γ, where Pλ = Rλ − λ2(m(−λ))2 and Rλ = λ2m′(−λ) + σ2γ(m(−λ)− λm′(−λ)) is the asymptotic standard risk, i.e., R(θ̂λ) a.s.−→ Rλ. The function m(z) is the Stieltjes transform of the Marchenko-Pastur law and is given by
m(z) = 1−γ−z− √ (1−γ−z)2−4γz 2γz . Further, the limit limλ→0R ,λ exists for all ≥ 0 and corresponds to the asymptotic standard ( = 0) and robust risks ( > 0) of the min-`2-norm interpolator θ̂0 (4).
We plot the precise asymptotic risks of the ridge estimate with optimal regularization parameter λopt2 and of the min-`2-norm interpolator for λ→ 0 in Figure 2. For the robust risk, we use = 0.4. We first observe in Figure 2a that ridge regularization reduces the robust risk even for d/n 1 well beyond the interpolation threshold – the regime where previous works show that the variance is negligible, and hence, regularization does not improve generalization.
Moreover, Figure 2b illustrates that the beneficial effect of ridge regularization persists even for noiseless data. This supports our statement that regularization not only helps to reduce variance, but also reduces the part of the robust risk that is unaffected by noise in the overparameterized regime. Furthermore, we show that experiments run with finite values of d and n (depicted by the markers in Figure 2) closely match the predictions obtained from Theorem 3.1 for d, n→∞ and d/n→ γ. This
2Here we choose λ using the population risk oracle. In practice, one would resort to standard tools such as cross-validation techniques that also enjoy theoretical guarantees (see e.g. [38]).
indicates that the high-dimensional asymptotic regime does indeed correctly predict and characterize the high-dimensional non-asymptotic regime. Finally, even though Theorem 3.1 assumes isotropic Gaussian covariates, we can extend it to more general covariance matrices following the same argument as in [23], based on results from random matrix theory [28].
4 Max-`2-margin interpolation in robust linear classification
Unlike linear regression, adversarially trained binary logistic regression classifiers may still interpolate the training data, resulting in robust max-`2-margin interpolators as λ → 0. Hence, in this section we train and evaluate classifiers with `∞-perturbation sets U∞( ), a standard choice in the experimental and theoretical classification literature [19, 24, 42, 47], but also discuss `2-perturbations in Appendix D.3 for completeness. Our theoretical results show that the robust max-`2-margin interpolator with λ→ 0 has a worse robust risk than a regularized predictor with λ > 0.

heading: 4.1 Interpolating and regularized estimator

text:
As discussed in Section 3, a common method to obtain robust estimators is to use adversarial training. However, for linear regression, adversarial training either renders interpolating estimators infeasible, or requires oracle knowledge of the ground truth. In contrast, for linear classification, interpolation is easier to achieve – it only requires the sign of 〈xi, θ〉 to be the same as the label yi for all i. In particular, when the data is sufficiently high dimensional, it is possible to find an interpolator of the adversarially perturbed training set.
We study the robust ridge-regularized logistic regression estimator with penalty weight λ > 0,
θ̂λ := arg min θ
1
n n∑ i=1 max δ∈U∞( ) log(1 + e−〈θ,xi+δ〉yi) + λ‖θ‖22. (6)
In the limit λ → 0 the results in [44] imply that the robust ridge-regularized logistic regression estimator from Equation (6) directionally aligns with the robust max-`2-margin interpolator:3
θ̂0 := arg min θ ‖θ‖2 such that min δ∈U∞( ) yi〈θ, xi + δ〉 ≥ 1 for all i. (7)
3While [44] only proves the result for = 0, it is straightforward to extend it to the general case where ≥ 0.
Standard risk Robust risk Normalized robust margin
We say that the data is robustly separable if the robust max-`2-margin interpolator exists.
The robust max-`2-margin solution is an interpolating estimator of particular importance since it directionally aligns with the estimator found by gradient descent [31]. Since the robust accuracy (i.e., the robust risk defined using the 0-1 loss) is independent of the norm of the estimator, we simply refer to the robust max-`2-margin solution as the normalized vector θ̂0‖θ̂0‖2 .
In this paper, we study two choices for the set of training perturbations U∞( ):
inconsistent perturbations U∞( ) = {δ ∈ Rd : ‖δ‖∞ ≤ } (8) consistent perturbations U∞( ) = {δ ∈ Rd : ‖δ‖∞ ≤ , 〈δ, θ?〉 = 0} (9)
Adversarial training with respect to inconsistent perturbations (8) is a popular choice in the literature to improve the robust risk (e.g. [19, 24]). However, perturbed samples may cross the true decision boundary, and hence, inconsistent perturbations effectively introduce noise during the training procedure. In particular, in the data model with noiseless observations that we introduce in Section 4.2, the ground truth function misclassifies approximately 8% of the labels when perturbing the training data with inconsistent perturbations of size = 0.1.
As mentioned in the introduction, in this paper we are interested in verifying whether regularization can be beneficial in high dimensions even in the absence of noise. Therefore, in the sequel we study the impact of both inconsistent (8) and consistent (9) perturbations on robust overfitting.

heading: 4.2 Robust overfitting in noiseless linear classification

text:
We now show empirically that regularization helps to improve the robust and standard risks when training with noiseless data and derive precise asymptotic predictions for both risks. Throughout this subsection we assume deterministic, and hence, noiseless training labels, i.e., yi = sgn〈xi, θ?〉. Furthermore, as we discuss in Section 4.3, the inductive bias of the `∞-robust logistic loss encourages sparse solutions. Since we are primarily interested in learning ground truth functions that match the implicit bias of the estimator, we assume the sparse ground truth θ? = (1, 0, . . . , 0)T .
We first show robust overfitting experimentally on noiseless data when training with inconsistent perturbations and subsequently demonstrate that overfitting persists even if the training procedure is completely noiseless (i.e., using consistent training perturbations). Finally, we provide theoretical evidence for our observations in the high-dimensional asymptotic limit.
Training with inconsistent adversarial perturbations Figure 3a illustrates the robust margin mini minδ∈U∞( ) 1 ‖θ‖2 yi〈θ, xi + δ〉 as well as the standard and robust risks of the estimator θ̂λ trained using inconsistent adversarial perturbations on a synthetic data set with fixed overparameterization ratio d/n = 8. We observe that decreasing the ridge coefficient well beyond the point where the minimizer of the robust logistic loss (6) reaches 100% robust training accuracy (i.e., the robust margin becomes positive) substantially hurts generalization.
In addition to varying the ridge coefficient λ, we notice that the same trends as for λ→ 0 also occur for the gradient descent optimization path as the number of iterations t goes to infinity. Figure 3b indicates that, similarly to ridge regularization, early stopping also avoids the robust max-`2-margin solution that is obtained for t → ∞ and yields an estimator with significantly lower standard and robust risks.
Training with consistent adversarial perturbations As discussed in Section 4.1, even for noiseless training data, inconsistent perturbations can induce noise during the training procedure. Hence, one could hypothesize that the noise induced by the inconsistent perturbations causes the overfitting observed in Figure 3. To contradict this hypothesis, we also study adversarial training with consistent perturbations. By definition, consistent perturbations do not cross the true decision boundary and hence leave the training data entirely noiseless.
Figure 4a shows that the adversarially trained estimators (6),(7) with consistent and inconsistent perturbations yield comparable robust risks. Moreover, robust overfitting occurs in both situations, as the risk is higher for the interpolating estimator λ→ 0 compared to an optimal λ > 0. Hence, our observations demonstrate that robust overfitting persists even if training with consistent perturbations in an entirely noiseless setting. This observation is counter intuitive since, according to classical wisdom, we would expect ridge regularization to only benefit in noisy settings where the estimator suffers from a high variance.
We now prove this phenomenon using the next theorem. In particular, similar to Theorem 3.1 for linear regression, we show that robust overfitting occurs in the high-dimensional asymptotic regime where d/n→ γ as d, n→∞. We state an informal version of the theorem in the main text and refer to Appendix F for the precise statement. The proof is inspired by the works [24, 46] and uses the Convex Gaussian Minimax Theorem (CGMT) [20, 51]. Theorem 4.1 (Informal). Assume that = 0/ √ d for some constant 0 and θ? = (1, 0, · · · , 0)T .
Then, the robust and standard risks of the regularized estimator θ̂λ (6) (λ > 0) and of the robust max-`2-margin interpolator (7) (λ → 0) with inconsistent (8) or consistent (9) adversarial `∞- perturbations converge in probability as d, n→∞, d/n→ γ to:
R(θ̂λ)→ 1
π arccos ( ν?‖ ν? ) and R (θ̂λ)→ R(θ̂λ) + 1 2 erf ( 0δ ? √ 2ν? ) + I ( 0δ ? ν? , ν?‖ ν? ) We denote by erf(.) the error function,
I(t, u) := ∫ t 0 1√ 2π exp ( −x 2 2 ) erf ( xu√ 2(1− u2) ) dx,
and use the notation ν? = √
(ν?⊥) 2 + (ν?‖) 2, where ν?⊥, ν ? ‖ , δ ? are the unique solution of a scalar
optimization problem specified in Appendix F that depends on θ?, γ, 0 and λ.
Since the theoretical expressions are hard to interpret, we visualize the asymptotic values of the standard and robust risks from Theorem 4.1 in Figure 4b by solving the scalar optimization problem specified in Appendix F. We observe that Theorem 4.1 indeed predicts the benefits of regularization for robust logistic regression and that simulations using finite values of d and n follow the asymptotic trend. We describe the full empirical setup in Appendix B.

heading: 4.3 Intuitive explanation and discussion

text:
Even though we explicitly derive the precise asymptotic expressions of the standard and robust risks in Theorem 4.1 that predict the benefits of regularization for generalization, it is difficult to extract intuitive explanations for this phenomenon directly from the proof. We conjecture that a non-zero
ridge penalty induces a more sparse θ̂λ (i.e., with a smaller `1/`2-norm ratio) than the robust max`2-margin solution θ̂0 and use simulations to support our claim. Since the `∞-adversarially robust risk penalizes dense solutions with large ratio of the `1/`2-norms (see Lemma A.2 in Appendix A.2), we expect more sparse estimators to have a lower robust risk. Indeed, Figure 5a shows that the `1/`2-norm ratio strongly correlates with the robust risk of the estimator.
We begin by noting that, due to Lagrangian duality, minimizing the ridge-penalized loss (6) corresponds to minimizing the unregularized loss constrained to the set of estimators θ with a bounded `2-norm. This norm decreases as the ridge coefficient λ increases. In what follows, we provide intuition on the effect of the ridge penalty λ on the sparsity of the estimator θ̂λ.
Large λ inducing a small `2-norm We first analyze the regularized estimator θ̂λ for large λ that constrains solutions to have small `2-norm. We can therefore use Taylor’s theorem and the closedform expression of adversarial perturbations (see Lemma A.2 in Appendix A.2) to approximate the unregularized robust loss from Equation (6) as follows:
1
n n∑ i=1 log(1 + e−yi〈θ,xi〉+ ‖Π⊥θ‖1) ≈ 1 n n∑ i=1 −yi〈xi, θ〉+ ‖Π⊥θ‖1. (10)
As a consequence, the minimizer θ̂λ should result in a large robust average margin solution, that is, a solution with large 1n ∑n i=1 1 ‖θ‖2 (yi〈xi, θ〉 − ‖Π⊥θ‖1). Indeed, we observe this using simulations for finite d, n in Figures 5b and 5c. In particular, the objective in Equation (10) leads to a trade-off between the sparsity of the estimator (via its convex surrogate, the `1-norm) and an average of the sample-wise margins yi〈xi, θ〉. We note that such estimators have been well studied in the literature and are known to achieve good performance in recovering sparse ground truths [5, 17, 39].
Small λ inducing a large `2-norm In contrast, a small ridge coefficient λ leads to estimators θ̂λ with large `2-norms. In this case, the estimator approaches a large robust (minimum) margin solution, i.e., a solution with large mini 1‖θ‖2 (yi〈xi, θ〉 − ‖Π⊥θ‖1) which is maximized by the robust max-`2-margin interpolator (7). As a consequence, this leads to a trade-off between estimator sparsity and the robust minimum margin mini 1‖θ‖2 yi〈xi, θ〉. Due to the high dimensionality of the input data, the training samples xi are approximately orthogonal. Thus, to achieve a non-vanishing robust margin, estimators are forced to trade-off sparsity with all sample-wise margins instead of just
the average. We reveal this trade-off in Figures 5a and 5b where the increase in `1/`2-norm ratios corresponds to a decrease in the robust average margin and an increase in the robust margin.
Finally, we observe that the sparse ground truth is characterized by a large robust average margin (horizontal dotted line in Figure 5b) and a small (minimum) robust margin (horizontal dashed line). Therefore, we expect that the solution that is sparser and which satisfies the same properties for the robust margin as the ground truth θ?, will achieve lower robust and standard risks. Indeed, our findings indicate that the regularized estimator θ̂λ for large λ aligns better with θ?, compared to the solution obtained for a small λ, and hence justify the better performance of ridge-regularized predictors.
4.4 Benefits of an unorthodox way to avoid the robust max-`2-margin interpolator
In the previous subsections we focused on robustly separable data and studied the generalization performance of regularized estimators that do not maximize the robust margin. Another way to avoid the robust max-`2-margin solution is to introduce enough label noise in the training data. We now show that, unexpectedly, this unorthodox way to avoid the robust max-margin solution can also yield an estimator with better robust generalization than the robust max-`2-margin solution of the corresponding noiseless problem.
Specifically, in our experiments we introduce noise by flipping the labels of a fixed fraction of the training data. Figure 6 shows the robust and standard risks together with the training loss of the estimator θ̂λ from Equation (6) trained with consistent perturbations for λ→ 0 with varying fractions of flipped labels. For low noise levels, the data is robustly separable and the training loss vanishes at convergence, yielding the robust max-`2-margin solution in Equation (7). For high enough noise levels, the constraints in Equation (7) become infeasible and the training loss of the resulting estimator starts to increase. As discussed in Subsection 4.3, this estimator has a better implicit bias than the robust max-`2-margin interpolator and hence achieves a lower robust risk.
Even though it is well known that introducing covariate noise can induce implicit regularization [8], our observations show that in contrast to common intuition, the robust risk also decreases when introducing wrong labels in the training loss. In parallel to our work, the paper [30] shows that training with corrupted labels can be beneficial for the standard risk.
However, we emphasize here that we do not advocate in favor of artificial label noise as a means to obtain more robust classifiers. In particular, even if the data is not robustly separable, the estimator with optimal ridge parameter λopt in Figure 6 still always outperforms the unregularized solution.
Finally, we remark that a similar effect can also be observed when training with inconsistent perturbations with large perturbation norm . We refer to Appendix D.1 for further discussion.

heading: 5 Related work

text:
Understanding robust overfitting The current literature attempting to explain robust overfitting [42] primarily focuses on the effect of noise and on the smoothness of decision boundaries learned by neural networks trained to convergence [16, 47, 53]. A slightly different line of work [45] shows that overparameterized models require regularization in order to achieve good classification accuracy on all subpopulations. However, a theoretical understanding of the role of regularization is still missing.
Theory for adversarial robustness of linear models Recent works [25, 24] provide a precise description of the robust risks for logistic and linear regression when trained with adversarial attacks based on the Convex Gaussian Minimax Theorem [20, 51]. The analysis focuses on inconsistent attacks for both training and evaluation. For linear regression, the authors observe that adversarial training with `2-perturbations mitigates the peak in the double descent curve around d = n and hence acts similarly to ridge regularization as explicitly studied in [23]. Several other works focus on the role of gradient descent in robust logistic regression. In particular, [56] proves that early stopping yields robust adversarially-trained linear classifiers even in the presence of noise. Furthermore, the results of [31] show that gradient descent on robustly separable data converges to the robust max-`2-margin estimator (7).

heading: 6 Conclusion and future work

text:
In this work, we show that overparameterized linear models can overfit with respect to the robust risk even when there is no noise in the training data. Our results challenge the modern narrative that interpolating overparameterized models yield good performance without explicit regularization and motivate the use of ridge regularization and early stopping for improved robust generalization. Perhaps surprisingly, we further observe that ridge regularization enhances the bias of logistic regression trained with adversarial `∞-attacks towards sparser solutions, indicating that the impact of explicit regularization may go well beyond variance reduction.
Future work Our simulations indicate that early stopping yields similar benefits as ridge regularization in noiseless settings. However, we leave a formal proof for future work. Furthermore, the double descent phenomenon has been proven for the standard risk on a broad variety of data distributions and even for non-linear models such as random feature regression. It is still unclear how our results translate to these settings. In particular, our theoretical analysis heavily makes use of the closed-form solution of the adversarial attacks, and hence, cannot be applied to non-linear models in a straightforward way.

heading: Acknowledgments

text: K. D. is supported by the ETH AI Center and the ETH Foundations of Data Science. R. H. is supported by the IAS at TUM, the DFG (German Research Foundation), and by the NSF under award IIS-1816986.

title: Interpolation can hurt robust generalization even when there is no noise


summaries: The paper proposes an autoencoder architecture that decouples point cloud’s representation into the global latent vector and spherical canonical embedding (in $\mathbb{S}^2$ space) for each of its points. It is trained in the unsupervised way on the category-specific point clouds. This canonical map turns out to be robust to missing parts due to a specially crafted regulariser. What’s new related to the prior art is that the method is somewhat robust to initial orientation of the shape. The formulation is simple and elegant, however, the method is tested only on synthetic ShapeNet data, so it is unclear whether it would work well in a more practical setting. There are also other methodological concerns and clarity problems.

summaries: This paper presents a novel solution for learning dense correspondence between un-aligned 3D shapes in an self-supervised manner. The key contributions this paper is to design a novel canonical space for representing all 3D shapes and learning an auto-encoder to learn a mapping to and from an input point cloud to this canonical space. The effectiveness of this approach is shown for the 3D semantic keypoint transfer and part segmentation transfer tasks across different categories.

summaries: The paper suggests an end-to-end learnable method to find dense 3D point correspondences of point clouds. The authors first project the input point clouds onto a canonical spherical UV space, where corresponding points of different shape instances map to similar coordinates. Then, an instance-based feature vector is concatenated with the UV coordinates and fed to a decoder to retrieve the original point cloud. Since the UV coordinates hold correspondence information, the output point cloud is, in fact, an ordered one.

summaries: The paper proposes a canonical point autoencoder for the purpose of unsupervised learning dense correspondences between 3D shapes of the same category. The canonical space is defined on a 3D sphere, but with extra flexibility that the template needs not to fully cover the full sphere. This gives the flexibility to generalize to non genus 0 shapes. The proposed method seems to give noticeable improvement over existing ones.

abstractText: We propose a canonical point autoencoder (CPAE) that predicts dense correspondences between 3D shapes of the same category. The autoencoder performs two key functions: (a) encoding an arbitrarily ordered point cloud to a canonical primitive, e.g., a sphere, and (b) decoding the primitive back to the original input instance shape. As being placed in the bottleneck, this primitive plays a key role to map all the unordered point clouds on the canonical surface and to be reconstructed in an ordered fashion. Once trained, points from different shape instances that are mapped to the same locations on the primitive surface are determined to be a pair of correspondence. Our method does not require any form of annotation or selfsupervised part segmentation network and can handle unaligned input point clouds within a certain rotation range. Experimental results on 3D semantic keypoint transfer and part segmentation transfer show that our model performs favorably against state-of-the-art correspondence learning methods. The source code and trained models can be found at https://anjiecheng.github.io/cpae/.

authors:
Ashutosh Saxena
Justin Driemeyer
Justin Kearns
Andrew Y Ng

title: Robotic grasping of novel objects

venue: In NIPS, pages 1209–1216,

authors:
Andrew T Miller
Steffen Knoop
Henrik I Christensen
Peter K Allen

title: Automatic grasp planning using shape primitives

venue: In ICRA,

authors:
Qiang Hao
Rui Cai
Zhiwei Li
Lei Zhang
Yanwei Pang
Feng Wu
Yong Rui

title: Efficient 2d-to-3d correspondence filtering for scalable 3d object recognition

venue: In CVPR,

authors:
Wang Zeng
Wanli Ouyang
Ping Luo
Wentao Liu
Xiaogang Wang

title: 3d human mesh regression with dense correspondence

authors:
Xueting Li
Sifei Liu
Kihwan Kim
Shalini De Mello
Varun Jampani
Ming-Hsuan Yang
Jan Kautz

title: Self-supervised single-view 3d reconstruction via semantic consistency

venue: In ECCV,

authors:
Angjoo Kanazawa
Shubham Tulsiani
Alexei A. Efros
Jitendra Malik

title: Learning categoryspecific mesh reconstruction from image collections

authors:
Abhishek Badki
Orazio Gallo
Jan Kautz
Pradeep Sen

title: Meshlet priors for 3d mesh reconstruction

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Thibault Groueix
Matthew Fisher
Vladimir G Kim
Bryan C Russell
Mathieu Aubry

title: 3d-coded: 3d correspondences by deep deformation

authors:
Syed Zulqarnain Gilani
Ajmal Mian
Faisal Shafait
Ian Reid

title: Dense 3d face correspondence

venue: IEEE TPAMI,

authors:
Angel X Chang
Thomas Funkhouser
Leonidas Guibas
Pat Hanrahan
Qixing Huang
Zimo Li
Silvio Savarese
Manolis Savva
Shuran Song
Hao Su

title: Shapenet: An information-rich 3d model repository

venue: arXiv preprint arXiv:1512.03012,

authors:
Zhiqin Chen
Kangxue Yin
Matthew Fisher
Siddhartha Chaudhuri
Hao Zhang

title: Bae-net: Branched autoencoder for shape co-segmentation

authors:
Feng Liu
Xiaoming Liu

title: Learning implicit functions for topology-varying dense 3d shape correspondence

venue: In NeurIPS,

authors:
Angjoo Kanazawa
Shubham Tulsiani
Alexei A Efros
Jitendra Malik

authors:
Shubham Goel
Angjoo Kanazawa
Jitendra Malik

title: Shape and viewpoints without keypoints

authors:
Shubham Tulsiani
Nilesh Kulkarni
Abhinav Gupta

title: Implicit mesh reconstruction from unannotated image collections

venue: arXiv preprint arXiv:2007.08504,

authors:
Charles R Qi
Hao Su
Kaichun Mo
Leonidas J Guibas

title: Pointnet: Deep learning on point sets for 3d classification and segmentation

authors:
Yaoqing Yang
Chen Feng
Yiru Shen
Dong Tian

title: Foldingnet: Point cloud auto-encoder via deep grid deformation

authors:
Theo Deprelle
Thibault Groueix
Matthew Fisher
Vladimir Kim
Bryan Russell
Mathieu Aubry

title: Learning elementary structures for 3d shape generation and matching

title: A papier-mâché approach to learning 3d surface generation

authors:
Guandao Yang
Xun Huang
Zekun Hao
Ming-Yu Liu
Serge Belongie
Bharath Hariharan

title: Pointflow: 3d point cloud generation with continuous normalizing flows

venue: In ICCV,

title: Machine Perception of Three-Dimensional Solids

venue: PhD thesis, Massachusetts Institute of Technology,

title: Visual perception by computer

venue: In IEEE Conference of Systems and Control,

title: Recognition-by-components: a theory of human image understanding

venue: Psychological Review,

authors:
Anton van den Hengel
Chris Russell
Anthony Dick
John Bastian
Daniel Pooley
Lachlan Fleming
Lourdes Agapito

title: Part-based modelling of compound scenes from images

authors:
Abhinav Gupta
Alexei A Efros
Martial Hebert

title: Blocks world revisited: Image understanding using qualitative geometry and mechanics

authors:
Gopal Sharma
Difan Liu
Subhransu Maji
Evangelos Kalogerakis
Siddhartha Chaudhuri
Radomír

title: Měch. Parsenet: A parametric surface fitting network for 3d point clouds

authors:
Shubham Tulsiani
Hao Su
Leonidas J Guibas
Alexei A Efros
Jitendra Malik

title: Learning shape abstractions by assembling volumetric primitives

authors:
Chuhang Zou
Ersin Yumer
Jimei Yang
Duygu Ceylan
Derek Hoiem

title: 3d-prnn: Generating shape primitives with recurrent neural networks

authors:
Boyang Deng
Kyle Genova
Soroosh Yazdani
Sofien Bouaziz
Geoffrey Hinton
Andrea Tagliasacchi

title: Cvxnet: Learnable convex decomposition

authors:
Despoina Paschalidou
Ali Osman Ulusoy
Andreas Geiger

title: Superquadrics revisited: Learning 3d shape parsing beyond cuboids

authors:
Kyle Genova
Forrester Cole
Daniel Vlasic
Aaron Sarna
William T Freeman
Thomas Funkhouser

title: Learning shape templates with structured implicit functions

authors:
Dmitriy Smirnov
Matthew Fisher
Vladimir G Kim
Richard Zhang
Justin Solomon

title: Deep parametric shape predictions using distance fields

authors:
Mingjia Chen
Qianfang Zou
Changbo Wang
Ligang Liu

title: Edgenet: Deep metric learning for 3d shapes

venue: Computer Aided Geometric Design,

authors:
Christopher Choy
Jaesik Park
Vladlen Koltun

title: Fully convolutional geometric features

authors:
Zan Gojcic
Caifa Zhou
Jan D Wegner
Andreas Wieser

title: The perfect match: 3d point cloud matching with smoothed densities

authors:
Bharat Lal Bhatnagar
Cristian Sminchisescu
Christian Theobalt
Gerard Pons-Moll

title: Combining implicit function learning and parametric models for 3d human reconstruction

authors:
Nenglun Chen
Lingjie Liu
Zhiming Cui
Runnan Chen
Duygu Ceylan
Changhe Tu
Wenping Wang

title: Unsupervised learning of intrinsic structural representation points

authors:
Tinghui Zhou
Philipp Krahenbuhl
Mathieu Aubry
Qixing Huang
Alexei A Efros

title: Learning dense correspondence via 3d-guided cycle consistency

authors:
Nilesh Kulkarni
Abhinav Gupta
Shubham Tulsiani

title: Canonical surface mapping via geometric cycle consistency

authors:
Tristan Aumentado-Armstrong
Alex Levinshtein
Stavros Tsogkas
Konstantinos G Derpanis
Allan D Jepson

title: Cycle-consistent generative rendering for 2d-3d modality translation

venue: In 3DV,

title: Unsupervised cycle-consistent deformation for shape matching

venue: In Computer Graphics Forum,

authors:
Jeong Joon Park
Peter Florence
Julian Straub
Richard Newcombe
Steven Lovegrove

title: Deepsdf: Learning continuous signed distance functions for shape representation

authors:
Lars Mescheder
Michael Oechsle
Michael Niemeyer
Sebastian Nowozin
Andreas Geiger

title: Occupancy networks: Learning 3d reconstruction in function space

authors:
Vincent Sitzmann
Michael Zollhöfer
Gordon Wetzstein

title: Scene representation networks: Continuous 3d-structure-aware neural scene representations

authors:
Ben Mildenhall
Pratul P. Srinivasan
Matthew Tancik
Jonathan T. Barron
Ravi Ramamoorthi
Ren Ng

title: Nerf: Representing scenes as neural radiance fields for view synthesis

authors:
Yang You
Yujing Lou
Chengkun Li
Zhoujun Cheng
Liangwei Li
Lizhuang Ma
Cewu Lu
Weiming Wang

title: Keypointnet: A large-scale 3d keypoint dataset aggregated from numerous human annotations

authors:
Li Yi
Vladimir G Kim
Duygu Ceylan
I-Chao Shen
Mengyan Yan
Hao Su
Cewu Lu
Qixing Huang
Alla Sheffer
Leonidas Guibas

title: A scalable active framework for region annotation in 3d shape collections

venue: ACM TOG,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Angela Dai
Angel X Chang
Manolis Savva
Maciej Halber
Thomas Funkhouser
Matthias Nießner

title: Scannet: Richly-annotated 3d reconstructions of indoor scenes

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

heading: 1 Introduction

text:
With prior knowledge and experience, humans can easily perceive corresponding object parts (e.g., the wings from two different airplanes), understand their shape and appearance variance, in order to distinguish different objects coming from the same category. In computer vision, modeling dense correspondence between 3D shapes in one category is fundamental for numerous applications, such as robot grasping [1, 2], object manipulation [3] and texture mapping [2, 4]. However, existing 3D cameras typically capture raw point clouds of shape surfaces that are arbitrarily-ordered and unstructured, in which correspondences are not established. 3D mesh representation, although is usually parameterized with UV maps that can indicate correspondences, cannot be directly obtained from sensors and needs to be reconstructed from other types of representations, e.g., 2D images [5, 6] or 3D point clouds [7]. In this work, we focus on learning point cloud correspondences, which remains an open challenge since it is infeasible to label ground truth correspondence annotations.
Without ground truth annotations, existing methods mainly discover shape correspondences via seeking a form of canonical space that can associate various instance shapes. For example, in particular shape domains such as human bodies [8] and human faces [9], parameterized shape primitives have been designed to fit the observed raw data and to obtain the correspondences. Such designs, however, cannot be generalized to other categories, e.g., man-made objects [10]. Recently, several part co-segmentation networks relax the requirements of specific parameterized primitives, but instead decompose input shapes into an ordered group of simplest part constitutions [11, 12], in a self-supervised manner. These methods, however, require careful selection of the autoencoder architectures (i.e., they need to be considerably shallow to let the branches only able to represent simple shapes), and the number of part bases. Moreover, such part-based representation does not explicitly provide fine-grained (e.g., point-level) correspondences.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this work, we introduce a novel canonical space where dense (i.e., point-level) correspondences for all the shapes of a category can be explicitly obtained from. Inspired by 3D mesh representation [5, 13, 14, 15] where shapes from one category are represented as deformations on top of a shape primitive, in our work, we set the canonical space as a 3D UV sphere. Our goal is to learn a “point cloud-to-sphere mapping” such that corresponding parts from different instances overlap when mapped onto the canonical sphere. In other words, similar to the mesh representation, a unique UV coordinate can represent the same semantic point/local region of shapes (e.g., the tip of an aeroplane’s wing), regardless of shape variations. Towards this goal, we introduce the canonical point autoencoder (CPAE): we place the sphere primitive at the bottleneck; the encoder non-linearly maps each individual input shape to the sphere primitive, where the decoder deforms the primitive back to match the original shape. We show that with several self-supervised objectives, this autoencoder architecture effectively (1) enforces the input points warped to the surface of the sphere primitives, and (2) encourages those corresponding points from different instances mapped to the same location on the sphere – both guarantee that the network learns correct dense correspondences. Essentially, we do not assume all object shapes in one category having the same topology, e.g., an armchair does not have correspondence on its armrests, with another instance without an armrest. To introduce such uncertainty for correspondence matching, we propose an adaptive Chamfer loss on the bottleneck to allow customized primitive for each instance. As such, we are able to determine if a point on one instance has a correspondence in another point cloud.
One advantage of the proposed method compared to the recent work [12] is that we can learn correspondences even when instances in the training dataset are not aligned, i.e., our model is rotationinvariant within a certain rotation range and does not need to predict an additional rotation matrix as used in [12]. The main contributions of this work are:
• We introduce a novel canonical space – a UV sphere, that explicitly represents dense correspondences of shapes from one category. • With the canonical space on the bottleneck, we design an autoencoder that learns such a “point cloud-to-sphere mapping” via a group of self-supervised objectives. • We apply the proposed method on various categories and quantitatively evaluate on the task of 3D semantic keypoint transfer and part segmentation label transfer, achieving comparable if not better performance than state-of-the-art methods.

heading: 2 Related Work

text:
Deep Learning on Point Clouds. As a flexible and memory efficient representation of 3D shapes, point cloud has been widely studied and combined with deep neural networks. The PointNet [16] solves point cloud classification and segmentation by using MLPs and a max pooling layer to aggregate 3D shape information. One crucial property of the PointNet is that it is able to handle unordered input and is thus invariant to point permutations. In our work, we utilize the first few layers of the PointNet as our shape encoder. Another line of works [17, 18, 19, 20] focus on reconstructing or generating point clouds. The most representative and related to our work is the FoldingNet [17], where a point cloud is first encoded by a graph-based encoder and then reconstructed by sequentially applying the “folding operation” (instantiated by MLPs) to a 2D UV map. In this work, we reveal why the MLPs are able to preserve point order and utilize it as building blocks in our CPAE.
Primitive Fitting. Primitive fitting has a long history in computer vision [21]. Several approaches focus on fitting individual samples with shape priors, such as blocks world [21], generalized cylinders [22], geons [23], Lego pieces [24], qualitative 3D blocks [25], and patches [26]. However, these primitives are analyzed per-instance without order, therefore, cannot be used for the correspondence. Some other approaches focus on fitting over a collection of shapes, which provide ordered set of primitives [11, 27, 28, 29, 30, 31, 32]. However, most of these approaches can only infer part-level correspondences and require additional supervision such as the number of primitives. In this work, we directly learns set-to-set alignment between point clouds, thus requires no shape prior.
3D Dense Correspondence. Given a pair of source and target instance in the same category, 3D dense correspondence learning targets at finding a corresponding point in the target instance for each point from the source instance. Several approaches [33, 34, 35] resolve this task through point cloud registration, using labeled pairwise correspondence as supervision. To relax constraints on supervision, Bhatnagar et al. [36] predict part correspondences to a template via implicit functions. Unfortunately, they require part labels for training. To unsupervisedly learn 3D dense correspondence,
Chen et al. [37] propose a method to learn 3D structure points that are consistent across different instances. However, the model assumes structure similarity among different instances, which ignores intra-class variants and fails to detect non-existing correspondences between dissimilar shapes in the same category. Most relevant to our work, Liu et al. [12] introduce an unsupervised approach that leverages part features learned by the BAE-NET [11] to build dense correspondences. Their algorithm is able to calculate a confidence score representing the probability of correspondence. However, in order to train the implicit function, they require additional knowledge of object surface to compute the occupancy. Moreover, the correspondence learning in [12] heavily relies on the completeness of the part features from the BAE-NET [11], which can lead to incorrect correspondences for parts that BAE-NET cannot separate (e.g., flat surfaces, objects with fine-grained details). In contrast, our approach directly learns dense correspondences from the point cloud with self-supervision.
Cycle Consistency. Our cross reconstruction loss is related to literature that uses cycle consistency as a supervisory signal to learn correspondence without ground truth annotations. Some of these works exploit the consistency among different modalities (e.g., 2D-3D). Specifically, [38] aim to learn cross-instance pairwise correspondence for 2D images using cycle-consistency terms guided by 3D synthetic data. [39] and [40] both leverage cycle-consistency terms to enforce correspondence between a 2D image and a 3D canonical template. Aside from these works that focus on crossmodality, work from [41] is mostly related to ours. They propose a “point-wise” cycle consistency loss that explicitly enforces a point deformed through any cycle of deformations to be mapped back to the origin location. Different from their approach, our consistency is instance-wise and we do not assume bijection mapping among shapes.
3D Deformable Mesh Representations. Our algorithm is also related to methods [5, 13, 14, 15] that represent instance shapes as mesh deformations of a mesh primitive, i.e. a sphere template. Vertices on each instance surface that are mapped to the same locations on the shape primitive are discovered as correspondences. One obvious limitation is that only genus 0 shapes, e.g., birds [5, 13] can be deformed from a mesh sphere. In contrast, ours does not have such restriction thanks to the proposed non-linear mappings, instead of explicit deformation.

heading: 3 Proposed Method

text: In this section, we introduce our end-to-end CPAE for learning dense correspondences from point clouds without ground truth annotation. Given a point cloud SA with individual point p ∈ R3 (see Figure 1), our model: (1) predicts its canonical primitive UA (a “deformed” point cloud with the same number of points as SA), which is supposed to be as close as possible to the canonical sphere in the bottleneck; (2) reconstructs the original input point cloud back from UA. We show that while the first ensures each input point cloud to be warped to the surface of the sphere primitive, the second indirectly encourages the corresponding points from different point cloud instances to overlap during mapping to the primitive. In the following, we first describe our network architecture, i.e., the encoder and decoder modules. We then introduce the adaptive Chamfer loss and the reconstruction losses that are applied to each individual module. Finally, we show that our decoder reconstructs ordered point clouds, i.e., different point cloud instances can fetch their correspondences directly via the point indices, which provides a more accurate inference.

heading: 3.1 Network Architecture

text:
Our method learns two mapping functions: one maps each individual 3D point p ∈ R3 in the world coordinates to the canonical space Φ(p) = u, u ∈ R3, while the other conducts the inverse mapping Φ−1(u) = p. Instead of using a reversible network, we instantiate Φ(·) and Φ−1(·) with two MLPs respectively, and cascade them to construct an autoencoder (i.e., Φ(·) is the encoder and Ψ(·) ≈ Φ−1(·) is the decoder). However, this mapping function cannot be generalized to different point clouds if it only receives the coordinate of a single point p as the input. Therefore, we formulate them as conditional mapping functions by concatenating the input with a shape latent code ZA that represents a unique input shape SA, e.g., Φ(p, ZA), in order to generalize the mapping functions to all instances in the same category.
There are three key modules in the proposed method: (1) a PointNet encoder that produces the shape latent code; (2) an encoder MLP (denoted as canonical mapping) that maps a point cloud to a primitive sphere, and (3) a decoder MLP (denoted as inverse mapping) that deforms the primitive sphere back to the input point cloud.
PointNet Encoder. As shown in Figure 1, given a point cloud SA ∈ Rk×3 with k points, we encode it using a PointNet [16] encoder in a way similar to [8, 18, 19]. Each 3D point of the input point cloud is represented as a 512 dimensional vector using an MLP with 3 hidden layers of 64, 128, 512 neurons and ReLU activations. We then aggregate all point features with max-pooling and a linear layer to generate a global latent code zA ∈ R512. We use PointNet because it produces a robust latent code representing the global shape, which is also invariant to input permutation.
Canonical Mapping Φ(·). To learn the canonical mapping function, we concatenate each point with the global latent code [p, Z] ∈ R515 as input to the MLP, which then outputs a 3D coordinate u ∈ R3 in the canonical space. We construct a sphere point cloud by uniformly sampling a large number of points from a standard sphere mesh, and place them as the canonical primitive at the bottleneck. A Chamfer loss is used to measure the difference between the outputted point u and primitive to encourage the mapped point adhering to the surface (see Eq. (1)).
Ideally, all the mapped instances from the same category should be as close as possible to the canonical sphere primitive. However, an instance may include parts/regions that do not exist in other instances due to intra-class variation, e.g., not all chairs include armrests. With a conventional Chamfer loss, the shapes for objects with rare components do not converge during training, i.e., those rare components are mapped to locations that are far away from the primitive surface. Thus, we relax the bidirectional constraint of the Chamfer loss and allow each instance to produce its own “instance primitive” to some extent (see UA in Figure 1 ). This is formulated via an adaptive Chamfer loss LACD:
LACD(UA, U) = 1 |UA| ∑ p∈UA min q∈U ∥p− q∥2 + α 1 |U | ∑ q∈U min p∈UA ∥q − p∥2 (1)
where α ∼ [0, 1] is an adaptive parameter indicating to what extent the predicted instance primitive should match a canonical sphere, UA and U are the instance primitive and the canonical UV primitive (e.g., a 3D UV sphere), respectively. When α = 1, LACD is equivalent to calculating the conventional Chamfer distance between the unfolded primitive and the canonical UV primitive. During training, α is initialized to 1 and gradually decreased to 0. This allows the canonical mapping to predict instance-aware primitive since the second term of the Chamfer loss no longer constraints the primitive to be consistent with a canonical sphere. In the experiments (see Section 4.5), we show that this design allows us to infer rare object components that have no correspondences in other instances since non-corresponding regions usually occupy a distinct area in the canonical space.
Inverse Mapping Ψ(·). Similarly, we utilize another MLP in the decoder, which receives the concatenation of one point from the bottleneck and the global shape code, i.e., [u, Z] ∈ R515, as the input. The function learns to map it back to its original world coordinate p, which can be fulfilled via a point-to-point reconstruction loss. We leverage an MSE loss LMSE , a Chamfer distance LCD and an Earth Mover Distance (EMD) LEMD between the reconstruction Ŝ and input point cloud P :
Lrec(P, Ŝ) = µ1LMSE(P, Ŝ) + µ2LCD(P, Ŝ) + µ3LEMD(P, Ŝ) (2) where µ1, µ2, µ3 are the weights, and empirically determined, µ1 = 1e3, µ2 = 10, and µ3 = 1.
The inverse mapping bears some resemblance to the principle of FoldingNet [17], which adopts an MLP architecture to map one 2D coordinate together with a global shape representation to the 3D
world1. However, since FoldingNet does not have the forward mapping function as ours and the input points are untraceable, it needs to use Chamfer loss, instead of a point-wise loss (Eq. (2)) as ours.
Align Canonical Mappings via CrossReconstruction. With the encoder and objective function, the canonical mapping is able to map the input points to the surface of the canonical primitive. However, even with the reconstruction loss (Eq. (2)), there is no guarantee that the corresponding points from different shape instances can be overlapped on the sphere – which is the key to learn dense correspondences. For instance, in Figure 1, while SA is mapped to the frontal half of the sphere, it is likely that another shape SB will be mapped to the rear half.
To better align the mapped points, we introduce a cross-structured decoder that leverages: (1) a self-reconstruction branch as presented in Eq. (2), and (2) a cross-reconstruction branch. As shown in Figure 2, we feed the combination of the predicted instance primitive UA of point cloud SA, with the shape latent vector ZB of another randomly sampled point cloud SB to the folding decoder. We then minimize the Chamfer distance between the output shape ŜA→B and SB . The cross-reconstruction loss between the point cloud SA and SB is:
Lcross(SA, SB) = LCD(ŜA→B , SB) (3)
The cross-reconstruction branch ensures even by swapping the predicted primitives UA and UB , the inverse mapping can still reconstruct their own shapes, conditioned on their own shape latent codes. That is, the decoder encourages UA and UB to overlap on the canonical primitive, and thus ensures the network learns correct correspondences.
Relation to Implicit Function. We note that since both mapping functions Φ(·) and Ψ(·) process each input point independently, they can be interpreted as conditional implicit functions, which are widely applied for 3D shape reconstruction [42, 43], view synthesis [44, 45], and recently for self-supervised 3D correspondence [12]. Such an interpretation reveals that the MLPs indeed learn continuous mappings that are feasible for interpolations, e.g., once the decoder MLP is learned, it is able to map any point on a continues sphere surface that is not necessarily among the mapped input u, to the world coordinate. E.g, one can sample points densely from the surface of the sphere to reconstruct a continuous surface or a 3D mesh.

heading: 3.2 Finding Correspondences from Ordered Point Clouds

text:
In this section, we show that the CPAE is able to generate ordered point clouds (see the output point clouds in Figure 1). Compared to the methods obtaining correspondences by directly tracing overlapped points from the canonical space, our model that makes use of ordered output point cloud generates more accurate results during the inference stage.
Reconstruction of Ordered Point Clouds. We show that an MLP [17] decoder preserves the order of points in the canonical primitives (shown as colored points within the sphere), when mapping them back to individual shapes. Given two adjacent points UA and UB from the sphere, we denote pA = Ψ(UA, Z) and pB = Ψ(UB , Z) as their mapped points in the output space, where Z is the latent shape code. Since Ψ(·) contains only linear projections and ReLUs (i.e., piece-wise linear), it is easy to be proved as a continuous function. As such, pA and pB will also be close to each other, e.g., in Figure 1, the output shape exhibits a smooth transition of color map similar to the colored canonical shape on the sphere. Thus, the order is maintained as opposed to being shuffled in the output space.
Inference via CPAE. Given a source shape SA and a query point pA ∈ SA, we target at searching the correspondence of the query point in a target shape SB . We first compute the shape latent vectors for the two shapes as zA and zB . The query point is then mapped to a point uA in the canonical space by the canonical mapping encoder. By feeding the concatenation of uA and zB to the inverse
1Unlike our method, it utilizes and samples points from a standard 2D UV map instead of a 3D sphere.
mapping decoder, we further map uA to a point pA→B on the reconstructed target shape SA→B . The correspondence of pA (denoted as pB ∈ SB) is thus the closet point on SB to pA→B .
Confidence of Correspondence. For each point and its correspondence pair (e.g. (pA, pB)), we can also compute a confidence score C(pA, pB) to measure the confidence of this mapping:
C(pA, pB) = 1−D(pA, pB) (4)
where D refers to the normalized Euclidean distance between pA and pB in the 3D world coordinate. Similar to [12], if C is lower than a pre-defined threshold τ , we conclude that point pA does not have a correspondence on shape SB .

heading: 4 Experiments

text: In this section, we present evaluations of the proposed dense correspondence learning approach. To the best of our knowledge, there is no benchmark that provides ground-truth dense correspondences for general objects, which is exactly our motivation to learn dense correspondence with self-supervision. However, thanks to the learned dense correspondences across pairs of instances, we are able to carry out the task of 3D semantic keypoint transfer and part segmentation label transfer to evaluate the proposed method as in [12]. In the following, we first introduce our experimental setup as well as baselines. We then report quantitative and qualitative comparisons with these baselines for 3D semantic keypoint transfer and part segmentation label transfer. We further present ablation studies to demonstrate the contribution of each component in the proposed model. Finally, we show that our model can generalized to real scanned point clouds unseen in the training stage. More results can be found in the appendix.

heading: 4.1 Experimental Setup

text:
Dataset. We carry out the semantic keypoint transfer task on the KeypointNet dataset [46] as the BHCP benchmark used in Liu et al. [12] is not publicly available. Compared to the BHCP benchmark, the KeypointNet dataset is more challenging because: (a) it contains diverse objects and comes with large-scale annotations, (b) it is template-free and annotated by a large group of people, thus is less biased compared to the keypoints in the BHCP benchmark, which are from predefined templates. For the part segmentation label transfer task, we use the ShapeNet part dataset [47] as in [12]. For both datasets, we use the split provided in the original paper, and generate all pairs of shapes in the testing set as our testing pairs. To avoid interference from non-existing correspondences, we leave
out instance pairs that do not share the same keypoint or part label. In all experiments, including our method and the baselines, we use a validation set for model selection.
Baselines. We evaluate the proposed method against state-of-the-art learning-based 3D dense correspondence prediction approaches, including AtlasNetV2 [18], FoldingNet [17], and Liu et al. [12]. Specifically, FoldingNet deforms from a fixed UV grid, while AtlasNetV2 explicitly allows the shape to be deformed from learnable elementary 3D structures. Neither of them estimates the confidence of correspondences. Liu et al. [12] propose a method that utilizes part features learned by the BAE-NET [11] to learn dense correspondence, including a mechanism that estimates the correspondence confidence.
Implementation Details. For both the point canonical mapping encoder and point inverse mapping decoder (see Figure 1), we follow [18] and use a three-layer MLP with ReLU activations, BatchNorm layers except for the last layer, where we use a hyperbolic tangent activation to obtain the final output. The training phase of our approach consists of two stages: (1) A pre-training stage trained with LACD (Eq. 1) and Lrec (Eq. 2) using α = 1 for LACD (2) A fine-tuning stage trained with LACD, Lrec, and Lcross (Eq. 3) where we set α = 0 for LACD. The total loss is formulated as Ltotal = ω1LACD+ω2Lrec+ω3Lcross, where ω1 = 10 for the pre-training stage; 20 for fine-tuning stage, ω2 = 1, ω3 = 10. For all experiments, we set k = 2048, τ = 0.9 (see Section 3.2), and the parameters of the network are optimized using the Adam [48] optimizer, with a constant learning rate of 1e−4.

heading: 4.2 3D Semantic Keypoints Transfer

text: For fair comparisons, we follow [12, 37] and compute the distances from transferred keypoints to ground truth keypoints and report the percentage of testing pairs where the distances are below a given threshold in Figure 3. We demonstrate that for 11 out of 12 categories (e.g. airplane, chair, mug, etc.), keypoints transferred via our learned correspondence are more accurate than other methods [12, 17, 18]. At the distance threshold of 0.05, our method performs 11.2% more accurately than Liu et al. [12] on average of all categories. Figure 3 demonstrates the qualitative results of the keypoint transfer task. Even for categories with large intra-class variation, e.g. bathtub, motorcycle, or vessel, our method is able to transfer keypoints accurately thanks to the learned dense correspondence.

heading: 4.3 Part Segmentation Label Transfer

text: We further validate our approach on the part label transfer task and present quantitative results in Table 1 and qualitative results in Figure 5. Note that the settings are different from that of Liu et al. [12], which directly utilizes the branched co-segmentation results for evaluation (thus different quantitative results between the Table 1 and that in their paper). In Table 1, we show the intersectionover-union (IoU) between transferred and ground truth part labels. Our method performs better than Liu et al. [12] in 12 out of 15 categories and has a higher average IoU. For categories with large intra-class variations, such as lamps, motorbikes, our approach significantly outperforms Liu et al. [12]. The performance difference is most likely due to the branched co-segmentation [11] adopted by Liu et al. [12]. Branched co-segmentation relies heavily on the size of training data available. Such an approach is vulnerable to large shape variations [11], and is unable to segment flat surfaces. Moreover, its performance is sensitive to the pre-defined number of branches. Instead, our method naturally links different instances through a canonical primitive and is thus more robust to large shape variations. We show the qualitative results in Figure 5. Thanks to the dense correspondence learned by the proposed method, we are able to transfer small parts more accurately such as the seat of a motorcycle (the green points) and the pipe of a lamp (the purple points) comparing to Liu et al. [12].

heading: 4.4 Correspondence Confidence

text:
Given a source shape SA and a target shape SB , for every point q ∈ SB , our model computes a confidence score indicating whether its corresponding point exists in SA, as discussed in Section 3.2. As annotations can be biased by the annotator’s definitions on keypoints, there is no absolute groundtruth for non-existence label between a shape pair. Thus, we visualize the confidence score as heatmaps for multiple target shapes in the airplane category in Figure 6 and compare with Liu et al. [12]. As shown in Figure 6, the proposed method is able to produce a more fine-grained confidence score compared to Liu et al. [12]. This is because our approach explicitly evaluates the confidence of
correspondences at a more fine-grained level – the distance between points, instead of a distance at the part-level, as proposed in [12].

heading: 4.5 Ablation Studies

text:
Effectiveness of cross-reconstruction. The cross-reconstruction architecture is designed to ensure that corresponding points overlapping as much as possible on the canonical space. In our experiments, we find that with the datasets containing shapes with aligned 6D poses [10, 46], a single branch encoder-decoder framework (i.e., w/o Lcross) already produces a reasonable prediction of correspondences. However, as shown in Figure 7 (red vs blue), our cross-reconstruction framework significantly improves the performance with a large margin.
In addition, we validate the effectiveness of the framework on un-aligned shapes, by rotating the input point cloud with radian noise N (0, 0.52). We note that all co-segmentation approaches assume that the pose of input shapes are consistently aligned [11, 12]. Consistent with the assumption, such rotation severely degrades the performance of Liu et al. [12] (brown line). In contrast, with the help of cross-reconstruction loss (orange line), our model is rotation-invariant to a certain degree.
Effectiveness of adaptive Chamfer loss. To show that the adaptive Chamfer loss is necessary, we train our model with constant α = 0 and α = 1, respectively. The results are shown in Figure 7. When α is set to zero consistently, the primitive would eventually condense to a single point in the canonical space, therefore, significantly hurts the performance (pink line). On the other hand, if α = 1, it is equivalent to enforcing a single canonical primitive for all instances by encouraging the
primitive to cover the entire canonical space. This ignores the intra-class variation and deteriorates the performance as shown in Figure 7 (green line).
Using a 2D UV grid vs. 3D UV sphere as a primitive. To analyze the effect of different canonical UV primitives, we further train our model using a 2D UV grid instead of a 3D UV sphere. Figure 7 shows that parameterizing the canonical space with a 3D sphere quantitatively outperforms a 2D grid (grey line). The main reason is that the sphere is continuous at any point while a 2D grid is discontinuous at boundaries.

heading: 4.6 Testing with Real Scanned Data

text: To demonstrate that our model is robust to the domain gap between real and synthesized 3D objects, we apply our model to the real scanned objects. Specifically, we train our network on the KeypointNet dataset and test the trained model on real scanned point clouds from the ScanNet dataset [49]. As the ground truth keypoints or semantic part annotations in ScanNet are unavailable, we show the qualitative results in Figure 8. Although our model is only trained using synthesized data, it successfully predicts the correspondence and transfers keypoints from the source to the target shape.

heading: 5 Conclusions

text: In this work, we propose a self-supervised model, CPAE, that learns dense correspondence between 3D shapes in the same category. We introduce a canonical UV sphere, where dense correspondence for all the shapes can be explicitly obtained from. The key is to learn a 3D world coordinate to canonical space mapping, so that points from different instances are regarded as a pair of correspondences if they overlap on the sphere. We fulfill it through an autoencoder equipped with an adaptive Chamfer loss in the bottleneck, and a cross-reconstruction structure in the decoder. Experimental results validate the proposed method performs favorably against state-of-the-art schemes in various tasks and ablations. We show that our model is much more robust to rotation than the existing approaches that are non-rotation invariant by design. The task of learning rotation-invariant representations for 3d dense correspondence is challenging and still far from being solved. In future, we plan to extend our work to handling larger rotations.

heading: Acknowledgements

text: This work was supported in part by the MOST, Taiwan under Grants 110-2634-F-007-016, MOST Joint Research Center for AI Technology, All Vista Healthcare, and NSF CAREER grant 1149783. We thank National Center for High-performance Computing (NCHC) for providing computational and storage resources.

title: Learning 3D Dense Correspondence via Canonical Point Autoencoder