acceptodds
Under review as a conference paper at ICLR 2027

Implicit Regularization of Bregman Proximal Point Algorithm on Separable Data: Sharp Alignment Bounds and Kullback-Leibler Geometries

Abstract

The Bregman proximal point algorithm (BPPA) has witnessed emerging machine learning applications such as knowledge distillation, policy optimization and fine-tuning, where the divergence is a design choice whose effect is not understood. We study this effect for linear classifiers trained on separable data with the exponential loss. The loss then vanishes along infinitely many directions, so the algorithm alone selects the classifier, which we judge by its margin. We first bound the margin by the alignment between the steps of the iterates and of their mirror images, which follow the negative gradient. If the alignment in a chosen norm stays above a constant and the divergence satisfies mild growth and curvature conditions, BPPA attains at least that constant times the maximum margin in that norm. The bound needs no strong convexity and recovers the condition-number bound of earlier work. It is tight: for every quadratic divergence and every norm, a one-point dataset attains the constant exactly. We then study two Kullback-Leibler (KL) geometries where the alignment has no positive lower bound, arising in exponentiated gradient and self-distillation. With KL on the parameters, for every constant stepsize the normalized -margin converges to its maximum, a discrete counterpart of a known mirror-flow result, whereas the Euclidean divergence selects the maximum -margin classifier. With KL on the predictions, when the samples are linearly independent and each proximal step is solved by gradient descent, BPPA converges in direction to the minimum-norm interpolator of the labels, a discrete analogue of a known natural-gradient-flow result. This limit maximizes the -margin if and only if every sample lies on the margin. Results for strongly convex and smooth divergences extend to mirror descent, and numerical experiments illustrate each result.

Primary area:
learning theory
Keywords:
Bregman proximal point algorithm, implicit bias, max-margin classification, mirror descent

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_beMEOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper aims to study what kind of "simple" solutions does a Bregman proximal-point algorithm produce for linear models with an exponential loss. The authors don't say it explicitly, but this typically occurs in Poisson regression, but Poisson regressions typically have a linear term.

Critical strengths

I was not able to find any strengths, unfortunately.

Critical weaknesses

For me personally the paper was very hard to follow. Filled with lemmas with a lot of cryptic letters and formulas, and symbols, carrying little meaning either geometrically or algebraically. The paper is simply unreadable for me.

The definition of the margin at the beginning, Defn 2.1, was simple. The motivation to the study of the exponential loss needs to be explained. It's not exactly Poisson regression per se. The theoretical study of this setting needs some motivation which is not obvious.

But starting from definition 3.1 the cryptic symbols begin. Why the weights in cˉT\bar{c}_T were chosen the way they were? Why use ratios? What is the motivation behind this definition?

In proposition 3.3 - what is the referred-to null-set?

In Proposition 3.6, item (2) appears to be a proof of linear convergence. It itself probably needs mentioning (contracting a loss by a constant factor), but on the other hand, the loss is exponential so it's not very meaningful. In any case, an explanation of the impact of the results is required.

And it continues on and on throughout the paper. Just a bunch of propositions with a lot of letters, definitions, and results, without explaining their meaning, impact, or giving the readers any insight.

The paper needs a serious revision before publishing, remembering that we write for humans.

Questions for authors

NA

Hard to ask questions about something so hard to follow.

4 comments
AuthorsOpenReview ↗

Response to Reviewer beME (Part 1)

We thank the reviewer for the review, and respond to the weaknesses and questions in the following.

[W1] Setting and motivation: The motivation for studying the exponential loss is not explained, and the setting resembles Poisson regression.

The paper studies binary classification with linear models on linearly separable data. This differs from Poisson regression: the labels are ±1\pm1, and the exponential loss is used as a classification loss. The exponential loss is the standard choice in this line of work [1-5], and we use it to keep the presentation simple. As for the motivation, on separable data, the loss can be driven to zero along infinitely many directions, so the optimization algorithm itself decides which classifier is returned. This selection is called the implicit bias, and separable classification with an exponentially-tailed loss is the standard setting in which it is studied. It arises in the over-parameterized regime with respect to the number of data points nn and the model dimension dd, and its characterization helps to understand the generalization of over-parameterized networks. We characterize the classifier selected by the Bregman proximal point algorithm and how this implicit bias depends on the divergence. The paper states this motivation in the introduction (lines 53–78) and the setting in Section 2 (lines 134–141).

