Quasi-Self-Concordant Optimization with $\ell_{\infty}$ Lewis Weights
Authors: Alina Ene
Ta Duy Nguyen
Adrian Vladu
Venue: NeurIPS 2025 poster ()
Keywords: Convex optimization
Quasi-Self-Concordant Optimization
Primary area: optimization
TL;DR: We give a practical algorithm for optimizing over-parametrized quasi-self-concordant functions to high precision via  $\ell_{\infty}$ Lewis weights

Abstract: In this paper, we study the problem $\min_{x\in R^{d},Nx=v}\sum\_{i=1}^{n}f((Ax-b)_{i})$
for a quasi-self-concordant function $f: R\to R$, where $A,N$ are
$n\times d$ and $m\times d$ matrices, $b,v$ are vectors of length
$n$ and $m$ with $n\ge d.$ We show an algorithm based on a trust-region
method with an oracle  that can be implemented using $\widetilde{O}(d^{1/3})$
linear system solves, improving the $\widetilde{O}(n^{1/3})$ oracle
by [Adil-Bullins-Sachdeva, NeurIPS 2021]. Our implementation of
the oracle relies on solving the overdetermined $\ell\_{\infty}$-regression
problem $\min\_{x\in R^{d},Nx=v}\|Ax-b\|\_{\infty}$. We provide an
algorithm that finds a $(1+\epsilon)$-approximate solution to this
problem using $O((d^{1/3}/\epsilon+1/\epsilon^{2})\log(n/\epsilon))$
linear system solves. This algorithm leverages $\ell\_{\infty}$ Lewis
weight overestimates and achieves this iteration complexity via a
simple lightweight IRLS approach, inspired by the work of [Ene-Vladu,
ICML 2019]. Experimentally, we demonstrate that our algorithm significantly
improves the runtime of the standard CVX solver.

