Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper derives a probabilistic convergence rate of the estimator obtained by the iterative Tikhonov regularization scheme when the hypothesis space is a Hilbert space within which lies the target function.
The analysis relies on the specific type of generalized self concordant losses, as well as some source and capacity conditions.
Through links with the theory of spectral filtering, optimal rates are given when the estimator does not saturate, showing that the iterative regularization scheme provides benefits for a certain class of problems.
Due to the iterative nature of the regularization scheme, an analysis of the error propagation at each iteration is also included, allowing to solve each problem with less and less precision while keeping statistical guarantees.
Numerical experiments on a toy dataset complete this study, showing the accurateness of the predictions.

main_review: -Originality:
The contribution is original, as it extends previous results for Tikhonov regularization and GSC losses to iterative Tikhonov.
Related work is appropriately cited, and the contributions are clearly stated.

-Quality:
The submission is of high quality. It is technically sound, claims are supported by appropriate mathematical proofs as well as an illustrative numerical study.

Q1: The assumption on the label space Y is very weak (Borel), how could the dimensionality of Y affect the convergence rate of the learning process ?

Q2: The assumption of the target function belonging to the Hilbert space is crucial for the proof as it relies on the geometry of that space, could it be weakened (similarly to the kernel ridge regression case where the target function can be anywhere from the RKHS to L2) to only keep a modified source condition that would characterize alone the smoothness of the target function ?

Q3: In practice, the number of iterations to perform is unknown as we do not have access to the true source condition, how could one set it given a specific dataset ?

-Clarity:
The submission is very well written. A special effort has been made to make the bounds understandable and relatable to previous works, which makes the reading enjoyable.

-Significance
Iterative regularization is an active topic in statistical learning, and the paper offers novel theoretical insights associated to this scheme, representing a significant contribution for the area.
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper the authors study methods for minimizing excess expected risk. More specifically, they show how to use an iterated Tikhonov regularization scheme, which is well-known for least squares, for losses which are generalized self concordant (GSC). By doing so, they go beyond some of the limitations of the standard Tikhonov regularization.
main_review: Overall the authors present an interesting method for minimizing expected error for generalized self concordant losses. My main concern is regarding differentiating this work from Marteau-Ferey et al. [1]. This deserves an extended discussion to make more apparent the novelty of the current works' contributions, including a more in-depth overview of the difference between the previously-used Tikhonov regularization, and the newly introduced iterated Tikhonov regularization scheme, as the improvements seem to be somewhat incremental. For example, it would help to include an overview of the specific results achieved by Marteau-Ferey et al. to more directly contrast with the new guarantees in this paper.

======Comments======

Generalized self concordance is defined differently in [2] (there, the generalization comes from varying the exponent on the second-derivative term). It would therefore be helpful to provide a comment distinguishing between the two notions of generalized self concordance.

The authors should be made aware of, and include a reference to, Carmon et al. [3], which uses a ball oracle (related to the prox method) for optimizing quasi self concordant losses (a special case of generalized self concordance losses).

"various set of" -> "various sets of"

"other examples when" -> "other examples include when"

"obtain fast learning rate" -> "obtain fast learning rates"

"While Thikonov" -> "While Tikhonov"


[1] U. Marteau-Ferey, D. Ostrovskii, F. Bach, and A. Rudi. Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance. In Conference on Learning Theory (COLT), 2019.

[2] T. Sun and Q. Tran-Dinh. "Generalized self-concordant functions: a recipe for Newton-type methods." Mathematical Programming 178, no. 1 (2019): 145-213.

[3] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y.T. Lee, A. Sidford, and K. Tian. "Acceleration with a Ball Optimization Oracle." Advances in Neural Information Processing Systems 33 (2020).

=======================================

After reading the authors' response, I appreciate the added clarity in differentiating from Marteau-Ferey et al. [1], and so I have adjusted my score accordingly.
limitations_and_societal_impact: Yes, they state that the contribution is purely theoretical.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider supervised learning problems based on generalized self-concordant (GSC) loss functions and iterated Tikhonov regularization scheme. Unlike the least-squares loss, there is no closed-form expression of the estimator induced by the GSC loss, which makes the generalization error analysis much more complicated. This paper shows that the proposed algorithm can overcome the limitation for GSC functions and achieve optimal learning rates.
main_review: The iterative regularization has a higher qualification compared to the conventional Tikhonov regularization scheme, which can overcome the so-called saturation effect. An important and interesting question is to investigate supervised learning problems associated with iterated Tikhonov regularization and generalized self-concordant (GSC) loss functions which are three times differentiable with their third derivative being bounded by the second derivative (e.g. logistic loss). In this paper, the authors investigate the benefit of iterated Tikhonov regularization in learning algorithms associated with GSC loss and show that the proposed method can still achieve optimal learning rates even when the index of the source condition is large. Sufficient conditions are also given for the computation of the proposed estimator in practice. Overall, the paper is well-written and technically sound, which provides new insights for the error analysis of estimators without closed-form expression. I was wondering if the boundedness of $\theta^*$ is required in the proof. In binary classification, the minimizer of the expected risk associated with logistic loss is usually unbounded (that is, $\theta^*=\ln\frac{\eta}{1-\eta}$ with $\eta(x)=P(Y=1|X=x$)).
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study a supervised learning method called iterative Tikhonov (IT) regularization where the loss function is a generalized self-concordant function. The method is a proximal point algorithm: 
- minimize (empirical loss) + (squared Euclidean distance from the previous iterate), 

run for t iterations. The authors show that their method (IT) achieves optimal excess risk in interesting regimes of signal smoothness (r) and difficulty of the loss function (\alpha).

They show the benefit of running multiple iterations of the proximal point algorithm when the signal is smooth. They also analyze their method when the proximal step has some optimization error.

main_review: The authors discuss relevant works appropriately. They explain their definitions and assumptions. The manuscript is well-structured. 

I have a few questions and comments.

1. What does Theorem 1 yield as t goes to \infty? As t goes to Infinity we should get the unregularized estimator, but the theorem gives good rates. In the statement of Theorem 1, please explicitly point to the assumptions you are making.

2. Line 235, why is the first term called bias? 

3. In Assumption 9 in the supplement, there is a lower bound on df_\lambda, but it is not present in the main paper. Can you please address the discrepancy, for my understanding?

Minor:
- Line 122: \theta* is the true signal, but here it is called the estimator
- Explain the [h,h] and [k,h,h] notation in the self-concordance condition
- Regarding Definition 4, for Tikhonov regularization, isn't q=1, not just ½? What are $\omega_\nu$ and $\kappa$?
- In Assumption 2, in the end, it should be $\theta,$ not $\theta^*$
- Line 226: should there be a 1/n in front of the summation?
- Line 282: self-reference to Prop. 2
- After line 299: y should be z

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper analyzes an iterative L2/Tikhonov regularization scheme for statistical learning with general self-concordant losses. All reviewers agree that the paper is technically quite interesting and well-executed, and I believe it will make a nice contribution to the conference program. 

Please add the discussion comparing to Marteau-Ferey et al., to the final version, as this was quite helpful for clearing up some confusions in the discussion phase. 
Decision: Accept (Spotlight)