[W2] Definition 3.1: Why are the weights in cˉT\bar c_T chosen this way, why are ratios used, and what motivates the definition?

cˉT\bar c_T is the weighted average of the alignments ctc_t over the first TT steps,

cˉT=∑t<Tct rt ∥Δt∥∑t<Trt ∥Δt∥,\bar c_T=\frac{\sum_{t<T}c_t\,r_t\,\|\Delta_t\|}{\sum_{t<T}r_t\,\|\Delta_t\|},

where ctc_t is the cosine similarity between the primal update and the dual update of step tt, ∥Δt∥\|\Delta_t\| is the length of the step, and rtr_t is the ratio of consecutive losses.

This quantity appears in the lower bound on the margin and simplifies the proof. Proposition 3.2 gives min⁡i⟨θT,zi⟩≥−log⁡n+γ∑t<Tct rt ∥Δt∥\min_i\langle\theta_T,z_i\rangle\ge-\log n+\gamma\sum_{t<T}c_t\,r_t\,\|\Delta_t\|, in which step tt enters with the weight rt∥Δt∥r_t\|\Delta_t\|, and this is why these weights are used. Dividing by ∥θT∥\|\theta_T\| gives

min⁡i⟨θT∥θT∥,zi⟩ ≥ −log⁡n∥θT∥+γ cˉT ∑t<Trt ∥Δt∥∥θT∥.\min_i\Big\langle\frac{\theta_T}{\|\theta_T\|},z_i\Big\rangle\ \ge\ -\frac{\log n}{\|\theta_T\|}+\gamma\,\bar c_T\,\frac{\sum_{t<T}r_t\,\|\Delta_t\|}{\|\theta_T\|}.

As ∥θT∥→∞\|\theta_T\|\to\infty and the steps become small, the first term vanishes and the last ratio is asymptotically at least one, so the normalized margin is at least γ cˉT\gamma\,\bar c_T in the limit. Since cˉT\bar c_T is what remains in the final result, we give it a name, which simplifies and unifies the statements.

It also connects this inequality with the theorems. The alignment condition gives a lower bound cwc_w on cˉT\bar c_T, where cwc_w is the alignment constant that appears in the margin guarantee of Theorem 3.5 and is shown to be tight for quadratic divergences.

We have added this explanation after Definition 3.1 (lines 184–186).

[W3] Proposition 3.3: What is the null set?

The null set accounts for distance-generating functions that are not strongly convex. It allows the lower bound λ(θ)\lambda(\theta) on the Hessian to vanish at some points, as long as these points form a set of measure zero, and this does not affect the conclusion that the alignment constant cwc_w is positive. Thanks to this assumption, the result can handle radial powers such as 1p∥θ∥2p\frac1p\|\theta\|_2^p, whose Hessian vanishes at some point (Example 3.4).

AuthorsOpenReview ↗

Response to Reviewer beME (Part 2)

[W4] Proposition 3.6(2): Item (2) appears to be linear convergence of the loss, which is not very meaningful for an exponential loss, and the impact of the results needs explanation.

Proposition 3.6(2) shows that, with adaptive stepsizes, each proximal step contracts the loss by a constant factor. However, this contraction is not a consequence of the exponential form of the loss. It comes from the convexity of the loss, which gives the one-step inequality

L(θt+1)≤L(θt)−Dt2ηt,Dt=Dw(θt,θt+1)+Dw(θt+1,θt).\mathcal L(\theta_{t+1})\le\mathcal L(\theta_t)-\frac{D_t}{2\eta_t},\qquad D_t=D_w(\theta_t,\theta_{t+1})+D_w(\theta_{t+1},\theta_t).

Then, by the inequality ex≥1+xe^x\ge 1+x, we get L(θt+1)≤L(θt)exp⁡(−Dt2ηtL(θt))\mathcal L(\theta_{t+1})\le\mathcal L(\theta_t)\exp\big(-\frac{D_t}{2\eta_t\mathcal L(\theta_t)}\big). By the bound Dt≥4γ2Lwηt2L(θt+1)2D_t\ge\frac{4\gamma^2}{L_w}\eta_t^2\mathcal L(\theta_{t+1})^2, we further get

