Distributionally Robust Linear Regression with Block Lewis Weights
Authors: Naren Sarayu Manoj
Kumar Kshitij Patel
Venue: ICLR 2026 Poster (2026)
Keywords: distributionally robust optimization
linear regression
acceleration
convex geometry
Primary area: optimization
TL;DR: We give algorithms for optimizing a distributionally robust/multidistributional loss for least squares linear regression.

Abstract: We present an algorithm for the empirical group distributionally robust (GDR) least squares problem. Given $m$ groups, a parameter vector in $\mathbb{R}^d$, and stacked design matrices and responses $\mathbf{A}$ and $\bm{b}$, our algorithm obtains a $(1+\varepsilon)$-multiplicative optimal solution using $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ linear-system-solves of matrices of the form $\mathbf{A}^{\top}\mathbf{B}\mathbf{A}$ for block-diagonal $\mathbf{B}$. Our technical methods follow from a recent geometric construction, block Lewis weights, that relates the empirical GDR problem to a carefully chosen least squares problem and an application of accelerated proximal methods. Our algorithm improves over known interior point methods for moderate accuracy regimes and matches the state-of-the-art guarantees for the special case of $\ell_{\infty}$ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.

Published as a conference paper at ICLR 2026
DISTRIBUTIONALLY ROBUST LINEAR REGRESSION WITH BLOCK LEWIS WEIGHTS
Naren Sarayu Manoj
Kumar Kshitij Patel
Department of Computer Science
Institute for Foundations of Data Science
Toyota Technological Institute Chicago Chicago, IL 60637, USA nsm@ttic.. edu
Yale University New Haven, CT 06510, USA kkpatel@ttic.ee
ABSTRACT
We present algorithm for the empirical group distributionally robust (GDR) least squares problem. Given m groups, a parameter vector in IR and stacked de- sign matrices and responses A and b, our algorithm obtains -iulipiillil optimal solution using O(min { (rank A), .mmmm)/.. g/3333/33 linear-system-solee of matrices of the form A BA for block-diagonal B. Our technical methods fol- low from a recent geometric construction, block Lewis weights, that relates the empirical GDR problem to carefully chosen least squares problem and ap- plication of accelerated proximal methods. Our algorithm improves over known interior point methods for moderate accuracy regimes and matches the state-of- the-art guarantees for the special case of too regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.
INTRODUCTION
Machine learning algorithms and their training datasets have grown substantially in both size and complexity over the past decade. This increased model complexity has made challenging to in- terpret and predict their behavior in unobserved scenarios. Hence, many applications that involve societal decisions still rely on simple, interpretable models like linear regression, often after feature engineering. Examples of such applications include predicting national housing prices, estimating wages across industries, forecasting loan amounts across banks, predicting life insurance premiums across groups, and projecting energy consumption across communities "chennAAdaal et al., 2024).
A shared safety and sometimes legal concern across the above applications is the potential for wildly different model qualities for different distributions, i.e., outputting a notably worse model for some source data distributions (Data, 2014; Barocas & Selbst, 2016; Hardt al., 2016: Veale al., 2018; Selbst et al., 2019; Berk et al., 2021; Corbett-Davies et al., 2023; Chouldechova, 2016; Kleinberg al., 2018; Agarwal et al., 2019; Cohen-Addad Addad et al., 2024; Song al., 2024). Specifically, consider fitting a linear model æ E R to make real predictions on some task over m groups where group i's dataset consists of entries and is denoted by S; {(a], b/).eem..)) The utilitarian or the minllcost-minimizing objective minimizes the average squared prediction error across groups, i.e.,
min mERd m.
(E(m) 1h ||As
Σ
x bs, bs
where As. =aa ... T E ga is the feature matrix and bs. = bT E Rd is the label vector for group E [m].
Due to the inherent heterogeneity the datasets, the model derived by optimizing the objective equation may be particularly detrimental to some groups, as the prediction error may be dispro- portionately higher for these groups. To overcome these limitations, the following egalitarian or group Distributionally Robust Optimization (DRO) objective has been considered in several recent works (Ben-Tat Tal et al., 2013; Duchi et al., 2016; Sagawa et al., 2019; Levy et al., 2020; Soma et al.,
"This work partly done while the author was fellow the Simons Institute for Theory of Computing.

---

Published as a conference paper at ICLR 2026
2022: Abernethy et al., 2022; Song al., 2024),
min 1 |As bs,
=ER se(m] 71;
Objective 2 is the "fairest" objective among all objectives that balance utility and distributional robustness (Kleinberg et al., 2018: Chouldechova & Roth, 2018; Asadpour et al., 2022; Chen al., 2022; Rahmattalabi et al., 2019; Golrezaei et al., 2024). Since objective a convex problem, natural to apply standard black-box optimization techniques solve it. However, identify several challenges in applying existing methods:
Efficient first-order algorithms have geometry-ddeendeet rates. To knowledge, using an efficient first-order method (such as sub-gradient descent) will incur a geometry-dependen runtime. In particular, if the matrices As, if the stacked matrix A = [A ... ASM! T are poorly condi- tioned, then this will be reflected accordingly in the convergence rates. This is a drawback of the existing results by Abernethy et al. (2022) and Song al. (2024).
Objective equation 2 is not smooth. Since the objective is the pointwise maximum of several continuous functions, the derivative is not well-defined at the points at which the maximizing func- tion changes. Thus, applying subgradient descent to this objective without tailored analysis will yield rather unimpressive 1 1/e² dependence in the iteration complexity.
Min-max optimization/regree minimization approaches have a 1/e² dependence on iteration complexity. Since problem 2 is min-max optimization objective, game theory-inspired approaches that use some oracle (such as gradients) for each group as a black box. For instance, we can cast objective 2 as repeated game between a min player (equipped with no-regret algorithm) and max player (equipped with the best response oracle). The main shortcoming of this approach is that even though the function for each group is smooth, the iteration complexity (to get average regret) for smooth online convex optimization still has an unimpressive 1/e² dependence (as opposed to 1 /e for smooth convex optimization) (Soma et al., 2022; Zhang al, 2024a). Thus, this approach is no better than optimizing equation 2 using sub-gradient descent.
also natural to try to use
Interior point methods have a poor iteration complexity for large m. Another natural approach (that can partially address the previous two issues), following the discussion by Boyd & Vanden- berghe (2004, Section 6.4), is to rewrite problem 2 in its epigraph form and use an interior point method (IPM) to solve the resulting problem (which, in this case, a quadratically constrained lin- ear program). Unfortunately, this will give an algorithm whose analysis is only known to yield an iteration complexity of O( ((m)), where each iteration solves linear system in matrices of the form A BA for block-diagonal B (see Remark 1.1). A naïve implementation of this algorithm will thus have a superlinear runtime in the number of groups, which undesirable when the number of groups is large. Alternately, consider example in which we copy each group k times in the ob- jective. The new objective value does not change from the original objective value, but the iteration complexity from the IPM now blows up to Vmk. This also signals to us that we should search for an algorithm whose iteration complexity is mostly independent from
Hence, designing an algorithm without these shortcomings requires novel ideas.
1.1 OUR RESULTS
In this paper, we present new algorithm (Algorithm 1) approximately optimize objective 2, which addresses the aforementioned difficulties. We state the iteration complexity of our algorithm in the following theorem.
Theorem (Robust regression). Let As E RRaxxd and bs, E TR. for all i E [m]] Denote their
concatenations by A = [A], ... Ay Rgud and b == [b], ... s IT E 18t where Lig(m) Di. Let > Then Algorithm 1 returns t such that,
max kE(m)
A t bs. 12.12 S (1 (1) min max HeRd ie [m] / nr;
A bs, 12
(3)
and it runs in
14/3
min (rank(A)) m/3 log
n log m
+ log log(m))
0
e//3
2

---

Published as a conference paper at ICLR 2026
Sehear-systemm-okfee in matrices of the form A BA,, where B is block-diagonal matrix for which block has size n, x nzz-
We prove Theorem in Appendix C. We compare the guarantee of Theorem baselines in Table 1.
against the other
Algorithm
Iteration Complexity
Each Iteration
Subgradient descent
x" l|a maxigism Vi As,
llop
Evaluate V fxx)
Nesterov acceleration on smoothened objective
1/2
x 1l maxisism
vnz As;
Evaluate V fa)
op
Abernethy et al. (2022)
2 max
sism
//y AAs, llop
Evaluate V {
Interior point with log barrier (Boyd & Vandenberghe, 2004)
Linear-system-solle in A BB
m 1/2 121/2log log (1)
This paper (naïve geometry)
1/8
Linear-system-solve in A BA
2473
for regression with Lewis weights (Jambulapati et al., 2022)
1// c275
Linear-syster-sollee in A DA
foe regression with IPM
rank (A) log (t)
1/2 (ianra A). 1/8
Linear-system-soole
(Lee & Sidford, 2019)
in A T DA
Linear-system-solve in A AB
This paper (Theorem 1)
2//3
The complexities of algorithms for optimizing equation 2 or for the special case of foo regression, assuming OPT = 1 (the first three guarantees are additive approximations) and ignoring polylog(n, m) terms. We write D to be a diagonal matrix and B to be a block-diagonal matrix where each block has size (n4 + o(1)) x (n: o(1)). We remark that in the special case where n, = 1, our algorithm exactly recovers guarantees of Jambulapati et al. (2022). We stress that we include the references to loo regression only show that our algorithm is worse than that of Jambulapati et al. (2022) in this special case of n; = for all i, and none of their algorithms apply to our general setting.
Table 1:
Unlike the aforementioned first-order methods, our algorithm has no -eometry-dependent terms. Additionally, our algorithm improves over the standard log- log-barrier IPM when the desired accuracy E 2 m 1/4 this improvement is more pronounced when m >> rank (A), i.c. when the number of data sources is much larger than the dimension of the parameter vector æ. Additionally, for 2 rank (A) our guarantee matches the best known guarantee for 4x regression (Lee & Sidford, 2019; Jambulapati et al., 2022).
Remark 1.1 (Why use linear shear-system-solve complexity?). We benchmark our algorithms using the number of thear-system-sohver for a few reasons. First, this is typically how second-order algo- rithms are compared, such as interior point methods for linear programming (Lee & Sidford, 2019). Second, the particular structure of the lineur-ysiem-soolvs presents the possibility of a faster amor- tized runtime for the systems over the algorithm's 's run. This observation, combined with an under- standing of how the linear systems changed between iterations, was used recently used achieve fast runtimes for linear programming (Lee & Sidford, 2019) and fox regression (Adil et al., 2024).
Interpolating between robust and nonrobust optimization. We also study the following family of objectives that interpolate between objectives I and 2 for different values of p 2 2,
min #ER
Σ EE [mm
1 71
As, x bs, 15
R/2
(4)
m
3

---

Published as a conference paper at ICLR 2026
In particular, note that choosing p 2 in the above objective gives us the average least-squares problem in objective 1, while p oo recovers objective 2. Varying from 2 to oo and minimizing gives solutions that interpolate between utilitarian and egalitarian approaches, allowing for smooth trade-off between utility and robustness. To this end, we give Algorithm 5 to approximately optimize objective 4 and prove the following guarantee about its iteration complexity.
Theorem 2 (Trading off utility and robustness). Let As. E RRxxd and bs. E E. for all i E [m] Denote their concatenations by A [As, ... A Raxd and b == [b,,.. ... SMr E I where n Eiglm) n4. Let p 2 2 and 0. Then Algorithm 5 returns Et such that,
P 1/p
p) 1/8
1
As. ã - bg. bs.ll1) )))
$ (1++))
min wERd
Σ
As x bs. bsilly l1
(5)
and runs in
o pi min {rank (A), m)
P-2 3p-2
pd
log
soles in matrices of the form A BA, where B a block-diagonal matrix for which block i has size X
We prove Theorem Appendix D.
In the special case where n, for all (and therefore the problem is ép regression for p 2 2), the complexity promised by Theorem is comparable to that promised by Jambulapati al. (2022) for lp regression. The main difference is that our iteration complexity is unconditionally polynomial in contrast, the comparable result from Jambulapati et al. (2022) seems to require mild assump- tions on the problem parameters (see the "Discussion numerical stability" by Jambulapati et al. (2022, Section 4)).
Remark 1.2 (Large values of p). Note that for values of p larger than logí log(m). solving equation 2 is almost equivalent to solving equation 4. To intuitively see this, first recall that for any vector a E Rd and p logz (mg2(m) we have, ||æ=|>> S ||a=|| 2 ||ar] loc. This implies that for all E [m]] have the following for objective equation 4 (for p lmg)(m)) (m)).fo for any x E RRd.
1/P
max iE(mm
AAs
bs, S
Σ 11A bs. {Elm]
< 2 max |As
bsill2
xE(m)
In particular, this means that minimizing the interpolating objective equation 4 also minimizes the robust objective equation (up numerical constants) and vice versa. Thus, for p= (logg (m)), for our intended applications, it makes sense to minimize the robust objective instead. This is why, in Theorem 2, we do not care too much about the exponent on p in the iteration complexity. Our main goal is to show that we can get a (poly(pp, log (t)) min {rank (A),m) mm iteration complexity.
1.2 PRIOR RESULTS, CONNECTIONS, AND OPEN PROBLEMS
Here, we discuss prior work that conceptually and technically relates to ours. We then suggest natural directions for future work.
Multi-distribution learning. Many learning problems involve multiple data sources, for instance, when multiple agents generate their data independently. One can formulate these multi-di multi-disttibution problems standard leamiin/optinizaaion problems by considering mixture of their distributions, as objective However, this approach often biases solutions toward dominant data sources, leading to poor performance on outliers-an an issue stemming from statistical heterogeneity. This limitation motivates the study of multi-objective optimization problems (Miettinen, 1999; Ehrgott, 2005), where each agent m has distribution D, that defines its objective Eg-DD,, (# and where models E,n can vary across agents a framework known as personalization.
One of the earliest algorithms for such problems introduced by Blum al. (2017), where each agent's ' objective must minimized to pre-specified threshold e with high probability, framed within PAC learning framework (Valiant, 1984; Vapnik, 2013). Subsequent research has refined
4

---

Published as a conference paper at ICLR 2026
these algorithms, achieving optimal sample complexity guarantees for learning from multiple dis- tributions (Chen et al., 2018; Nguyen & Zakynthinou, 2018; Hanneke & Kpotufe, 2019; Haghta- lab et al., 2022; Zhang et al., 2024b). Our objectives 2 and offer different approaches to multi- distribution learning, where data distributions correspond to empirical agent distributions. In par- ticular, Mohri et al. (2019) analyzed objective 2 to establish generalization bounds for unknown mixtures of agents" distributions.
Beyond sample efficiency, researchers have also examined other challenges, such as communication costs in large-scale distributed optimization (McMahan et al., 2016). A particularly relevant study is that of Bullins al. (2021). which employs an efficient distributed quadratic sub-solver (Woodworth et al., 2020; Patel et al., 2024) to implement an inexact Newton method for optimizing quasi-self- concordant functions (see Definition 2.1).
Group fairness. Recently, interest in algorithmic faimesss has intensified (Barocas & Selbst, 2016; Abebe et al., 2020; Kasy & Abebe, 2021) with researchers exploring faimess across various do- mains, including supervised learning (Calders al., 2009; Dwork et al., 2012; Hardt et al., 2016;
Kusner et al., 2017; Goel et al., 2018; Ustun et al., 2019), resource allocation (Bertsimas et al., 2011; 2012: Hooker & Williams, 2012; Donahue & Kleinberg, 2020; Manshadi ing (Mulvany& & Randhawa, 2021), online matching (Chierichetti et al., 2019; Ma et al., 2023), assortment planning (Singh Joachims, 2018; Biega et al., 2018; Singh & Joachims, 2019; Chen et all,, 2022), and facility location (Gupta et al., 2022). The extensive literature on algorithmic fair- ness falls into three main categories: (1) individual fairness, which ensures that similar individuals receive comparable predictions (Dwork et al., 2012; Loi et al., 2019; Chen et al., 2022), (2) group fairness, which aims for equal treatment of different demographic groups, often in terms of resource allocation performance parity (Singh & Joachims, 2018; Balseiro et al., 2021), and (3) subgroup fairness, which blends aspects of both individual and group fairness (Kearns et al., 2018; 2019).
al., 2021), schedul-
This paper focuses on a well-studied group fairness notion in machine learning literature: the group DRO problem (al et al., 2013; Duchi et al., 2016; Sagawa et al., 2019). The idea of inter- polating between robustness and utility is also common (Golrezaei et al., 2024) and closely related to multi-objective optimization, where scalarization (Miettinen, 1999; Ehrgott, 2005) helps recover desired solutions along the Pareto frontier.
Linear programming and Ep regression. In the last several years, there has been surge of work in obtaining second-orded condition-free algorithms for linear programming and Ep regression (Bubeck et al., 2018; Lee & Sidford, 2019; Adil et al., 2019; Jambulapati et al., 2022). Observe that Ep regression is a special case of the problem we study in objective equation 4, which is re- covered when all n, = 1, and loo regression is captured by linear programming. Note that neither of these problem families is expressive enough to capture the objectives we study. In general, to achieve iteration complexities in the smaller of the two dimensions for these problems, it appears that a geometric understanding of the solution space is required - these ideas were central to the improvements obtained by Lee & Sidford (2019); Jambulapati et al. (2022) as well as our work.
Open problems. Our work raises several open questions. One limitation of Theorem is that its iteration complexity is not high-accuracy, meaning its dependence on E is not polylog(1/e) Designing a high-accuracy solver under the same conditions Theorem 2 with iteration complexity δ (poly(min [rank (A). .m. log (1)) remains an open problem.
A more ambitious general goal is to design algorithms for convex quadratic programs with the afore- mentioned iteration complexity. This would generalize analogous results for linear programming (Lee & Sidford, 2019). We view the current work as first step towards this goal, as the objective equation 2 is a structured convex quadratic program for which we get an iteration complexity inde- pendent of m. It would also be interesting to consider other complexity measures beyond rank (A), for instance, assumptions about the ground-truth labeling vector an for each group's 's data S.
Finally, our results suggest that optimizing for "L "Iz-interpolants"" between non-robust and robust ob- jectives may be computationally easier than optimizing for the robust objective alone. A more pre- cise statistical characterization of how robustness and utility trade-off as p varies in collaborative, fair, or nulti-diistibutionaal learning settings would be valuable. Additionally, exploring interpola- tions or solution concepts along the Pareto frontier of the m-dimensional multi-objective optimiza- tion problem or other DRO notions (eg Wasserstein DRO (Blanchet et al., 2019; Cisneros- Velarde et al., 2020)) could yield further insights.
5

---

Published as a conference paper at ICLR 2026
1.3 PAPER OUTLINE
In the remainder of this paper, we will outline the key details of our approach and provide a proof outline for our theoretical results. In Section 2, give proof sketches of our main results. In Appendix A, we give an analysis of mirror descent under inexact subproblem solves we will need this in the proof of Theorem et al. (2022), which we will use to iterate calls to the proximal subproblem solver equation 8 for the proof of Theorem 2. In Appendix C, we prove Theorem In Appendix E, we prove some background results that appear in the main body, particularly about block Lewis weights. Finally, in Appendix F we include an empirical comparison of our proposed algorithms against the aforementioned baselines.
In Appendix B, we modify an acceleration scheme due to Carmon
Appendix D, we prove Theorem 2.
2 TECHNICAL OVERVIEW
In this section, we sketch our proofs for Theorem and Theorem 2.
Notation. Here and in the rest of the paper, we ignore the dataset size normalization factors 1/ /n as we can fold this into As, and bs, Additionally, let fx)) = E |As x bl, if S p < co case, we let (x) be the pth power of the objective written in Theorem 2; this to make future calculations easier and makes difference of only polynomial factors in in the iteration complexity. Without loss of generality (by rescaling). let OPT I, where OPT = f(x*). So, it is enough to get an e-additive optimal solution λ. Also without loss of generality, let A be such that rank (A) d. For positive semidefinite M paxd, denote | Vx Mæ. As shorthand, for y E R",
and let f(xr) = maxigişm || bs, lg if p. xc. Note that in the 2 S P
will often refer to the norm ||yllg, (E Ilys, I12) for p 2 1, where with slight abuse of notation ys, denotes the coordinates of y indexed by S,. Finally, in abuse of notation, for symmetric matrices M. let M denote the pseudoinverse of M.
Recall that many iterative methods for convex optimization can be seen decomposing a com- plex problem into a series of simpler subproblems (Nocedal & Wright, 2006). Our algorithms for distributionally robust linear regression follow this pattern, where the simple subproblem resembles
O(g) = x a-gllax
min
[(x)
for some positive semidefinite M and for some ball radius rg which may depend on the query q- Sub-routines like equation 6 are central to many trust-region methods (Conn et al., 2000; Nocedal & Wright, 2006), and, importantly when is the sum of a linear function and self-concordant barrier, interior point methods derived from the self-concordant barrier framework (Nesterov & Nemirovskii, 1994).
With such subproblem structure in hand, three questions arise. (1) How do we solve the subprob- lems efficiently? (2) How do we combine our subproblem solutions to arrive at our final answer? (3) How do choose the "local geometry" M to optimize the iteration complexity we get from the previous two parts? We address these concerns in order in the following discussion.
2.1 SOLVING PROXIMAL SUBPROBLEMS
For this discussion, let M be any positive semidefinite matrix, as the arguments apply for any ge- ometry M. It will be helpful to assume that || M is good approximation to our objective function in the sense that for some distortion A that is as close to as possible, we have
for all x Idd
x bll S Σ E|As, bs, 1P
SA x
b1 blim
Here, we discuss how to solve problems of the form equation 6 for a fixed query q. Our strat- egy follows two general steps. First, we establish some form of local stability for f² within the ball we are solving in, i.e., we want V fxx) to not change too much inside the ball x E Rd | - allm S } Second, we use this to demonstrate that an appropriate second-order algorithm exhibits favorable convergence rate an approximate solution for our subproblem. We handle the so and 2 < < oo cases separately below.
"In this case, the matrix M is given by the Hessian of the barrier function evaluated the subproblem's solution.

---

Published as a conference paper at ICLR 2026
2.1.1
THE ROBUST CASE (p oc).
Unfortunately, since is not even differentiable (it is the pointwise maximum of Euclidean norms, each of which is also not differentiable), we cannot directly argue about the stability of V f(x). We therefore first need to find some surrogate objective so that:
1. The upproximation error - is small;
2. The surrogate objective f is smooth in Il-IIM such a way that we can solve the proximal subproblems fast.
To smoothen (xx) we use the family of objectives parameterized by 3,
V82 ||A bs. 112
fa,(x)) = 3 log
Σ exp
This can be seen composing the softmax function with temperature 3 with "inner functions"
V8 || bs 2 8. It is straightforward show that for all IRd, (a,((r) f(x)) S
Blog m + 6. So, setting 3 = e/4 log m and 8 = =/4, it is sufficient to optimize Fa.8 to e/2 additive eπror to get an e-additive suboptimal solution our original objective. Furthermore, we prove that fa.s is O(1/3 + -mmothh in the norm || = maxisism ||A2||2- Thus, || is a good approximation ||A A. we will get that fa.s is also smooth in the norm || |all
Next, Carmon et al. (2020) show that if fa.s satisfies higher-order smoothness condition called craus--eef--oncorrei
with respect to the norm II-Ilm then we can get the required Hessian stability for fixed ra (11/e) (in particular, rg does not depend on here). To clarify, we define quasi- seff-concordance as follows.
Definition 2.1 (Quasi-self-coneee concordacee adapted from (Karimireddy et al., 2018, Appendix A)). Let f: f: + R. We say that f is v-quasi-self- directions d E R and E R, we have
in the norm II-I| if for all vectors y E R$
dtt) (
fly + td) Sv ||d]] ( (d)
fly + td)
Then, Carmon et al. (2020) shows how to leverage this Hessian stability to implement equation with low linear-system-solf iteration complexity. However, previously, it only shown that the composition of the softmax function with linear functions is quasi-self-concorlant. So, it was unknown whether composing softmax with other functions could also be quasi-self-cooccrddan.
To resolve this, we prove a much more general composition result, which to the best of our knowl- edge was not known prior to this work and may of independent interest. It essentially states that if we compose the softmax function with any combination of "inner" functions that are quasi-self- concordant, the resulting function also quasi-self-comn self-coooordantt. For more formal statement, see Lemma C.3.
Lemma C.3 (Composing softmax with quasi-self www-ssellf----oceee concordant functions). Let |1:I1 be an arbitrary norm and hi...., Rm be such that h4: Rd - R. Let h be the vector formed by concatenating the results of h1,.... ., Amn- Additionally, let hy,..., Jim be such that for all 1 S S m and for all y, d E Rm and E R.
d
h:(y + td) < ||d]
(Lipschitzness))
dt
3
) h + td)
d
h + td) S v ddl
(guasiseelf-comcordamne))
dt
dt
Then, for all y, d E R and all l E R, we have
(
3
(hily-ta) + t())
))
16
Blog
Σ cxp
<
+ +2)
||d]|
(seg(h(e) + td)).
dt
3
B
dt
7

