acceptodds
Under review as a conference paper at ICLR 2027

Robust Learning Meets Quasar-Convex Optimization: Inexact High-Order Proximal-Point Methods

Abstract

Robust representation alignment can lead to nonsmooth and nonconvex objectives when paired features are corrupted or mismatched. We show that several realizable alignment models built from stabilized capped and anisotropic losses are strongly quasar-convex. Motivated by this geometry, we study Inexact HiPPA, an inexact high-order proximal-point method with regularization order . Under summable model-value inexactness, bounded HiPPA sequences converge in objective value to the global minimum, while strong quasar-convexity makes boundedness and uniqueness automatic. Under local stability and suitable forcing of the inexactness, the method converges linearly for and superlinearly with -order for . A capped-quadratic alignment model verifies these local assumptions explicitly. On a controlled CIFAR-100 feature experiment, the mean outer iteration count drops from for to for and for . A second corrupted-feature experiment uses a computable residual-and-descent rule and shows the clearest benefit from capped fitting under severe replacement corruption.

Primary area:
optimization
Keywords:
Robust learning, Nonsmooth and nonconvex optimization, Quasar-convex functions, High-order proximal-point method, (Super)linear convergence rate, Complexity

Reviews

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

This paper studies inexact high-order proximal-point methods (Inexact HiPPA) for nonsmooth, nonconvex objectives motivated by robust representation alignment. The authors establish strong quasar-convexity for several stabilized capped and anisotropic losses under clean realizability and identifiability assumptions. They prove global convergence under summable model-value inexactness and, assuming additional local stability and accuracy conditions, linear convergence for 1<p≤21<p\leq 2 and superlinear convergence of Q-order p−1p-1 for p>2p>2. They also derive stability and local recovery results under target corruption. Experiments on CIFAR-100 features examine local convergence rates and robust alignment under controlled replacement corruption.

Critical strengths
  1. Meaningful geometric characterization of robust objectives. The paper establishes strong quasar-convexity for several nonsmooth, nonconvex capped and anisotropic alignment losses, with explicit constants and identifiable conditions.​

  2. Careful theoretical formulation and controlled validation. The paper distinguishes three notions of proximal inexactness, provides verifiable local convergence examples, and reports lower-level computational work alongside outer iterations.

Critical weaknesses
  1. Restricted applicability and unclear incremental significance of the main convergence results. Clean realizability makes the ideal alignment map directly recoverable by least squares, whereas corruption removes the global quasar-convex guarantee. The Q-order p−1p-1 result assumes a corresponding local recurrence (Assumption 10), explicitly verified only in a locally quadratic basin; meanwhile, the motivating nonsmooth examples exhibit finite proximal identification for every p>1p>1 (Remark 31). This limits the demonstrated generality and leaves the novelty relative to existing HiPPA theory insufficiently established.

  2. Insufficient evidence for practical computational and robustness advantages. The local-rate experiment uses oracle-dependent accuracy schedules and remains inside a quadratic basin, while the corrupted experiment compares different orders using a common β\beta without demonstrating comparable regularization scales or tuned computational budgets. The striking 240/240240/240 versus 0/2400/240 endpoint result therefore requires further validation through matched evaluations, wall-clock time, and stronger optimizer baselines. Moreover, the quadratic stabilizer yields unbounded large-residual influence, leaving the robustness advantage over alternative robust losses insufficiently characterized.

Questions for authors
  1. Can Assumption 10(b) be verified for a meaningful non-quadratic, nonsmooth objective without finite proximal identification? What are the precise new rate guarantees relative to Ahookhosh et al. (2026a,b) and Ahookhosh and Nesterov (2024)?
  2. Can the claimed rates be retained using a fully computable stopping and forcing criterion that requires neither the unknown proximal minimum nor the distance to W⋆W^\star? What rate guarantees apply to the practical residual-and-descent rule?
  3. How do the p=2p=2 versus p=3p=3 results change with separately tuned or scale-covariant β\beta, comparable accuracy schedules, and matched wall-clock or lower-level computational budgets? Could the authors also report p=2p=2 test MSE and variability?
Reviewer_7eVKOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper shows that several nonsmooth, non-star-convex robust alignment losses are strongly quasar-convex when the clean problem is exactly realizable and identifiable. These are a stabilized capped loss, a capped-quadratic loss, and an anisotropic kinked loss used for model stitching.

It then analyses an inexact high-order proximal-point method. With summable model-value errors, the method converges globally. Under a local stability assumption, it converges linearly for p <= 2 and with Q-order p-1 for p > 2. Further results cover stability and local recovery when the targets are corrupted.

In experiments on CIFAR-100 ResNet-18 features, p=2 needs 14.8 outer iterations, against 4 for p=3 and 3 for p=4. In a corruption test, p=3 reaches all 240 endpoints while p=2 reaches none, and p=3 has the lowest test MSE at the highest corruption level.

Critical strengths

The geometric results appear correct as far as they were checked for this review. Concrete, ML-motivated examples of nonsmooth, non-star-convex, strongly quasar-convex functions are useful for a literature that has few of them. The global convergence proof under summable inexactness is clean.