L(θt+1)≤L(θt)exp⁡(−2γ2Lw ηtL(θt) rt2),rt=L(θt+1)L(θt).\mathcal L(\theta_{t+1})\le\mathcal L(\theta_t)\exp\Big(-\frac{2\gamma^2}{L_w}\,\eta_t\mathcal L(\theta_t)\,r_t^2\Big),\qquad r_t=\frac{\mathcal L(\theta_{t+1})}{\mathcal L(\theta_t)}.

This also holds in the proof for constant stepsizes. We observe that ηt\eta_t and L(θt)\mathcal L(\theta_t) appear together as a product. If this product is set to αt\alpha_t, i.e., ηt=αt/L(θt)\eta_t=\alpha_t/\mathcal L(\theta_t), we get rt≤exp⁡(−2αtγ2Lwrt2)r_t\le\exp\big(-\frac{2\alpha_t\gamma^2}{L_w}r_t^2\big). This implies that rt=L(θt+1)/L(θt)r_t=\mathcal L(\theta_{t+1})/\mathcal L(\theta_t) is at most a factor q(αt)<1q(\alpha_t)<1. This contraction does not rely on the explicit form of the exponential loss. It uses only the convexity of the loss, the inequality ex≥1+xe^x\ge 1+x and the bound on DtD_t. The result thus shows how to choose the stepsizes so that the loss contracts. The same argument can also be considered for other losses with an exponential tail. The exponential loss itself is the standard choice for linearly separable data, as discussed in [W1]. We have added this discussion after Proposition 3.6 (lines 273–275).

[W5] Readability: The paper is hard to follow, with many symbols and propositions whose meaning and impact are not explained.

We have revised the presentation at the places the reviewer points to, and where the same issue arises. The results and their proofs are unchanged. The revision adds short explanations and simplifies some statements, and all changes are highlighted in the revised version.

In the introduction and Section 2, we add why separable data and the exponential loss are studied (see [W1]), and the loss is stated once so that the theorems do not repeat it. In Section 3, Definition 3.1 and Condition 3 are each followed by a sentence on what the quantity is for and what it gives (see [W2]), and Proposition 3.2 is stated without auxiliary quantities. The assumptions of Theorem 3.5 are stated as a separate condition, with a sentence on what each case allows. Proposition 3.6 (accelerated rates) states the convergence results for each stepsize, together with a discussion of the loss contraction (see [W4]). Theorem 3.8 states clearly that Theorem 3.5 (implicit bias under alignment) is sharp. In Section 4, we explain the motivation and the role of each proof step in more detail. In Section 5, we add a discussion of why the solution of the proximal step has to be selected in this setting. In Section 6, we add the setting and the takeaway of each experiment.

References

[1] Soudry, Hoffer, Nacson and Srebro. The implicit bias of gradient descent on separable data. ICLR, 2018.

[2] Gunasekar, Lee, Soudry and Srebro. Characterizing implicit bias in terms of optimization geometry. ICML, 2018.

[3] Lyu and Li. Gradient descent maximizes the margin of homogeneous neural networks. ICLR, 2020.

[4] Ji and Telgarsky. Characterizing the implicit bias via a primal-dual analysis. ALT, 2021.

[5] Wang, Hu, Muthukumar and Abernethy. Faster margin maximization rates for generic optimization methods. NeurIPS, 2023.

AuthorsOpenReview ↗

Approaching the end of the discussion period

Dear Reviewer beME,

Thank you again for your review. We have discussed the points you raised and answered the question about the setting. We have also made a dedicated revision of the presentation. As the discussion period ends soon, we wonder whether we have addressed your concerns, and whether any question remains.

Best regards,
The authors

This addresses some of my concerns, but my main readability concern stays - it's a very terse and compressed bulk of symbols, indices, definitions, letters and various cases. I do understand that there's an underlying theme - the margin the direction of the parameters converges to, but it's simply extremely hard to read. Perhaps such a paper doesn't even fit the ICLR short paper format, and should have been a JMLR paper, or alternatively, reduced in scope and made more focused. The concerns are impossible to address with a small diff. I do not believe readers of this papers will be able to learn something from it.