---

Published as a conference paper at ICLR 2026
Hence, show the requisite Hessian stability, we use the following steps. We show that the "inner" functions for equation 7, v 62 + ||As, x - bs. 6, are each (a11/8)-qasi--elf--ooo
in
the norm |As, So, we can apply our composition result Lemma C.3 to prove that fa.s is in the norm [mx ||As, 2|22- Again, assuming that Il-IIM is a good approximation to ll-1gg.. we will get that Sa, is guasi-self-concordaae in || M as well.
O11/3 (uaii--uuusssllff-ooooooaal
With these analytic inequalities in hand, we finally apply the recipe given in Carmon et al. (2020) and get our subproblem solver for the 20 case.
2.1.2 THE INTERPOLATING CASE (2 S < oo).
Instead of explicitly constraining rg like in the p = oo case, we regularize our movement from q in the norm || M Specifically, the subproblem we solve for any query q is
argmin ((x) + ep" | q qll
wek!
This is the natural generalization of the proximal problem that Jambulapati et al. (2022) use to get their results for Ep regression, and the outline of our solver for these subproblems is similar to what Jambulapati et al. (2022) use for this special case (see their Section 4).
However, we go a step further and show how to obtain approximate stationary points equation instead of just getting a small objective value. This is because the acceleration scheme we use to iterate subproblem solutions to get our final answer E requires us obtain an approximate stationary point for equation 8. The main new technical tool we develop for this purpose is a form of strong convexity for functions of the form |///l2 for y E R for any & 2 1. See Lemma D.3.
Lemma D.3 (Strong convexity of | (l))))) Ler E RR for K z 1. For any E IR, we have
4 |
1 AIE Z |0 +1 (u, A)
With Lemma D.3, we can argue about the strong convexity of || 9 which means that we can convert approximately optimal solution to equation 8 in function value to one that is approxi- mately optimal in parameter space as well. We combine this with a local gradient Lipschitzness property of the objective equation 8 to get our approximate stationary point, which is enough for our purposes. The local gradient Lipschitzness property itself follows from form of Hessian stability that we show for the objective equation 8. See Lemma D.9.
Finally, to obtain an approximately optimal solution to equation 8 in function value, we again apply the Hessian stability property to conclude that equation is relatively smooth and relatively strongly convex in simpler reference function. We show how to solve optimization problems in this refer- ence function up to an approximate optimality that sufficient for the rest of our applications this requires mild modification of the standard mirror descent analysis, and we do this in Appendix A. Combining all of these building blocks gives us our subproblem solver for the 2 S p < oc case.
2.2
ITERATING PROXIMAT. CALLS
We now discuss the second item. Recall that we think of O(q) as answering proximal problem for the query q. It is not hard to show that under reasonable conditions on I and on the structure of the subproblems, we can iterate calls to (gg) to optimize f (see, e.g., (Carmon et al., 2020, Appendix A)). This conceptually simple approach will already give us guarantees of the form ||000 xx I for the problems we study.
But we can do better. An acceleration framework originally due to Monteiro & Svaiter (2013) and generalizee/rrefied in subsequent works (Bubeck et al., 2019; Carmon et al., 2020; 2022) gives a recipe to iterate calls of O(q) to optimize the original function f. From these, the iteration com- plexity we need for an e-additive solution with an initialization Do and optimum x= is roughly (I|=0 x0 l /E/2/3 (see Theorem B.3 for more formal statement). This cosmetically resembles the rate we get in Theorem 1. To get something that looks like our rate for Theorem 2, we use our new strong convexity lemma (Lemma D.3). With this, we can demonstrate that after sufficient number of iterations, we have || æx - Il S 0.5 |ao x=1 ll Therefore, repeating this argument yields high-accuracy solution, required.
8

---

Published as a conference paper at ICLR 2026
Interestingly, algorithm for the 2 I p oc employs form of the accelerated scheme developed in Carmon et al. (2022), which does not require solving an implicit equation for the query point, thereby improving upon the results from Jambulapati et al. (2022) for lp regression. It would be practically relevant to obtain this for the = oo case (in Appendix B, we discuss a technical challenge in obtaining this).
2.3 THE GEOMETRY OF THE PROXIMAL SUBPROBLEMS AND BLOCK LEWIS WEIGHTS
At this point, we have the tools we need to get rates of the form O ((|=0 x= MM /t) 2/33) for the
robust objective (Theorem 1) and the form O [| - x= M (p-2)/ 2) (3p-2) for the interpolating
objective (Theorem 2). From this, see that the rates depend the geometry M that impose on our problem. Our goal this section is to choose this geometry M.
Observe that when solve equation 6, are solving an optimization problem over the sublevel sets {æ | M S rr) these are ellipsoids. Now, consider choosing the & geometry that best approximates our loss function. Specifically, recall that earlier in the section, we stated that for some distortion A 2 that is as close to as possible, we want
for all x E RR:
x - bll S
Σ
As bs. 12
SA
b M
To see what kinds of distortion guarantees we can hope for, let us see what happens when we choose the most "obvious" geometry. By relating f to eor, we get
m
m
m
Σ
|AS bs, 12
S
Σ
|AS bs. bs.
5 -
Σ
|As. x by. 112
b122- bbz- Thus, setting M ATA (which is what we call the naïve geometry in Table 1) gives us our basic rate of - in the setting of Theorem and ( in the setting of Theorem 2.
and notice that ->
As.æ
bs 2)
Ax
But, there exists an improvement over above naïve geometry. Note our loss function is norm on Rdd in particular, we can check that for y R", the functions lIvlle (E Ilys, 12) 1/2 for S p S 0o are norms. Now, recall John's theorem, a fundamental result high-dimensionall convex geometry.
Theorem 2.2 (John's theorem, John (1948)). For any symmetric convex body K C IRd, let E(K) denote the ellipsoid of maximum volume contained within K. Then, we have
E(K) S K Vd E(K).
Moreover, the vd is worst-case optimal (e.g. g. let K be the unit foo ball).
It easy to see that sublevel sets of norms, i.e., sets of the form {x Rd ||ج||| S 1)). are sym- metric convex bodies. Hence, using John's 's theorem, we see that for our normed losses, there exists M that achieves distortion A < vd. From this, it is easy to see that there exists M for which we can guarantee ||zg- - x= I'I < vd. Plugging this into the guarantees from the previous subsections, we get that we choose the M from John's 's theorem, and then switch based on whether m S we get exactly the rates quoted in Theorem I and Theorem 2.
However, as written, this is only an existence result. To make this useful for us and actually find M. we need an algorithm to calculate John's 's ellipsoid for the level sets of our losses (or some other ellipsoid that gets an even better approximation factor). To this end, result of Manoj & Ovsiankin (2025) gives
efficient algorithm to find this l2 geometry for the loss families we consider.
Theorem 2.3 (Combining Lemmas 5.6, 5.8, Equation (1.8) from Manoj & Ovsiankin (2025)). Let p 2 2. There exists algorithm that finds positive diagonal matrix W e R such that for all x E IRd and all c e I,, we have
W (Ax cbb]
m
<
Σ
As x - cbs, 1P
W (Ax cb)
(2(rank (A) - 1))

---

Published as a conference paper at ICLR 2026
The algorithm runs in (log m) linear-system- solves in matrices of the form A DA for positive diagonal matrices D.
The diagonal entries of matrix W are called block Lewis weights. This is generalization of Lewis weights, and both objects have been used previously for various matrix approximation problems (Bourgain et al., 1989; Musco et al., 2022; Jambulapati et al., 2023b;a; Manoj & Ovsiankin, 2025). Furthermore, Lewis weights are central improvements in the iteration complexities for linear programming and vanilla Ep regression (Lee & Sidford, 2019; Jambulapati et al., 2022). We go into greater detail about block Lewis weights in Appendix
Additionally, notice that the distortion Orannk (A)1/2-1/p) guaranteed by Theorem 2.3 is opti- mal. To see this, let A E Rnxd be such that for E [d]. row et where is the ith standard basis vector. Then, for all + 1 S S n, let a, 0. In words, A is the d-dimensional identity matrix atop a large matrix of all Os. It is easy to see that for any we have ||Aæ|| || and the
best distortion we can get for relating ||ær to any d-dimensional & norm is d 1/pl.
With Theorem 2.3 and its near optimality in hand, we choose M A www 2 A if rank (A) S m and M A A if rank (A) 2 m (recall that in the latter case, we get a v m distortion for free from relating en to ( Combining this with the results from the previous two subsections gives us Theorem and Theorem 2.
2.4 ALGORITHM FOR DISTRIBUTIONALLY ROBUST REGRESSION
In Algorithm 1, we present pseudocode for the algorithm that yields the guarantee in Theorem 1. We compare the empirical performance of this algorithm against other baselines mentioned in Section and examine the effect of Lewis weights in Appendix F.
Algorithm MinMaxFegression: optimizes equation to (1 + +) mmultipliccative error
Require: Regression problems (As,, bs, b.,)..... .........A (As.,, bs... accuracy > 0 Using (Manoj & Ovsiankin, 2025, Algorithm 2) with input [b], find nonnegative diagonal W
and weights wi,..., Wm such that for all E S. Wü]l w; and for all æ E Rd and E R,
|Ax cbllg-
/ Ax /w//2b|
2((nkk (A) + 1) ||Ax cb cbllg=
2: if Σ - wi m then
rank (A) + 1 Σ 1=1 wq S 2(rank (A) 1)
3: L
Reset W = I,
4: Let Ba (A WA) A Aw..
2n argmin #ERd
| w
5: Let
m
V 82 + | x
bs:
Ta,0(0)) = log
Σ exp
B
where 4 4log and
> A family of smoothenings of the objective.
6: Let f(x) == fe log e/4 (x) 1000 min((
W W2 /2 - 2o)ll
7: Using (Carmon et al., 2020, Algorithm 3), implement
- -ball optimization
(rank(
oracle for f, where C is universal constant. & Iteration complexity guaranteed by Lemma C.5
8: Using (Carmon et al., 2020, Algorithm 2). implement MMS oracle for f.
min (rank(a) m/1// log(
9: Run (Carmon al., 2020, Algorithm 1) for Ō
iterations using the
2273
MS oracle from the previous line and with initial point æp and final point T.
10: return
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank Aaron Sidford for useful comments during the early stage of the project. We also thank the anonymous reviewers at ICLR'26 and NeurlPS'25 25 for their significant contributions to improv- ing the paper. Most of this work was done when NS and KKP were graduate students at Toyota Technological Institute, Chicago (TTIC). KKP and NS were supported through the NSF TRIPOD Institute on Data, Economics, Algorithms and Learning (IDEAL) and other awards from DARPA and NSF.
REFERENCES
Rediet Abebe, Solon Barocas, Jon Kleinberg, Karen Levy, Manish Raghavan, and David G Robin- son. Roles for computing social change. In Proceedings of the 2020 conference on fairness, accountability, and transparency. pp. 252-260, 2020.
Jacob D Abernethy, Pranjal Awasthi, Matthaus Kleindessner, Jamie Morgenstern, Chris Russell, and Jie Zhang. Active sampling for min-max fairness. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th In- ternational Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research. pp. 53-65. PMLR, 07 2022. URL https:: sttpss//prooeeedigg mlr wwwss/weessl2 abernethy22a. html.
Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Iterative Refinement for lp- norm Regression, pp. 1405-1424. 2019. doi: 10.1177/.97816611954422..6 URL hetps:
// //epubs.... si am. org/ doi /abs//b/////// /10.//1... 11 31 /1 9781 611 975482.
Deeksha Adil, Shunhua Jiang, and Rasmus Kyng. Acceleration meets inverse maintenance: Faster fx regrrssss,, 2024. URL https:///// // arrxiv. org/ abs/ /20ss/2499..0 20030.
Alekh Agarwal, Miroslav Dudík, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and reduction-based algorithms. In International Conference on Machine Learning, pp. 120-129. PMLR, 2019.
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
Arash Asadpour, Rad Niazadeh, Amin Saberi, and Ali Shameli. Sequential submodular maximiza- tion and applications to ranking an assortment of products. Operations Research, 2022.
Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fair- and beyond. In International Conference Machine Learning, pp- 630-639. PMLR, 2021.
Solon Barocas and Andrew D Selbst. Big data's disparate impact. Calif. Rev. 104:671, 2016.
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Sci- ence, 59(2))3411-37,, 2013.
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3-44, 2021.
Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of faimess. Operations research, 59(1):17-31, 201
Dimitris Bertsimas, Vivek Farias, and Nikolaos Trichakis. On the efficiency-farrmes trade-off. Management Science, 58(12):2234-250, 2012.
Asia Biega, Krishna Gummadi, and Gerhard Weikum, Equity of attention: Amortizing individual fairness in rankings. In The 41st international acm sigir conference on research & development in information retrieval, pp. 405-414, 2018
Jose Blanchet, Yang Kang. and Karthyek Murthy. Robust wasserstein profile inference and applica- tions to machine learning. Journal of Applied Probability, 56(3):830-857, 2019.
11

---

Published as a conference paper at ICLR 2026
Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning. Advances in Neural Information Processing Systems, 30, 2017.
Jean Bourgain, Joram Lindenstrauss, and Vitali Milman. Approximation of zonoids by zonotopes. 1989.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Sébastien Bubeck, Michael Cohen, Yin Tat Lee, and Yuanzhi Li. An homotopy method for Ip regression provably beyond self-concordance and in input-sparsity time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 1130-1137, New York, NY, USA, 2018, Association for Computing Machinery. ISBN 9781450355599.
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Curran Associates Inc., Red Hook, NY, USA, 2019.
Brian Bullins, Kshitij Patel, Ohad Shamir, Nathan Srebro, and Blake E Woodworth. A stochastic newton algorithm for distributed convex optimization. Advances in Neural Information Process- ing Systems, 34:26818 88 26830, 2021.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE international conference on data mining workshops, pp. 13-18. IEEE, 2009.
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020.
Curran Associates Inc. ISBN 9781713829546.
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter acceleration. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 978171387101
Jiecao Chen, Qin Zhang, and Yuan Zhou Tight bounds for collaborative pac learning via multi- plicative weights. Advances in neural information processing systems, 31, 2018.
Qinyi Chen, Negin Golrezaci, Fransisca Susan, and Edy Baskoro. Fair assortment planning. arXiv preprint 0tt.::2200.0734444 2022.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvtiskii. Matroids, matchings, and fairness. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2212-2220. PMLR, 2019.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. big data, 5 (2), 163-163, 2016.
Alexandra Chouldechova and Aaron Roth. The frontiers faimesss in machine learning. arXiv preprint arXiv: 2018.
Pedro Cisneros-Velarde, Alexander Petersen, and Sang- Yun Oh. Distributionally robust formulation and model selection for the graphical lasso. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificcal Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 756-765. PMLR, 08 2020.
Vincent Cohen-Addad, Surya Teja Gavva, CS Karthik, Claire Mathieu, and Namrata. Fairness of linear regression in decision making. International journal of data science and analytics, 18(3): 337-347, 2024.
Andrew R Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.
Sam Corbett-Davies, Johann D Gaebler, Hamed Nilforoshan, Ravi Shroff, and Sharad Goel. The measure and mismeasure of faimess. The Journal of Machine Learning Research, 24(1):14730- 14846, 2023.
12

---

Published as a conference paper at ICLR 2026
Big Data. Seizing opportunities, preserving values. The White House Report Washington, 2014.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Kate Donahue and Jon Kleinberg. Fairness and utilization in allocating resources with uncertain demand. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 658-668, 2020.
J Duchi, P Glynn, and Hongseok Namkoong. Statistics of robust optimization: generalized em- pirical likelihood approach. arxiv. Machine Learning. 2016.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science confer- ence, pp. 214-226, 2012.
Matthias Ehrgott. Multicriteria optimization, volume 491. Springer Science & Business Media, 2005.
Davide Giraudo. Bound the variance of the product of two random varables. Mathematics Stack Exchange, 2014. URL https: / /math. st ataceccaange com/ wtt.:/cccc/////cc/ccccccec.occ.e 8/1044864.
Naman Goel, Mohammad Yaghini, and Boi Faltings. Non-discriminatory machine learning through convex fairness criteria. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 116-116, 2018.
Negin Golrezaei, Rad Niazadeh, Kumar Kshitij Patel, and Fransisca Susan. Online combinatorial optimization with group fairness constraints. Available SSRN 4824251, 2024.
Swati Gupta, Jai Moondra, and Mohit Singh. Socially fair and hierarchical facility location prob- lems. arXiv preprint arXiv:2211. 14873, 2022.
Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. Advances Neural Information Processing Systems, 35:406 419, 2022.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. Advances in Neural Information Processing Systems, 32, 2019.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, Advances in neural information processing systems, 29, 2016.
John N Hooker and H Paul Williams. Combining equity and utilitarianism in mathematical pro- gramming model. Management Science, 58(9):168--169; 2012.
Arun Jambulapati, Yang P Liu, and Aaron Sidford. Improved iteration complexities for overcon- strained p-norm regression. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 529-542, 2022.
Arun Jambulapati, James R Lee, Yang P Liu, and Aaron Sidford. Sparsifying sums of norms. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1953- 1962. IEEE, 2023a.
Arun Jambulapati, Yang P Liu, and Aaron Sidford. Chaining, group leverage score overestimates, and fast spectral hypergraph sparsification. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 196-206, 2023b.
Fritz John. Extremum problems with inequalities subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, pp. 187-204. Interscience Publishers, Inc, 1948.
Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Global linear convergence of new- ton's 's method without org/ /1066. 00413.
or lipschitz gradients, 2018. URL https: //arxiv.
13

---

Published as a conference paper at ICLR 2026
Maximilian Kasy and Rediet Abebe. Faimess, equality, and power in algorithmic decision makinn.. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp- 576-586, 2021.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faireess gerryman- dering: Auditing and learning for subgroup fairness. In International conference on muchine learning, pp. 2564-2572. PMLR, 2018.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich sub- group fairness for machine learning. In Proceedings of the conference on fairness, accountability, and transparency, pp. 100-109, 2019.
Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ashesh Rambachan. Algorithmic fairness. In Aea papers and proceedings. volume 108, pp. 22-27, 2018.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
Yin Tat Lee and Aaron Sidford. Solving linear programs with sqrt(rank) linear system solves, 2019.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distribution- ally robust optimization. Advances in Neural Information Processing Systems, 33:8847-888 8860, 2020.
Michele Loi, Anders Herlitz, and Hoda Heidari. A philosophical theory of fairness for prediction- based decisions. Available at SSRN 3450300, 2019.
Haíhao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first- order methods, and applications. SIAM Journal on Optimization, 28(1):333-354, 2018.
Will Ma, Pan Xu, and Yifan Xu, Fairness maximization among offline agents in online-matching markets. ACM Transactions Economics and Computation, 10(4):1 2023.
Naren Sarayu Manoj and Max Ovsiankin. The Change-of- Method, Block Lewis Weights, and Approximating Matrix Block Norms. 2025.
Vahideh Manshadi, Rad Niazadeh, and Scott Rodilitz. Fair dynamic rationing. Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 694-695, 2021.
HB McMahan, E Moore, and D Ramage. S. hampsonet al., "ll"ccommuicaatoonefiieee learning of deep networks from decentralizeeddata.. arXiv preprint arXiv:1602.05629, 2016.
Kaisa Miettinen. Nonlinear multioojecttive optimization, volume 12. Springer Science & Business Media, 1999.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- lional conference on machine learning, pp. 4615-4625. PMLR, 2019.
Renato D. C. Monteiro and B. F. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Opti- mization, 23(2):1092-1125 2013. doi: 10.1137/1 10833786. URL httph::t////dte /r0/ 1137 10337786.88887
Justin Mulvany and Ramandeep S Randhawa. Fair scheduling of heterogeneous customer popula- tions. Available at SSRN 3803016, 2021.
Cameron Musco, Christopher Musco, David P Woodruff, and Taisuke Yasuda. Active linear re- gression for E, norms and beyond. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 744-753. IEEE, 2022.
Y. Nesterov and A. Nemirovskii. Interior Point Polynomial Algorithms in Convex Programming. SIAM studies in applied and numerical mathematics: Society for Industrial and Applied Mathe- matics. Society for Industrial and Applied Mathematics, 1994. ISBN 9780898715156
14

---

Published as a conference paper at ICLR 2026
Huy Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative pac learning. Advances in Neural Information Processing Systems, 31, 2018.
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 2006.
Dmitrii Ostrovskii and Francis Bach. Finite-sample analysis of m-estimators using self- concordance, 2020. URL https: / /at///axxii
httgg/bb///11000 06838.
Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U Stich, Ziheng Cheng, Nirmit Joshi, and Nathan Srebro. The limits and potentials of local sgd for distributed het- erogeneous learning with intermittent communication. arXiv preprint arXiv:2405. 1667, 2024.
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. Exploring algorithmic fairness in robust graph covering problems. Advances in neural information processing systems, 32, 2019.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generaliza- tion. arXiv preprint arXiv: 1908731,,, 2019.
Andrew D Selbst, Danah Boyd, Sorelle A Friedler, Suresh Venkatasubramanian, and Janet Vertesi. Fairness and abstraction in sociotechnical systems. In Proceedings of the conference on fairness, accountability, and transparency, pp. 59-68, 08, 2019.
Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 2219-2228, 2018.
Ashudeep Singh and Thorsten Joachims. Policy learning for faimnsss in ranking, Advances in neural information processing systems, 32, 2019.
Tasuku Soma, Khashayar Gatmiry, and Stefanie Jegelka. Optimal algorithms for group distribution- ally robust optimization and beyond. arXiv preprint arXiv:2212. 13669, 2022.
Zhao Song, Ali Vakilian. David Woodruff, and Samson Zhou. On socially fair regression and low- rank approximation, 2024. URL https: http:////ppppeeeeeeeeeeeeommee wwwpeeewwwwww.eeeeeeeeeeeeeeeeee forum iid
Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Arthur Gretton and Christian C. Robert (eds.), Proceedings of the 19th Interna- tional Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pp. 957-965, Cadiz, Spain, 05 2016. PMLR.
Berk Ustun, Yang Liu, and David Parkes. Fairness without harm: Decoupled classifiers with pref- erence guarantees. In International Conference on Machine Learning, pp. 6373-6382. PMLR, 2019.
Leslie G Valiant. A theory of the learnable. Communications the ACM, 27(11):1134-1144 1984.
Vladimir Vapnik. The nature of statistical learning theory. Springer science business media, 2013.
Michael Veale, Max Van Kleek, and Reuben Binns. Fairness and accountability design needs for algorithmic support in high-stakes public sector decision-making. In Proceedings of the 2018 chi conference on human factors in computing systems, pp. 1-14, 2018
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mema- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020.
Lijun Zhang, Peng Zhao, Zhen-Hus Zhuang, Tianbao Yang, and Zhi-Hua Zhou Stochastic approxi- mation approaches to group distributionally robust optimization. Advances in Neural Information Processing Systems, 36, 2024a.
Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S Du, and Jason D Lee. Optimal multi mustiidistribution learning. In The Thirty Seventh Annual Conference on Learning Theory, pp. 5220- 5220-5223. PMLR, 2024b.
15

---

Published as a conference paper at ICLR 2026
A MIRROR DESCENT WITH INEXACT UPDATES
Notation warning. This section is meant to be a self-contained, standalone analysis of mirror descent under inexact updates. The notation is chosen to be consistent with most material could find on mirror descent and therefore conflitts with the notation used in the rest of the paper.
In this section, give an analysis of unconstrained mirror descent when each Bregman proximal problem is solved only approximately (Algorithm 2). Although we expect that this is standard fact about mirror descent, could not find appropriate reference. Hence, we produce here.
Implements mirror descent optimize convex and dif- ferentiable f given L-relative smoothness and p-relative strong convexity the reference when may not be able solve each proximal problem exactly.
Algorithm 2 ApproximateeirrorDssssooo
Require: Initial point Zo, iteration count T.
1: Define
(a, y) = h(x) - h(y) - (Vhly), x y)
x² argmin f(x)
zER
2: for 1, ..... 7 do
3:
x argmin (1) + (V[(x;-1), - xz,1) + LD, x1,1) We may only be able EER4
to approximate x; - see the next line.
4: Let be an approximate stationary point for the above objective.
return argmin f(x;)
0SiST
In Algorithm 2, we assume that the function f is p-relatively strongly convex and L-smooth in reference function h. This means that for x, E R we have
(an y) S f(x) [(y) - (Vi(y), y) < LDn(2, Using (Lu et al., 2018, Proposition 1.1), when / is twice-differentiable, this condition is equivalent asking for all Rd.
( fm)) = IV²)
We are now ready to state the performance guarantee of Algorithm See Theorem A.1.
Theorem A.1. Let index j be the index output by Algorithm 2. Let A be defined such that
A (((xi)))) + L (Vh(æ,) Vh(a:-1)).
Then, have
f(r))-((x")) < L (1- 11) Da(=", æo) + max (A,, D; - -xx))
ISiša
To prove Theorem A.1, we begin with a few standard facts about the mirror descent iterations.
Lemma A.2. Let y E Rdd be arbitrary. We have
(V)(x x4 y) L (Di, (y, x4-1) Dn xe.) Da xx-1)) (Di, xz y)
Proof of Lemma A.2. By the three point identity (see, e.g., (Sra et al., 2016, Equation (A.9))), we have
Paly, (n mx.) D2 (Vh(w,, Vh(2;-1) -
1 (Vf(x,-1) - 4.. - -
completing the proof of Lemma A.2.
Lemma A.3 (Mirror descent lemma under approximate stationary point updates). Let y E Rd be arbitrary. For every iteration we have
[(x)) f(y) & (I. Dy, x;-) I.Day. m:) + (Ai, v: 9)
16

---

Published as a conference paper at ICLR 2026
Proof of Lemma A.3. The definition of p-relative strong convexity tells that
f(x f(v) - (V y) paD (y. ai-1)).
We now write
f(x)) - ((v) v ((;-11 - f(y) + (V[ - - + 24-1)
(I--RS)
< (V n. v) (D xi-1) + LDn 2i-1)
(J-RSCC)
I (L D) (y, LD xi) + (Di,
(Lemma A.2)
completing the proof of Lemma A.3.
We now have the tools to complete the proof of Theorem A.I.
Proof Theorem A. Let E. f(x;;) f(x=) (A,; 02 x²)) Substituting y x= and rear- ranging the conclusion of Lemma A.3 gives
E S (L D))n( 23-1) D LD"
We multiply both sides by L-H and write
L -- E, (L -)*-1 Dz(x" xi-1) - Li+1
(L - uis Dn(x",x;)
Adding over all iterations yields
T L ( E, LD 2o)
Σ
(T=/)²
T LDn ( S LDn(x* (zo)
i=1
Expanding out the definition of E, and rearranging gives
L (1-m))
Σ
(f(z)) f(=")) < (Dx 200) + Σ
(Di, xi - xx').
--
11)
1=1
By the geometric series summation formula, we define and have
T Cr Cr
11- (
L # L
T
L
Let j be the index that Algorithm 2 returns. It is easy to check that
(J(as) f(x²)) 2 Cr (J(æz) (xx"))
1=1 I--
and
I ) (A,,0; -2')=xx) Cr max (A,, x; -x") Isi5n
Σ
L 1-11)
This gives us
f(x;) - f(x')
Da(x", xo) + max (Ai, xz x²)
C2
13i5n
Finally, notice that
L
< (1-
CT
(1+
Combining everything completes the proof of Theorem A.I.
17

---

Published as a conference paper at ICLR 2026
Finally, add another useful lemma that quantifies the descent, if any, in the objective value between iterations.
Lemma A.4. For every iteration we have
f(x;) - f(x;-1) - - (L + (Ai, xi-1))
In particular, if 24 xi-1) S I,, (1 vi), then iteration i a descent step.
Proof of Lemma A.4. We substitute y 0;-1 in the conclusion of Lemma A.3, This gives f(xr,) (( < - (m: + (Ai, 2; ai:1)),
completing the proof of Lemma A.4.
B OPTIMAL MS ACCELERATION UNDER CUSTOM EUCLIDEAN GEOMETRY
In this section, we adapt the bisection-free Monteiro-Svaiiee Svaiter acceleration framework developed in Carmon et (2022) to handle custom Euclidean geometries. The object of interest here is Algo- rithm 3, which we will call with different choices of the oracle Oss for our algorithms.
Algorithm 3 OptimallSSAoceleration optimizes function f given MS oracle Oms-
Require: Initial zo. function f. oracle OMs, initial X6. multiplicative adjustment factor 1.
iteration count T
Set eo 2p. Ag 0, A/ = O. 2: Set Æ1, \1 Owo; Xo) and X A1.
3: for 0, O.....To do
4:
d'+1 2X,41 (1 + v 11)+1
5:
41 = =A + d
q: K Art ditl
6:
T+t1
Vr
7:
ift > 0 then Ti+1, det1 Oms (q:; X
8:
1 min 1, Aet1
N4+1
9:
at+1 = 7+11/41 and A411 A + 01+1
b A441 A/41 - (1 7442)044
(1-7+1) + T4r Trs1
10:
F++1 1e-1
Aet1
if 7+1 then
12:
X = -
else
14:
X41 = =aM+1
15:
1t+1 =
M M ((
order to state the performance guarantee Algorithm 3, we require the notions of an MS oracle and movement bound. See Definition B. and Definition B.2.
Definition B.1 (MS oracle, generalization of (Carmon et al., 2022, Definition 1)). Let M E idddd be positive semidefinite matrix. An oracle O: Rd R>0 Rd x R20 is o-MS oracle for function I: Rd R for every q E Rdd and X' > 0, the points (æ, A) Olq:N) X) satisfy
1 M ((w))
S a || Allm
Definition B.2 (Movement bound (Carmon et al., 2022, Definition 2)). For norm I|-llm induced by positive semidefmite M E Rdxd numbers > 1. O, and x. y E Rdd say that (ar, y, A) satisfies a (s, c) -ovoement bound if
2 --
if < if 8 = 00
x yll >
18

---

Published as a conference paper at ICLR 2026
With these in hand, ready to state the convergence guarantee get with Algorithm 3. See Theorem B.3.
Theorem B.3 (Modification of (Carmon et al., 2022, Theorem 1)). Let f: TRd R.. be convex and differentiable. Consider rumming Algorithm with parameters
exp 3 -3-211 and a a-MS oracle with S < 0.99 (Definition B.1). Let 8 2 1 and e> and suppose that for all such that X X or t 1, the iterates (æt, 1t) satisfy an (s, mmveemme bound (Definition B.2). Let be a universal constant. For any iteration count T satisfying
=41)
("11mo=="113k 5
if <.00
T2C
(c|lw0
x01l 10m x=
2/3 log As log w'13 1i4
if
we have
( f(x)) Se.
The proof of Theorem B.3 follows the same recipe the proof of (Carmon al., 2022, Theorem 1). The only modification needed is that stated Lemma B.4.
Lemma B.4 (Replaces (Carmon al., 2022, Proposition 1)). In the context of Theorem B.3, let
F. = f(x))) f(x'), Dr 2 ||l, x: lI N4+1 == Re41 q:11is Then, for all t 2 we
have
A411 - Dot1 + (1 A4) min {1++1, N41 S A,E, + Dr.
Consequently, for all T 1, Ar 2 1 Eies Vx.
Do AT
ET <
and (1 (1-o²) Σ
A.N,N, Ar.
1ES
Proof of Lemma B.4. This proof is straightforward modification of (Carmon et al., 2022, Proposi- tion 1). We have
Dot1
1
||1411 - x ==1
1
|o a4+1 vf((++1)
-V - x= 1=
2
2
V (+ ab+1 | |M
= + a1+1 (M (M- (T(4),)) v2)
By definition of q: and A/+1 = A + d/+1, we have
d' A/ qt- A,T: d' w + A/41 (g: -T++1) A₁ (#:: Tz-1)
Subtracting x41 and taking the inner product with M - (V((4411) gives
a'+1 (M ( x² -u:) M
- (
xe+1) + A/411 (#++1 - q:) + A₁ (x:, Te+1)
$ a4y1 f( + A14+1
11 - qi) + A, (f(x;) - f(ā(+1)
A,E, N/11 (f(+++))) f(xx)) A/41
3t+1 -qi) q1)m-
Rearranging gives
A/t1 (f()+1)) - f(x))) < A,E, + o/41 VV- 0; - x M
+ (M- ( q:)
Next, recall that by Definition B.I, we have
M MM'V - det1 (5++1 - 1:) S 02 || - 1:
-
19

---

Published as a conference paper at ICLR 2026
We use this to write
Ae11 (M- V ( 06 - -
1 M V ( 10+1(111111 - - M
1
M
[((@T+1))
1|
1i+1 |
q: M
S - - (1 1
from which we conclude
( Be+1 (t) M S (1o) 2d++1
M V (3
Substituting back gives
A4+1 (f(3)+1) f(x²)) I A,Es + 4/41 (M
x²) MM
+ Al+1 (M- V Te+1 - 44:
< A,E; + 4/41 (M V (() U1 - x²" M
A/+1
A/+120+1 (1 0²) N
| ( (
2
Next, recall that 7410441 = 0c+1 and 7+111++1 = min { X J. by construction. Let πet1 = min (A++1, M441 We multiply both sides by 7t+1 and conclude
A441 (f(0++1) - f(x)) S 1t+1A,E, + dc+l AMM
- x²)) x²)M
- - N2) 2o41 [
M
2d++1
Now, by convexity of ʃ and from the definition of 11 we have
f(x(+1) - f((x)) v (1-7++)AA
A++1 (f(x)) - f(xx)) + 16 (f(T(+1) - f(x)))
A4t1
Recall the definition of E,, multiply both sides by A4ti, apply our bound T+11 1/41 (f(ā++1) - ((x))), and we get
A411 S (1 (111) + 4441 (f(ā++1) - f(x'))
A,E, d++1 (( Ve- x²)) '
1441
- -1-02)
N
2x
After shifting terms around, we see that it remains to show
704144+1
3 D. De+t.
at+1 (M-*V (" De x²) '
2
In fact, by the choice of d'41 and the definition of A/41, we have
(4 a'م1 + A A/+1-
Multiply both sides by 1/ and we get
2
7 A/+1 min
1,
X Xet1
7441
7411A44
2
2X++1
2X
2d141
We recycle an earlier computation and know that
22 -
D. D1+1 = 0.41 (M-'V (( vz x²)
11414/11
2 0+41 - V
1, vi x" )²)
M
2h++1
which completes the proof of the potential decrease.
The remaining statements follow as written in (Carmon et al., 2022, Proof of Proposition 1), and we conclude the proof of Lemma B.4.
20

---

Published as a conference paper at ICLR 2026
Now that we have shown Lemma B.4, refer the reader to (Carmon et al., 2022, Appendix A) for the proof of Theorem B.3, as now follows exactly as written there.
We also give additional bounds on the movement of the iterates in Il-l which is a straightforward adaptation (Carmon et al., 2020, Lemma 31) to the improved framework from Carmon et al. (2022).
Lemma B.5, For all t 2 1, we have both
| x0II S 2 2 - x=" x=||MM
X 2 o²
||0 x x0
22
max IsiSt
|1:00 x= x=
X
In the statement of Lemma B.5, the cost of overshooting the guess X becomes evident without an additional strong convexity guarantee, it is challenging to ensure that each iterate remains a small ball around x*. This is the main reason we are unable apply the framework of Carmon al. (2022) to the xo case.
Proof of Lemma B.5. Using the same notation in Lemma B.4 and in that proof, define
P. == A,E, + D₃
x min (2z, X33-
By induction on the conclusion of Lemma B.4, for t 2 we have
2 00 10 = D2 S P. (1 0²) Σ A6 Ax No S Po = |00 - -x"1] =='
Thus,
I x M S V222 I'
For the second conclusion, we introduce the following notation.
(1 - 74
A
At
Bt+1
A1+1
71+1
d'41 A
8e41 1 (1-00+1)(1- 10011--1111 Be+1)
Ac+1
A/+11
Art1
We also establish for any
7
A
1
X
X
Xmn(aa)
7
X
max
X
which implies
nAA
X1 1 A; 5.
a, max
Notice that
| x=1| 1l
5 04+1
[t x=
+ (1 a441) || | -x* I|
< 04+1
[ x²
M + (1 - a141) (1lqe - x=1| M + || - q: qellm))
S 04+1 [x x² M
+ (1 - 14) (Bt+1 || |x; - x=" llm + (1 - Be+1) l|,. - x01lm + || ge (mm)
(Br+1 ax4 0,+1 ||x, x=1
+ (1 - a441) (1 - B(+1) |/0 x ==' + (1 at+1) | qellm
8.+1 ||a, xx" Ilm (1 5(+1) || x= Il (1 a0+1) || qellm
21

---

Published as a conference paper at ICLR 2026
6141
200
x²IlM² +
1 II0++
0s+1
110r
IMI
20
2=0
++1
8G(1 (1:1-a)]1o |,
qi-1 |M
== -=
++1 ++1
S <v2 ag
x= a²Ilm= +
6y(1 - ax)) |0;; -q:-1 -qi-1ll
j=++1
A;
= =22 xx x x²Ilm= +
(1
||;; q:-1 MM P
Ar+1
A
v2 1:000 x² x'IIM=
||:;
9i-1llm
Ac+1
Ai
1
1+1
7
= v2 [0200
x I'IlM= +
ArrAA |:c q:-1llm
Ac-1 i=1
A
(+1 mA!
1/2
1/2
2i=1 A;
S 222 11:00
x=
X
||;; qi
96-111% 11/21
A
++1 n
1/2
2iml Ar
S V2 100
x'IIM= +
o² [ x² ll
Ar+1
S 22 12000
x x''IM +
si ag max
++
1,
X
Ar
2
I - x 1l
Ac+1
1 0²
X
2
22 120000 x= a='Il
max 1si5t+1
11:00 x= a*|l M
X
/2 max
X
2
V 1- o²
|
x= Il
1sist+1 X;
completing the proof of Lemma B.5.
C MINIMIZING THE DISTRIBUTIONALLY ROBUST LOSS
The goal of this section is to prove Theorem 1. We break up the proof into parts as described in Section 2. We structure the section as follows. the rest of this subsection, we present Algorithm 1, our algorithm that minimizes the distributionally robust loss. In Appendix C.I, we introduce our smooth approximation for the objective equation 2 and show that it a good additive approximation (this is standard argument, but we include it as it provides crucial intuition).
As the main difficulty of the proof in Theorem is to establish a Hessian stability for our surrogate loss, devote the bulk of this section proving this. Recall that in Section 1.1.1, we claimed that a higher-order smoothness condition called quaxi-self-comccrrlune gives us the needed Hessian stability in fact, this follows from (Carmon al., 2020, Lemma 11). In light of this, suffices to demonstrate that our surrogate loss is quasi-sel--concordan..
In Appendix C.2, we work out some calculus facts related to the softmax function. In particular, it is in Appendix C.2 that prove the general composition result Lemma C.3 that states that if we take the softmax of several quasi-self-cet cenncccoann functions, then the resulting function is also quaai-self-conccrdaat. In Appendix C.3, apply this composition fact to prove that surrogate objective is quasi-self-ee conf-rannord.nt. Finally, in Appendix C.4, we combine these building blocks with the acceleration framework in Carmon et al. (2020) and complete the proof of Theorem 1.
22

---

Published as a conference paper at ICLR 2026
C.I SMOOTHLY APPROXIMATING THE OBJECTIVE
Recall that for E IR", let |y = max sigm lyss ll where for y E IR" we let ys, refer to the vector in R indexed by the indices in St.. Also, for E R let (se refer to the function
(3) = log
Σ exp
1/ 3
At high level, our algorithm will minimize the function
Vo
82
As
bs.
8
Fz,((x) = 3 log
Σ cxp
B
for appropriate choices of the parameters 3 and 8. This choice of smoothening is natural because of the following approximation statement - see Lemma C.I.
Lemma C.I. For all RR have
[a,a(z) ||A bllا S 3 log m + 8.
Proof of Lemma C.I. These guarantees are well-known, but we prove them anyway for the sake of self-containment. We first prove that for any E IRm we have
max I (se < max + 8 log Isnsm
15i5m
In one direction, we have
m Σ (s) S log
)
maxi Ui
exp
3 log m + max Wi
1
15
and in the other, we have
maxi 1s
(s) 2 B log
exp
max ON- 1sism
B
Next, for v E 1 we will show that
||1l|2 85 v v02
|100 5 85 |01|
Indeed, we have
82 + ||01| 1 5 s V82 + VI0lI2 = =110112-
and
v + 110112 5 v /1111/ 5 ||0||2 8.
From this, we get
Fz.o(z) <
max 1sis
002+ | - bs. bs.112 -8) 5)
logm - |Ax bllg_ 3 log
and
Σ exp ||As
bs. 11 - 1) 2 Axx - -bll - 5.
Fz.( 3
B
Putting these together gives
Fa,0(2) - Ax
bll bllgg
< max (3 m, 8) S 3 log m + 5,
completing the proof of Lemma C.I.
Eventually, will choose e/l4 m) and 5 e/4 and then minimize Fa.s to e/2 additive error. In light of Lemma C. this will be enough to get an z-additive approximation to the optimum for |A bllg..
23

---

Published as a conference paper at ICLR 2026
C.2 CALCULUS FOR LOGSUMEXP
We investigate certain properties of (y) when each entry [y]] is a function h1 for E R for all [m]. Let h(t) E IR denote the vector where its ith entry is given by hg (t). We treat each h; as mie-dimmnsional restriction of function 9: R + R, so ht(t) = gi + td) for center y and direction d (we omit the parameters y, d in the notation h; as it will be clear from context). Finally, recall the definition of quasi-self-concordane (Definition 2.1).
We begin with calculating the first two derivatives of (se)()(t)) with respect to in Lemma C.2.
Lemma C.2. Let (x(t) exp (t) Then, have
Eim ()a(t) M((1))
(sen)h(tt)
dt
Di Ae(()
d
= E A(O))((E)
EE ( ) T Ei=A A(t))
))
E. MOO)))
(sen()(1))
d1
EES A(t)
EE Ai(t)
Proof of Lemma C.2. The first derivative follows from the chain rule. Indeed, we have
Σ (Ae(t) M(O) 3
-- x(t -i=1 (1(
ΣE (Ax(t) M((t)) DE Ac(1) S max max/((()) (t()).
Ise's (h((t) =
3
E (²)
For the second derivative, we use the differentiation rule for multiplication and division and the chain rule, giving
m Ise ()(()) = X(O)() + ((O))()) (E) ( X(OI - 3 ( A((0))))))
E (c)))²
EE ((OM((1 + (A) (E A((0) - (E (EMAOO)) M())²
#
En MONOO
EE A(OMOOO CESA0
E. A(ON((
+
3
Th DE xi(1)
This completes the proof of Lemma C.2.
Next, we prove a general fact regarding composing Ise with vector formed by functions that are themselves quasi self concordant. See Lemma C.3.
Lemma C.3 (Composing softmax with quasi-sel--concordant functions). Let ||-I1 be an arbitrary norm and hi,..., Rim be such that h4: Rd -> RR Let h be the vector formed by concatenating the results of hy,..., hm-- Additionally, let hi,..., hm be such that for all 1 S S m and for all y, d E Im and E R.
d
hely + +td) ||d]
(Lipschitzness)
dt
(
d
3
Sv sv||d| ( d ) h:ly td)
hily
id)
(guasisself-comcordannee))
dt
Then, for all y, d R and all R. we have
d
h4 aly-tu td)
16 B +v)
d
8 Blog
exp
||d||
Ise (h + td)).
dt
3
dt
As far as we are aware, this type of composition result was not previously known and may be of independent interest.
To prove Lemma C.3, need Lemma C.4.
24

---

Published as a conference paper at ICLR 2026
Lemma C.4. For any two random variables X, Y, we have
Var [XY] - 2 Var [X] + + Var [Y]
Proof of Lemma C.4. The proof follows that of Giraudo (2014), but we reproduce it here for com- pleteness. First, notice that for random variables U, V, we have
2arr [U] + 2Var [V] Var [U + V Var [V] + Var [V] 2Cov [U Var (U V] 2 0.
Let U = (X- E Y and V = E X Y. Then, U + V XY, and we have
Var [XY] 2 2ar [XX - 18 | + 2ar E [ YJ = 2ar [(X - [[X]) + 2B [X] Var [X]
remains bound Var [(x
y. By Hölder's inequality, we have
Var [X - [ < E [[(X - E (X] < R [[ - E [X]]] |
Var [x]]
Combining everything gives us the conclusion of Lemma C.4.
We are now ready to prove Lemma C.3.
Proof of Lemma C.3. Let (t) = exp (t,(t)/5).
In this proof, we will encounter many weighted averages of vectors 2 E RT of the form
1= (((1)zz
TH X:(1)
Let D be the distribution over [m]] whose entries are given by Dj 2,)00/0)/>0 A,(t). In the rest of this proof, all expected values, variances, and covariances will be taken with respect to this distri- bution. In an abuse of notation, let ht()) denote the "random" variable that is (4) with probability D, Define h' (t),, h² (t),,, h² (t) analogously.
To find the third derivative of (I)))))))),, we start with its second derivative. By Lemma C.2, is given by
1
> m A(OO))(0)2
> Liml X(OO)(()
ET A(OO)(()
(h(())
3
Σ (1)
Σ A((1) A(())
T2
1 Var (t) + (N))
3
We now differentiate the above term by term. First, we have
E de(t) (( 12(0))())
+))((()
1 E ((tMM(()) EE ((O))(())
(t)
En Ai(t)
B
1 i= (())
EE M(O)((() EE (((E)N(()) E 2₂(1))
E M()) M1))
3
E (t)
1 Cov [H'()), h2" (())) + E (t)]
3
Next, we have
1 {EN(()) = 2E (V()) _ BW 2B [M(O0] (H + (000)+E[W0 ((((()))
di
and
(t)))
dt
25

---

Published as a conference paper at ICLR 2026
E + 2K((0)()))))))))) E (.(1)) -
(E ((O))0))
E Xx(())2
EE (((1))(()) (ETh (((O))(()))
EE= (t(
B
MAL D 1:(1)
+ +22((0)N(()
(E ((O))(()) (E A(044(0))))
E (t)
B
C Ar(t))
1 Cov (())) 2E (M((W"
3
Combining everything gives us
Ise"" (h(t))
1
+ (+) 2B (T((t) (1 Var [M) E[
Var
B Cov
+ Cov (M)) [E)*)(((++*))))))))
3
Cov (t), H1 (t) - 32 E (t) Var [+(( _ Cov (t), (()] + E [E (t).
82
We first analyze the terms that only depend h (t). To do so, Lemma C.4 to write
Cov (M(1), S Var [W[1]] v Var [N(
||l|| Var [b)())-
Now, we have
g2 Cov [1'))) 21 (t) [+])
82 Cov [M (t)
+
E (t) Var [N())]
g²
4
|d] Var W (t)]
[d][ls)((((()))
g2
3
Next, we take care of the remaining terms. We have
3
6
Cov [C') h² (t)]l + E (((((t)]
<
max h1(() E (1))(tt) E( [E
<
||d]] Ise", (h(1)))))))))))))))( + E ((II
/
12
||d]] Ise") (h((t) + v d E (t)
3
12
+ v)
||]|| (1)())
8
where the penultimate line follows from Lemma C.7. Combining these conclusions yields
(M(()) <
16
3 v) ||d] (he))))),,
completing the proof of Lemma C.3.
C.3 SMOOTHNESS AND QUASI-SELF-CONCORDANCC OF THE MODIFIED OBJECTIVE The main result of this subsection is Lemma C.5.
Lemma C.5. Let W be such that for all E Rd we have Ax S | A || For all 2,2 2 E Rdd and t E R, we have
d Ja,6( + 12) <
+ 3
1
11
Az
Az
(smoothness)
dt
26

---

Published as a conference paper at ICLR 2026
Ja. + 12) (a) dt
16 3 3 {1
( d 2 dt )
A=
J0.0(0 + (z)
(quaas--el)
Our goal in the rest this section is to prove Lemma C.5. We begin with defining (t) as (absorb the y: d parameters into the definition of h;)
h2(1) = 602 + lys: Ids, 11
Let ht) denote the vector whose ith entry is (t).). Then, observe that
(t((t) B
)
m
V82 + lys. + lds. 11
Isea (h(()) = ,3 log
Σ
exp
Bog
Σ exp
B
It is easy to see that every one nne-dimensional restriction of fa.6 can be obtained by an affine transfor- mation of Ise (h(t)) after appropriate choices of y. E R Hence, we first analyze Ise, (h(()) for all y, d E I
We begin with proving the smoothness of Ise (h(t)) with respect I|-1
Lemma C.6. For all y, d E Ih" and all t E IR, we have
d
(he)()(()) s - Idl.a
dt
Proof of Lemma C.6. By direct calculation, is easy to see that k((t) (ys, + tds, ds.)
h1,(1)
(1) |ds, (2)((t) M((t)P,,(t) ht)
||ds.12 - -1(())
(t)
We plug this into the result of Lemma C.2 and get
Ise (se((((())) < max 11(1)² - max max (t)
(us. + ids,, ds:)
||ds, 12 h2(1)²
8 max
+ max
V 82 llys, + ids:11..
v 82 1/y.. Ids,
(1
+ 1 ||
Σ B max ds, 112 + 8 max Ids,
3
completing the proof of Lemma C.6.
Our next task to show that (se))(((t) is we will appeal to Lemma C.3. To be able to do this, we first have to prove the quasi-self-ee cuasii-eff-concoddancc of each component function in Ise; (h)t)..
http://gqaaiixlfff-oooooooooood in 11-1|g_ To do so,
Lemma C.7. For all y, d E Tm and all I R, we have
d di
3
3 x
((
llus, Ids, 1l
dss
V 88 1/2+100
llys, + ids. 12
Proof of Lemma C.7. Although a similar fact appears in (Ostrovskii & Bach, 2020, Section 2.1.2), it is not in the exact form need. So, we prove the required statement here.
Recycling the computation from equation 9, recall
|ds, 1t(t)2
h" (t)
ht(
27

---

Published as a conference paper at ICLR 2026
which gives
- (M000000000)0000000000000
34((0)))) hx(t)
NM" (t)
(t)
Finally, again recalling equation 9, notice that
K
M
(ys. tds.: ds.)
ys tds.
ds.
ds
ht(t)
ht))
82 ys. + tds, 1/
V02 lys. tds,
Combining everything completes the proof of Lemma C.7.
We are now ready to prove the quasi-self-conncrrancc of (se)(h(tt) in I1-Ila. Lemma C.8. For all y, d E Imm and E I, we have
d dt.
16
3 +
) Ise (h(1)). dt
d
(be)()(())
|dll
B
Proof of Lemma C.8. In the statement of Lemma C.3, let ||-|1 I1-11g... By the definition of ||-1lg.. and h,, we have for all and that (t) < ||d|| Additionally, from Lemma C.7, we have that the (t) are lel-quus--eef--ooooobbbee in the norm |d[le for all i. Lemma C.8 now follows immediately from Lemma C.3.
Finally, we can prove Lemma C.5.
Proof of Lemma C.5. By the conclusion of Lemma C.6, know that for all y, d R and e R that
d 2
Ise <
|1=16-0
dt
Let y = Ax - for some æ and d A= for some z. Let
v 82 + ys. 1 8
g(v)= = 3 log
Σ
exp
3
1=1
Then,
(4) ( F0.s +1x) +=)( ) g(Ax b+
(1 ( ()) || 11=
- (Az) <
With the exact same reasoning applied to the conclusion of Lemma C.8, we also see that
(aa)
3
F0 tz)
16 3 (44
|A=1I
d ( Fo.s + tz).
3
The conclusion of Lemma C.5 then follows from remembering that we have W such that for all E Rdd ||Az|lg < [w1/2 (following from Theorem 2.3).
C.4 ANALYSIS ALGORITHM 1
In this subsection, use the calculus facts from the previous two subsections analyze Algo- rithm I. The outline of this proof follows that (Jambulapati et al., 2022, Thcorem 2), which in turn builds up to using the proof used in (Carmon et al., 2020, Corollary 12). The main idea is to define the algorithm based on the norm given by a good choice of positive semidefinite M, given by Theorem 2.3.
In the rest this section, let W be factor-2 block Lewis weight overestimates for [A] As in Line 1 of Algorithm and from the corresponding guarantee given in (Manoj & Ovsiankin, 2025,
28

---

Published as a conference paper at ICLR 2026
Lemmas 5.6, 5.8), this means that within 2 2log sinear-ysttem-solve in A DD for diagonal D, we can find W such that for all æ E R" and c E R we have
|Az = = w w/2
Az 12
AwA--w//bb) S 22((ank (A) + ||Az cbllg
Note that choosing = yields our original objective on either side of the above inequality. Moti- vated by the above, it natural use the norm given by M = A WA to give the geometry for the ball optimization oracle and for the analysis. Additionally, without loss of generality and for the sake of the analysis, let rescale the problem so that
1 = OPT == || bl
Also, mentioned earlier, assume without loss of generality that rank (A) d. We begin with Lemma C.9, which bounds our initial suboptimality in f and in II-IIm:
Lemma C.9. Let &3, == argmin (a,s(z). Then, meRd
| colmm S (2+ m ()) f0o) Fa,s (T S 2( 1+ 2(8 log m + +8)
Proof of Lemma C.9. It is easy to check that
x = (A WA) -1 A Twb = argmin æER
/ Ax w
By Lemma C.I, for all Rd.
(3,0(2)) ||A bllsm
s 1lg + 8,
implying
||At* - -bll_- - Fooo(E0,s) s 3.oogmm m +
Combining this with Theorem E.3, we get
1 |Ax - -blla I 1|AT bllo> $ 1///2A00 w1/2b/
and
1 w1/26/12
W1/2Ax
w1/2b// -
<
< AA - -bllaa = 1.
12(d+1)
12(d+1)
Combining these gives
1 1 W1/2AA0 - w1/2//l S 2(d
Additionally,
w 1/2 A
w1/20/|
< v2(d+1) 1) |A - 6l1gm.
S (2(d+1) (Ta.((Ep,6) + llg m +6)
v2(d+1) (11Ax -11gg 2(B log m + 6))
/2(d+ 1)(1 + 220llgmm +8).
Then,
- xollM- = 1 A wl/2b)
(W1/2 Ax0 w b)bb
5 W w1/2b
W1/2Ax wl/26/|
29

---

Published as a conference paper at ICLR 2026
$ (2 2(3 log + +))
and
F0,(20) - J0, - |A - -bl6a.. - -IAAa - -bls_. +2(3 log m + +
$ w Ax0 w -OPT + 2(3 log + 6)
S 22 1 2(3 (3log m 5).
This completes the proof of Lemma C.9.
We are now ready to prove Theorem
Proof of Theorem I. Algorithm optimizes the regularization f given by
f(xx) = Fo,5(x)) 110R2
1 A(x =20
where R is such that ||a0 33,6 IM
I R. Let ã argmin f(x:). Using (Carmon et al., 2020, æe
Proof of Corollary 12), we know that for every iterate of Algorithm 1,
[(xx) - (3. S
We now choose 3 = e/( (4 log m) and 5 = 8/4, so that Jz.5 approximates f up to error e/2 on every point. Using Lemma C.9, this gives R (2 + e)d 1). is therefore sufficient optimize up to e/4 additive error.
Next, using Lemma C.5 and (Carmon et al., 2020, Lemmas 11, 43), we have that f is (1/u, e)- Hessian stable in II- for / 12(1((= log m)). We now invoke (Carmon et al., 2020, Theo- rem 9), which tells us that we can implement a (C/Vd, C/e)-ball optimization oracle for f with log (1)²) limear-system-solves
The next step is to turn the ball optimization oracle into a -MM oracle (Definition B.1). Using (Carmon et al., 2020, Proposition 5), we get ball oracle complexity of O (log (z)) to implement the MS oracle. In total, our linear-system-solve complexity for implementing the MS oracle for iteration is O log (9))
Finally, using (Carmon et al., 2020, Theorem 6), we get that Algorithm has a Newton iteration complexity of
(1 (1+s)Vdlog) m
2/3
Vd +
(log
(1 (1
log
log
8
//3
d log m
14/3
-0
g2/3 log
as promised.
Next, analyze what happens if fall in the case where W I.. Here, by using the Vm distortion from approximating em with er, we have for all x E IRd
Ax bll < ||Ax bllga S A - bl12-
m
Using this and repeating the previous analysis with this choice of M gives us rate of
m 1/3 m log m
14/3
0
log
2233
E
30

---

Published as a conference paper at ICLR 2026
required.
remains to determine the form of the Newton steps. For this, it is sufficient to understand the Hessian of f. A straightforward calculation shows that is of the form A T BA where B is a block- diagonal matrix where each block has size |S;] [S: Thus, each Newton step solves a linear system of the form A BA = v.
Combining this with the iteration complexity guarantee to find W (see Theorem 2.3) completes the proof of Theorem 1,
D INTERPOLATING BETWEEN AVERAGE AND ROBUST LOSSES
In this section, we prove Theorem 2. As before, our proof follows the outline in Section 2. The main technical challenges are to establish a form of strong convexity for our objective f and then to build solver for the proximal problem equation 8.
The rest of this section is organized as follows. In Appendix D.1, we derive caleulus facts about our objective f, including bounds on its Hessian and the promised strong convexity (particularly Lemma D.2 and the more general result it builds on, Lemma D.3). In Appendix D.2, we prove some facts about the iterates of Algorithm 3 when applied to setting. In Appendix D.3, This section is fairly
more precisely define and analyze our solver for proximal sub-problenn technical and we give more detailed outline there. Finally, in Appendix D.4, assemble all these components and analyze Algorithm 5, thereby proving Theorem 2.
Throughout this analysis, rescale the problem that f(x*) 1. is now sufficient to solve for an e-additive error solution.
D.1 CALCULUS FOR THE OBJECTIVE
In this section, we work out some calculus facts related to our objective || - bllg, Throughout this discussion, let (ax = ||A G
Lemma D.1. For any IRd, we have
M As - 1 |A,
= < (v2f(z)) p(p 1) Σ
|| As. x bs.112 ||As, 2112
Proof of Lemma D.I. Let us first calculate the derivative and hessian for f(-) using the chain rule and usual matrix differentiation rules:
|As x 65.11 f(x) = Σ
1=1
m
Vf(x) = P Σ
A5 bs, 11 18-2 AAJ. (As, bs.)
(10)
V²ʃ(x) =
A S. bs: 12 1 AAJ As:
+ p(p - 2) Σ |AS bs [AJ, -
(As) -bs.) bs.) (11)
Using this formula, we take the quadratic form with respect to a vector z. By Cauchy-Sehwarz, notice that
|As x bs, 1P [A], (As, bs.)(As,z bs.) bs.) AAs.) )
As bs, (As, As,x - bs.)² < As, bs, 1:-2 ||As =11
With that, we have
T (v))(x)) z $ Σ
Ag bs.1 b- 21 1 (p 2) A
s, x bs. 2-2
A 2113
31

---

Published as a conference paper at ICLR 2026
m
r(p 1)
1 A s. x. bs, 1 | 9. =1/
(12)
For the lower bound, we use our calculation for v2 fax) to write
(V) Σ As 1s || 212
completing the proof of Lemma D.1.
D.1.1 STRONG CONVEXITY OF THE OBJECTIVE
The main pair of results of this section Lemma D.2 and Lemma D.3. We can think of Lemma D.2 as form of strong convexity for our objective.
Lemma D.2 (Strong convexity of f). Let ((x) = |A blgg. For all d E Rd. have
4
f(x + 2 f(z) (Vf(z), d) +
|Ad| p 9p
2F
and therefore
| w''l M $ 23/22 /2--1//()) - f(a' 1)=r))
Lemma D.3 (Strong convexity of || 2). Let I for k 1. For any RR, we have
| + A 2 | + 1| (v. A + 2
A
To motivate Lemma D.3, let us see how Lemma D.3 implies Lemma D.2.
Proof of Lemma D.2. Note that
m
Vf(z)= = Σ p P1AA, 1s 2 (As, bs.)
This implies
m Σ p ||A bs, b 2
bs. As.d) 1
(Vf(=).d)
Combining this and applying Lemma D.3 (which is strong convexity lemma for || 11 that we prove subsequently in this section), we get
f(x + d) = ||A (x + d) - blli, = ||Ad + (Aæ b)ll?,
Σ
A s, d (A x bs.)
=
m
(Lemma
AA bs. pl| As 1s.12-2 ((As, - bs.), + |As
4
A s. bs, 12 + +<+p(/l |1|/As bs. 11 A (As, 1esss,-bss,,ooo bs.), + Ass
2
4
equation 10 A blli, + (Vf(z). d) +
2p |Ad| = f (V fz). d) +
2F |
We now take care of the second statement. Observe that at optimality, we have V fx(x*) = 0. Plugging this in (replace æ by x and d by x² above), rearranging, and taking pth roots gives
4
1/p
2 41/p (f(x)) 1/=
|| A x²) lGG <
(f(x)
/r
2F
Next, recall that by Thcorem 2.3,
x IM
w1/2-1/p A(x -x*)
S (2d) || 2")16
Stitching the inequalities together completes the proof of Lemma D)2.
32

---

Published as a conference paper at ICLR 2026
In the rest of this subsection, we prove Lemma D.3. We begin with few numerical inequalities. Lemma D.A. For S -1/2 and p 2 2, g(a) = [-(2++1jjp7 is nonincreasing in a.
1+pa
Proof of Lemma D.4. We first take the derivative of with respect to a,
g(())= (2 1)) - ((-2)) (2a + 1))9/2-1) + pa))
(-(2a + 1))²
p(-(2a + 1)m/3) + p (-(2aa + 1))p/2-1 (1 (1+pa)
(- + 1))8
=p. (-(2a + 1)) + + pp))
(-(2a + 1))p/2+1
(p - 2)
p (-(2a
1))p/2+1 11)p22) 0
where in the final inequality used that 2 2 and 1 -1/2. This completes the proof of the lemma.
We also need the following lemma, which is similar to result due Adil et al. (Adil al., 2019, Lemma 4.5). It amounts to proving Lemma D.3 when the dimension k = 1.
Lemma D.5 (Case A. of Lemma D.6). For any R and p 2 2,
4
1 + a 2 1 + pa + 2
lao"
Proof of Lemma D.5. Note that the inequality true when p 2 and becomes an equality. We consider the case when p > 2 and use h(a) to denote the error function,
Ma)= = 11 + ail -(1
(1+pa-
+
2P la!"
We aim to show h(a) 2 0 for all E R. Let us first write the derivatives of h.
1((a)) ( 11 + cop (1+
1+
4
|a|"
(alp~2a) a))
2"
h²(a) p(p- -1 [1+
4
|a
p-
- plp 1) 1 [1+ap- 1
2
It is now easy to verify the following statements about h,
(-(2)) (-)- and (a)a)) for < -2 = within the range (-x0, -2] the function h is minimized at -2;
II. h-(-2) 0 and h²(a)= S 0 for E (-2,-221) + 1'(a) in the range 2233), i.e., in that range the function h is minimized at -2/3;
M.. (-23)
1/(0) and h² ((x) > for > -2/3 = the function decreasing in (-2/3,0) and increasing in [0, oo), i.c., within the range (-2/3, oo) the function h is minimized at O.
As result of the above observations, it is enough to check the inequality at the inputs a {-2, 12/3, 0). We have for > 2,
h(-2) = (1
2p 2p
4>0
(-2
2p
-
) =
1
2p
2p
+
>
3P
3
20
3P
3
3"
3
3P
h(0) 11-1-0
This implies that h((a) for all values of a, concluding the proof of Lemma D.5.
33

---

Published as a conference paper at ICLR 2026
Next, we prove special case of Lemma D.3.
Lemma D.6. For any a E R. B 2 0. and 2 2. we have
((1 + a)² + 3 2 + pa + 2 (a² + /3)/112
Proof of Lemma D.6. Let us study the difference of both sides of the inequality using the following function,
M), = ((1 + +a)² + 32)p//2
p/2 (1 1 par +
4 (a² + g9)p12
2
We want to show that for a E R. B 2 0, and p 2 2, h(a, 3) 2 0. We will break this proof into three
cases: A. a E R and 3 = 0: B. E (-oc, -2] U 22 and 3 > 0: and C. E -2/3)
and B > 0. These cases together cover of the entire range of a E R and B 2 O.
Case A. When 3 = 0, the proof simply follows from the statement of Lemma D.5 by noting Jal" - (Va2)* = (a2)
In the remaining two cases we will show that for any a E R. increasing the value of B still maintains Ma,, 3) 2 O. To see this, we first note that the derivative of ha(a,, 33) w.r.t. ,3 is given by,
Vah(a, 5)= = p3 ((L+a)² (
82)01221
4 (a² + 82)0/2-11
2F
For B >>0 0, ensuring this derivative is positive is equivalent to the following,
Vah(a, 3) 0 p3 (11 + + 332/0/221
4
(a² //2)//2-1
> pB
2F
2/(x-2)
=(~320) (1 (1+ + B
1
(a² + +²)
2p-2
1
= a1+ + 3 >
(a + 8²)
4
= =3a² + 8a + 4) > 0,
2 8 a
4
3² >
(13)
Case B. Note that the roots of the quadratic function 3a + 8a + 4 are given by 01 = -2 and
02 = 2/33. This means that for a E (-xx,- u [-233, oo) we have 3a² + Sa + 42 0 which is
sufficient to ensure using equation 13 that V vph(o, > 0, and hence h(a, B) > 0. This takes care of Case B.
Case C. Now we only need to consider the range (-2, 22/3) with B > 0. In this range, the recall the equivalence equation 13,
4 +
V () T)>
0.
=: Bo(a)
3
3
Thus for all B >> fo(a) we know that h(a, 3) is increasing in 3 and vice-versa. This allows us for any given a E 2-23) to further break Case C. into two sub-cases:
Case C.I For 3 [0, 9o), since h( ,3) is decreasing in 3 its lowest value is attained at B 0 and we only need to verify that h(a, 0) 2 O. We get this directly from Lemma D.5.
Case C.II For 3 E [So. oo), since h(a, 9) is increasing in B its lowest value is attained at , = 3o and we only need to verify that h(a, 8 (a)) 2 O. We first simplify the expression for h(a, (o(a)),
Ila, Bo(a)) = ((1 + a)² +
++) p/2
(1 (1+ pa + K2 (a² + 23) p/2
2
9/2
4
8
4
p/2
0k
1 + pa +
= a
3
3
28
3
3
34

---

Published as a conference paper at ICLR 2026
2
R/2
(
1
p/2
-
+ pa pa-aa +4
3 3
3
2
1 P/2
pa 3
-1 pa 3p/2-1
(-2x 1)8/3
- (-2 1)p/2
1 + pa
(-2a - 1)p/2
3P/2-1
Now since E 2233) < -1/2 we can use Lemma D.4 to note that the first term is non- decreasing in which means that its lowest value in this range can be lower bounded by its value at = -2, i.e. for (-2, 2/3),
h(a, Bo(a)) 2 11 ((-2,,P((22)
=-3 (1
2p
1
+
3p/2
3p/2 2
2p 1 1- 3 2(p
2)
which finishes the proof of Case C.Il and also Case C. Together Cases A. B and C complete the proof of Lemma D.6.
Li
We are now ready to prove Lemma D.3.
Proof of Lemma D.3. First, assume that ||0|| 1. We will later extend the result to all v.
Bww where (v, w) 0 and || 1, that we have || = a² + g², Without loss generality, we have B 2 Fixing w and a for now, it is enough
Since | 2 1. we can write A
to show that for all 33 2 0, we have
! a))+ = ((1 + a)² + 82)p/2 21 + pa + +pt
|4 = 1 + pa + 20 (a² + 82)p12
2
This follows immediately by Lemma D.6.
We now extend the result for all v. Let : =
// ||1|| and note that
A
p
4
||u - 21l | 12
+
|0
1 +
+
l2
2
2
|
4
||011
+
(v,
A)
+
|
11
2F
completing the proof of Lemma D.3.
D.1.2 SMOOTIIESS OF THE OBJECTIVE The main result of this subsection is Lemma D.7.
Lemma D.7. For all Rd, we have
f(x) - f(x') < p(p p()) ||A(x (()0-2))11, 2')
f(x))
2
Proof of Lemma D.7. By Taylor's/mean-Ve theorem, we can write for some on the line con- necting x² and x,
f(x) = f(x²) + (Vf(x"), x²)) + (x Tt) x²)
2
sequation 12 f(x*) + p(p 1)
2 Σ A
11.115-2 | (x -x*)11
35

---

Published as a conference paper at ICLR 2026
p=2
S f(x") + p(p - 1)
Σ
|ASy y bs.1l²]
Σ
IIA (a x")
2
- f(x") + p(p - 1)
2 f(x)* 1- ||A(x - x")6,,,
completing the proof of Lemma D.7.
D.2 FACTS ABOUT THE ITERATES
The main result of this section is Lemma D.8. In words, Lemma D.8 tells us that each proximal query make in Algorithm& 3 (see Line of Algorithm 3) has bounded objective value. We will need this later when we argue about the convergence rates for the algorithms used to solve the proximal subproblems.
Lemma D.8. For all queries qu, we have
[(a) s f(x:) + (9p(p 1)) d
Proof of Lemma D.8. We establish the following upper bound on f(v,) - f(x") using the ingredi- ents developed so far:
f(v.) f(x)) p(p
p(p-1) - f(v,)' || =x0)11
(Lemma D.7)
2
p(p 1)
f(v,)= ||u, 201
(Theorem 2.3)
2
< p(p 1))(v,) - |1000 1'
(Lemma B.5)
S p(p (), (22
(Lemma E.5)
S
Now, recall that assume by rescaling that f(x*) 1. From this, it trivially follows that 1 < - - 1) Combining these and re-arranging the above inequality leads to the following polynomial incquality in f(v)).
2 f(v:) - 8d' 3 p(p 1-
f(v:) 9d p(p 1)f(v:)) + +d' d'-² "p(p 1)f(v:)) 3-3
f(v)) 9dt-3 p(p 1)f(v:)'-3
(14)
where in the last inequality we used the fact that the optimal value f(x*) = (due to our rescaling), which implies that for 2
S f(v)) S dt 1p(p=))((())))
Solving for f(v:) in equation 14, we get
f(v:) < (9p(p 1)) -
Using the definition of qi from Algorithm 3 (Line 6) along with the convexity of f (Jensen's 's in- equality), and using our bound f(v;) note that,
f(q:) S f(x)) + f(w.) f(())) + (9p(p 11) db
which completes the proof of Lemma D.8.
36

---

Published as a conference paper at ICLR 2026
D.3 Let
PROXIMAL SUBPROBLEMS CALCULUS, ALGORITHMS, PROOFS
4q a) = f( + epp q ll
In this subsection, design and analyze an algorithm (Algorithm 4) that approximately solves the subproblem
argmin fg. (i). EER
Specifically, we will output (Ā++1, A ) that satisfy the 1/2 --MS oracle condition (Definition B.1) and an appropriate movement bound (Definition B.2).
This subproblem is the workhorse of Algorithm 5, and once we implement and analyze the solver, it is very straightforward plug this into Algorithm and Theorem B.3 get our final iteration complexity.
Algorithm 4 GoRegressionProxOOaael: Implements 1/ -MS oracle for |l-lls, regression (see Lemma D.20 and Algorithm 2.
Require: Query dc previous iterate Ti, intended parameter distance 7, 1: Define
Jq. ( == f()) + ep" 1 qt PM
hgg [ = a q: ) + ep" a|e 9:113
Dhat (x, y) == hgg (a)) hgg (y) - (Vhg (y), x y)
Eq. == argmin fa. (zz)
HERd
2: Let T (p) (dpehg. (z
(
3: Run Algorithm 2 with input iteration count T,, base function fq. reference function hgg and initialization Q:-
The goal of the rest of this section is to analyze Algorithm 4. The analysis follows several steps:
1. We find a reference function fgg that depends on the query point qi for which the proxi- mal objective fq. is relatively smooth and relatively strongly convex with O())()) con- dition number (see Appendix A for sense of why this is useful). The main result here is Lemma D.9.
2. We show that Sq. is strongly convex, following from Lemma D.3. This will help un- derstand the argument suboptimality for any point that approximately optimizes fg. in function value. We also show that the reference function hg. strongly convex, using the same tools, for the same reason.
3. We show a form of smoothness for fq. This helps bound the gradient of any point that approximately optimizes fq. Combining these later will tell us that an approximate solution to fg. in argument value is also approximate stationary point, i.e. it satisfies the 1 MS condition (Definition B.1).
4. We solve the proximal subproblems. This solution itself follows a few steps:
(a) We apply Theorem A. This tells that as long as we can approximately solve the Bregman proximal problems (approximately implementing Line in Algorithm 2), will be in good shape.
(b) This means we have to figure out how to approximately solve problems of the form argmin (g, x)) Lhhg (æ:), where L is the smoothness constant derived for fq. with æERd
respect to hg. We do this up to accuracy that approximate mirror descent handle (see Theorem A.I for details on what we want this approximation to look like). For the approximation work, need approximately solve this problem up
37

---

Published as a conference paper at ICLR 2026
to both argument accuracy and approximate stationarity. The main technical result of interest here is Lemma D.18.
5. We use the smoothness and strong convexity guarantees to show that our solution from the previous step satisfies the 2 2MS oracle (Definition B.1), which means we can plug-and- play into Theorem B.3.
D.3.1 HESSIAN STABILITY
Throughout this section, we adopt the following notation:
Cp =pp
f(x) = Σ || Ass bs. 112
i=1
fa(Ø) = f(x) + Cp |2 qllb
hz(x) == || 1- - Cpp || 9
We begin with proving our Hessian stability fact, which should also be equivalently viewed as show- ing that fa is relatively smooth and relatively strongly convex in hg. with Opp()) condition num- ber. Our main result is Lemma D.9 which relies on analytical results Lemma D.10 and Lemma D.11 that we prove later.
Lemma D.9. For all Rd and p 2. we have
1
1h (x) V (q 3 p. eV)))aa)))))))
2p e
Proof of Lemma D.9. Using an arbitrary = E Rdd we can write the following quadratic form of the hessian of J,
[(x)= ((2) p- (p- - 1)
Ass x - bs 112 |As 21.
bs,
m
= =p. (p- 1)
|| s. (a: q) + As. - bs: 11-11 " ||,
1=1
50h p. (p- 1) Σ
a 2 A A (x 9)11822 - 212 188 1AsAss bs.11- Ass 21,)11
<10) p. (p- - 1)
of 2-2
| s (x - 4)1) |As, x12 (p - 1) 38-22 (²)(g)z
( (p - 1) -
p-2 2
(|2
q ( (m-2)/0 (|=
)² 2/D + (p 1) 8p 2z f(g)=)
= p (p 1) . a
2-2
|| qllia²
2ー
||=11/- + (p - 1). . -3) 2 T TV2 f()))
<(() (p - 1) of p-2 2
2 3q
(z) + (p 11 1). 3p- 22 f(g)=
(15)
Cp
where in (a) we apply the upper bound from Lemma D.1, in (b) we pick 0p: Pp 2 such that 1/ap- + 1/Bp = 1 (we will choose them later), in (c) we apply the lower bound from Lemma D.I. in (d) we use the choice of our weights in designing M and Theorem 2.3 and finally in (e) we use the following calculations for the regularizer term for some z E Rdd,
(x) = Cp || 4ll :
(z) pC, a q a1l2=2 M(x - 9)
p || alliT M(x q)xx - -) M 2 3g (x)= = pCp ||0 - U || M + p(p - 2)Cx ||0 - alliTa ((x - -q) a) "=²² 2x(22)
42 (x) = pCp ||= - allk>² M + p(p - C2
Combining equation 15 with the definition of fg gives us,
z [VD = z 2 f()) V
38

---

Published as a conference paper at ICLR 2026
qusing equation (p- 18 2 V= [(q)=+ + (1+ (v 1) (0- a..
2 V 9q (2)2
Cp
Thus, in order to finish the proof for the upper bound we need to pick ap, Sp. We split the analysis here into two cases: A. p > 2 and B. p = 2.
Case A. (p> > 2) For simplicity we will just pick ap = p - 1 and 3p = p-1 which implies.
p-2
V fg(xx)= S 1)) (1+ p 1 (1+p-2)
2-2) 2 = =V\= +
p-2
11 (p- 1) (p 1
= 2T 1
[V)gg(x)2
Cp
S (0- 10-11 1) ez T {})(()) (1-
---1-- 1)p-1
(p- -
(0)())))
Cp
(p 10-11 1) e
[+ (p 170-1
T (V Vigg(z))) +
2 z
2
Cp
<(>22) p. ez T (2) + (1+ (p- 1)m=1
(p- 1)
TV (z)(2))
Cp
2
V hg (z))= + 1 1)-1)--1
(p- 1) e) 2
V (x)) ,
cpp
2
11 emmaa 1.10)
p ez (2)g(z)z
where in the final inequality we use Lemma D.10 which tell us that for p 2 2 the constant in front of = T V2 (a)) is negative along with the fact that =T V
g2 (2)z is non-negative. To get the lower bound we first exchange x, q in equation 15 (and use the values of ap and 3p) to get,
p-2 2 TT(2(())= S (p- 1) (p- - 1)p -2 2 = 2T TV gz))))))+ + (p - 1) (
1
z v f(x)=
cpp
+ x xv < (p- (p-1)p -1p-1
2 T
9x (q)
+ (p 1)ez T v2 f(x)z
epp
(p- 1)e [q)z= (p (p-1)p- 1)p- z TV Jm (q)z S = [>2
222p
We can finally lower bound,
z TV fz)))()>== = T 22 f(x)=+ + x (x)()))
(p-1)- 1)m-2 T V2 (g)z + = T [V²gg(z)2 ,
2 (p- 1)e* z V22 f(q)=
62p2 =
(p 11-1)=2
T (V2hg(z)= - V²gg((z))
z VV2 I [V29g(z)2
2(p -1ee*
62p
> (o))
1
2 T (2 + (1-
(p- (1-1)=-2
[V2gg(0)=
2pc
2(p - 1)e
c2p'
1
(emma D.1I)
= 42
(z)
2pe
where in the final inequality we use Lemma D.11 and the fact that 2 T TV2 (²)g()) is non-negative. This finishes the proof for Case A.
We finally consider the corner case with p = 2.
Case B. (p- 2) In this case the proof is trivial, and follows from simply writing the quadratic forms for Ja and hg. We do so below,
fg()====== = = f()))=++ (z)
(())) :
22 Vz + 2C 11 = [T
39

---

Published as a conference paper at ICLR 2026
which shows the relative smoothness with constant of which is smaller (and hence better) than the claimed constant (for p = 2) of 2e in the lemma. Now for the relative strong convexity we do the same,
V fg()== z V (<)) 20 1|=1|
2z V f(x)> 2C2 [
2 2 1 2 (g))22)
which shows relative strong-convexity with constant of which is larger (and hence better) than the claimed constant (for p 2) of J. in the lemma. This finishes the proof for Case B.
This completes the proof of Lemma D.9.
We prove two small technical lemmas that we used in the above proof now.
Lemma D.10. For all p 2 2, x(p) = 1 (p-1)8-1
(p-1) 1)
2 < 0.
epp
Proof. First note that at p 2 the function takes strictly negative value,
(1
4e - 26 < 0
( 14 +
22
4e
We will now show that the function is increasing in p for p 2 2.
g'v)) (p 10001pp(1a +1) (p 1)p
(In(p 1) + 11
p2p
pp
2
(p 1)8-1 In(p/ (p 1))
<
p?
Thus, the function attains its maximum value at p 2 in the range p 2 2, implying it is strictly negative in that range.
Lemma D.11. For all p 2 2. g(p)
(p- 1)
2(p-1)) l)e
6 pp
Proof. First note that at 2 the function takes a strictly positive value,
1 10
1
4ea -e -
9( =
>
2e
2222
2e
4e
46a
We will now show that the function is increasing in p for 2 2,
(p - ((n(() +1) (p- 1)P
(In(p - 1) + (p -
g'())
+
2(p
1)26
22p20
c2''
(p - ()np)(n(p)) + 1) (p- 1)-1)--- 1)8-2 (In(p -1)+1 - 1/(p-1)) 11)
+
2(p
1)2e
e2p2
e2pp
(p - 1)2-2 (In(p/ (p 1)) + 1/(p-1) 0.
2(p 1
e2p'
Thus, the function & attains its minimum value p 2 in the range p 2 2, implying that it is strictly positive that range.
D.3.2 STRONG CONVEXITY OF THE PROXIMAL OBJECTIVE AND FRIENDS We begin with showing that the proximal objective enjoys a form of strong convexity.
Lemma D.12. For all d Rd, have
4 (IAdl?, + +Cp (Id((a))
fa(x + d) 2 fa()) + (Vig(z). d) + 2F
40

---

Published as a conference paper at ICLR 2026
Proof of Lemma D.12. Let Kp 2n
The plan is to apply Lemma D.3 to fo + d). We start with the regularizer. Notice that
| + d - qllaa
/ (xc + d (d 9)
/ ②) +M P
>1eemaa D.3)
M 1 - 2) 1/
(16)
pp |M (xc 2)
1/ 10-2 M2 (x: - q), M -)), + Kp |
x glliu + (p || ul|i>² M( - q), d) + Kn llllir
= a q all + < (1L= - n ( : d) + K2 l|d
(17)
We combine this with the conclusion of Lemma D.2, giving
fa + d)
f(x + d) + -
eermmn D.2) f(x) + (Vf(2), + K2 Adl + Cplla + d - -lll
equation 17
Adll' Cp | qll
+ CG vv [)) ||
= f(x) + Cp - (fe((())) + Cp || alla) d)
+ Kp Ad G. + C |d]
fg()) (z) (z)),) d) Kp (IAdlE,, + Cp [Id][(s)
completing the proof of Lemma D.12.
We also show that the subproblems we solve in Line of Algorithm 2 are strongly convex.
Lemma D.13. Fix z, q, d E Idd and let > 0. Consider the function
g(ø) = (z, x) + (1 all + Cp || qqlim)
Then,
gla + d) g(x) + (Vg(z), d) + 1 (idl 40p
|dllis
20
In particular, if 2 is the minimizer for then for any d E TRd,, we have
2
g(z d) g(z)
1/P
||d| Idlmm= S p- (4
Proof of Lemma D.13. This is pretty much the same proof as Lemma D.12. It easy to check that
[ + d) - 4 - = | q _ + (2v2 f(g)(( q), d) + [
(18)
and using Lemma D.3 in the same way as in the proof of Lemma D.12, we have
4
[| + d) q 4 >
equaaion
|| q ll
(p 2 M(x - 9). a) +
|d
2p
Combining this with the definition of g gives the following,
g(x + d) = (z, x + d) + L (I + d - g + Cp || + d d
equation 18, equation 17 (z, (z.d) + L | g ( (2V2 [q) 2),d)
| ul + (p || - u M(x 9). d) + 4
+ T. T.l + I.Cpp
l| M
2
41

---

Published as a conference paper at ICLR 2026
= g(x) + = 1=+2LV f(q)(z - q) + LCpp
allM² M(x - -))
+ L [|d|| (ldd| + 4Cp
|ddl'x
2
= =g(x) + (Vg(z), d) + [|d|
+
4Cp
||
2
which proves the first result of the lemma.
To get the second result, we observe that V=(=) = 0 by the optimality of z. Ignoring the ||d] f()()) terms and rearranging gives the conclusion of Lemma D.13.
D.3.3 SMOOTHNESS OF THE PROXIMAL ORJECTIVE
We first bound the operator norm a matrix related to the Hessian of the proximal objective.
Lemma D.14. For all q: E Rd we have
M 1/2 (V2 M M- 12
sp (2/(1))- -0 C, bly -
)
op
Proof of Lemma D.14. Recall from the proof of Lemma D.9 the definition of the regularization term 9gl Cp lly al for Cp = ep" as well as the following calculations,
(gy Cp l1y q l
Vg (y) = pCp y q M(y q)
V (v) pC, y 4lli=² M + p(p 2)C,, 11 Uाi Miy 2) - 9) TM.
By Lemma D.9, we know that
fgy) I ep (2V2 + 9r))
Observe that
M M-1// 1/2
(v)) M M- 1/2 = pCp (Il- ul|اT + (p 2) Iyy "اأ M 2 - 4)(y - g) 22
3 pCp 11
q ||<22 1P-2 I (p 2) 1 M - M - -)( - 9) M
op
qlli> 1 I + (p- 2) ly " |M -a) 011? II,
3 pCp ly
q
3 p(p 1)C ly q p
and, applying Lemma D.1 (with 1 as the vectors in the quadratic form) and Hölder inequality
with norms ||
(le/((-2))
|| /lp/2. for z E R2d we have
m
x MM-1/2 (v2f(q)) M 1-1/22 < p(p 1) Σ
As. q 1s.11--2
Ag M 1/2
2
m As, M 1/2
splp 1) 1)
[As - bs.
$ s 1))()))
M 1/2 x
= p(p 1- 11
M
Combining gives
1-2 (V2)(()))) M- 1 epp 1/ vigg()) M-1/2
3 2ep 1) ep² 1)C, lly q M
3 - 1) (2 Gp | -q --
completing the proof of Lemma D.14.
42

---

Published as a conference paper at ICLR 2026
Next, show a bound on the norm of the gradient of any solution that is approximately optimal for fq.
Lemma D.15. For all q, x IR4, we have
|M fala)ll ep (f(a)*=3+ Cp max {|| gllm || allaa ||e Fallx
Proof of Lemma D.15. We use a continuity argument. By Taylor's theorem, we know for some along the line connecting æ and wy (minimizer of fq) that
(z)) (2ggg)) 42 fa zq) Va) Fqg)
Taking M 1 -norm of both sides gives,
[Vg()))
M M- 1/(2))
M M-1/272fg(y)(== -2g)))ag)))) 112
M (
zg)) 111
M 1/ (V (v))
M 1/2
| Fgg PgllM
op
The rest the proof involves bounding the operator norm term. Lemma D.14, from which we get (using convexity of || [l))
This follows directly from
M MM [2 1/2
S <ep2(p 1) (2(())²= + Cp =lli²²))
op
S epp 22( Cp max {1Lx allm 1 - allm)>->
Putting everything together, we get
[M-'Vf(( [=V S sep2(p-1) 1) (2f(g))- Cp max {11 ql :111g qll | 1 ||
Fgg Ml
completing the proof of Lemma D.15.
D.3.4 SOLVING THE PROXIMAL SUBPROBLEMS
We begin by showing that the optimal solution to the proximal problem &g. = argmin Sa. (x) is not too far from x²"
mERd
Lemma D.16. For all proximal queries qt. we have
|| xx IM d (2+ + +4).
Proof. the rest of this proof, we omit the subscript wherever it is clear which iterates we are working with.
We first show that
|: allm S ||x= allm
To see this, suppose this is not the case. Then, we have
f(x") + Cp || allha < f(xg) + Cp ||00 - -llf2
which contradicts the optimality of x, for fg-
We now write
[gq.
x x'1l
< || q: full + 1|
q: Il
< 2 ||
q: Z
43

---

Published as a conference paper at ICLR 2026
2 x= =='l ||0, x='1 ll
where in the last inequality, we used the definition of q, from Line in Algorithm and the convexity of || llM- The required control on 1/ --= =*IlM comes from Lemma B.5 and Lemma E.5 (along
with re-scaling assumption to make the optimal value 1) - we have
1/ xx IM S v2 - Il S 4d
For the other term, we apply Lemma D.2 and get
> x² ll 23 (f(x;) (() < 2àd f((x)).
Adding gives us the conclusion of Lemma D.16.
The next few lemmas are targeted at solving the proximal subproblems. We begin with a calculation that we will use showing that the initial Bregman divergence between our initialization and the optimum is small.
Lemma D.17. In the same setting as Lemma D.9. for all æ, y E Rd, we have
hg(#gg S p(p 1)f(q)²= 1- |لا
qlli + Op | 4ll f()) + Cp 11 allir s 2f(g).
Proof of Lemma D.17. By optimality of xg for the subproblem, have
f(zg) + Op و|اا - allk S f(q) + Cp 11 allia = f(q).
Rearranging gives,
|00g allba < f(g) f()))
f(g)
(19)
Cp
Cp
We now use the definition of hg and Lemma D.I to write
hy (2xg)) = |1:g 21|² - + Cp ||a. - <llia
Lemma D.I plp 1)
A 5,
1s,
|As((a,) 22112 Cp || - -lliv
iml
1-3
$ +
(10) plp 1)
Σ
|As q bs, 112
Σ |IAs, (xtg 9]113
Cp وx
(0)) p(p 1) 1-2 |:0 -l1 MMMMa
+ Cp ||0g
qllhv
2
f(g) Cp
qquatonn 19 p(p - ())(g)
+ CCp || 411ia
=C, (p 1p f(g) + Cp ||
cp
< f(q) + Cp | <li
equation 19 2g(
where in (a) we used Hölder inequality with norms || (lp/((-)))> || 1lp/22 and in (b) we used Theo- rem 2.3.
This completes the proof for the series of inequalities in Lemma D.17.
We now have the tools to show how to approximately solve problems in Line 3 of Algorithm 2 when applicd in our setting. Although this and future complexity bounds depend on f(x),, we will later be able to use Theorem B.3 to "bootstrap" and get unconditional upper bound below.
44

---

Published as a conference paper at ICLR 2026
Lemma D.18. Let S 1/2. In the context of Algorithm 5, there exists algorithm that approxi- mately solves subproblems of the form (for p 2 2 and L = =pe),
argmin (g.x) L 1| allo)/(0) + +Cp 1| -q11a)
=ER
in the sense that we output for which,
max [|z==Ilm: M 1 2L (M- Cp || q allia2 (x qi) 10mmmb sa m
The algorithm takes p ( log
pdt fla)
linear-system--soles in matrices of the form BBA for
block-diagonal B, where each block in has size |S [Sa]-
Proof of Lemma D.18. This proof is lengthy, and splitting it into lemmas would disrupt the intended reading flow. So we break it up into several key components here.
Motivation for the lemma. First, let us see why this lemma is even useful. In each iteration of Algorithm 4, which in turn calls Algorithm 2, the main primitive computing
T; = argmin fq. (ā.-1) + (Q. (i.-1), ã x.-1) + peDn.. (ū.ē;-1)
BeRd
argmin fa. (i; + ( fq. (i; Ā x + pe (hq. (t) - ha. (ã;-1) (V Vgg (2) (0;-1), x)-
#ERd
argmin Sq. (ãi-1) peha (i. 1) + (v (z: 1) pe Vlg (i; 1), Tz-1) 1) + pelia (x)
aeR!
argmin (V (3:-1) pe V hg.. (3: )) + peh.. (क) aex"
Observe that the subproblem is of the form
argmin (g, x)) + pehn (a:
wERd
argminn (g. x) + pe gll= s(a) + Cp || - qlla1)
(20)
=ER*
and so our goal is to show how to solve these types of problems.
The general algorithm.
Consider solving the related subproblem (instead of equation 20),
argmin (g.z) + L (II= ملل + C, 91 2 #ER4
for some fixed 2 0. This is quadratic problem, and therefore solve it in linear-system-
solve. It is easy to check that at optimality, we have
g + 2pe (V f()) 9) CorM(x -q) =
which rearranges to
1 2pe
(v2f(g) CTrM) g
q q=
Note that at optimality for original subproblem equation 20, we have T* := 11== where
z is the solution of subproblem equation 20. Also note that || allm is a decreasing function because,
|
Ap2e2 -
and for S T2,
(V2 [V))(g) C) M (V2)(g) CTTIM) 2 (v2 CC,m)
C,TMM - M (V f(2) G,raM
RReall that f(g A B,A for block-diagonal by construction, A A where W consists of the block Lewis weights on the diagonal. Thus, v2 + C,rM = A A A for black- diagonal Bg.
45

---

Published as a conference paper at ICLR 2026
We therefore see that if x q a where is the optimal solution for a fixed then we are regulaagug and need to decrease T and versa. This means we can binary search for the appropriate value of To execute this, first need to establish the accuracy up which we have to identify T.
Convergence Argument. By Lemma D.13 (setting x 2), recall that it is enough to solve sub-problen equation 20 up additive accuracy (p/2)² Lae to get | = S a. Suppose we find r for which F* & T T" + 6. By writing the objectives and comparing. we see that the a find from using gives the bound from Lemma D.13 tells us that we should choose = (p/2)p To2 hooe//d /d, and plugging this steps, as needed.
most 8 d-suboptimal solution compared z. Plugging this into
into the binary search over r E [0, (1 + [(g)) gives us po(1) log pat f(a)
First-order stationary point.
We first claim that it enough to get
VM - M Vhg a
Indeed, let be the optimal solution for the subproblem. This means that it must satisfy the first order stationary condition, namely,
+ LVhg = O.
Multiplying both sides by M subtracting, and dividing both sides by L gives the expression we are interested in.
Writing first order stationary conditions gives both
+ 2L ((9)((=====(x--)))(e)>>(>)) - + -)) 4)) 21 (V> - CpT -)) = =))=
Multiplying both sides of both equalities by M-1 and subtracting these gives
2L M 22 f(a)(( 2) + Cp (r(x 9) - - - 4))) =.
Expanding out L(M (2)
M M (=) and subtracting the above gives the desired condition
2L r x p-2
|
q all
Next, let run the binary search from above so that we get argument convergence, i.c. || = =|IM= S a < 0. for some constant C. Using the fact that the approximate mirror descent step using decreases the objective value (Lemma A.4), observe that
x - 4ll S I - MllM + | - = S ||q - 2 + $ vd(1+ + f(g)).
then follows that binary searching т to additive accuracy al alvd(1 (()())(())))))) sufficient. By the same argument above, this takes 0(1) log pddf(a)) steps, completing the proof of Lemma D.18.
We now combine Lemma D.18 with Theorem A.1 and Algorithm 2 to obtain approximate argument optimality for each proximal subproblem.
Lemma D.19. Let 7 > and xq argmin (x). There exists algorithm that returns for zeRd
which
|| 2gllm S
The algorithm takes at most O (D)(1) log ( (1)) )) iterations of solving subproblems of the form argmin (g. x) + ephy(x)) (x) for fixed vectors and #ERd
46

---

Published as a conference paper at ICLR 2026
Proof of Lemma D.19. This proof resembles (Jambulapati et al., 2022, Lemma 4.5), which uses an exact version of mirror descent arising from Lu et al. (2018). The main difference between our argument and that of (Jambulapati et al., 2022, Lemma 4.5) is that rigorously identify a concrete upper bound on the complexity needed to satisfy the MS condition and argue that the mirror descent algorithm can handle the inexact Bregman proximal problem solves.
First, we use Lemma D.12 on the approximate solution æ and true solution ii and get,
[a( 2 [g( +
4
[IA(zz (aax=)=)1 + Op || - x 22l(a))
2
4Cp
2 fg(x) +
p
|| x: xIIMM
20
Rearranging, we get
2P
1/8
|00 - x111 1
(fa(z) - -
AC,
2F
1/8
(fg(z) -F((zgg)) 1/8
4epp
2
(f(()) - fa(
p
Using the notation from Lu et al. (2018), for convex h: Rd - R2 let
(x y) = h(x) h(y) (Vh(y), x y)
Recall the conclusion of Lemma D.9 we have for μ = 12pe)) and L = pe that
4 hg (x) = 2 fg (z) = hz))
By Theorem A. and Lemma D.9, using the same notation from Lemma D.9, we have for all itera- tions i of Algorithm 2 (with f f4 and h = hgg) that,
fa(w;) - fa())) - L (1 (1- Dn. (x ②) + max (Ai, 3; xg)
IsiSt
= 2L (1 (1- " hg hg(wag)
max Isist
(4i xt xzg
Hence, for 2 L log (1/hg(rg))
4 p7
) ) it is easy to check that for 2 2,
log( Ling (Lh ((a)))
fa(xz) - ,g(arg) 2T.
hg(
+ max (Ai, Dr Fgg)
18i5t
pr
2
max (Ai, 8t. -rrg)
15i5t
P7
(A,, xz -
ISSE
and combining this with Lemma D.18 make the error term on the order of our accuracy, we get || - xlIM S 7. We thus conclude the proof of Lemma 1.
The last step use our proximal problem solver to build a valid MS oracle.
Lemma D.20. In the context of Algorithmm 3, there exists an algorithm (ex+1,)4+1) Oprox (gr)
that approximately solves
argmin f(ă) + ep" 1 qi I
aER
using O ( (10)) log p(a.)
linear-system-ssolves in A T BA, in the sense that
M V + + qi)
| qellm-
epe+1
1|
2
M
47

---

Published as a conference paper at ICLR 2026
Proof of Lemma D.20. The point of this proof is to give analysis of Algorithm 4.
For notational simplicity, let æ = 1(+1 and = Ae+1- We will reintroduce the indices when it is essential clarify the iterations we are discussing.
First, it is helpful to why the stated notion of approximation is useful. Let Cp ep". Observe that at exact optimality, we have
(x0g) epptt 110g
allss M(x ②) -
(21)
This motivates the approximation in our lemma statement, with us asking for a --aprroximate MS oracle (Definition B.1) for f. This also tells us that at optimality in equation 21, we have,
V (z)g) + eppt1 ||
q q
M(x 9) =
+ M (1/2)((zg) = =pppp ||
all'm 2 (x q)
M 1/2 (M1125(zza))
ppCp1 ||
allba / 9)
+ 20g allm=
pCp
We now break up our analysis into two cases. e/ |m= x= x=IMM: Then, by convexity, we have
In the first, suppose that || V S
f(xg) - f(x') z (VI(xg), x²) M MM/VV/(ag)))) |00g - x x''l Il Se.
Hence, for the rest of the proof, assume that M (V) not the case, in the algorithm we can simply check whether the MS condition is satisfied - if not, then we know this assumption was violated and we are done anyway). We run the algorithm implied by Lemma D.19 and obtain an approximate solution for which
f| 100g-=1llpp I*IlM (because if this is
Cp cp(p (p(p-1) 1)
||0g all M
P-2
| 2ig MM S a: ||2gg all for a min
1
(22)
f(q)² :
Since the guarantee in equation 22 gives us,
| xq M S a || allm 5 a
| all
(23)
and further applying triangle inequality gives us
|:0g 4ll < ||0
+ |10g æ2ll
M
1
<
| qll + 1 1 a
x a M
1 - a
1
| ql PM
(24)
1 a
Hence, we get
cp(p - 1)f(q)=
|| xgllMM = ep(p 1p(--1)
f(q)
p-2
|x-- - xyllM
Cp || -
1 2-
Cp
| - q Il
equation 22
|10g 9 PM
1
1
sequntion 24
5
1
||
M
< x q
all
(25)
48

---

Published as a conference paper at ICLR 2026
where in the last inequality, we used that due to our choice in equation 22. We now call Lemma D.15, divide both sides by X, and get
M (x(x))
+ (x-
q)
eppt1 |
Mll
1--
IM
[(q)== 11
[ AllM
v-3
}) | Fgllm
LLmmma D.15)
ep(p-1) 1)
+ max {
Cp || - qllM
1 q M
f(q)² 3
equation ep(p 1)
+
11 - Fg lgll
Cp || - MllM ?
(1 a)m-2
requation 23 ep(p - 1)ʃ(q)
|| aallM + cp(p 1)x
|| - all
Cp x
q qllM
(1 arp-
sequation 24, equation 1
+ ep(p - 1)50-2
|| gll
x 9 all
40-1
1 x qll $ 2
giving us the approximation guarantee.
It remains to understand the complexity of solving the proximal subproblem to the accuracy required in equation 22. Plugging in y a Fy qilM into Lemma D.19 and using our bound on hg (2gg) from Lemma D.17 gives an iteration complexity of (ignoring the constant in front of the big-O)
p (1) log
pa |.z -911m/ =1
2
)
<p log
p (p(o- 1)f(g)) 1-2 =||0gg 911>> + +pp ||:g allbs)
(
2
all )
(pae 1|:0a
pp log
( p )
2
p(p -1)s(g) 1- || q aliir + Cp 1| 2 lll
ap 18g - 4llir
2 p
p(p 1)
1-2 Cp
= o log
ap ||
q 9
M
We have two cases to analyze for the value of a. In the first, suppose we get a = 5. By the definition of a, this means we have
D-2
Cp
|10.g 9ll
21
ep(p-1 1)
f(9)
which means the complexity we get is p(1) log We now handle the other case, i.e., a p-2
Co
||m | Ml
Here, it will be useful keep track of the timestep t that are working
1cplp-1j
f(q)²
with. Recall that
V (
-
+
||
qe q0ll2x
(26)
pC,,
pCp Lq..
x PM
so the complexity we want to control is given by
log (2)) P
2f(g:) - 11
p 0(1) 10
ap 12g.
Sequation 22 0(1) log ((2)
{2)²
2 (5ep(p - 1))² f(q.)=-1
Cp
|ppp 2)
Dgg. 9:l
49

---

Published as a conference paper at ICLR 2026
S 1000lo log p 2 11)0 f(q:) )m
00
pad
| - 91 M
p(p-1)
2 2110e(p - 1))2 pplp+1) f(g:) (09:))-11
eeuuation 26
p pll) log
11 - x "liv
pp² c0
2 (100(( 1))2 p )(g)))-))
Sepuation 26
p pou
log log
|
x0 a0llba
6
pf(g)) [gg - x= lM
(() log
pf(q))
Lemma D.16)
00 log
pf
Kemmma D.8)
p p log
completing the proof of Lemma D.20.
D.4 THE ALGGRRITHM
We are now ready to combine the results from the previous two subsections to build our algorithm for gy-regression and prove Theorem The main algorithmic object here Algorithm
Algorithm+ 5 GpRegression: Optimizes equation 4 up to (1 + =) -ullipliccative error
Require: Regression problems (As, b..)....: ..: (As.. bs... accuracy > 0 1: Using (Manoj & Ovsiankin, 2025, Algorithm 2) with input [A])], find nonnegative diagonal W such that for all æ E Fd and IR,
|| Ax cbll.
W
A cw (2(d ()) || cblls...
2: Let
A
W 3 AA)
A w
b.
t 3D = argmin =E
w Ax w
3: Using Algorithm and Lemma D.20, implement 1 -MS oracle for f (Definition B.
4: Run Algorithm 3 with the oracle from the previous line and with as the initialization for
O po)((p) min (rank (A), m] $ log (+) iterations.
5: return the output of the previous step.
Proof of Theorem 2. By writing the stationary condition of the proximal problem, it makes sense to choose dc+1 ep |[+t11 Ill
easy to check that
To
epp+11 ||
98 p- M ((epet)) --
1 qellm=
and therefore the triple (3.+1, Cr, ep ||ā gt 11 always satisfies (p- 1, (epp-1)2/(0-) movement bound (Definition B.2).
Next, we calculate the iteration complexity we need to reduce the enror to half of what we started (z5(f(()) - f(x)). By Lemma D.2, we have
with. For an arbitrary initial iterate æ.
|| x: lI <
f(x*)),
MM
combining this along with the fact that c* ep and applying Theorem B.3 with our proximal solver Lemma D.20 yields
p p-1 (DC, 230/2+1 10/21)))1/1111)11 - < 1/3
Tmin
3
50

---

Published as a conference paper at ICLR 2026
Next, we initialize z0 = (A T W w/P//AA) -1 -/2/bb.. Using Theorem E.3 and Theorem E.4, we have
f(x0) - (000/211((x)))
so reaching an iterate a for which f(z) - f(x²) & Ef(x*) takes Tiin log (d//2-1/E) =
p ///3 log ( calls to prex-
We now resolve the full iteration complexity, including the bootstrapping step show that f(x)) is reasonably bounded so that we get unconditional upper bound from Lemma D.20. At the end of iteration f, from (loosely) inverting the bound in Theorem B.3, we know that
fxx)) - f(x") < (Cp²) J (2d)
By
Since T only depends on qr which in turn only depends on æ; and un, it suffices use the above bound for f fxz), which gives iteration complexity of p01) log we get from plugging into Lemma D.20).
compute œ;-1 (which
Combining this with the iteration complexity of O prax gives the result of Theorem 2.
E BLOCK LEWIS WEIGHTS AND PROPERTIES
In this section, introduce block Lewis weights and explore of their properties. Several of these statements can be found Jambulapati et al. (2023a); Manoj & Ovsiankin (2025), but we include definitions and proofs here for self-completion.
We first need to define leverage scores.
Definition E.1 (Leverage scores), For matrix A Rexd with a1,.... Ons let Tj denote the jth leverage score of A, which we define to be
(aj, 20
(A)
= max (ER |Ax||
0 (A (ATA) a,
We now introduce the main object of interest in this section, Definition E.2. Our version of the definition is adapted from (Manoj Ovsiankin, 2025, Definition 1.2) (there, we set P1
Pm 2, let their W = I, replace À with w/ ||w/], and rescale 5* appropriately).
Definition E.2 (Adapted from (Manoj Ovsiankin, 2025, Definition 1.2)). Let w E R and
W 20 be diagonal matrix for which for all E S, we have W;; = Let >> 0. We say that is block Lewis overestimate for all i E [m]) we have
Ejes, Tj
w (
<1
Wi
The main reason that Definition E.2 is interesting is that it gives formula with which we can relate the level sets of the group norm Il-1lg, to lz. See Theorem E.3.
Theorem E.3 (Block Lewis weights give us ellipsoidal approximations to I1-11g,). Let 2 2. If a block Lewis overestimate, then all æ E Rdd, we have
Aar
Amlle & | Am
We prove Theorem E.3 in Appendix E. An analogous statement can also be shown for p S 2, but since do not in this paper, do not write it here.
Observe that if we can get w that satisfies Definition E.2 and for which ||w|| = rank (A), then Theorem E.3 gives us the optimal relationship between & and [1-1lg, whenever rank (A) <
51

---

Published as a conference paper at ICLR 2026
Furthermore, for intuition, suppose p oc. By John's theorem, know that for any symmetric convex body, there exists an ellipsoid such that the ellipsoid approximates the convex body up to a Vd distortion. Moreover, this is worst-case tight (e.g. the best distortion we can get when we approximate ef with lg is vd). Thus, assuming we can find || = rank (A), in this case, we get guarantee that is similar what John's theorem tells us.
Now, assuming we can find a low-distortion ellipsoidal approximation to the level sets of our loss, we get that the "effective" diameter of our problem is ~ vd. Combining this and the discussion in Section 2.3 (or, more formally, Theorem B.3), we can see why we should expect an iteration complexity of /3/3 (or better, if we can find better ellipsoid).
What left is whether weights w satisfying Definition E.2 with small sum can be found. To this end, we invoke (Manoj & Ovsiankin, 2025, Algorithm 2).
Theorem E.4 ((Manoj & Ovsiankin, 2025, Algorithm and Lemma 5.6)). There exists an algorithm that returns block Lewis overestimate for which || 1 I 2rank (A). The algorithm runs in (log m) linear system solves with matrices of the form A D nonnegative diagonal D.
Thus, by applying Theorem E.4 as a preprocessing step, we get an l2 geometry under which we can the accelerated proximal algorithms. As example of the power of this, observe the following.
Lemma F.S. Consider the matrix A = Alb E Rax(d-1) that is formed by appending the column vector b to the right of the matrix A. If we have vector w of block Lewis overestimates for the matrix A, then there exists an algorithm that finds an initialization No for which
x - x1'
< 2 (2rank (A))² ||Ax" - bll.,
A
W A
FA
| - blla, & (2rank (A)) ||Ax" - blla,
The algorithm runs in 1 linear system solve in A DDĀ
Proof of Lemma E.S. By Theorem E.3, our weights ur are such that for all x E IR" and reals c IR,
W + A. cwi || cb
- / Ax ot
(2 + 1))
Let Zg be the solution to the least squares regression problem
2 AA) A Tw - W 1 Ax w w 1b|l (A Awww-
3g argmin
#ERd
It is easy to see that computing De amounts 1 linear system solve in A DA.
Next, let M A- A and observe that
|20 xx IM= = W w Aac w bb) -(W3- Axx -
22
2 W -a--- 22(d)) - ||Ax* - -bllo..
Finally, write
| bllg, < - - Aa0 - w 166 -
< W - A w - 5 (2d)
1 ||x - -llo,
giving us the conclusion of Lemma E.5.
Proof of Theorem E.3. Let X == w/ [wwl and A = probability measure [m]. When p > 2, using monotonicity of Lp norms taken under probability measures, we get
W/| It is easy to check that is
1 = Σ A
2
1/2
1212
\ As x
2
Σ
A
AS
52

---

Published as a conference paper at ICLR 2026
Expanding the RHS and substituting X, w///
||||| gives
W
: A.
|
For the "hard" direction, we will use Definition E.2 a nontrivial way. Notice that
m
1
m
P
1/
W
A
S.
WA
W
As,
W
As
2
W/ 1
P-2
A S. x
m
1
Wi
Wi
8, 2
12
meR
max (0))
W 3 A.r
P-2
2
3-11
-1
1
A S.
m
Wi
1
max (E
W
2 1
A.
1--
W 1
Ax.
2
Ejes, Ty (W3-$A)
3-1
2
Wi
F
A
s
20
[ - Ax
2
W4
2
1
Definition E.2
S
Σ
m
Wi
A
8, a
W $
A.
p-2
w $ Ax
so combining our upper and lower bounds gives the conclusion of Theorem E.3.
F EMPIRICAL EVALUATION OF OUR APPROACH AGAINST OTHER BASELINES
F.1 SYNTHETIC HETEROGENEOUS REGRESSION CONSTRUCTION
We construct synthetic group-structured regression problems designed test optimization under severe group heterogeneity. The data consist of m groups Each group i has its own design matrix As, and target vector bs,, and defines quadratic loss
((x)) =
A x bs. 11
The objective of interest is the worst-group loss (as in equation 2)
F(x)
max (x) iE (m)
We generate two qualitatively distinct group types to separate average performance from worst- group performance. The majority of groups are benign and geometrically aligned, whereas a small number have very high curvature, are geometrically misaligned, and are far from the population cen- ter. This construction ensures that minimizing the average loss does not coincide with minimizing the worst-group loss, and that curvature heterogeneity strongly affects optimization behavior.
We construct all group covariances relative to a shared orthonormal coordinate system. This al- lows to control curvature across groups Each group, therefore, has a quadratic loss whose Hessian shares eigenvectors with the others but whose eigenvalues vary across groups
direction while keeping
the ambient geometry comparable
53

---

Published as a conference paper at ICLR 2026
Normal groups. Most groups are generated with moderate condition number. Their Hessians have eigenvalues that vary across coordinates but remain within a controlled range. The correspond- ing optimal parameters are sampled from distribution concentrated around common center in parameter space. Independent noise is added to each group so that these losses are smooth and moderately curved. As a result, normal groups are geometrically aligned: their curvature structure is similar, and their optima lie in a relatively small region of parameter space.
Outlier groups. A small subset of groups is constructed be adversarial in two distinct ways. First, each adversarial group has one direction with extremely large curvature, while the remaining directions retain moderate curvature. These sharp directions differ across adversarial groups. Sec- ond, the optimal parameter of each adversarial group lies far from the population center along its corresponding high-curvature direction. In addition, the noise level in these groups is set to be very small, their losses sharply concentrated around their optima. Together, these properties ensure that deviations along the sharp directions incur very large increases in the worst-group loss.
Implications of our construction. This construction produces three key phenomena:
1. The stacked design matrix has large condition number.
2. The curvature directions that dominate different groups are misaligned.
3. The empirical risk minimizer (which minimizes the average loss) can perform well on most groups while incurring substantial loss on small number of adversarial groups.
Because most groups share similar geometry, gradient averaging implicitly emphasizes their curva- ture structure. Therefore, first-order methods, reduce the average loss efficiently but make compar- atively slow progress along the sharp directions that control the worst-growe objective. In contrast, methods that adapt local curvature explicitly control worst-case behavior continue to de- crease the max-loss objective.
For the default instance used in Figure 1, the problem dimension is d = 10 with 100 groups, of which 5 are adversarial. The stacked Gram matrix has a condition number on the order of 108. and the empirical risk minimizer exhibits clear gap relative to the robust optimum computed via convex programming. For more details on data generation, see the included Jupyter notebook.
F.2 COMPUTING THE ROBUST OPTIMUM VIA CONVEX PROGRAMMING
To obtain a reliable reference point for evaluation, we compute the exact optimum value of the worst-group objective using convex solver. Concretely, we solve the robust regression problem that minimizes the maximum group mean-squared error. Although the objective takes the form of a pointwise maximum group loss is a convex quadratic.
groups, it remains convex function of the parameter vector because each
We programatically formulate this problem using the epigraph trick. We introduce auxiliary scalar variable & that upper-bounds every group loss, and then minimize this upper bound. If we write the group loss as the mean squared residual for that group, then the epigraph reformulation becomes
min subject (x(x)) S for every group i [m]] 2,
Each constraint convex quadratic inequality, the resulting problem is convex quadratically constrained program. We implement this formulation in CVXPY (Diamond & Boyd, 2016; Agrawal al., 2018) by declaring decision variables for the model parameters and the epigraph variable, adding one quadratic constraint per group, and calling a standard convex solver. We treat the returned epigraph value the robust optimum value.
In all plots, we report the gap between an algorithm's 's current worst-group loss and this robust opti- mum value. This subtraction makes the figures directly comparable across instances and highlights whether method continues to reduce the true robust suboptimality, rather than merely decreasing surrogate objective.
F.3 BASELINES
We compare the following methods.
Subgradient method. We run subgradient descent directly on the nonsmooth max-loss objective 2, using both fixed and diminishing step-size schedules, and report the best variant.
54

---

Published as a conference paper at ICLR 2026
Smoothed gradient methods. We apply eup smoothing (see 7) to approximate the max operator and optimize the resulting smooth objective using:
Gradient descent,
Heavy- -Bal (Polyak) momentum,
Nesterov acceleration.
Interior-point method. We implement a log-barrier-based interior-point method that solves a se- quence of smooth approximations using Newton steps.
Ball-oracle methods (ours). We implement two trust-region style methods that repeatedly solve smoothed objective using damped Newton solver (Section 2.2):
Euclidean geometry (naive ball),
Leight geometry, where the trust region is defined using a data-dependent positive definite matrix constructed from block Lewis weights.
After each outer step, the center is updated to the new solution, and the trust-region radius is option- ally shrunk. For simplicity, we do not consider the acceleration of the ball-oracle method.
F.4 HYPERPARAMETER TUNING
We tune every method via grid search over its relevant hyperparameters:
Step sizes for gradient and subgradient methods;
Smoothing parameters and momentum coefficients for smoothed methods;
Barrier parameters and inner iteration counts for the interior-point method;
Initial trust-region radius, smoothing strength, and radius decay factors for the ball-oracle methods.
All methods use the same warm start. For each configuration, we run a fixed number of outer iterations and select the configuration that achieves the lowest worst-group loss within this budget.
F.5 EMPIRICAL BEHAVIIR
Notably, the meaning of an iteration differs across algorithms:
For subgradient and smoothed gradient methods, one iteration corresponds to one full gra- dient subgradient update using all groups.
For the interior-point method, one iteration corresponds to one outer Newton step of the barrier procedure.
For the ball-oracle methods, one iteration corresponds to one call to the trust-region Newton solver (i.e., outer iteration).
In all iteration- omplexity plots, we compare methods using their own natural outer iteration count.
Iteration complexity. On the adversarial instances, first-order methods make limited progress. Subgradient descent improves briefly but quickly plateaus. Even the best-tuned mmotthed-gradien contrast, both ball-oracle methods steadily decrease the
variant stalls far above the optimum. worst-group loss across outer iterations, whereas the IPM converges rapidly. We also note that the IPM achieves the best final loss among all methods, which is unsurprising, as CVXPY natively uses the same algorithm to compute the maximum-loss optimum.
Runtime complexity. While we do not spend significant effort simulating a time-complexity model or hyper-optimizing our code, we also plot the runtime complexity of all the algorithms to control for the different meanings of an iteration. Because Newton steps are computationally more expensive, first-order methods initially appear competitive wall-clock time. However, they plateau early and fail to approach high accuracy. Interior-point and ball-oracle methods continue to reduce the worst-group loss gap and eventually achieve near-optimal solutions, whereas first-order methods remain stuck far from the optimum. We observe very slight benefit from using the Lewis geometry our ball oracle method.
55

---

Published as a conference paper at ICLR 2026
Convergence on Max-Loss Objective (0-100 iterations,
OPT-subtracted)
1500
ERM OPT (2.21e+03)
Subgradient Max (fixed)
F_smooth Nesterov (best)
Best-so-far (max-group
1000
IPM
Ball-Oracle Naive Geometry
Ball-Oracle Lewis Geometry
500
10a
10a
10a
Iterations (log scale)
(a) Max- suboptimality versus itcration count (log scale on the x-axis),
Time Accuracy: Best Tuned Methods
OPT-subtracted, shared init)
2000
1500
Best- (max-group
1000
ERM OPT (2.21e+03)
500
Subgradient Max (fixed, best)
smooth Nesterov (best)
IPM (best)
Ball--On Oili-Orrlle Naive Geometry (best)
Ball--rra Call-Oraccee Lewis Geometry (best)
10-7
10-6
10-5
10-4
10-3
10-2
10-1
10a
Runtime (seconds, log scale)
(b) Max-loss suboptimality versus runtime in seconds (log scale on the x-axis).
Figure 1: Comparison of first-order, interior-point, and ball-oracle methods on adversarial heteroge- neous regression instances. All curves report the worst-group loss minus the optimal value computed via CVXPY.
56


Reviews:
[{"review_id": "C9nfxnfkDP", "reviewer": "Reviewer_fntP", "summary": "This paper develops an algorithm for 'distributionally robust linear regression'. Namely, it assumes m datasets for linear regression to be given, corresponding (for instance) to m distinct data sources. Instead of aggregating the data and fitting a linear model via least squares, the distributionally robust optimization (DRO) approach minimizes the maximum ell-2 error across the m datasets.\nThe paper also considers an objective that interpolates between the aggregate ell-2 error and the maximum of ell-2 error by averaging the p-th powers of ell-2 errors. \nThe new algorithm follows a general scheme from Carmon et. al (2020), and proceeds by solving a sequence of proximal problems defined on suitably constructed ellipsoidal trust regions. \nThe main technical innovations are a smoothening of the objective, and a new construction of the trust regions.", "questions": "1. A general suggestion. I think that the technical overview is the most interesting and important part of the paper. I would suggest to make it more precise and detailed, eventually stating auxiliary lemmas. In contrast, it would be sufficient to focus on the p=\\infty case. \n\n2. Are the complexity of the inner calls in IPM and in the present method comparable? They appear to require the solution of linear systems with somewhat different structure.\n\n3. It would be useful to have an overall presentation of the algorithm. The definition is now dispersed across multiple sections.\n\nMinor:\n-I do not think the adjective \"existential\" is used correctly at the top of p 9", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is quite fundamental, and this paper improves over the state of the art.\nThe results appear to be sound and technically novel.", "weaknesses": "- The new method only improves over interior point methods (Lee ans Sidford, 2019) for large m\n- It is unclear how practical is the algorithm, given the nested structure\n- The authors apply a general framework from earlier work, and innovations is rather in specific aspects of the problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uvukCFJzkH", "reviewer": "Reviewer_caGj", "summary": "The paper presents condition-number-free algorithms for empirical group distributionally robust (GDR) least-squares regression and for an $\\ell_p$-style interpolation between average and worst-group loss.  \nThe main theoretical claims are:\n\n1. An algorithm achieving a $(1+\\varepsilon)$-approximate solution to  \n   $\\displaystyle \\min_x \\max_i \\frac{\\|A_{S_i}x-b_{S_i}\\|_2}{\\sqrt{n_i}}$  \n   using $\\tilde O(\\min\\{\\mathrm{rank}(A),m\\}^{1/3}\\varepsilon^{-2/3})$ linear-system solves of the form $A^\\top B A$ for block-diagonal $B$.\n\n2. An extension to $\\ell_p$-type interpolants between the average and robust objectives with iteration complexity $\\tilde O(\\mathrm{poly}(p)\\min\\{\\mathrm{rank}(A),m\\}^{(p-2)/(3p-2)})$.", "questions": "na", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides an algorithm that can solve empirical group distributionally robust least-squares regression with STOA complexities.", "weaknesses": "Honestly, I am not an expert in optimization theory. However, I think this paper may be more suitable for a journal such as *Mathematical Programming* rather than ICLR. Moreover, the paper does not provide any numerical results.\n\nThe complexity analysis depends on the oracle for solving linear systems, which may not be a fair comparison to the gradient evaluation oracle.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nubcUzEWOW", "reviewer": "Reviewer_Q7n9", "summary": "In this paper, the author proposes a novel second-order algorithm based on accelerated proximal methods to solve the empirical group distributionally robust (GDR) least-squares problem, aiming to improve group-level fairness in linear regression.\n\nThe proposed algorithm achieves a (1+ε)-multiplicative optimal solution through a series of linear-system solves. Moreover, the author introduces a continuous interpolation between robust and non-robust optimization, which elegantly bridges the utilitarian and egalitarian objectives. Theoretical analyses are provided for both the accuracy bounds and the iteration complexity, allowing readers to compare the proposed method against existing optimization approaches.\n\nFrom my perspective, the writing of this paper is clear, professional, and well-organized. The author explains the intuition and derivations of the algorithm in detail, and systematically contrasts it with classical methods. The theoretical sections are rigorous, with definitions and notation clearly presented. Additionally, the discussion of parameter roles and practical implications is thoughtful and accessible, making this paper almost textbook-level for readers who may not be deeply familiar with theoretical optimization.", "questions": "1. In some DRO frameworks, researchers may add more assumption on different groups, e.g. the weighted addition or Wasserstein distance. What will happen if we extend the algorithm to this area?\n2. In real world, the number of group m is rarely greater than the number of features, which influences the Rank of A. So, will the gap between proposed method and standard log-barrier IPM be not so significant in practice?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\tElegant writing and well-structured mathematical presentation.\n2.\tExtensive and up-to-date literature review that situates the work within the broader DRO and optimization landscape.\n3.\tCareful and coherent technical overview that guides readers through the proofs.\n4.\tThe paper clearly acknowledges limitations and points out meaningful future directions.", "weaknesses": "1.\tAlthough the algorithm avoids geometry-dependent convergence and relies only on linear-system solves, its numerical accuracy remains lower than that of interior-point methods (IPM) in high-precision regimes.\n2.\tGiven the complex form of the theoretical bounds, it would be valuable to include numerical experiments that empirically illustrate the relationship between ε and runtime or accuracy, and directly compare with IPM and Lewis.\n3.\tMany recent DRO frameworks adopt a regret-minimization perspective, which also leads to convex formulations with desirable properties. It would strengthen the paper if the author could discuss or contrast their approach with regret-based DRO methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qZ4rxtdwuG", "reviewer": "Reviewer_kYbK", "summary": "The paper proposes two algorithms for solving the “egalitarian”/“group DRO objective” of multi-group regression: one algorithm for the “robust” version of it—i.e., the maximum over each group’s squared prediction error—and one which interpolates from the “robust” version to the fully “nonrobust” version—i.e., the average squared prediction error across groups. The contribution is to obtain, in terms of linear-system-solves of some specific matrices of the problem, approximation guarantees that: (i) holds for more families of objective functions than currently in the literature, and (ii) can match best-known error accuracies in the literature for particular cases.", "questions": "Please, see the Weaknesses section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of the paper are:\n- It is rigorous and the authors have tried to explain the layout of their proof in the main paper, making explicit connections with previously published results that they use, expand, or improve on.\n- The contribution of the paper is clear and the problem they study can benefit diverse communities in machine learning, statistics, and signal processing. \n- Results are clearly compared with the existing literature, e.g., see Table 1.", "weaknesses": "I have a series of things to point out about the paper.\n\n**>>About clarity and results:**\n- Line 107 mentions that, compared to all other methods in Table 1, the paper’s results do not have “geometry-dependent terms”. Can the authors pinpoint what those “geometry-dependent terms” are in the other methods from Table 1? A definition of what this phrase means will be useful.\n- In line 151 inside Remark 1.2: the term “morally equivalent” does not sound technically correct. What do the authors mean by this? Perhaps another phrase could be used. \n- Theorem 2 is also valid for $p=2$, which is also the setting of Theorem 1, though the complexity of linear-system-solved are different between both theorems. Can the authors comment on the differences between the complexity of these two approximation results? Can the authors also comment on the main differences between Algorithms 3 and 5 and how these reflect on the approximation/complexity results?\n- Lines 225-226 states that “our results suggest that optimizing (...) between non-robust and robust objectives may be *computationally easier* than optimizing for the robust objective alone”. Could you indicate how this is suggested by simply looking at Theorems 1 and 2, or is there some missing information?\n- Equation (6), which is the decomposition of equation (2) or (4) into subproblems, is introduced (i) without explanation of how it was obtained and (ii) without a formal justification for it. Can the authors explain this? Also, the authors claim that this decomposition is a common procedure in convex optimization—see line 285—however, no citation is added.\n- I am trying to understand the paragraph that starts in line 356. I am sure that the second sentence is, using the notation of Definition 2.1, referring to $f(\\cdot)=\\sqrt{\\delta^2+||\\cdot - b\\_{s\\_i}||\\_2^2}-\\delta$ and the norm $||\\cdot||\\_2$. Can the authors confirm this? For some reason the authors are introducing the term “$A_{S_i}x$” as an argument, which is confusing.\n- When finishing Section 2.1.1, I don’t see any indication on how to choose the radius $r_q$ in the proof outlined so far. Is this something which is missing or am I missing something? This is important since line 366 of the next Section 2.1.2 seems to indicate that $r_q$ has already been “explicitly” constrained in Section 2.1.1.\n- Line 407: it is mentioned that the “diameter of our problem will have decreased by a constant factor”. However, what does “decreased by a constant factor” mean here? Is it an *additive* constant factor or a *multiplicative* one? I suppose it is not an additive factor, unless it somehow shrinks due to some parameter.\n\n**>> Paper organization:**\n- It is important to include Algorithm 3 in the main paper (if possible, I would also suggest including Algorithm 5, but I understand that this could be more complicated since it uses Algorithm 4 and other results that may be difficult to fully include). This will make things more self-contained. Also, Algorithm 3 shows mathematical constructions and references mentioned in Section 2, which can help the reader to better follow the paper.\n- Move Table 1 earlier in the paper, close to the first text where it is referred to: right after Theorem 1.\n\n**>>About the title:**\n- The “Block Lewis Weights” are only mentioned as part of a technique for the papers’ proofs: the reader has to wait **until the last page of the paper**, where Theorem 2.3 is, to know what they are. It is strange that nowhere earlier in the paper, **including the abstract itself**, an idea of what “BLock Lewis Weights” are provided, even though the phrase is in the title itself. Thus, I strongly suggest two things:\n  - Change the title to something like “Solving Distributionally Robust Linear Regression Using Block Lewis Weights”.\n  - Mention earlier in the paper, perhaps Section 1.1 when introducing the results, what Block Lewis Weights are and how they are used in the proof.\n\n\n**>>Other things:**\n- There is a typo in equation (4): the exponent “$2$” of the $l_2$-norm of the prediction error should be “$p$” instead.\n- In the related literature mentioned in Section 1.2, I suggest mentioning works that have studied the connection between distributionally robust optimization (DRO) and the effect of regularization on regression problems and other estimation problems. For example, two works come into mind:\n  - “Robust Wasserstein profile inference and applications to machine learning” by Blanchet et al., 2019 studies this problem in the context of logistic regression and linear regression (including lasso).\n  - “Distributionally Robust Formulation and Model Selection for the Graphical Lasso” by Cisneros-Velarde et al., 2020, studies this problem in the context of precision matrix estimation.\n- The last sentence of the first paragraph (line 029) needs a citation.\n- I suggest using parentheses every time an equation is referenced. E.g., instead of “equation 1” use “equation (1)”.\n- The paper mentions references where equation (2) has been used; however, no references are provided where equation (1) has also been used.\n- Line 145: instead of the word “promised”, a more appropriate term would be “guaranteed”. \n- Line 201: I suggest indicating in the paper that “DRO” stands for “Distributionally Robust Optimization”.\n- Line 294: when mentioning the “three questions” that arise when dealing with the subproblems, I would suggest adding the fact that these three questions correspond to three *consecutive* subproblems/steps of the main proof.\n- Title of Lemma D.3.: it may be better to use “$||\\cdot||_2^p$” instead of “$||y||_2^p$”\n- Lines 411-422: I suggest replacing the expression “It would be nice to obtain this” by “It was difficult to obtain this”.\n- Line 436: the word “existentially” does not seem appropriate, perhaps replace it with “further”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)