The paper is also careful about what each notion of inexactness buys. It points out that a small model gap does not imply a small residual. It links the model gap to metric error under a growth condition. For the practical acceptance rule, it claims only Clarke criticality.

Critical weaknesses

The main concern is with the rate results. They add little beyond their own assumption, and they do not apply in a nontrivial way to the models that motivate the paper.

Assumption 10 directly assumes the recursions r_{k+1}^2 <= eta r_k^2 + C eps_k and r_{k+1} <= a r_k^(p-1) + b sqrt(eps_k). Theorem 11 unrolls them, and Theorem 13 turns them into iteration counts. The suggested way to verify the assumption combines exact proximal rates from earlier work with a standard perturbation argument.

For the capped feature-alignment and stitching models, Prop. 30 and Remark 31 show that the exact proximal map is locally constant, so there is no nontrivial p-dependent behaviour to explain. The only model where the rates matter is the capped-quadratic loss, which is a strongly convex quadratic near the solution. For p > 2, the forcing condition depends on the unknown distance to the minimizer, and the experiment can compute it only because W* is known.

More broadly, strong quasar-convexity is shown only under exact realizability, which is the case where a robust loss is not needed. Under corruption, the paper does not claim the geometry, and the experiment switches to an acceptance rule with only criticality guarantees. The framing in the title and abstract is broader than what the results establish. Either of two things would address this: a local quasar-convexity result for the corrupted objective (for example near W* under the margin condition of Theorem 15), or a more modest framing.

A second concern is that the comparisons across p are confounded by the choice of tolerances and beta.

  • In Sec. 5.1, p=2 uses a geometric tolerance eps_k = 1e-6 * 0.75^(2k), while p > 2 uses distance-based forcing. The late-stage p=2 ratios in Appendix E.1 are 0.74-0.77, essentially the 0.75 built into that schedule. On the local quadratic, an exact p=2 step with beta = 1/m shrinks the error by at least a factor of 2 per step. The gap between 14.8 and 4 iterations therefore seems to reflect the p=2 tolerance schedule rather than the order of the method.
  • In Sec. 5.2, p=2 and p=3 share beta = 0.05. The regularizer ||d||^p/(p beta) scales very differently with p when ||d|| < 1, so p=2 failing to reach any endpoint may only mean that its effective step is too small.
  • Table 2 reports no variance over the five seeds. At the middle corruption level, the p=3 and Group-LAD MSEs differ only in the fourth decimal.
  • LS and Group-LAD are not defined.
Questions for authors
  1. In Sec. 5.1, how many outer iterations does p=2 need with exact or distance-based tolerances and a tuned beta?
  2. In Sec. 5.2, does p=2 reach the endpoints when beta is tuned separately for each p?
  3. Apart from the locally quadratic capped-quadratic case, is there any model in the paper for which Assumption 10 holds with nontrivial dependence on p?
  4. Is there an implementable forcing rule for p > 2 that does not require the distance to the minimizer?
  5. Theorem 9(d) uses the quadratic growth bound from Fact 18, which is stated for locally Lipschitz h, while Assumption 7 only asks for lower semicontinuity. Does the growth follow directly from Definition 1? It seems to for kappa < 1, by taking lambda = 1. This is a minor point.
  6. Please define LS and Group-LAD and report standard deviations in Table 2.
Reviewer_6a9kOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper connects robust alignment losses with strong quasar-convexity and studies an inexact high-order proximal-point method, HiPPA. Theorem 9 gives global convergence under summable model-value errors. Under additional local assumptions, Theorems 11 and 13 give linear or superlinear convergence depending on the order pp. Experiments use CIFAR-100 representations to study local convergence and fitting under target corruption.

Critical strengths
  • The explicit nonsmooth, non-star-convex losses with strong quasar-convexity are interesting. Theorem 9 gives a clean global convergence argument under summable model-value errors without requiring a residual error bound.

  • The paper handles rank deficiency on the observed feature span and uses real CIFAR-100 features. It certifies the model-value gap in the controlled experiment and reports lower-level evaluations alongside outer iterations in Table 1.

Critical weaknesses
  • The connection to robust learning is limited. The geometry requires exact realizability (lines 162-165), and Section 5.1 pairs features with the same network's logits (lines 383-387). In this setting, least squares already recovers the affine head. The corrupted experiment uses two different networks (lines 416-422), for which the clean geometry is not established.

  • Proposition 14 bounds a global minimizer, and Theorem 15 gives a local recovery condition, but neither shows that the implemented method reaches such a solution. What recovery guarantee applies to the corrupted experiment?

  • Assumption 10 already assumes the perturbed linear or superlinear recursion used in Theorem 11. Exact HiPPA rates are already known from Ahookhosh et al. (2026a) and Ahookhosh et al. (2026b), as acknowledged in lines 111–118. Please clarify the main new difficulty under inexactness. The novelty of the algorithmic theory seems to be limited as compared to existing literature.

  • In Table 2, the proposed method is worse than least squares at 10% corruption and very close to Group-LAD at 20%.

Questions for authors
  • The forcing rule in line 392 uses the unknown W⋆W^\star. Can a computable stopping rule preserve the fast local rate in an actual alignment problem?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.