Reviewer_dV3VOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the implicit bias of exact Bregman proximal point iterations for separable linear classification with exponential loss. It derives a margin lower bound from primal-dual step alignment, obtains an exact worst-case constant for quadratic geometries, and sharpens earlier finite-time bounds. Separate analyses establish l1 maximum-margin convergence for parameter-space KL and minimum-norm label interpolation for prediction-space KL under independent samples and a specified inner-solver selection.

Critical strengths
  1. The alignment/path-length formulation is clear, and the exact quadratic construction identifies the worst-case geometric factor precisely. The sharper finite-time bounds and removal of global strong convexity in Theorem 3.5 are genuine improvements over Li et al. (2021).

  2. Theorem 4.2 is the strongest technical contribution: the multiplicative-weights potential and dual-clock argument establish discrete KL-BPPA convergence for every fixed positive stepsize, including support persistence. This is a substantive extension of the known continuous-time result.

Critical weaknesses
  1. My main concern is the magnitude of the advance over the closest literature. Li et al. already establish the condition-number margin guarantee, its sharpness up to a constant, the Mahalanobis limit, and the benefit of adaptive stepsizes. The exact Euclidean quadratic factor improves the earlier guarantee by at most a factor of two and uses the classical Kantorovich angle inequality. The two KL limits are discrete counterparts of known biases from Pesme et al. and Kerekes et al. The discrete proofs and improved rates add value, but the paper offers relatively limited new qualitative understanding of which classifier is selected. Moreover, uniform alignment is zero for the headline KL cases, so these require specialized analyses outside the general alignment guarantee.

  2. The scope of the new KL results leaves their broader implications uncertain. Parameter-space KL has no pointwise margin-convergence rate or inexact-solve guarantee. Prediction-space KL requires full row rank and exact proximal minimizers selected by Euclidean gradient descent; its parameter-space conclusion therefore depends on the solver selection as well as the divergence. The main numerical examples appropriately verify these restricted constructions, but do not resolve those scope limitations. Appendix H also uses 800 epochs for BPPA versus 200 for SGD, so the reported gain does not isolate the effect of the geometry at equal total training budget.

Questions for authors
  1. Can the authors give a nonquadratic, nonhomogeneous geometry for which Theorem 3.5 yields a new informative prediction beyond existing homogeneous-potential or horizon-based analyses?

  2. Can the integrated-gap analysis in Theorem 4.2 yield a pointwise margin-convergence rate or a finite-iteration criterion for approaching the l1 maximum margin?

  3. What conditions on finite inner-solver error preserve the KL conclusions? For Theorem 5.3, how does the selected limiting direction change with another inner optimizer, such as preconditioned gradient descent?

4 comments
AuthorsOpenReview ↗

Response to Reviewer dV3V (Part 1)

We thank the reviewer for the review, and respond to the weaknesses and questions in the following.

[W1] Magnitude of the advance: The advance over the closest literature is limited. The condition-number guarantee, its sharpness, the Mahalanobis limit and the adaptive stepsizes are known, the KL limits are discrete counterparts of known flow results, and the KL cases fall outside the general alignment guarantee.

As for the advance over the closest literature, the contribution of this work is the characterization of the implicit bias of BPPA. The results of Section 3 are part of this contribution, and they are better not read as a comparison with a separate work. We have revised the presentation of Section 3 accordingly. Briefly, the contributions of Section 3 consist of the convergence of the loss, the margin guarantee, and the acceleration of the margin convergence by adaptive stepsizes. The alignment constant places these results in one framework and extends them to divergences without strong convexity (Theorem 3.5). For quadratic divergences, the same framework gives a tight result, with an exact characterization of the margin (Theorem 3.8).