Quas--Sef--Concordant Optimization with Lewis Weights
Alina Ene
Ta Duy Nguyen Department of Computer Science Boston University taduy&bu. edu
Adrian Vladu CNRS & IRIF
Department of Computer Science Boston University aene@bu. edu
Université Paris Cité vladu@irif
Abstract
In this paper, we study the problem mingeRd NN== Ex f((Az bb):) for quasi- self-concordant function f R R, where A, N are n x d and m x matrices, b, are vectors of length and with 2 d. We show an algorithm based on a trust-region method with oracle that be implemented using ((d//3) linear system solves, improving the ( 1/3) oracle by -Adil-Bullins Saciiins-Saheaa,,,. NeurIPS 2021]. Our implementation of the oracle relies on solving the overdetermined foo- regression problem min .Na=v || - b|l We provide an algorithm that finds a (1+ approxxmmae solution to this problem using O((d1/3/e 1/=²) log(n/e)) linear system solves. This algorithm leverages foo Lewis weight overestimates and achieves this iteration complexity via a simple lightweight IRLS approach, inspired by the work of [Ene-Vladu, ICML 2019]. Experimentally, demonstrate that our algorithm significantly improves the runtime of the standard CVX solver.
Introduction
Quasi-self-concordaar (QSC) optimization encompasses a broad class of problems that have long been central to convex optimization, numerical analysis, robust statistics, data fitting, and constrained optimization [Bac KSTT8 MFBRT9 STD19, CJJ+ CHJ 22, Doi23]. Notable special cases include logistic regression, softmax regression, and regularized l, regression, which have been widely studied due their broad range of applications in machine learning.
Due to their favorable properties, QSC functions have enjoyed efficient optimization methods which require strictly weaker curvature assumptions than, for example, strong convexity. Yet, without strong promises about the underlying model, QSC optimization is still a challenging problem for which first order methods only provide low precision solution with poly(1/E) convergence rate opposed to the desirable poly log(1/e) rate, where s is the sub-optimality gap, while typical second order methods computationally expensive. Thus significant challenges remain for the pursuit of more efficient optimization algorithms for this class of functions.
In this work, study the constrained QSC optimization problem
min h (x) = Σ f ((Ax- -b,) Naww
where f + R is QSC function, A Raxd N R.xdd matrices, and b R.. E Rm vectors. Each term I ((Ax - b),) can be viewed as measuring the fit to a single datapoint. We focus in particular the overdetermined regime where the number of datapoints is significantly larger than the number of variables d. This setting is central to large-scale data analysis. In regression tasks, standard techniques for managing large include data sparsification (SS08 15) subspace
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

embeddings [NN13], and tools from randomized numerical linear algebra [DMI8]. However, for QSC objectives, existing approaches typically exhibit iteration complexity that scales with n rather than the intrinsic dimension d, which makes them poorly suited to modern high-sample regimes. Thus, the central question to our work is:
Can we design an algorithm for Problem ! with iteration complexity nearly independent of n?
We address this question by showing that QSC functions can be minimized to high precision (poly log(1/E) convergence rate) in O(d//3) iterations, each of which makes constant number of calls to a linear system solver involving structured d x matrices, thereby drastically improv- ing efficiency and scalability of existing approaches. Our approach is based on a trust-region method, for which we show a fast oracle implementation. Our oracle implementation relies on solving for regression problems. Instead of leveraging data sparsification reduce problem size [CP15 JLLS23 ULL424 [Y24], which often entails high computational costs when n large, our algorithm inspired by the recent advances on general lp regression, such as the work of Jambulapati- Liu-Sidford [JLS22]. We introduce a new approach that leverages &o Lewis weights inside a simple, lightweight Iteratively Reweighted Least Squares (IRLS) algorithm [EV19), which of independent interest. A simple modification of our algorithm can be used to solve QSC optimization problems in the underdetermined regime n S d as well, and it provides a much simpler and practical algorithm with theoretical guarantees that mirror those of the state of the art algorithm of [ABS2]] that currently lacks a practical implementation.
1.1 Our contributions
We consider the QSC optimization problem [T. where f is general C-QSC function (Definition) 2.1 potentially non-smooth and not strongly convex. Following the literature on regression algorithms [APS19 AKPSI9 JLS222 and the prior work by [ABS2I], we focus on designing highly efficient iterative algorithms that rely on (structured) linear system solvers. Throughout this paper, we define one iteration as single call to the linear system solver. Since the linear system solves dominate the running time in all algorithms we discuss, the total runtime is essentially the product of the iteration count and the cost of solving these systems.
Our first main contribution is new trust-region method for affine-constrained C-QSC optimization that achieves the following performance guarantee.
Theorem 1.1. Let f IR + R be a C-quasi-self--oocortaa function, let A E Ruxd N Ruxd b E IR and v E R.' with n > d. Define the function h Rd - IR as h (x) E' ((Ax-b),) - b);)- Let (00) be an initial solution satisfying Nx) = and let R be any value such that max ne ae (=sM(a))(((t))))) ||Ar Ax* S R. Suppose h is bounded from below, and let B be
any value satisfying h(x)= 2 for all x E Rd. Then there exists an algorithm that, given x00), R. and B as imput, computes an e-additive approximation to the problem mingeed ii h(x)) by solving O (CRlog (CR) (h(= -h(=)) subproblems, each of which makes O (d'/3 log n)
calls linear system solver with matrices of the form A DA and N (AT DA) NT, where D is a positive diagonal matrix.
Comparison to prior works: Prior to our work, the algorithm with state of the art iteration com- plexity for general (non-smooth) QSC optimization was given by [ABS2I], which achieved iteration complexity O 1n3 logo(u (n) Col (CR) log [h ) h(aa)
Our algorithm improves this
to a dependence on d/33 which is a substantial improvement in the overdetermined regime n >> d. Moreover, the algorithm of [ABS2I] is complex and makes use of several parameters set to guarantee the theoretical runtime. In practice, to obtain an efficient algorithm, these parameters need to be carefully tuned and currently this algorithm of [ABS2I] lacks practical implementation for this reason. On the other hand, our algorithm is significantly simpler and implementable in practice, with an excellent empirical performance compared to CVX.
Our algorithm builds on a trust-region based algorithmic framework developed in prior work AZL.O117 CMTVI7 20 ABS21. An important property of QSC functions shown by KSJ18] is that the Hessian at a point e is relatively stable in region around x. Prior works such as [CJJ=20 ABS21 build on this property and design algorithms that iteratively minimize local
2

---

second-order approximation of the function in region where the Hessian is sufficiently stable. The key difficulty in implementing this approach lies in designing efficient algorithms for solving the resulting subproblems. One of our main contributions is new efficient subroutine for solving the resulting subproblems. We develop our subroutine by first designing a novel and simple algorithm for solving & regression, which is of independent interest. Our subroutine algorithm then solves lz-regularized Lo regression problems, enjoying the simplicity and efficiency of our &oo regression solver. The following theorem states the guarantees for our to regression algorithm.
Let A E R=xd, N E R b E R" and v E R", with n. > d, and let s > O be a scalar. There exists an algorithm which provides a (1 + muutiiplicai approximation to the so regression problem mingeR", ||A =0 by solving O (log los(n) subproblems, each of which makes O (( ( } log + calls to a solver for structured linear systems involving matrices of the form A DA and N (AT NT, where D is a positive diagonal matrix.
Theorem 1.2.
(({++))
Our algorithm for &o regression achieves state of the art iteration complexity (in terms of dependence on the dimension d) via an iteratively reweighted least squares (IRLS) approach that solves weighted least squares instance in each iteration, whose solution is provided by a single linear system solve. IRLS algorithms are favored in practice due to their simplicity and ease of implementation. IRLS algorithms were first introduced in pioncering work from the 1960s [aw66] RU68). Subsequently, there has been significant interest in developing IRLS methods with provable convergence guarantees
SV66 V66a EV19 APS19].
Comparison to prior works: Prior to work, the state of the art IRLS algorithm for foo regression is the algorithm of [EV19]. The work [JLS22] gives a non-IRLS algorithm for lo regression with the state of the art iteration complexity Ô (d2/3/ //23)) We highlight the differences between our algorithm and these works. The algorithm of JLS222 works by leveraging loo Lewis weights, and uses a reduction to the Monteiro-Svaite accelerated gradient descent algorithm by [C]+ Monteiro-Svaiter acceleration is a complex scheme, requiring solve an implicit equation in each iteration. While an implementation is later provided in (CHJ+22), the practicality of Monteiro-Svaiice acceleration remains an open question [CHJ+22) Our fxo regression algorithm also uses Lewis weights, but from a completely different approach, based on an IRLS algorithm. The starting point of our algorithm the algorithmic framework by (EVI9) However the algorithm by (EV19) is very specific to the uniform initialization of the solution and only achieves iteration complexity Ô
The non-uniform initialization via loo Lewis weights in our algorithm immediately breaks the analysis by [EV19]. To overcome this barrier requires new insights. Our algorithm
also further improves the iteration complexity of [EVI''s algorithm to Ô (d + while retaining the simplicity and practicality of an IRLS method.
Underdetermined regime n S d: A simple modification of our algorithm can be used in the regime I d and it obtains guarantee which is analogous to Theorem I.] but with iteration complexity that depends on the smaller dimension n. Our algorithm matches the iteration complexity of the state of the art algorithm of [ABS21] up to poly-logarithmic factors, while being significantly simpler and more practical. As discussed above, our algorithm is an IRLS based method where the main computation in each iteration is weighted least squares regression, which is beneficial in practice.
Further extensions: It worth noting that while we followed the formulation from [ABS21], our solver can handle more general functions provided that their Hessian is stable within any foo box of fixed radius. This allows, for example, to minimize functions of the form Σ fa ((Ar - b),) both the constrained and unconstrained settings, where each fo in the decomposition has a bounded third derivative. The same framework applies to functions without the decomposable structure, provided that a similar stability property holds.
1.2 Related work
The class of quasi-selff-comcordat (QSC) functions was introduced [Bac10] extending the defini- tion of standard self-concordant functions to logistic regression models. As QSC functions encompass various other important models, such as softmax and & regressions, they have been further explored in scries of influential works [STD19 KSJ18
CJJ 20 ABS21 Doi23].
3

---

Most of these studies rely on trust-region Newton methods, which inherently introduce a dependence on the number of iterations dictated by the shape and size of the trust region. Typically, these regions are 62 balls centered at the current iterate, leading to convergence guarantees expressed in terms of the l2 diameter of the search region. Notably, [ABS2] I applied the techniques of [AZLOWIZ] CWWWII/CMVVI CMTVI7) to instead establish guarantees in terms of the & diameter of the search region by solving sequence of second-order subproblems with Eoo constraints. Our algorithm for QSC optimization follows a similar principle.
significant contribution by [Doi23 introduced acceleration techniques to achieve an iteration complexity of ((CR))/33) where denotes the l diameter of the domain. However, since the worst-case ratio between the &2 and &oo diameters is vn, the iteration complexity may degrade by factor of n 1/3 when measured under the &oo benchmark used in [ABS2I] and in this work-while still maintaining the desirable sublinear dependence on C' and R. In comparison, our approach incurs only a d3/3 factor, which represents a substantial improvement when n > d. Additionally we note that accelerated algorithms typically require smoothness, and this is the case for those given in 2CJJ+20 Doi23]. However, both the algorithm from [ABS21] and ours manage to achieve an improved iteration complexity, without resorting to smoothness or other additional properties. We note that [KSJI8] provide an analysis for both the smooth and non-smooth settings, but they exhibit a dependence on the lg diameter of the level set of the initialization point, which scales as n22 in the worst case.
to regression is classical optimization problem, but the first major breakthrough occurred in the special case of max flow in 11M+ where the authors developed an algorithm requiring Ô (n//3) linear system solves, improving upon the standard Ô (n2 complexity. This result was further refined and generalized in [CMMP13 EV19], both achieving Ô (n 133 iteration complexity. More recently, [JL222 studied both Ep regression for general p < co and for regression, presenting algorithms whose iteration count depends on d rather than n, leveraging Lewis weights. Previously, [LS4]] devised an interior point method for tall LPs where the number of iterations depends on d rather than n by employing Lewis weights. For the specific case of Loc regression, [JLS22] incorporated Lewis weights into the accelerated second-order method of [CJJ+20), which approximates the foo norm via the Hessian of a log-exp-sum function. In contrast, while we also draw on the Lewis weight approach from [LS22)], we develop simpler, lightweight IRLS method inspired by [EVI9).
1.3 Overview of our approach
To establish our main result, we employ a trust-region method. While such methods have been extensively studied, the distinguishing feature of our approach is that the convergence rate depends on the loo diameter of the level set that contains the initialization point, rather than its Eg diameter, which can be larger by up to a factor of vn. This yields both theoretical and practical improvements. Our method is motivated by the box-constrained Newton method which was introduced by [CMTV17 minimization [ABS2I]. This perspective allows us reduce the optimization process executing an outer loop of O (CR Colo h(xx)-b(x") 6 iterations, where C' is the QSC parameter of f and R = max || Ax Mx) I h(ro)) denotes the loo diameter of the level set of the initialization point zo--
AZLOWI7]. and later adapted to mewsii-elf-concooree
In each iteration of the outer loop, we compute the update by approximately minimizing a quadratic approximation of h over the foo ball of radius 1/C centered the current iterate. This radius constraint guarantees that the Hessian of / remains well approximated within the entire trust region. Consequently, the approximate minimizer computed here achieves sufficient decrease in objective value compared to the true minimizer of the region.
We then show that the required subproblem is of the form
max 9 (AA)) 2 (AA) D (AA), |
where g E IR' is a vector and non-negative diagonal matrix and can be reduced to implementing a residual solver which approximately maximizes concave quadratic objective as in (2) subject to to constraints. We describe this reduction in Section 4 To obtain an efficient residual solver, we design an IRLS method whose convergence rate depends only on the smaller dimension d, requiring

---

Throughout the paper, when it is clear from context, we use scalar operations between vectors to denote the coordinate-we zu in the i-th coordinate. For RR we use diag (w) gaxd to denote the diagonal matrix with only Ō (dv/3) linear system solves. Finally, the extra factor log (CR) log ((ol0))h(e")) comes
from binary search procedure, detailed in Section 4
2 Preliminaries
Notation.
application, e-g, for x E TRd, x? is an IR vector with entry
diagonal entries given by w. When it is clear from context, we also abuse the notation and use the scalar to denote the vector with all coordinates having value a, and the dimension will be inferred from the context.
functions. We recall the definition of quasi- mefeii-eel-coocordan functions. Definition 2.1. A function f RR + R, is C-quasi-self-comccrdaat for C' >> 0 if for all x E R. [f* (x))
Lewis weights and computation. Our main algorithms rely on the use of foo Lewis weight overestimates. start, we introduce leverage scores and to Lewis weights for matrix E Raad
Definition 2.2 (Leverage scores). For matrix A, the leverage score of the i-th row of is given by (A), a. (ATA)= -Ta; where is the i-th row of A.
Definition 2.3 (foo Lewis weights). The foo Lewis weights of matrix A are the unique vector W E IR that satisfies uz = (diag(w) A) for all i E [n).
While finding fox Lewis weights is computationally expensive, for the purpose our algorithms, we only need to use foo Lewis weight overestimates, notion introduced by (JLS22].
Definition 2.4 (f Lewis weight overestimates). The foo Lewis weight overestimates of matrix A are vector R that satisfies d < ||w||| < 2d and w; 2 (d)ag(w))//2 A); for all E [n].
One efficiently compute &o Lewis weight overestimates of matrix A by the fixed point iterations by [CCLY19, using O(1) linear system solves (see also (]L222)
Linear system solver. Our algorithms in the unconstrained setting assume access to an oracle that solves problems of the form mingg."" T z== (r, (Ax)²). Finding the minimizer æ is equivalent to solving linear system of the form A DAr = 9, for diagonal matrix D. The problem has closed form solution
1g where = Ar.g(r)A.
B-
Energy increase lower bounds. Our approach based on the electrical flow interpretation of the problem. Electrical flow interpretation
developed for flow problems graph, and later extended for problems involving general linear systems. For vector E Rd, matrix E IR nxd and vector E B% which will refer to resistances,
consider the following quantity E(r) min 2=-1 (r, (Ax)?), which we will refer to as the electrical energy. ((r) has the nice property of being monotone in r. The increase in the energy when the resistances increase is lower bounded in the two lemmas A. A.2 (provided in the appendix), which are both critical in the design and analysis of our algorithms.
3 Loc- Regrressio with Lewis Weights
As warm up for the general QSC optimization algorithm, in this section, we solve the problem of overdetermined -rgreessni to
+ + approxiiitnoo in the form
min |||
where A E Raxd with 2 d. That is, we want to find solution x to the above problem that satisfies
g r -1 and ||Ar]|o I (1 + e)| |loo, where we denote x² = arg miny == ||r We note that the commonly seen problem min, || blloc can be transformed into the above form by adding b column to A and considering E Id+1 with the extra dimension having value - 1.
5

---

Algorithm 1 regressin for m x---1 |z
Input:A. g.
2: Output: Find such that g² -1 and || S (1 + ming x= ||
3: Initialize z2(0) arg mingT x==-1 ||Azzll: L = [logi+e |xx00 12
nt/2 J; U Llogi+e ||Ax
4: while L U:
5: P=
-
6: Subsolver(AA, (A, M) ) infeasible then L = P+1
7: else let (+) the output of Subsolver(A, M)); -
8: return (1))
Algorithm 2 Eoo regression Subsolver g,, M)
1: Output: Find such that ||Ax|oo I (1 + s)M or find such that
E(r)
M
TFil
I+f
2: Initialize: r()) = + d where is an foo Lewis weight overestimate vector of A
3: -0,t' 0, st')
4: while |||((] 11 S
5: xx1) arg min "ng" T -=-
(r(t), (Ax)?)
6:
if (- 1
(Ar
(1+c) then return (1)
7:
if |1 00 (1+ then return (9)
8:
[1 x S d M:
D Case
9:
Let be an index such that (Ar(t));) = ||Ax
(1+1) (1) j
10:
+1 j=i
11:
else:
D Case
Let 1' 1; 51') s(tt' s(t'-1) 1) + 19;;
13:
if ||As(t)) '1 1lo0/t' S '1 (1++))) E)M then return s(() /t'
(1) (Aml))) if (Ar(1)3 2 (1 + e)M²
14:
((+1)
M2
otherwise
1 1+1
16:
return (t)
3.1
Algorithm
The main part of our algorithm is the subroutine shown in Algorithm 2 which takes input guess for the optimal objective of Problem 3 To obtain (1 + apprroxximtaoonn for this value, our main algorithm proceeds by performing a binary search. Starting with an initial solution (0))) arg min," T a=-1 |Aa||a the algorithm performs binary search on the (1 + e)-grid between
|| 2|2 and
[|
wi/2 (which are an upper bound and a lower bound for Ax The number of
[|A=(()
guesses is at most log
Olog log
Our main focus in this section then to demonstrate that Algorithm 2 given a guess M, outputs solution with ||Ar]]oc S (1++) any. For our convenience, we start with the dual formulation of the problem with the squared objective
((r) r20 |r]l
min --==11
|
(Ar))) max min (r, (Axx)) 8 -T==-1 ||lll==
min max
||r||==1 x=-1
where we use E(r denote the objective minyTz==1 (r, (Ax)²). For guess M for the optimal
objective of Problem 3 the goal of our algorithm is to produce primal solution x such that J
and x satisfies Ax]loo < (1 (1++))M e)M or certify that mingT -=- Ax = max,20 | > (ML in which case need to increase M.
Eir)

---

The core idea of our algorithm is to maintain in each iteration t the following invariant
E(rlH+)) - E(r()) 2 M (( - 11rr
(4)
The telescoping property of this invariant guarantees that if the algorithm outputs dual solution y-(2) with ||r || significantly large compared to the initial || [I, we will have ((r(2)
.22
[|
[I+2)7
We leverage the energy increase lower bound lemmas A.2 and A.1 to determine the update for the dual solution First, the initial dual solution r(()) is set to w + n.' where w is a Eso Lewis weight overestimate vector for matrix A, which can be efficiently obtained using the fixed point iteration from [CCY19), which revise in Section E of the appendix. The component is added guarantee that the coordinates the dual solution are not too small. With this initialization, subsequent update ((() always satisfies the condition of Lemma A.2 and thus we can apply when necessary. To update the dual solution, the novelty in our method to distinguish between the two regimes. In the high width regime (Case 1), ie, when the corresponding minimizer w(()) to ming" ==-1 (r, (Ax)²) satisfies (I oo > S, where S is set to d M, we update single coordinate that achieves the maximum value [ [Az(");l = || || by setting r; (t-1) =r 1. Lemma A.2 will guarantee
that the invariant 4 holds, and at the same time, & (r(9) increases fast. In the low width regime (Case
2), when Ax
S. we use the lower bound given by Lemma A.1 In order to maintain the
(Am00gg.0))
invariant A.2 we can guarantee for each coordinate j, can derive the update rule as shown in Algorithm 2 We give the full description in Algorithm 2
M From here, we
1040 (1)
3.2 Analysis
We show the full analysis of Algorithm 2 in Appendix B To show Theorem 1.2 first, we can see that the algorithm performs O log
log(1) Azoll -|AA )l binary search steps. Our analysis shows that,
in each step, the algorithm uses (( + 4//8 log )) calls to the solver for problems of the form
min.g x= (r, ?). By combining these two facts, we immediately have Theorem 1.2
Quass-Self-Conorddant Optimization
Algorithm 3 Algorithm for optimizing h(x) Ci b),)
Input: initial solution xo. lower bound B on h, diameter R of sub-level set Lo.
2: Output: Find such that (xx) & h(x)) +
3: Initialize: (,()) Za
4: Let T = 0 CRlog h(an -(a=))))))
5: for (t = 0, 1 Tút + t+
Di or terminate when h(x((+))))
- M(x(0) S (e/CRR
6: A + (0)
> set of candidate updates halving after each step halving after each step Let Au,s be a primal solution output by ResidualSolver(("") M) if any A A U (A.,r)
7:
for (u -u= h)x(0)) -(:l)))B:vee;v -B:
8:
for (M = e²v; M 2 eR; 1)
9:
10:
(++1) (1) 40 (0) where A (1) arg migmmnaal h (z(0) A
P update step
12:
To simplify exposition, we present algorithm for solving the unconstrained problem
min h(x) = Σ f(Ar- 1 ((Ax-b))))
(5)
7

---

Algorithm 4 ResidualSSover((,, M)
1: Initialize: r(0) = w + a. where w an &o Lewis weight overestimate vector of A
2: gi (A
f ("A(());:,, 0, 1' 0, v(())
3: while |||| _ 2(1[w=1| 1 +
4: Let = = + + MC² ((); A (t) = arg min Bo=TA=-1 (p()) (AD)3)
5:
if
MC²
|r (1)
,(u
2 13M then return ,())
6:
|A
(1) 10 غ then return (
7:
||A [1) |m 5
1125.
b Case
8:
Let be an index such that (AA()); || 11
j j=i
9:
else:
Case
Let = t' + 1; v(())) = -(('-1) A(1
11:
if ||((t)) "1000 1lo//t S C
then return ult') //t
(1)
(AA 12) if (A) 100
((+1)
otherwise
14:
1= ++++1
return (()
where f : + R is C-guusissl function defined in Definition 2.1 A Rexd and E IR' with n 2 d. In the appendix, we give an extension to the fully generalized constrained problem Ni= Σ ((Ax b):) as stated in Theorem 1.1
Notation: We denote by x= the optimal solution to the problem and (0))) the initial solution used by our algorithm. Also, let us write ff(x)= = (f' ((Ar - diag (f" ((Ax- - A (z))
((Ar b)n)) T. V fz)
8" ((Ax - b)m) We then have Vh(xx) = A AV)()x and VPh(x) =
Assumptions: Our algorithm and its analysis require the following assumptions.
Assumption 1. We assume that there exists finite value B such that h(x) > B, for all x E Idd,
Assumption 2. Let Co
{z h(x) $ h(x(0))). We assume that there exists a finite value such that maxzeco Ar - Ax" 1l < R.
We note that Assumption I is standard in prior work (eg. by (ABS2]) Many commonly used functions are non-negative and thus admit a trivial lower bound B O. Assumption 2 the boundedness of the diameter of the level set is also common in prior work on trust-region Newton method, such as [KST18 Doi23]. Such dependencies are natural, and virtually all known algorithms for QSC optimization have dependency on the size and shape of the trust region, as well as on the distance between the initial and the optimal point (e.g. [BSSI define their distance parameter such that || |Axx < R and ||Ax* 2 < Rt).
Our approach: We follow trust-region based template. In particular, our approach leverages the box-constrained Newton method [CMTV17], which was used in the context of matrix scaling, a special case of QSC minimization. A similar method was developed in parallel by [AZLOW17] and was employed by [ABS2I] for optimizing problem 5 The general idea behind these trust region templates is that, if the Hessian of the objective promised to not change by more than constant multiplicative factor within an fo region centered around the current iterate, then minimizing the local quadratic approximation within this region yields new iterate which makes significant progress in function value. In fact, this progress is comparable to the progress made by moving to the best point within the E. region. Hence the remaining challenge to approximately solve the quadratic minimization problem subject to an fxx constraint. Since the subproblem is very robust to approximation, suffices obtain a constant factor approximation to a regularized 12 + & problem, which we achieve via new IRLS solver. Now
provide formal statements.

---

implies Hessian stability, which allows us to reduce Problem to solving sequence of residual problems of the form
max rcs V.((z) - (AA)) AA S
(6)
We prove that an approximate solution to Problem 6 alloow make significant progress in the function value of h. The full proof can be found in Section C
Lemma 4.1. Consider an iteration of Algorithm and let x! be the current iterate. Suppose the ResidualSolver can compute I such that res,
( 2 |aa = S
res Then we have eCR (h(z)-
h
h(x²)
Consequently, Algorithm constructs a solution xTT) such that h(x(T) S hh(x)) + using T
0 RC log h(2(0))-((2)) iterations of the outermost for loop.
K
To solve Problem 6 we recast it in more amenable form, which is related an -egressioo problem, but with the key difference that it contains an additional quadratic term (s, (AA)²).
Specifically, given guess M for the objective value, define the minimization problem
min (8, (AA)?) + MC² g A=-1
2
where 9: = - (=)) and s, = f" ((Ar);) for all i. We show that algorithm ResidualSolver satisfies the following invariant.
Invariant 1. The algorithm either outputs solution A such that g A -1 ||AA S 11 and (s, (AA)²) I min, A=-1 (s, (AA)²) + MC² |AA| bo or certifies that min," T A=-1 (s. (AA)))) +
MC² 2
1 2 13M.
The output of an algorithm satisfying Invariant can be converted into a good approximate solution to Problem We prove this formally in Lemma C7 this point the major challenge is providing such an algorithm. We show that we can achieve it by extending our approach for solving foo -regression from Section B] The key difference in this setting is the presence of an additional quadratic term, which makes the extension non-trivial and limits us to achieving only a constant-factee approximation. Nonetheless, this level of approximation suffices for our purposes.
The following lemma provides formal guarantees for the ResidualSolver, and its full proof can be found in [C
Lemma 4.2. For an iterate x, let A arg max SICC res (A) and OPT res, (1*). For
M such that OPT (Z/ M). Algorithm 4 oulputs A such that || | xx S è and res, ( > OPT
20
and makes (d2s3 log n) calls to linear system solver.
Having provided the description of the ResidualSolver and its guarantee, we now describe and analyze the main routine shown in Algorithm 3 The algorithm starts with solution 2())) and iteratively updates it. In each iteration, it performs a binary search for the objective of residual problem
o using the two for-loops in Line 7 and Line g With each guess for this objective, the algorithm uses the ResidualSolver (Algorithm 4 to find a solution. Algorithm finally uses the best solution among the ones that are found to update the iterate. To analyze the algorithm, first use the following fact from [BS21].
Lemma 4.3 (Lemma 4.3, 4.4 (BS2L)). 1)(((19) - M(x*) E v), then OPT Further, if OPT E M M) then (AA*) ('(())AA))) s eM.
(G0 e²y
This lemma guarantees that the steps executed in the two for-loops in Algorithm 3 are sufficient to find sufficiently close guess for the residual problem objective. In total, the number of steps
required to find M such that OPT E ( (M,M) is O (log (CR) log (((
Finally, combining Lemma 4.1 Lemma 4.2 with the binary search procedure in Line 78 (Lemma
4.3) we can conclude that the total number iterations of Algorithm t3 find an e-additive solution
O ( (Clllog (CR) ())=(()))h(>") -h(=") each of which uses (d'/3 3 log nog linear system solves.
This concludes the proof for Theorem I.1

---

Nunsen Metrics,
Song Your Notcton,
Power Corsuratiion de
Proicit de?
2040
1000
Random Matt cas, dw100
Song Your Prodictoon deds
Toner Corsumption dw11
Prote n Prosuryy sed
heydln
Neatan
Reattn
Roaton
4306 5693
5633
20.00
$030
22.0
$8.00
Figure 1: Runtime (in seconds) on random matrices and three real-world datasets when p 8 and E = 10 10-10, 10, We run each each experiment times and report the mean and standard deviation of the runtime. The first row shows the absolute difference in the objectives returned by CVX and Newton's method against our algorithm on the log scale.
Table I: Performance of our algorithm on the large instances. In the last row, we show the gap in the objective value between Newton's 's method and our algorithm.
Dataset
Random Matrices
Song Year
Consumption of Power (HB06)
Protein Property [3n
Prediction [M11
Size
100000 x 100
463811 x 90
1844352 11
41157 9
Newton (s)
0.5
2.7
3.0
0.2
Ours (s)
1.3
7.5
6.5
0.3
Gap
-3.6 x 10-12
2.6
10-9
4.5 x 10-9
-7.1 10 10-11
Experiments
We test our algorithm on fz-regularized& én-regression problems: min, || - bll + 11 =1|AAx - 61(2.
For 3, the function |x + uz² is C-QSC for C pN 1((p-))
Baseline. We compare our algorithm runtime against CVX and the Newton's method in KSJ18. For the Newton's 's method, we use a line search to set the step size in each iteration.
Problems and datasets. We study the Ep + f regression problem in two settings: 1) Random matrix A, b: The entries of A, b are generated uniformly at random between 0 and 1, the second dimension (d) of A is fixed to 100; 2) On real world datasets:
for real-world datasets available for regression tasks on UCI repository. The dataset sizes are reported in Table [I Since CVX slows down significantly on larger instances, we only randomly pick up to 2500 in each instance. For our algorithm and the Newton's 's method, we also measure the time they run on larger instances and the entire datasets. In all experiments, we use p = and precision ε 10 10 μ 1.
To verify the correctness of our algorithms, we assume that CVX gives a solution with high precision. We plot the absolute difference between the objectives outputted by CVX and Newton's 's method and the objective by our algorithm. In all cases, the difference is within the margin of error (s 10-10), indicating that our algorithm outputs high-precision solutions.
Correctness.
Performance. Implementations were done on MATLAB 2024a on a MacBook Pro M2/16GB RAM. The performance of all three algorithms is reported in Figure I On all small instances, our algorithm and the Newton's 's method have comparable runtime and are both significantly faster than CVX.
We further compare the performance of our algorithm and the Newton's 's on large instances (reported in Table I Both algorithms are efficient, and are even faster than the time CVX runs on small instances. However, there is a gap in the runtime between our algorithm and Newton's 's method. We note that Newton's method has been shown to perform very well in practice. Nevertheless, comes with a significantly weaker theoretical guarantee [BV04]. Our algorithm, on the other hand, provides a stronger theoretical convergence rate and, as proof of concept, gives a close comparable performance.
10

---

Acknowledgement
AE was supported in part by an Alfred P. Sloan Research Fellowship. AV was supported by the French Agence Nationale de la Recherche (ANR) under grant ANR-21-CE48-0016 (project COMCOPT).
References
[ABS21] Deeksha Adil, Brian Bullins, and Sushant Sachdeva. Unifying width-reduced methods for quasi-self-concordlat optimization. Advances in Neural Information Processing Systems, 34:19122-19133, 2021.
[AKPS19] Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Iterative refine- ment for ---nrrm regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1405-1424. SIAM, 2019.
[APS19] Deeksha Adil, Richard Peng, and Sushant Sachdeva. Fast, provably convergent irls algorithm for p-norm linear regression. Advances in Neural Information Processing Systems, 32, 2019.
[AZLOW17] Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 890-901. IEEE, 2017.
[Bac10] Francis Bach. Self-concordant analysis for logistic regression. 2010.
[BM11] T. Bertin-Mahieux. Year Prediction MSD. UCI Machine Learning Repository, 2011. DOI:
[BV04] Stephen Boyd and Lieven Vandenberghe. Convex optimization, Cambridge university press, 2004.
[CCLY19] Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near-optimal algorithm for approximating the john ellipsoid. In Conference on Learning Theory, pages 849-873. PMLR, 2019.
[CHJ+22] Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive monteiro-svaiter acceleration. Advances in Neural Information Processing Systems, 11:20338-20335 2022.
[CJ]+20] Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Accelcration with a ball optimization oracle. Advances in Neural 2020.
Information Processing Systems, 33:19052-1999
[CKM+1L] 11] Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hus Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 201 I, San Jose, CA, USA, 6-8 June 2011, pages 273-282. ACM, 2011.
[CLM+15) Michael Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng. and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 conference on innovations in theoretical computer science, pages 181-190, 2015.
[CMMP13] Hui Han Chin, Aleksander Madry, Gary L. Miller, and Richard Peng. Runtime guarantees for regression problems. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS 11, Berkeley, CA, USA, January 9-12, 2013, pages 269-288, ACM, 2013.
[CMTV17] Michael Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton's method and interior point methods. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 902-913. IEEE, 2017.

---

[CP15] Michael B Cohen and Richard Peng. Lp row sampling by lewis weights. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 182-192. 2015.
[DM18] Petros Drineas and Michael W Mahoney. Lectures on randomized numerical linear algebra. The Mathematics of Data, 25).). 2018.
[Doi23] Nikita Doikov. Minimizing quasi-self-concorramm functions by gradient regularization of newton method. arXiv preprint arXiv:2308. 14742, 2023.
[EV19] Alina Ene and Adrian Vladu. Improved convergence for l and Eoe regression via iteratively reweighted least squares. In International Conference on Machine Learning, pages 1794-1801 2019.
[HB06] Georges Hebrail and Alice Berard. Individual Household Electric Power Consumption. UCI Machine Learning Repository, 2006. DOI: https://oo..rgg1002444////3//
[JLLS23] Arun Jambulapati, James R Lee, Yang Liu, and Aaron Sidford. Sparsifying sums of norms. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1953-1962. IEEE, 2023.
[JLLS24] Arun Jambulapati, James R Lee, Yang P Liu, and Aaron Sidford. Sparsifying general- ized linear models. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1665-1675, 2024.
[JLS22] Arun Jambulapati, Yang P Liu, and Aaron Sidford. Improved iteration complexities for overconstrained p-norm regression. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 529-542, 2022.
[KSJ18] Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Global linear con- vergence of newton's 's method without strong-convexity or lipschitz gradients. arXiv preprint arXiv: 0041,, 2018
[Law61] C.L. Lawson. Contributtions the Theory of Linear Least Maximun Approximation. University of California, Los Angeles, 1961.
[LS14] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in (yrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424-433. IEEE, 2014.
[MFBR19] Ulysse Marteau-Ferge Francis Bach, and Alessandro Rudi. Globally convergent newton methods for ill-conditioned generalized self-concordant losses. Advances in Neural Information Processing Systems, 32, 2019.
[NN13] Jelani Nelson and Huy L. Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pages 117116.. IEEE, 2013.
[Ran13] Prashant Rana. Physicochemical Properties of Protein Tertiary Structure. UCI Machine Learning Repository, 2013. DOI: http::/ddo..rr/11.24443//.C
[RU68] John R Rice and Karl Usow. The lawson algorithm and extensions. Mathematics of Computation, 22(101): 18-127, 1968.
[SS08] Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposium Theory of computing, pages 563-568, 2008.
[STD19] Tianxiao Sun and Quoe Tran-Dinh. Generalized self-concordant functions: a recipe for newton-type methods. Mathematical Programming, 17 178(1):145-215 2019.
12

---

[SV16a] Damian Straszak and Nisheeth K. Vishnoi. Natural algorithms for flow problems. In Robert Krauthgamer, editor, Proceedings of the Twenty-Sevente Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1868-1888 SIAM, 2016.
[SV16b] Damian Straszak and Nisheeth K. Vishnoi. On natural dynamics for linear pro- gramming. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16. 2016, page 291. ACM, 2016.
[WY24] David P Woodruff and Taisuke Yasuda. Nearly linear sparsification of Ep subspace approximation. arXiv preprint arXiv:2407.03262, 2024.
A
Energy Lemmas
Lemma A.1. Given r, r' R and r' 2 r. Let x arg min Tam- (Ax)?), then
E(r')-E7 2 Σ Frx -
The proof for this lemma can be found in prior works such as [EV19 (for special case) and ABSS2 (Lemma C.I).
Via foc Lewis weight overestimates, [1S222 also show the following
Lemma A.2 (Lemma 3.6 (JLS22)). Let be toc Lewis weight overestimates vector for matrix A.
For r 2 w, let x = arg min -==1((10)) (Ax)²)) Then for E 1R20 such that ||e|]] S
- {(r) Σ (Ax))
B Analysis of the loc Reggressio Algorithm
In this section, we give the analysis of the main subroutine of our loo -regresiio algorithm, shown in Algorithm
B.1 Correctness
Now we will show the correctness of our algorithm. That is, A primal solution such that g² x 1 and x satisfies ||Ar|] S +) or a dual solution with E(r)
[[]] 2 (14))²
First, we can see that if Algorithm 2 outputs primal solution x in Line 10 and Line 17, immediately have |/A < (1 + M. Therefore, we only have to show guarantees for the dual solution. As hinted, we first show that Algorithm maintains invariant 4 in the following lemma.
Lemma B.l. Algorithm maintains that for all
E(r(++1)) - ()) ||([+]]]||
2 M
||r(
( (1)
Proof. When || 2 S, we have 1 ((+1)
for a coordinate such that j #
+1
j =
((Ax())) = ||Ax0(0) Ilss Let = I, be the indicator vector for coordinate i. We have ((++)) = (() + and ||a|a 1. Since (1)) > (0)) w, apply Lemma A.2 and have
((1(++1)) - -((-())
(Ar((
82 /2/3M²
|||[+1)]]| ||r(0]]1 >
2 M
2
13

---

When ||Az|loo < S, for each coordinate j such that (e+1) Hence,
; > r
we have ((+1)
" = r1)) M
(A
(8)
(Ar()))r (1
[++3
(3r
M
{
(1+1)
]
r((t1)
By Lemma A.1
m E, E,(er!))3 (1
E(ritt1)) - E(r(1)) ||((+)/|| - |||(00]11
13
2 M
Egn((t)) (t)
Lemma B.I allows us to show the quality of the dual solution, if output.
Lemma B.2. If Algorithm returns a dual solution (T) then
b 2 ( I+5
E(r(P)
Proof. The case when the Algorithm terminates in Line 8 immediately gives us the claim. We only have to care about the case when the while-loop terminates with ||r(1]]] have that
(1 Ils By Lemma B.1
T-1
E(r()) 2 M²
||
[n((+11]]
11
leading to (T((T) 2 M (1( - [|x(00)1)) Since || >
|n:00 112
E(r(T) |r(T))11
M22 (1 ||:00/11 ||1 2 2 (1 =) 2
1+s ) 2
M
as needed.
B.2 Runtime
To bound the runtime of Algorithm 2 we also splits the iteration by the width of ||Ar Let The and Tio be the iterations when || |l S and ||Ax(*)) Il S S. respectively before the algorithm returns solution. We also abuse the notations and denote by Thi and Tio the numbers of such iterations, respectively. The following lemmas bound Ths and Tio.
Lemma B.3. The 6/
Proof. Again, for such that ||-Az(0) 11.0 > S, by Lemma A.2
we have
E(r((+1)) E(r(t))
24 (Ax(((()))
S
d
M
||(+1]||| - ||r10]|
Vi
2
Since [|((t)))| ||^(1)/// 1, we get ((r(t+1)) ((r(t)
>
/
Therefore E(r(T)) 2 Ths-
2
M² Notice that [|rr S |1 la < and E(n(T))
M (1tt) we get that Thi S 6d
O
||r
Lemma B.4. Tho < ( + a Togd log
Proof. Let Let 10 5 c
(11))
Before the algorithm terminates, we have
ELer x(1)
A
2 (1+ + E)M
Tho
14

---

[(
This means there must exist coordinate such that Σ EIen (Azlin) M2
2 (1 = We have
M
< (1 + E), then )a
(A*
)
(Axl1))
< (1+ 2). and if
2
(1 +E),
M2 = a; 1. Hence,
M
M²
())
E
12 >1 Vo.0 (
M
2
We obtain
Tio(1 + g)+
Σ
Va 2 e1+
(f)
and thus Ener V Val
The 2
For such that 0g 1, we have Va
((Ax(0))
E
M
[(++ + ,,)+,,t], By Lemma A.I from [VV1)) we have a lower bound for I ( ai
(1)
Tn dd ddaaat 2nt
( 2 min (1 + +8)aa+02
(8)
On the other hand, is an upperbound for Il 1 (") >1 a;
(i)
We initialize r. 2 and before
the algorithm terminates (2) S || I wtd
<
3d
We now have that
3d
n
3n
(9)
r
d
8
1ETTu.0 >
From 8 and 9
we obtain T% - (((
3n log
ing
C Analysis of the QSC Algorithm
In this section, we analyze main Algorithm 3 for QSC optimization. The algorithm starts with solution (o) and iteratively updates it. Building on prior work [CMIVI]JAZLOWTI
AZLOW17 ABS21 we
show that the algorithm returns a nearly-optimal solution provided we have access to an algorithm
for solving the following residual problems. Letting (*)) be the solution iteration of Algorithm
we would like to find an approximate solution to the following residual problem:
(t)) (A) = V (T) (AA) - (AA) V> (AA)
(10)
A: |A $
Using a binary search approach as in ABSS2 1 we can find a value M that is a 2-approximation to the optimal value the above residual problem. This binary search is shown in the two for-loops in Line 7 and Line [ of Algorithm 3 With each guess M, the algorithm uses the ResidualSolver (Algorithm 4 to find a solution to the residual problem. We show that if the residual solver returns constant factor approximation to the residual problem then Algorithm returns nearly-optimal solution. We now give the formal analysis.
We start by showing that the steps executed in the two for-loops in Algorithm B are sufficient to find sufficiently close guess for the residual problem objective. The lemma follows from Lemmas 4.3, 4.4 in ABS21
Lemma C.1 (Lemma 4.3, 4.4 ABS21I). For each value of the outer-most iteration with iterate
2(t), there is inner-most iteration 3 which the following hold. Let M be the value considered that iteration. Consider the residual problem:
rCs res (A) = V (AA)
(AA))
max A: [AAII S1/C
Let A * E arg ma S1/C res,in(A) be an optimal solution to the residual problem, and let OPT = res,((A)) be its objective value. We have OPT E M (M,M) and
V 5 SeM.
15

---

Next, we show that ResidualSolver (x(1) M) returns a constant factor approximation to the residual problem maxa; |||||| SI/C ges (A) when we run with the value M guaranteed by the above lemma. We will provide the proof of this lemma in Section C.I
Lemma C.2. Consider an outermost iteration t of Algorithm and an innermost iteration with a value M with the properties guaranteed by Lemma C.I Let
A
A., M be the solution returned by
ResidualSolver(<"" M). We have | S C and ges (A)
OPT
Equipped with the above guarantee, we can show that the algorithm converges in a small number of iterations. To this end, we first prove the following lemma which shows that each iteration significantly reduces the optimality gap.
Lemma C.3. Let x be an iterate. Suppose that ResidualSolver(z, M) returns solution i satisfying || 30 S c and res A 2 k | res (A). We have
h
h(**) S (1 -.RRR
In order to prove Lemma C.3
first we recall the notion of Hessian stability.
Definition C.1. A function IR + is -eessian stable in the -nrm iff for all x, y such that | ylloc I r we have
( = d(r)VPM(x).
d(r)
Fact C.1 (From c11+20) For stable in the so nomm.
f. E, f(x)) is (r, -Hsssan
We now give the proof of Lemma C.3
Proof. Let x" arg min h (z). we have ||Az Ax 1l $ R. and h is (r, e)esssnn stable where
r r= J. Let f h (1 h)) x; and let â f0 n (a x²). We have A
S
Suppose that A is an optimal solution the residual problem. Also recall the notation Vh(z)-
( |'(AAE- - b),)
[((Ax= b)1)
) (2f(2) =
A fz) and (²h(2) = v2 V (x)) where we write Vf(x)
((Ax= - - - b)n)).
Let k = e² and using hessian stability, we have
h (x- 2) h (x) N V (x) (Aã)
exp (Cr) (ΛQ) T (2f(x) (AD)
v (x)
(A
(AĀ)
V²f (Λã)
-resx (
T
AÄ
Cr
h
T
(())
(x)
exp
4 (x)
k
k
1
v. (x:T
T
(AĀ)
1
(A
V²f (2)) (Aã)
h:
é
res (
16

---

Since res
A
xIeSs (A+)
kress A
we have
h
1
- h (x)
-
K
res5 (
k
K
1i
h
x 2) - h (z))
k
(h (2) - h (x))
K
kr
(n (x=" - h (2))
kR
This give the conclusion
h
A
h hx*) S =1-
KF kR
(h (h h (x*)).
By combining Lemmas
C.2 and C.3
obtain the following convergence guarantee.
Lemma C.4. Algoritim
constructs solution (T) such that h(x(T) S h(x*) + using
O [RClog log
h(x ( hh((") iterations of the outermost loop.
Next, we analyze the overall running time of Algorithm 3 We have the following upper bound on number calls that Algorithm 3 makes to the residual solver.
Lemma C.S. In each iteration t, Algorithm 3 makes residual solver 1
(log (CR) log
--(=)))))))))))))))))))))))))) calls to the
Proof. The algorithm executes binary search using two for-loops and 8 for for-loop 7 is O log M(=())-B) O (log -(===))-((z") and the number of steps of for-loop O (log CR), giving us the claim.
The number of steps of
In Section C.6 we show the following upper bound on the running time of the ResidualSolver. Lemma C.6. ResidualSolver uses Odd1/3 n) linear system solves.
Finally, to conclude the proof of Theorem we only have to combine Lemmas C.4
C.5
C.6
C.1 Proof of Lemma
this section, we prove the approximation guarantee of the ResidualSolver stated in Lemma C.2 and M be the input to the ResidualSol ver. As before, we let A E maxA: ||AA|les res, (A)
Let
and OPT (Ass As in Section 4 let di i.
J (A Vf())) and 8; f" ((Ax))) for all
We start with the following lemma.
Lemma C.7. Consider an iterate x and guess M. Consider an algorithm that takes input
and M and it outputs a solution to the Problem If OPT E (2/ .M] and the algorithm satisfies
Invariant ] then the algorithm outputs solution A such that for A n we have OPT
A
A
and res, 2 20
Proof. Let a = -g A Note that A satisties g T TA -1. Since OPT E M (M,M) M). we have
Vf(x) (AA*)
OPT
2
M
M
2
17

---

Moreover since ||A 1o S
and from Lemma
4.3
we have
A A'
MC
A
S 4eM + 2M < 13M.
2
00
This means, our algorithm will output solution A that satisfies
(x (AA) = M
11
|1 - C s, (AA)))
(ss)))))))
MC²
min g -=
|
< 13M
Let Â
11 we have
M
Vf(2) AA
11 1
S
C
8, AĀ
.M
121
which gives us
res A
M
13
M
M
2
OPT
11
121
20
20
Thus it only remains to show that ResidualSolver satisfies the aforementioned invariant. Notice that the Problem 7 has a similar structure as an loo reggressoon problem solved in the previous section, albeit with additional quadratic term (s, (AA)² )²) Fortunately, the algorithm only needs return a constant factor approximation, instead of a 1 + approximation. This allows us to extend the approach we used for Algorithm 2
and use similar analysis.
In the remainder of this section, we show the following lemma, using similar ideas as in our analysis
of our Lx regression algorithm.
Lemma C.8. Algorithm satisfies Invariant 7
By combining Lemmas C.7
and C.8
we obtain Lemma 4.2
We proceed with the proof Lemma C.8 Lemma C.9. For all iterations
by showing the following lemmas.
of ResidualSSlverr, we have
8, (AA(1)
21
< min (s. (s,(A)))
MC²
||AD|
2
Proof. Let A arg ming A=-1
(0, (AA)))
+ MC² ||AII We have
(1]w|11 + +d) +00 (AA())))) 21
MC²
(0)
+d) 2
(0)((AA)))) (AAD))
2
2C
(1) + 2( + + 8, (AA*)
due to the optimality of (t)
2
< 2 (|//|1
+d)
MC² p())
+ 8, (A
since ||/00| 2 + dd
|r(0 ||
18

---

which gives
(s, 8, (1A11)) 8)
MC² r(0)
||| + (1A))2
2
x (s, (AA))) + MC²
|AA |
2
as needed.
Lemma C.10. ResidualSolver maintains the invariant that. for all 2 0,
3 {p(t+11) E (pl0)
|r(et]] |(10]| 2 26..
Proof. When [AA (t)
2 Fatt
we have r (((+1)
i x =
for a coordinate
+1
such that (AA (1)); = ||A (4)
Io Let v = 1, be the indicator vector for coordinate i. We have
p((+1) (() and ||0||1 1. Using Lemma A.2 we have
E ( - E (p(o))
MC² 2 (AA 2
MC
26M 2 26M.
||||tt1|| |r(0 11
4
When (A 80
< S, for each coordinate j such that ((+1) > (9 we have r((t1)
1 (2) 52 j
()) C Note that pit+t
1443 Hence,
(A) (1)
(A) 2 n00
(p (t+1) - -p,-) (1)
1
14+J
p. [2]
P.
(++1)
(t)
r1 (++1)
rj
rj
MC² 2
(A1 (0)
(1)
(,(14)) - -,
(r)
(1+1) (1)
26M.
by Lemma A.I
E3 (AA 2, 1
E (p(c++1) - 3 (p |||[+1]]|| - ||,1
Ej (((tt))) -r(())
(/ (1) (
(2)
Σ Egnggtt (A
P3
Egngtt>>
(e+1)
-r (21)
26M.
Lemma C.11. Rosiiuullolover returns dual solution (T) then E
s ASC²
x(7))
> 13M.
2||,(3)||,
Proof. By Lemma C.10 we have that
T-1 Σ 3 (pllt2)) - E (D!o) 2 26M
T-1 1
p
(++1)
(0))
k
0
19

---

leading to
E(plT)) 2 26M (1/00) 1-000 11)
Since ||r| 1 2 2 (1]w|11 + +d)
3 s
||| (()
MC²
2 3
2 211wo) |r(T)
+ d)s
||(t)|]] ,(())
MC²
((1)
1 11:0011
26M
2 13M,
as needed.
Lemma C.12. If ResidualSolver returns primal solution A then ||A 1 I C
and
s. (Ab)²) -
min gTA=-1
(s, (AA)
MC
|
?
Proof. If the algorithm returns A, we have |A loc I 11 either by a solution in a single iteration,
C
or the average over iterations when ||AA0)) loc I S. In both case, by Lemma C.9 and convexity, we have
(s. (A2))) S
min -A=-1
(s, (11)))
MC²
||
C.2 Proof of Lemma C.6
In this section, we analyze the running time of the ResidualSolver (Algorithm 4. The rumning time dominated by the linear system solves, and thus we upper bound the number of calls the linear system solver.
We proceed similarly the analysis of our for regression algorithm. Let The and be the iterations when |A (t)
S and || (A) < S, respectively before the algorithm returns a primal solution or a dual one. We also abuse the notations and denote by The and Ti the numbers of such iterations, respectively.
Lemma C.13. Thi S (d2/3).
Proof. Again, for such that
A (1) > 5, by Lemma A.2
we have
& (p((+22) - (p(1)
|1(+1))11 ||/0 2 26Md3
Since || ||:0011 11, we get
& (plttt)) - (p()) 2 26Mdi
Therefore
MC²
3 ([|w|) + d) s +
-,()))
> 26Md3Tma
2
Notice that |r(3) s 2 ([ww]] + d) s 6d and
s
MC²
|
((3)
S 13M ||
MC² (T)
s MC²
((T)
3 2( + +d) s
2 2[1w|l
+ ddE
2
2 (11w|] + d)
MC²
p(T)
< 3dg
s
|
< 78dM.
20

---

We obtain Thi S 3d
Lemma C.14. Ti I 0 dd' log (n))
Proof. Let a ((+1)
We have
Σ EiEr.
A
11
2 C
Tio
We obtain that there exists coordinate such that
Σ LETιo
AA (t)
C2 117i
We have if (AA10)) C2 100, (AA C 10, and if (AA(0)) C z 100, (AA()) 0²
52a (0) Hence,
(AA
C 10 +1
2 >1 52xg
We obtain
Tio
Σ
Vai
11
2
522
LETI.
(1)2
(t) > 1, we have For such that a;
AA Ce
10
11db
522
V52
v52
Similarly Lemma B.4 we obtain
Tio S 00 log (m)
Lemma C.6 now follows from the above lemmas.
D QSC Algorithm for the Underdetermined Case
In the underdetermined case I d, instead of using Lewis weights in the residual solver, we can simply return the algorithm by [VV19] and use a uniform initialization of the resistances. We provide the algorithm in Algorithm 5 The analysis follows similarly (which we omit). The number of linear system solves is 2/33/3 l)gn).
E Approximating the Lewis Weights
Here we review the fixed point iteration by [CCLY19 for computing approximate too Lewis weights. While the algorithm is known to provide only one-sided approximation, this guarantee suffices for our application.
Theorem F.1. On input A E Buxd the algorithm ApproxLewis( A) returns w.h.p. loc Lewis weights overestimates w E RD in the sense that
w; 2 w/ A A 1
(AA A A
d |||] < 2d,
in time O (logn n TA), where Ta is the time to solve a linear system involving a matrix A DA, where D is a positive diagonal.
21

---

Algorithm 5 ResidualSSlverrt, M) for S
1: Initialize: r(0) =1
2: gi NI (AT (ATAAf(fa Vf(2)) f ((Ar)) 0, = -0, =
3: while |||(0]] 11
4: Let p(() 2ns + MC p(0) A arg ( (AA)3)
5:
if
MC² plnl
| (AA (2)
2 13M then return (())
6:
if (AA
y then return A
M (0) 1100 S 113..
7:
if
8:
Let L' =
v(() (0' (
9:
if [|
100/11 C then return ult1/t 1/(
(1)))
()) if (A (A) 2
100
10:
((+1)
0
otherwise
11:
1= 1++1
12: return (()
Algorithm 6 Approximate foo Lewis weights ApproxLewis(A)
1: Input:A symmetric polytope given by -I, S Ar < In. where E Raxd
2: Oufput: Approximate foc Lewis weights w such that Waue w and Σ S d
3: Initialize: w."
d for 1, ,.....,.. n. T = 10 log n.
4: for k
5: W(k) = diag (wi*)).
6: B(k) A.
7: Let ((k) _2x0 be random matrix where each entry is chosen i.id. from N (0, (),1), i..
the standard normal distribution.
8:
for i 1....,
(B(A)BB())) wi (k+1) 5/h0 ((M) (B(N) B(0))= (Voo (vof(aa)) )a)
9:
+ E w
(k) for I...,, m.
Wt
F Handling Affine Constraints
In this section we show that the problem we solve is in full generality, in the sense that even in the presence of affine constraints we can still minimize objectives of the 5 without significant overheads. Formally, given an objective of the form
min NI
f ((Ax 6);) -b))
1=1
where A E Raxd and N E Rmad with m < d, we can minimize it to high precision using the algorithms from Section with minimal changes. Indeed, we can observe that, assuming the existence of an appropriate residual solver, Algorithm [3ji completely unaffected by this subspace constraint. Hence the only difficulty is posed by solving the residual problem described in Algorithm 4 while additionally enforcing the subspace constraint. Recall that this problem, in its most general form, takes as input matrix A, well as weight vectors 8, u, and seeks an approximate minimizer for
(s, (Ax)))
min 23 A2) --1 Na
To handle the affine constraint No 0, we can convert this objective into an unconstrained problem via change of variable. Indeed, let zg be point satisfying Nx,- = Then any x in the affine space can be expressed as
By.
22

---

where B Bexddinkorr ker(C) and im (B) = ker (N). In other words, the columns of B form a basis for the null space of N. Thus our problem is equivalent
(s. (ABB)))
min (:(u, A
and takes exactly the form required for the fee regression routine from Algorithm 4 which leaves us with an optimization problem over lower dimensional space y E (er(M) Unfortunately, constructing the matrix B explicitly may be costly, so want to avoid doing so. Instead, claim that the regression algorithm can be directly exccuted using solvers for matrices the type A DA and N "AAAA)
+ N where D is a positive diagonal.
The key difficulty lies in computing the least squares step
(t) = Byy (2)
(11)
yO) = arg
min
(p (ABy)))
(12)
ABy)
without explicitly accessing B.
Lemma F.1. The solution the least squares problem defined in (7 12 as
can be explicitly computed
(1)
T AA A.
A - (AT (-NT (NT) N (AT
Au+AAu
where diag (p(t)
Proof. We notice that the solution to this least squares problem has solution
y() TA (BTAATA ATPAB) BTA -(B (BAA ATA
and equivalently (t) satisfies (t)
ABZ 2, where
B A PAB2 B ATu..
Therefore there exists T such that:
PAP Bz A w E ker (BT) im (B) = ker (N)+ im(NT).
and thus we can write
Bz = (A (w (w+A* ATu)
wich implies that
N (ATPA)) (w + ATu)==0 =0,
and hence
N PA) (N (N =0.
This allows us to explicitly express
r = (NT NT)* (ATTPA) ATu,
w -NT -N (ATTA)))NT))) (AT ATu,
which finally yields
Bz = PA (-NT (P (NNT(N(ATAA)'NT) PAT Auu+ ATu)
and
((() = Byll)) ()
1
ABz
Therefore the entire algorithm can be carried out as in the unconstrained case.
23

---

F11 Lewis Weights in the Affine-constrained Setting
In addition being able properly execute the least squared steps in Algorithm proper initialization of weights. While in general, there is no direct notion of Lewis weights in the case where affine subspace constraints are included, we can apply the same reparametrization idea. After reparametrizing the null space of N in terms of the image of matrix B, we obtain an unconstrained problem involving the matrix AB, which is the matrix for which we need to compute the for Lewis weight overestimates we use at initialization. Again, we argue this can be done without explicit access B. Note that the fixed point iteration algorithm of [CCLYT9) only requires computing leverage scores of the underlying matrix 1 AB (B" A PAB) B AA Since, for increased efficiency, the algorithm also uses Johnson- Lindenttsnnnsssssuuss sketching, we further require being able to evaluate bilinear forms of the type
4 one also requires
w AB (B' T A PAB) A
where is a positive diagonal. As we saw before, we can evaluate
B (B PTAB) A
=(ATPA)* (-NT (N(ATAA)* NT) (AT Au ATu)
which yields the expression for the required bilinear form, it can be directly applied inside the Lewis weights estimation algorithm.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The introduction includes main results, which we provide proofs and support- ing empirical evaluation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [No]
Justification:
We leave addressing the paper limitations to future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Assumptions are stated along with the theorems. Proofs are provided in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provide the code and necessary information for reproduction.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer: [Yes]
Justification:
We provide the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.ccppullc//uuuii wwwticccguie//eeeeeeeeeii CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details are included in the paper. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are included.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
27

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Machine specifications are listed.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The paper is mainly thcoretical and does not have any potential harms to the socicty.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [No]
Justification: The paper mainly theoretical and does not have any potential harms the society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [No]
Justification: The paper does not use pretrained language models and only uses synthetic and publicly available data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All data and code used in this paper are cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We release the code and data generation procedure described in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The experiments in this paper do not concern human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The experiments in this paper do not concern human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
30

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We did not LLM at anytime in the development of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https://neure) /ttp:pp////erreeec//o//ooeeeerer /ct.//ooooeeencc//22/////1/ for what should or should not be described.
31


Reviews:
[{"review_id": "GB1k76YkUE", "reviewer": "Reviewer_Gv4i", "summary": "This paper considers the problem of optimizing generalizing linear models, i.e., $\\min_{x} \\sum_{i} f_i(a_i^\\top x – b_i)$ in the case where all the $f_i$ are the same and quasi-self-concordant (though the techniques of the paper may apply more broadly). The paper provides a trust-region based method to reduce the problem to approximately solving variants of $\\ell_\\infty$-regression which they solve in turn with Lewis weight overestimates used with an iteratively reweighted least squares (ILRS) algorithm. Ultimately, this provides an algorithm which solves the problem in $\\tilde{O}(d^{1/3})$ iterations where $\\tilde{O} (\\cdot)$ here hides polylogarithmic factors as well as polynomial dependencies on a quasi-self-concordance parameter and a $\\ell_\\infty$ measure of the size of the effective domain. Additionally, the paper performs experiments comparing their proposed method against certain benchmarks.", "questions": "Question / Suggestion: The paper asserts that it is simpler than ABS21 and that JLS22 is complex. In what way is that true? I think more justification of this earlier would be beneficial. Additionally, JlS22 provided two sets of algorithms, some based on accelerated optimization and some for (p \\neq infinity) that looked more like ILRS. I think the paper would benefit by more clearly comparing its algorithm to all of this prior work, e.g., making clear how challenging it is to adapt previous ILRS methods to work with the norms induced by Lewis weight over estimates in the appropriate way and how hard it is to adapt the ILRs style method in JLS22 to $\\ell_\\infty$\n\nSuggestion: It would be good to clarify what QSC means on the first page and how it is used in this paper. A variety of prior work define QSC with respect to a norm (in the non-1d) case and I think it is good to clarify when the paper uses the QSC term it is very clear whether they are discussing the 1d f or the entire objective.\n\nSuggestion: Since the experiments are done for a regularized variant of p-norm regression it might be beneficial to compare against methods tailored for that problem as well or change the problem (especially since some use similar techniques).\n\nHere are additional detailed comments that might be helpful:\n\n* Page 2: Line 57: “Since the linear system solve …” – there is extensive research on decreasing the cost of iterations of related methods below the time to solve a single linear system. I think this might be important to mention here.\n* Page 2: Line 64: I think it might be helpful to somewhere clearly explain why the eps^{-2} in the abstract doesn’t appear in the theorem. \n* Page 3: Line 130 – 131: (CR)^2/3 type rates for quasi-self-concordant functions with respect to quadratic norms were established earlier in [CJJ+20]. It seems odd to single out Doi23 as a reference for this assertion. \n* Page 3: “can handle more general functions” – Is that a new feature of the method in this paper? It might be nice to clarify.", "limitations": "Yes, with the possible exception of the concerns raised elsewhere in the review.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: As the paper well-articulates, the problem considered encompasses a number of natural optimization problems. Consequently, it is a natural and important problem to seek improved optimization methods for. The paper provides a natural straightforward strategy, which they then implement and perform experiments on. I think this paper nicely highlights the importance of a problem which they provides an elegant solution for it while demonstrating its promise empirically. This paper seems to be making progress by promoting a natural optimization problem, providing a key theoretical benchmark for it, studying the problem in practice, seeking simpler / more straightforward algorithms, and building out the theory of ILRS. I think this paper could facilitate further research in theory and in practice on solving algorithms in this space.\n\nWeaknesses: It is unclear how challenging it is to obtain the $\\tilde{O}(d^{1/3})$ rate provided by the paper by using prior tools and the relationship of the approach to prior work could perhaps use further explanation. The paper provides a reduction from the problem to trust region problems related to $\\ell_\\infty$-regression and then provides a solver for both this problem and the more speciialized $\\ell_\\infty$-regression problem. The reduction to trust region problems seems fairly standard in light of prior work related to quasi-self-concordance that the paper cites. Additionally, as the authors note, $\\ell_\\infty$ regression is then solve-able more efficiently than the method the paper proposes for it (at least in terms of not having an extra $1/\\epsilon^2$ factor, though potentially in a more complicated fashion). Consequently, the novelty in the paper seems more in solving the trust-region problems (as opposed to $\\ell_\\infty$ regression) and in providing an arguably simpler approach than what the literature gets for solving $\\ell_\\infty$ regression (at the cost of the $1/\\epsilon^2$ factor). However, these distinctions and comparison could be better clarified and it is unclear how challenging it is to adapt prior work to solve the trust region problem. Additionally, the empirical results only compare against a limited set of methods. \n\nUltimately, the paper provides a new runtime for a natural quasi-self-concordant optimization problem and provides a new algorithm for $\\ell_\\infty$-regression. Consequently, this paper could make a great addition for NeurIPS. However, I think the writing could be improved to more clearly articulate its contributions and its relationship to prior work.", "was_revised": true, "final_justification": "The discussion regarding the paper addressed some of my concerns and elevated my view of the submission. That the paper ultimate provides their results for QSC optimization I think gives a strong reason for acceptance. However, I think the depth of these results, the challenges in obtaining them, and the relationship of the approach to related work could still use careful consideration in the final version.", "rebuttal": "We thank the reviewer for their work and helpful feedback. We would like to address the reviewer's concerns below.\n\n**Weakness**\n> The reduction to $\\ell_{\\infty}$ regression seems fairly standard in light of prior work related to quasi-self-concordance that the paper cites (and the paper “Matrix Scaling...” which is not cited but seems relevant to this reduction and may be good to discuss). As the authors note, $\\ell_{\\infty}$ regression is then solve-able more efficiently than the method the paper proposes for it (at least in terms of not having an extra factor, though potentially in a more complicated fashion\n\nWe cite and briefly discuss this work (CMTV17) on lines 80-89. We would like to clarify that this and other prior work do not provide a reduction to $\\ell_{\\infty}$ regression, and there is currently no known way to directly apply $\\ell_{\\infty}$ regression algorithms to QSC optimization. Building on these works, we reduce the QSC problem to a sequence of subproblems where we are optimizing a quadratic function subject to an $ \\ell_{\\infty}$ box constraint (in addition to the linear system constraint). This problem is related to but distinct from $\\ell_{\\infty}$ regression and the prior work on regression is not sufficient to solve these problems even if we are only aiming for $n^{1/3}$ iterations, as we can see from e.g. ABS21. CMTV17 (and AZLOW17) provide an algorithm for these subproblems only for the specific function arising in matrix balancing, and it does not apply to general QSC functions (in addition to its iterations scaling with n instead of d). The main contribution of our work is to design a new solver for these subproblems for general QSC functions that significantly departs from ABS21 and other prior work. We would like to highlight some distinctions\n\n- Comparison with JLS22: While JLS22 introduces a new algorithm with Lewis weight for $\\ell_{p}$-regression, this algorithm does not include $p=\\infty$. There is a fundamental reason for this. This algorithm follows the line of works for $\\ell_{p}$-regression that use the Taylor expansion to approximate the $\\ell_{p}$-norm. This does not work for $\\ell_{\\infty}$ norm. As a consequence, for $\\ell_{\\infty}$-regression, JLS22 use softmax as a proxy, and Monteiro-Svaiter acceleration with a ball oracle to obtain $\\tilde{O}(d^{1/3})$ rate. Monteiro-Svaiter acceleration is a complex acceleration method, and there have been multiple attempts (eg. Carmon et al. 2022) to simplify it (for example, this method requires to solve an implicit equation to find the coefficients), but the practicality of this method remains unclear. Our work on the other hand uses the dual formulation of the problem, which is fundamentally a different approach. We show a simple algorithm that incorporates Lewis weights, without any complicated acceleration scheme and allows for an efficient implementation.\n\n- Comparison with ABS21. Our work reduces the iteration complexity for solving the subproblems from $\\tilde{O}(n^{1/3})$ to $\\tilde{O}(d^{1/3})$ with a new insight from solving $\\ell_{\\infty}$ regression. As pointed out by JLS22, the approach to gain the improvement does not simply stem from sparsification with Lewis weights. Instead, this requires a new and clever way of using Lewis weights in the algorithm, which is not at all an apparent application of prior approaches. In particular, our algorithm for solving $\\ell_{\\infty}$-regression with Lewis weights departs from prior approaches as explained above. From the practical side, the algorithm of ABS21 uses several different parameters ($\\tau,\\zeta , \\alpha$). In practice, this algorithm requires to tune these parameters to obtain a fast runtime, which makes it not a practical algorithm.\n\n- Comparison with EV19. While the framework of EV19 provides the basis for our algorithm, their framework requires very specifically that the solution is initialized (close to) uniformly. A significantly different initialization using Lewis weights immediately breaks EV19's convergence analysis. While being simple in hindsight, our algorithm requires a subtle use of the new energy lemma by JLS22 in a fundamentally different approach. Moreover, we cannot use the algorithm of EV19 to solve the subproblems of QSC since it is specifically designed for only pure $\\ell_{\\infty}$ objectives, whereas we need an algorithm that solves $\\ell_{\\infty} + \\ell_2$ objectives\n\n> they only compare against a limited set of methods\n\nThe set of implementable algorithms beyond first order methods (which are not apt for high-precision) is very limited. For reasons mentioned above and below, existing algorithms such as ABS21 do not provide a practical implementation.\n\n**Questions**\n> Q1. The paper asserts that it is simpler than ABS21 and that JLS22 is complex. In what way is that true? \n\nWe would like to stress again that the algorithm by JLS22 for $\\ell_{p}$-regression does not include $p=\\infty$. Their algorithm for $\\ell_{\\infty}$-regression relies on a complex acceleration scheme. On the other hand, the algorithm by ABS21 uses a number of parameters that need to be tuned in practice, which makes it difficult to be efficiently implementable.\n\n> Q2. “can handle more general functions”. \n\nOur claim here is that our approach generalizes to $\\sum f\\_{i}((Ax-b)\\_{i})$, where each $f_{i}$ is QSC. This generalizes the setting in ABS21 where the objective is $\\sum f((Ax-b)_{i})$ for a QSC function $f$.\n\n**Suggestions and comments**\n\nWe thank the reviewers for the suggestions and comments. We will incorporate them in the next revision of the paper. We will also add the above clarifications and comparison with prior work."}, {"review_id": "7Mesyvs8kH", "reviewer": "Reviewer_h9Py", "summary": "This paper considers quasi-self concordant optimization, i.e., $\\min \\sum_{i= 1}^n f[Ax-b]i$ , $x\\in R^d, Nx = v$ where $f$ is quasi self concordant. Prior state of the art includes work by [Adil-Bullins-Sachdeva, NeurIPS’21] which solves the problem in $n^{1/3}$ iterations, each iteration solving an $n \\times n$ linear system. This paper uses $\\ell_{\\infty}$ lewis weights and gives an algorithm that finds a solution in $d^{1/3}$ linear systems, where each system solves a $d \\times d$ system.\n\nThis is a big improvement for overdetermined systems when $n>>d$. Prior such improvements have been seen for $\\ell_p$ regression as in the work of JLS’22, where they used $\\ell_p$ lewis weights to obtain such improvements. Furthermore, the paper gives an IRLS based algorithm inspired from EV’19 which can be implemented easily.\n\nThe algorithm is similar to the algorithm of EV’19 where the weights are replaced by overestimates of the $\\ell_{\\infty}$ lewis weights.", "questions": "Questions:\n1. What is new in the analysis that allows for the incorporation of Lewis weights into EV’19? It seems like reducing to solve to $d\\times d$ systems is new but I am not sure.\n2. I am not sure how much easier this is than ABS’21 for simple cases of softmax regression or $\\ell_{\\infty}$ norm regression. Do the authors have a sense of why their algorithm might be better in practice?\n3. I believe prior works on QSC optimization including ABS’21 and CJJ+’20 also work for hessian stable functions. They just seem to not explicitly write it but the proofs are done for hessian stable functions.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The paper gives a significant improvement over prior works in the over-constrained regime, for important regression problems.\n2. The algorithm is fast in practice.\n\nWeaknesses:\n\n1. How much of the analysis is new is unclear as similar ideas have been used before in JLS’22 where they use a similar change in weights to recover a similar improvement to AKPS’19.", "was_revised": true, "final_justification": "I was mainly concerned that the results were easily derivable from previous results, but based on the rebuttal it seems like it is not completely straightforward, which is why I am changing my score.", "rebuttal": "We thank the reviewer for their work and helpful comments. We would like to refer the reviewer to our response to Reviewer  Gv4i for the clarification of our contribution in comparison with prior works. We would like to address the reviewer's concerns below.\n\n**Weakness**\n\n> How much of the analysis is new is unclear as similar ideas have been used before in JLS22 where they use a similar change in weights to recover a similar improvement to AKPS19.\n\nWe would like to first clarify that the improvement that the reviewer mentioned is for $\\ell_{p}$ regression problems with finite $p$ and does not apply to the QSC or the $\\ell_{\\infty}$ regression problems we consider in our work. JLS22 provides two very different algorithms: the algorithm the reviewer mentioned is for finite $p$ that builds on the regression algorithm of AKPS19 and does not work for $p=\\infty$, and a separate algorithm for $p=\\infty$  that builds on the algorithm of CJJ+20. Since it cannot handle $p=\\infty$, the former algorithm cannot be combined with existing trust region templates for QSC optimization such as those used in our work or the prior work of ABS21 (see also our response to Reviewer Gv4i). Since the latter algorithm uses a completely different approach from AKPS19, it is not clear how one could leverage it for QSC optimization. We refer the reader to our response to Reviewer Gv4i for a more detailed discussion.\n\n> Q1. What is new in the analysis that allows for the incorporation of Lewis weights into EV’19? It seems like reducing to solve to $d\\times d$ systems is new but I am not sure.\n\nThere are two new ideas that allow for the incorporation of Lewis weights into EV19, which does not come from sparsifying the problem using Lewis weights or a direct application of the ideas from previous works. First, our algorithm differ from EV19 in the initialization using Lewis weights instead of a uniform initialization. Second, in Case 1 in the algorithm 1, we need a different update where we only update one coordinate but with a large additive step. Uniform initialization is critical in EV19's algorithm which relies on the fact that each $r_{i}$ is sufficiently large. Initialization using Lewis weights breaks this condition and thus requires a different update scheme and a new analysis.\n\n> Q2. I am not sure how much easier this is than ABS’21 for simple cases of softmax regression or $\\ell_{\\infty}$ norm regression. Do the authors have a sense of why their algorithm might be better in practice?\n\nOur algorithm has an iteration complexity $\\tilde{O}(d^{1/3})$ while it is $\\tilde{O}(n^{1/3})$ for ABS21, which we expect it will directly translate to faster running time in practice on overdetermined instances. This improvement does not come readily from prior work. For example, the improvement for softmax and $\\ell_{\\infty}$ regression is shown in JLS22, which is built on top of CJJ+20, which needs a complex acceleration scheme. Our work, on the other hand, provides a very simple method that does not use any acceleration, which has several advantages in practice as we discuss next.\n\nIn practice, our method is robust and exhibits numerical stability. In contrast, accelerated methods require careful adjustments to their step sizes to handle precision errors, or errors from the least-squares solver (see e.g., http://blog.mrtz.org/2014/08/18/robustness-versus-acceleration.html, Devolder-Glineur-Nesterov '23), and even algorithms that have a good theoretical behavior in fixed-point arithmetic may encounter difficulties when executed on real-life floating point numerical architecture. Additionally, the algorithm by ABS21 includes several parameters ($\\tau$, $\\zeta$, $\\alpha$). In practice, these parameters require tuning which degrade the practicality of the algorithm.\n\n> Q3: I believe prior works on QSC optimization including ABS’21 and CJJ+’20 also work for hessian stable functions. They just seem to not explicitly write it but the proofs are done for hessian stable functions.\n\nYes, these works extend to Hessian stable objectives, as they use the same trust region template that only requires Hessian stability. We note that the main challenge is to solve the resulting subproblems. CJJ+20 provide such an algorithm for only smooth functions, and both algorithms have iteration complexity scales with $n$. Our algorithm is for general (non-smooth) functions and its iteration complexity scales with $d$ instead of $n$."}, {"review_id": "x4aHxqcDzP", "reviewer": "Reviewer_eTKg", "summary": "This paper considers the quasi-self-concordant (QSC) minimization problem, which includes logistic regression and regularized $\\ell_p$ regression as special cases. Based on the observation that QSC functions are Hessian stable, the authors propose an iterative algorithm that solves a sequence of $\\ell_{\\infty}$-norm constrained quadratic subproblems, reminiscent of trust-region methods. Then the authors connect their subproblem to an overdetermined $\\ell_{\\infty}$-regression problem. As a contribution of independent interest, they design a new $\\ell_{\\infty}$ regression algorithm based on iteratively reweighted least squares (IRLS) insipred by (Ene and Vladu'19). By incorporating $\\ell_{\\infty}$ Lewis weight overestimates, they improving the complexity from $\\tilde{O}(n^{1/3}/\\epsilon^{2/3})$ in (Ene and Vladu'19) to the-state-of-the-art $\\tilde{O}(d^{1/3}/\\epsilon^{2/3})$. This improvement directly translates to a faster algorithm for QSC minimization, particularly when $d \\ll n$.", "questions": "## Questions\n- The $\\ell_2$-regularized $\\ell_p$ regression problem is a key application of QSC optimization, and the authors include it in their experiments. How does the complexity result in this paper compare to existing results specifically for this setting?\n- The main algorithm in Algorithm 3 involves two binary search steps over $\\nu$ and $M$. While this only incurs extra logarithmic factor in the final complexity bound, it adds complexity to the implementation. Do the authors think it is possible to remove these binary search steps?\n\n## Suggestions\n- It would help readers if the authors elaborated on why their initialization using $\\ell_{\\infty}$ Lewis weights offers an advantage over uniform initialization. As I understand it, the main insight comes from Lemma A.2 due to (Jambulapati, Liu, Sidford'22), which provides a potentially tighter lower bound on the increase in energy.\n- On a first reading, it was unclear how Section 3 relates to the central QSC optimization problem. I suggest switching the order of Sections 3 and 4 to better motivate the introduction of the $\\ell_{\\infty}$ regression problem.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The paper presents a simpler $\\ell_{\\infty}$ regression algorithm for the overdetermined setting ($d \\ll n$). The proposed algorithm matches the state-of-the-art result of (Jambulapati, Liu, Sidford'22), and it is conceptually more straightforward and potentially more practical. It builds on the IRLS method from (Ene, Vladu'19), with an effective initialization using $\\ell_{\\infty}$ Lewis weight overestimates.\n- The authors show how $\\ell_{\\infty}$ regression can be used as a subroutine in a trust-region framework for QSC optimization, simplifying the approach of (Adil, Bullins, Sachdeva'21) and achieving better complexity in the overdetermined regime. \n\n## Weaknesses\n- While QSC optimization covers important problems such as logistic regression and regularized $\\ell_p$ regression, the paper does not clarify whether the proposed method yields concrete improvements in these specific applications. \n- The exposition could be improved. In particular, compared to prior work, the two key contributions are: (1) showing that the residual subproblems in (5) can be treated as $\\ell_{\\infty}$ regression problems, enabling simpler IRLS-based methods; and (2) using $\\ell_{\\infty}$ Lewis weight overestimates to initialize the resistances to replace the dependence on $n$ with $d$. However, these points are relegated to the appendix, with limited discussion or intuition in the main text.", "was_revised": true, "final_justification": "During the rebuttal, the authors clarified that their convergence bounds also improve upon previous results in the context of logistic regression and regularized $\\ell_{\\infty}$ regression problems, particularly in the regime $d \\ll n$. Given their commitment to improving the paper’s presentation, I have decided to maintain my initial rating.", "rebuttal": "We thank the reviewer their work and encouraging feedback, and the suggestions for improving the paper.  We would also like to refer the reviewer to our response to Reviewer Gv4i for the summary of our contribution.\n\n**Weakness/Questions**\n\n> The $\\ell_2$-regularized $\\ell_p$ regression problem is a key application of QSC optimization, and the authors include it in their experiments. How does the complexity result in this paper compare to existing results specifically for this setting?\n\nThe improvement in our paper implies a direct improvement in logistic regression and regularized $\\ell_{p}$ regression. More specifically, for logistic regression, the number of calls to a system solver by our algorithm is $\\tilde{O}\\left(d^{1/3}R\\right)$ compared with $\\tilde{O}\\left(n^{1/3}R\\right)$ by ABS21. For $\\ell_{2}$-regularized $\\ell_{p}$ regression, the number of calls to a system solver by our algorithm is $\\tilde{O}\\left(d^{1/3}Rp^{2}\\mu^{-\\frac{1}{p-2}}\\right)$ compared with $\\tilde{O}\\left(n^{1/3}Rp^{2}\\mu^{-\\frac{1}{p-2}}\\right)$ by ABS21.\n\n> Removing the binary search. \n\nUsing binary search has been a commonly used approach in solving this problem. We agree with the reviewer that removing the binary search is an important direction. In practice, we can use a variant of the algorithm that updates the values of $\\nu$ and $M$ during the algorithm without using binary search, and we provided such a variant in the code. However, currently we do not have a theoretical analysis for this variant and we leave it for future work.\n\n**Suggestions**\n\nWe thank the reviewer for the suggestions. We will incorporate them in the next revision of the paper. We will also add further discussion on our contribution and comparison with prior work as discussed in our response to Reviewer Gv4i."}]

Author rebuttal:

Meta-review: This work studies the constrained quasi-self-concordant (QSC) minimization problem. The main contribution of the paper is a new algorithm for solving each subproblem in a trust-region method in $\tilde{O}(d^{1/3})$ calls to a linear system solver, which improves upon the previous $\tilde{O}(n^{1/3})$ calls. These results are furthermore based on a new (and arguably simpler) IRLS algorithm for $\ell_\infty$ regression which nearly achieves the same rate as the previous approach of [Jambulapati-Liu-Sidford '22] (though with an additional $\frac{1}{\epsilon^2}$ term). The discussion between Reviewer Gv4i and the authors provided much needed clarity on the particular placement on the work in relation to previous literature, and this ultimately strengthens the view of the work as a whole. All of the reviewers have expressed support for acceptance, and I also believe that this work would provide a meaningful and interesting contribution to the conference, though I strongly encourage that the authors incorporate the reviewers' suggestions that arose during the discussion.
Decision: Accept (poster)