As for the relation to the flow results, a discrete algorithm is harder to analyze than its continuous-time limit, and its behavior can differ from it, because the stepsize affects the solution. For example, Nesterov's accelerated gradient method and gradient descent with momentum coincide as the stepsize tends to zero, but with a non-negligible stepsize they behave differently, and Nesterov's method has a better complexity on certain classes of problems [1]. Likewise, SGD with a constant stepsize may not converge, whereas it converges when the stepsize tends to zero. Passing from continuous time to the discrete algorithm can therefore change the conclusion, and a result for the flow does not imply one for the algorithm. Moreover, the two works mentioned analyze the mirror flow and the natural gradient flow, and not BPPA. Beyond the discretization, BPPA is an implicit scheme: each step is defined through the gradient at the next iterate and requires solving a minimization problem, which has no counterpart in the flow. We prove our results for BPPA with a constant stepsize. For the KL divergence on the parameters, the geometry is neither strongly convex nor uniformly well conditioned, and the alignment between the primal and dual steps cannot be controlled. Our proof instead analyzes the iterates through a multiplicative-weights potential. In terms of qualitative understanding, our results establish, for the discrete algorithm, that the divergence affects which classifier BPPA selects.

As for the specialized analyses, our analyses serve the core question of the paper, which is whether the divergence affects the implicit bias of BPPA. The alignment guarantee covers a wide class of divergences for which one uniform argument works, and the KL cases lie at its boundary. The three analyses share the same starting point in the dual space: by the optimality condition, the dual iterate moves along the negative gradient for every divergence. They differ in how the mirror map relates this dual trajectory to a primal direction. For a well-conditioned geometry, it roughly preserves angles, which gives the alignment guarantee. For the KL divergence on the parameters, its inverse is a coordinatewise exponential, which concentrates the mass on the coordinates with the largest dual variable and leads to the ℓ1\ell_1 geometry. For the KL divergence on the predictions, it depends on the parameters only through the logits, in which the dynamics can be solved exactly.

AuthorsOpenReview ↗

Response to Reviewer dV3V (Part 2)

[W2] Scope of the KL results: The parameter-space KL result has no pointwise margin rate and no guarantee for inexact solves, the prediction-space result requires full row rank and a specific inner solver, and Appendix H uses 800 epochs for BPPA against 200 for SGD.

For the KL results, Theorems 4.2 and 5.3 establish the convergence of the margin for BPPA with the KL divergence, together with finite-time bounds on the loss. For the KL divergence on the parameters, a pointwise rate for the margin is harder, because the geometry is neither strongly convex nor uniformly well conditioned, and we do not have a finite-time rate of the kind proved in Section 3. As mentioned in W1, the alignment is not bounded below in the KL cases, so we analyze them with dedicated techniques that still start from the dual space, and we characterize the limiting direction and its margin.

As for full row rank, it is the standard situation in the over-parameterized regime, in which the number of samples nn is at most the dimension dd. There the samples are linearly independent whenever they are in general position, and linearly independent samples are separable.

As for the proximal minimizers, they are not unique in this regime, and we analyze the solution reached by gradient descent, the most natural inner solver. The predictions and the loss do not depend on this choice, and only the direction in parameter space does (see Q3).

In Appendix H, the goal is to compare the two divergences, the squared prediction distance and the KL divergence, which use the same budget. Each proximal step is solved by SGD with the same schedule as standard training, so the total number of epochs is the number of proximal steps times the epochs per step. The squared prediction distance, with the same 800 epochs, changes the accuracy little compared with SGD, whereas the KL divergence improves it. The additional epochs alone therefore do not explain the gain.

[Q1] Theorem 3.5 beyond quadratic and homogeneous geometries: Can the authors give a nonquadratic, nonhomogeneous geometry for which Theorem 3.5 yields a new prediction?

Theorem 3.5 requires a positive alignment constant, which holds whenever the Hessian of the divergence is well conditioned at each point, while its magnitude may vary freely (Proposition 3.3(ii)). This condition asks for neither homogeneity nor global strong convexity and smoothness. Since it is pointwise, it holds for instance for the sum of a quadratic and a radial power, which is neither quadratic nor homogeneous. For such a geometry, Theorem 3.5 gives a finite-time margin guarantee for BPPA, whereas the homogeneous-potential analysis requires homogeneity and the horizon-based analysis is in continuous time, so neither covers a discrete algorithm with a nonhomogeneous geometry. Our focus is the general condition and what it implies.

[Q2] A pointwise rate for Theorem 4.2: Can the integrated-gap analysis yield a pointwise margin rate or a finite-iteration criterion?

Theorem 4.2 gives a finite-time bound on the loss and shows that the margin converges to the maximum ℓ1\ell_1-margin. Our current analysis does not yield a finite-time rate for the last iterate, which is harder. In the KL geometry, the alignment is not bounded below, so the argument that gives finite-time margin rates in Section 3 is not available. Establishing the convergence for the discrete algorithm with the KL divergence requires a dedicated analysis, which we provide through a multiplicative-weights potential on the dual iterates, and a pointwise rate is substantially harder.

In the other cases, we establish finite-time guarantees for the margin. Under a positive alignment constant, the margin guarantee comes with a rate, with both constant and adaptive stepsizes (Theorem 3.5 and Proposition 3.6). For the KL divergence on the predictions, the direction converges at the rate O(1/t)O(1/t) (Theorem 5.3). We state the rate for Theorem 4.2 as an open question (lines 377–383 and 518–520).

AuthorsOpenReview ↗

Response to Reviewer dV3V (Part 3)

[Q3] Inner solver: What conditions on the inner-solver error preserve the KL conclusions, and how does the limit of Theorem 5.3 change with another inner optimizer?

Since the proximal minimizers are not unique in this regime, the proximal step alone does not define θt+1\theta_{t+1} given θt\theta_t. So a natural choice is the solution reached by gradient descent on the proximal objective, and this is the one we analyze.

The logits, and hence the predictions and the loss, are determined uniquely by the proximal step, and only the parameter θt+1\theta_{t+1} depends on this choice. With another inner solver, such as preconditioned gradient descent, the direction can be different, and it can be analyzed in the same way: the logits are unchanged and the inner iterates stay in the subspace spanned by the preconditioned samples, so the limit is the interpolator of minimum norm in the geometry of the preconditioner.

Since our focus is the implicit bias induced by the proximal step itself, we analyze exact proximal steps. A full treatment of other inner solvers and of inexact steps could be a possible future direction.

References

[1] Shi, Du, Jordan and Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, 2022.

AuthorsOpenReview ↗

Approaching the end of the discussion period

Dear Reviewer dV3V,

Thank you again for your review. First, we have adjusted the presentation in the paper and restated our contributions (Section 3 and lines 509–518), and we also discuss them in the rebuttal. Second, regarding the implications of the KL results, we discuss them in the rebuttal and add the related explanation in the experiments. In addition, regarding the inner solver, we also discuss it in the rebuttal and have revised the paper to add this discussion. As the discussion period ends soon, we would appreciate it if you could let us know whether these points are resolved, or whether any question remains.

Best regards,
The authors

Reviewer_AMyoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper targets the topic of the aligning of BPPA when applied to data separation tasks. The authors show that for many distance generating functions the limiting direction of BPPA is in fact a support vector. This includes common separating functions such as norms generated by positive definite matrices and the l_p norms. This claims come together with guarantees of the asymptotic behaviour of the loss function. They also show failure of their initial assumptions for the negative entropy Bregman divergence but manage to show a limiting direction result non the less. Finally numerical experiments are presented to match the theoretical claims.

Critical strengths
  1. The authors seem to present genuinely novel research. Which adds to the pool of knowledge on BPPA.
  2. The authors cover a wide range of distance generating functions. This presents a big picture analysis of BPPA applied to data separation tasks.
Critical weaknesses
  1. The paper does a poor job of convincing the reader of the results relevance.
  2. The numerical experiments are poorly described and their significance is not sufficiently established in the eyes of the reviewer.
Questions for authors

See critical weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer AMyo

We thank the reviewer for the review, and respond to the weaknesses and questions in the following.

[W1] Relevance of the results: The paper does not convince the reader of the relevance of its results.

We have revised the conclusion to state the relevance of our results (lines 509–518), and we describe the experiments in more detail (lines 452–505), so that the significance of the results is clearer to the reader. They all answer the research questions of the introduction.

The results describe what the choice of divergence does to the classifier that BPPA returns. On separable data, many classifiers fit the data, and the algorithm decides which one is returned. For gradient descent, steepest descent and mirror descent this choice is known (lines 53–55). BPPA is their implicit counterpart, since they are obtained from it by linearizing the loss in each step, but which solution it favors under different divergences is much less understood.

Our results answer this question, which is the research question of the introduction (lines 56–65). For divergences with a well-conditioned geometry, one quantity, the alignment, describes the implicit bias: BPPA attains a fixed fraction of the maximum margin, and this fraction is tight for quadratic divergences. The KL divergence does not have this property, but it is widely used in practice, so we analyze it separately, using the specific structure of each KL geometry. On the parameters, it selects the maximum ℓ1\ell_1-margin classifier. On the predictions, it selects the minimum-norm interpolator of the labels. Together, these results show that different divergences lead BPPA to different solutions on the same data, so the divergence affects which classifier is learned.

[W2] Numerical experiments: The experiments are poorly described, and their significance is not established.

We have revised Section 6 so that each experiment states its purpose, its setting and its significance in detail, and each figure in the appendix now has a sentence on what it shows (lines 452–505).

The experiments are designed to confirm each theorem and to show that the choice of the divergence changes the classifier. Figure 1(a) verifies the tight constant of Theorem 3.8: the margin ratio equals cw=2κ/(1+κ)c_w=2\sqrt\kappa/(1+\kappa) at every iteration, so the guarantee of Theorem 3.5 is tight. Figures 1(b) and 1(c) support Theorem 4.2: on the same data, the KL divergence approaches the maximum ℓ1\ell_1-margin classifier, whereas the Euclidean divergence approaches the maximum ℓ2\ell_2-margin classifier. Figure 1(c) shows that the direction converges in every coordinate. Figure 1(d) verifies Theorem 5.3: with the KL divergence on the predictions, the iterates converge to the minimum-norm interpolator of the labels and not to the maximum ℓ2\ell_2-margin classifier.

AuthorsOpenReview ↗

Approaching the end of the discussion period

Dear Reviewer AMyo,

Thank you again for your review. We have responded to your two concerns, the relevance of the results and the description of the experiments, and the revised paper addresses both in the introduction and in Section 6. As the discussion period ends soon, we would appreciate it if you could let us know whether these points are resolved, or whether any question remains.

Best regards,
The authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers

We thank the reviewers for their comments. The three reviews share one question, which is what the results tell us. Reviewer AMyo asks about "the results relevance", Reviewer beME writes that the setting "needs some motivation", and Reviewer dV3V finds "relatively limited new qualitative understanding of which classifier is selected". We answer this question once here, and then list what changed in the revised paper.

What the results show. On separable data, many classifiers fit the data, and the divergence affects which one BPPA returns, and not only its speed of convergence.

  • Under the uniform alignment condition and a growth condition (Conditions 3 and 4), BPPA attains at least the fraction cwc_w of the maximum margin in the limit (Theorem 3.5). For quadratic divergences, this fraction cannot be improved (Theorem 3.8).
  • The two KL divergences do not satisfy the alignment condition, and we analyze them separately. For the KL divergence on the parameters, BPPA attains the maximum ℓ1\ell_1-margin for every constant stepsize (Theorem 4.2).
  • For the KL divergence on the predictions, with linearly independent samples and each proximal step solved by gradient descent, BPPA converges in direction to the minimum-norm interpolator of the labels (Theorem 5.3). This is the maximum ℓ2\ell_2-margin classifier if and only if every sample is a support vector.

Figure 1 shows these effects on small datasets, where the KL and the Euclidean divergences lead to different classifiers on the same data.

What changed in the revision. We agree that the motivation of the setting and the meaning of several quantities needed more explanation. The revision adds it, and all changes are highlighted. The results and their proofs are unchanged, and some statements are simplified.

  • Introduction. We state why separable data and the exponential loss are studied (lines 69–74).
  • Section 3. We explain what the alignment quantities are for, after Definition 3.1 (lines 184–186) and Condition 3. The assumptions of Theorem 3.5 are stated as Condition 4, and the loss contraction behind the adaptive stepsizes is discussed after Proposition 3.6 (lines 273–275).
  • Sections 4 and 5. We explain the role of each proof step of Theorem 4.2, and why the solution of the proximal step has to be selected in Section 5.
  • Section 6 and the conclusion. We state the purpose, the setting and the takeaway of each experiment (lines 452–505), and the relevance of the results (lines 509–518).

Thank you for your attention. We would be glad to answer any further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.