Inverse classification with logistic and softmax classifiers: efficient optimization
Authors: Miguel Á. Carreira-Perpiñán
Suryabhan Singh Hada
Venue: Accepted by TMLR ()

Abstract: In recent years, a certain type of problems have become of interest where one wants to query a trained classifier. Specifically, one wants to find the closest instance to a given input instance such that the classifier's predicted label is changed in a desired way. Examples of these "inverse classification"' problems are counterfactual explanations, adversarial examples and model inversion. All of them are fundamentally optimization problems over the input instance vector involving a fixed classifier, and it is of interest to achieve a fast solution for interactive or real-time applications. We focus on solving this problem efficiently with the squared Euclidean distance for two of the most widely used classifiers: logistic regression and softmax classifier. Owing to special properties of these models, we show that the optimization can be solved in closed form for logistic regression, and iteratively but extremely fast for the softmax classifier. This allows us to solve either case exactly (to nearly machine precision) in a runtime of milliseconds to around a second even for very high-dimensional instances and many classes.

Published in Transactions on Machine Learning Research (03/2026)
Inverse classification with logistic and softmax classifiers: efficient optimization
Miguel Á. Carreira-Perpiñán Dept. of Computer Science & Engineering University of California, Merced
Suryabhan Singh Hada"
shada@paypper com
PayPal
Reviewed on OpenReview: https: // openreview. net/ forun? id- 7P30l
Abstract
In recent years, certain type of problems have become of interest where one wants to query a trained classifier. Specifically, one wants to find the closest instance to a given input instance such that the classifier's predicted label is changed in desired way. Examples of these "inverse classification" problems are counterfactual explanations, adversarial examples and model inversion. All of them are fundamentally optimization problems over the input instance vector involving a fixed classifier, and it is of interest to achieve fast solution for interactive real-time applications. We focus on solving this problem efficiently with the squared Euclidean distance for two of the most widely used classifiers; logistic regression and softmax classifier. Owing to special properties of these models, we show that the optimization can be solved in closed form for logistic regression, and iteratively but extremely fast for the softmax classifior. This allows us to solve either case exactly (to nearly machino precision) a runtime of milliseconds to around a second even for very high-dimennional instances and many classes.
1 Introduction
In abstract sense, machine learning classifiers can be regarded manipulating three objects: the input feature vector x, the output label and the classifier model f. Training or learning (x,y + f) is the problem of inferring from x and (the training set), and is usually formulated
optimization problem. Inference or prediction (x, - y) is the problem of inferring from x and f (the training set), and is usually formulated via the application of an explicit function f to x. Both training and inference have been long studied for a wide range of classifiers. The third problem (f.y > x), which can be called inverse classification, is find from y and f, and can also be formulated as an optimization problem. This problem is far less popular than the other two but has received significant attention in recent years in specific settings. One of them is in adversarial eramples. We are given classifier f, such neural net, and an input instance x which is classified by J as (say) class 1. The goal is to perturb slightly (or equivalently to find close instance to x) such that it is then classified by f as (say) class 2. The motivation is to trick the classifier into prodicting another class and trigger some action (such as having a self-driving car misclassify a stop sign as a yield sign, say). Another setting is in counterfactual explanations. Again, we are given a classifier / and an input instance x which is classified by f as (say) class which undesirable. The goal is to change x in a minimally costly way so that it is classified as (say) class 2, which is desirable. As an example, x could represent loan applicant (age, salary, etc.) and f could predict whether to approve the loan or not.
*S. S. Hada's work took place while was UC Merced.

---

Published in Transactions on Machine Learning Research (03/2026)
Problems of this type have become particularly important in the context of transparency in AI, where users may want to interpret, explain, understand, query or manipulate a trained classifier.
Such inverse classification problems can be naturally formulated as an optimization involving a distance or cost in feature space and a loss in label space. While many recent works have focused on the motivation or application of adversarial examples and counterfactual explanations, here we are interested the numerical optimization aspects of such problems. Indeed, we recognize it as a novel type of optimization problem with specific characleristics that deserves special attention. Such problems are computationally much smaller than the training problem (which involves dataset and model parameters as variables), but it is still important to solve them fast: some of the applications mentioned above require real-time or interactive processing, and this processing may often take place in limited-comm sunited-computtiion devices such as mobile phones. Besides, the optimization can be nontrivial if the number of features is in the thousands or milions.
In this paper, we consider logistic regression and softmax classifiers (also known as multinomial or multiclass logistic regression), which are among the simplest yet most widely used classifiers in practice; and the squared Euclidean distance as cost. We will define inverse classification that, while encoding the idea of inverse classification in natural way, is computationally convenient. Then, we characterize it in theory and provide what probably are the most efficient solutions possible for either type of classifier.
certain optimization problem
2 Related work
As noted earlier, some forms of inverse classification problems exist, although generally the emphasis has been in the application of such problems rather than on understanding the optimization problem in theory and solving it efficiently.
Most inverse classification works concern neural networks. Inverting neural nets with continuous outputs has been investigated since the 1980s (Williams. 1986 Kindermann & Linden, 1990, Hoskins et all 1992: Behera et. al. 1995 Jensen et. al. 1999). The algorithms were usually based on minimizing the squared error between the desired output and the predicted one via backpropagation, i.e., gradient descent. The widespread deployment of large, highly accurate neural nets in many practical applications in the last decade has brought new interest in inversion problems. One of them is activation maximization, which-wae goal of understanding the inner workings of deep net seeks imput. vectors that cause particular neuron in the net to have a large output (Simonvan et all, 2014 Zeiler & Fergus, 2014 Mahendran & Vedaldi, 2016 Dosovitskiy & Brox, 2016 Nguyen el. al. 2016 Hada & Carreira-Perpiieee examples, mentioned in the introduction (Szegedy et al., 2014 Goodfellow et al., 2015). Again, these works typically use gradient descent as optimization method, which is greatly facilitated by automatic differenti- ation, now commonly available in libraries such as PyTorrhh or Tensorflow (although the ReLU activation commonly used in deep nets is not differentiable everywhere). Some of these works also explore different for- mulations of the problem, such as different distance or cost functions, different constraints or different ways to perturb the instance, sometimes in an effort to find input instances that are realistic or suitable for specific data, such as images, audio or language (Nguven et al. 2017: Dhurandhar et al. 2018 Alzantoi et al. 2018
the
2021a).. Another is adversarial
Carlini & Wagner, 2018 Goodfellow et al. 2018 Finlayson et al., 2019 Van Looveren & Klaise 2021
A more recent trend are counterfactual explanations (Wachter et al. 2018 Ustun et al., 2019: Russell 2019 Karimi et. al., 2020). Some of these use agnostic algorithms which assume nothing about the clas- sifier other than it can be evaluated on arbitrary instances, using some kind of random or approximate search (Sharma et. all, |2200 Karimi et. all, 2020). One can also restrict the instance search space to a fi- nite set of instances and do a brute-force search, as in database search (Wexler et all, 2020). Other algorithms are specialized for decision trees and forests, which have the added difficulty of defining a piccewise constant classifier or regressor (Kantchelian et al.. 2016 Chen et al. 2019 |Parmentier & Vidal. 2021 Parreira-Perpiián Hada, 2021alb: Hada & Carreira- Perpinná 2021b Carreira- Pereiira-eerpiinn Hada,
2023a
Driven by practical applications, problems related inverse classification have also been studied in data mining knowledge discovery from databases as a form of knowledge extraction from trained model
2

---

Published in Transactions on Machine Learning Research (03/2026)
(Yang et al. 2006; Bella et al. 2011 Martens & Provost 2014 Cui et al 2015), in particular in applications such customer relationship management (CRM).
Finally, inverse classification or regression arises also as a step within the method of auxiliary coordinates (MAC) [Carreira- Perriián & Wang 2012: 2014). MAC seeks to train nested functions in machine learning, resulting from function composition, such as g(((x)) where f is a feature extraction stage whose output is fed a classifier g. MAC operates by introducing auxiliary variables z that decouple from g, turning this into a penalized optimization, and solving it by alternating over the original parameters of f and g and the auxiliary variables 2. The latter step over the auxiliary variable 2, of each training instance (x Vn) can be written as "minl,.. bllzn f(xx)]l + ly g(zn))", which takes the form of an inverse classification regression, similar to eq.
3
Inverse classification as optimization: softmax classifier
3.1 Definition of the optimization problem
Consider K-class softmax classifier, where the softmax probability of class {l...., K} for instance R is defined as p(x) P.. (x)) with
pr(x) = e² Σ e i (I,...:K}
(1)
where z Ax+ b E R and the parameters E RXD and b E Dx are matrix of weights and a vector of biases, respectively. Throughout this paper, we assume the parameters (hence the classifier) are fixed, presumably by having been learned on training set. Obviously, each p: value is in (0,1) and their
is 1. Define the function 9x(x) = lx) > O. Write A = (aa .kk where each a, is of D x 1 (ith row of A, transposed). Define A = A lag of K x D, where 1 is vector of ones (and likewise ass- = as)
and 52 = b - b of K 1. Note that A₁ has one row of zeros (row k).
The following results characterize the problem. Theorems B. 3 are well known in convex optimization. The remaining theorems exploit the particular mathematical structure the K-class softmax classifier, logistic regression and the & norm (the dinedimenii Hessian representation for the K-class softmax classifier and the closed-form solution for logistic regression). This affords important computational advantages which do not arise with other classifiers or other norms.
Theorem 3.1. For each i {I,..., K} we have that gi is convex (bul not strongly convex).
Proof. This is a well-known result, see e.g. Boyd & Vandenberghe 2004 87).
We define the optimization problem l
min E(x; A,) = XE30
x1| + gx())
(2)
where x E R is the source instance, l: E (1...,,K) K} the target class and À trades off distance to X with class-k probability. Next, we give several results about the problem and about Newton's method and discuss their implications in section B.G. An alternative formulation of interest is "ming ||x - x| s.t. 9k (x) & a.. Although we do not consider it here, can be solved by trying different values A in (2), possibly using a bisection search. This can be done efficiently by scanning a solution path over X via warm-start (see
section 3
Theorem 3.2. F(x;A, is strongly conver. Hence, has unique minimizer x".
All (vector matrix) norms are l norms throughout the paper. "Note that Pk itself not convex (even for K and ueither is A|x x|| (x()). Defining model inversion this way has local minima (in fact, scems to have local minimum very near which useless but makes finding useful minimum hard).
3

---

Published in Transactions on Machine Learning Research (03/2026)
Proof. This follows (Nesterox, 2004) from the fact that E equals the sum of convex function, ga (from
theorem and strongly convex quadratic function, 3 - x|2
3.2 Gradient and Hessian
It easy to see that the gradient and Hessian of E' wrt x are:
Vx X, k) = X(x X + p(x)
(3)
Ex k) = AI + A (diag (p) - pp")),:
(4)
To avoid clutter, we will usually omit the dependence on x, X, k. We will also call the matrix Af (diag (p) Ax the "softmax Hessian".
Theorem 3.3. The Hessian 42 Ex) satisfies the following Vx E RD; it is positive definite; its largest eigenvalue and condition remmber upper bounded by x+ || 2 and + ||/x, respectively; all its D eigenvalues are greater or equal than X; if K D then at least D - K + eigenvalues equal X.
Proof. Ex) is symmetric positive definite since the softmax Hessian is positive semidefinite (from the- orem and the A-term Hessian is positive definite. Hence, the eigenvalues of V²x(() equal its singular
values and have the form À + λæ, where & dD S .... I A are the eigenvalues the softmax Hessian.
We can find an upper bound for a as follows. Let be an eigenvalue of A (diag (p) A then:
7 A (diag (p) - )
= u" A diag (p) A, u² A PEP A AT
u² A diag (p) A,u |p" Asul
S u A diag (p) Agu
its largest eigenvalue Å is smaller or equal than the largest. eigenvalue of A diag (p) Ak, which equals | diag (p) Axll- But ||A] diag (p) A < || ||]ldia (p)ll < || (since p is in the interior of the regular simplex, its largest element smaller than 1). Consequently cond (V²E(x) (A+Ai)/(AADD) s (A + AA)A 1+ |Alle//.
Note that |x equals the largest eigenvalue of A& (or Af
If K < D then rank (Aa) < K; since A contains one row of zeros, and the rank of the softmax Hessian (which involves a product with A&) is at most K - 1, so 0 AD =... Ax I λK-1 S ..... I a1 Hence Ex) has at least D - + eigenvalues equal to and the rest are all greater or equal than X.
Theorem 3.4. The gradient Ex( is Lipschitz continuous with Lipschitz constant = A A
Proof. This follows from the fact that, since F(x) is convex and twice continuously differentiable, then T. is Lipschitz constant of (x() iff (
Vx IR (which itself is direct consequence of the mean || I|?, which can take L.
value theorem). From theorem 3.3 2
E
x
I A ||
Theorem 3.5. X >>>>> 1 then ( AI Vx
RD. If X < 1 then F(x" = AI.
Proof. For > 1 the result follows because the soft Hessian is bounded (from theorem 3.3 For A <
the softmax probabilities satisfy px(x*) R and p, (x") R 0 + k, diag (p(x*) p(x p(x)) )r & 0 and the result follows.
Theorem 3.6. The invverse Hessian can be written as:
(V-E)-1= (YI + A (diag (p) pp" AA) H (H (
(5)
where v ATP and H = 1 (I A7 (AtA7 + A (p)-1) A Likewise:
-(V2E) A - -1 (x-x) v H l
(6)
4

---

Published in Transactions on Machine Learning Research (03/2026)
Proof. Calling v A p and H AI + A diag (p) Ar, we can write the gradient as VE X(x x) + and the Hessian as F = -vvv? The results follow from applying the Sherman-Morrison-onnn
formula (A + BCD) = -A -A
DA- - DA -1 twice: first to V by taking A = H.
== = v and C = -1, and then to H by taking A = AI, BT = D As and C = diag (p).
Although the expressions above look complicated, they reduce the computation of the Newton direction by requiring K K inverse (of A + X ddag (p)-1), rather than D D one (of V E). Since typically K < D, this is an enormous savings. Unfortunately, it is not possible to speed this up even further and avoid inverses altogether by caching a factorization of A + A diag (p) pp because it is a diagonal update. Note that we never actually invert any matrix: for reasons of numerical stability and efficiency, expressions of the form A b are computed by solving a linear system Ax = b rather than by explicitly computing A and multiplying times (in Matlab, x = A\b rather than x = inv(A)
Having obtained the solution (A) for a value of X, we obtain the corresponding softmax probabilities px(x" (2)) for = 1,..., K by evaluating the softmax function at x". Also, from the definition of the objective function in eq. (2 we have that pi(x* exp (2llx - xx| [[==((x(A)))
3.3 Convergence and rate of convergence
Theorem 3. states that Newton's 's method with line search (I.s.) will converge to the minimizer of E from any starting point (global convergence). It is a consequence of our results above and the following theorem
Theorem 3.7. Consider function S: RD - R, not necessarily conver, bounded below and continuously differentiable in IR,, and with L-Lipcchitz continuous gradient (i.e., [[V Vf < L||x -e--vl yll Vx. y E TR and L > 0). Consider an iteration of the form Xk+1 = Xx + 04,8k, where Xy E RDD is any starting point, Sy a descent direction (i.e., ((xe) <0 if (xxx) + 0) and the step size Og satisfies the Wolfe conditions. Then Σxz0 cos? 0% [ < x0, where cos og = =f V ((VT(xx)//ls)) III fxx)]l
Now assume 8 = BV where, for each 0, 1, 2..,, BN is posilive definile and cond (Bą) S M for some M 0. Then [[vx( +0 as 00.
Proof. This theorem is amalgamation of theorem 3.2 (Zoutendijk's theorem) and exercise 3.5 in Nocedal & Wright (2006). The bound cond (Bx) I M implies bound cos 2 * > 0, from which the second result follows. The theorem also holds for other L.s. conditions such as the strong Wolfe conditions or the Goldstein conditions.
Thcorem 3.8. Consider the objective function E(x) of eq. 2 and an iteration of the form Xk+1 = X Og (V= for k = 0,1,2.... .., where Xo E RD is any starting point and the slep size Okk salisfies the Wolfe conditions. Then limg-+x X2+ = =x", the unique minimizer of E, and lim [[ 0.
Proof. Since E(x( is positive definite, - -(V' [x(x) is a descent direction. The function E(x) is nonnogative (hence lower bounded) and continuously differentiable in RD, Its gradient Ex) is Lipschitz continuous in RD (from theorem X
and its Hessian's condition number is upper bounded [xx)]l + as k + do. Since E is strongly convex
(from theorem 3.3). Hence, from theorem and differentiable, there can only be one point with zero gradient, which is the global minimizer x", hence X2 x".
Further, theorem 3.5 in Nocedal & Wright (2006) states that, if the starting point xy is sufficiently close to x" (which can always be achieved by the Ls.) and if using unit step sizes, then both the sequences iterates {xx} and of gradients [VE(x))) converge quadratically to x* and 0, respectively. Although the theorem we give requires a L.s. with Wolfe conditions, a backtracking search that always tries the unit step size first also works, because it is sufficient to take us near enough the minimizer and then using unit step sizes converges quadratically.
SIn this section (and elsewhere in the paper when referring to an iterate), we the subindex k to indicate the kth iterate in the optimization algorithm. This should not confused with the use of indicate class index, as in eq. 2
5

---

Published in Transactions on Machine Learning Research (03/2026)
For gradient descent, global convergence is also assured with Lss. (by taking BN I in theorem B with a fixed step size of T/L. (Nsterovv 2004). For other algorithms (Polak-Ribière CG, and (T-)BFGS) it is harder to give robust global convergence results (Nocedal & Wright,, 2006), but in any case they are inferior to Newton's method in our casc.
3.4 Computational complexity
For Newton's method, the dominant costs are as follows. There is a setup cost of O(K33) to compute A Per iteration, we have a cost of O(D(2K + 1)) for the gradient, O(2 + 6K for the Newton direction, and ODD(K + +1) per backtracking stop; our experiments show that most iterations use a single backtracking step (see fig. 3i D K one Newlon iteration costs about gradient computations.
3.5 Solving for path over À
It is of interest to solve problem 2 not just for a single value of X, but for a range of values of X. This can provide a set of counterfactual explanations at different distances and with different target class probabilities, which a user may examine and choose from. It is also a way to solve the constrained form of the problem, namely "minx ||x- x|| s.t. (x(x) S a", since tracing this over a corresponds to tracing (2 over A.
Using algorithm to optimize for each À value, solving for path of À from large to small (say 10 to 10-5) is very efficient by using warm-start over X. The first À value is initialized from x = =X, to which the solution is very close. If À changes slowly, i.e., we follow fine path, step size of 1 in Newton's method typically works, but we try more À values. Alternatively, we can change X more quickly, i.e, we follow a coarse path and try few À values, but we will need more Newton iterations per X. Either way, since the algorithu is very fast, this does not matter much, and solving for the whole path is just a bit slower than solving for single A. We illustrate this in our experiments (see fig. +
3.6 Discussion
An inverse classification problem (e.g. a counterfactual explanation) requires a definition of distance or norm in instance space that measures the cost of changing the source instance. In general, the norm depends on the application. For example, some works in the adversarial examples literature have used the l norm, such as SSegedy et al (2014), section 4.1) or Moosavi-Dezzooli et al. (2016, section 1). Other works have used the é or loo norm. In this work we use only the l2 norm bocause, together with the logistic regression softmax classifier, it makes a very elficient compulation possible for ils unique solution. We are not aware of a similarly efficient solution for other norms. This is particularly useful in real-time or interactive scenarios where fast foodback mattors. For instance, in a credit approval or documont moderation system, a user may want to understand which minimal changes to the input, such as adjusting an income-related feature or modifying a small portion of the text, would be sufficient change the model's decision. The efficiency of our approach makes possible compute such counterfactual explanations on demand, allowing users or practitioners to explore different "what-if" scenarios interactively.
Although the objective function F. is nonlinear, the special structure of its Hessian makes minimizing it very effective. Firstly, since E is strongly convex, there is unique solution no matter the value of X or the target class Second, if K < D (which is the typical case in practice, fewer classes than features) then the Hessian has D K eigenvalues equal to and K - greater or equal than X. This means that the Hessian much better conditioned than it would otherwise be; it is "round" in all but K-1 directions, and all optimization methods will benefit from that. That said, using the curvature information is still imporlant to take long steps. Finally, the Hessian is actually round everywhere if À > 1 near the minimizer if X < 1.
This special structure also makes Newton's method umusually convenient. In practico, Newton's method is rarely applicable in direct form for two important reasons: 1) the Hessian is often not positive definite and hence can create directions that are not descent, so needs modification, which computationally costly (o.g. it may require factorizing it). 2) Computing the Newton direction requires computing the Hessian (in ODD) time and memory) and solving a linear system based on (in O(D*) time). To make this feasible with large D requires approximating Newton's 's method, which leads to taking worse steps and losing its quadratic
6

---

Published in Transactions on Machine Learning Research (03/2026)
convergence properties. None of this is problem here: our Hessian is positive definite everywhere, and computing the Newton direction (via theorem B.6j requires a linear system of a K x K matrix, where K is in practice small (less than 100 is the vast majority of applications), without ever forming a D x D matrix, which then scales to very large D. Finally, while Newton's 's method still requires a line search for the stop size to ensure the iterates descend, near the minimizer a unit step works and leads to quadratic convergence. As result we achieve the best of all possible worlds: global convergence (from any starting point); very fast iterations, scalable to high feature dimensionalities and many classes; and quadratic convergence order, which means it is possible to reach near machine- machine-precision accuracy.
This theoretical argument strongly suggests that no other (first-order) method can compete with Newton's 's method in this case, particularly if we seek a highly accurate solution (unless we use a huge number of classes K); and this is clearly seen in our experiments. The runtime ranges from milliseconds to a second over problems with feature dimension ranging from 10 to 10 and tens of classes.
This may surprise readers used to optimizing convex problems in machine learning using gradient descent with a fixed step size and no line search (which converges linearly with strongly convex problems), or even online form of gradient descent. This is convenient when the objective function is costly to evaluate, for example consisting of a sum over a large training set. But the setting here is different: it is as if we had a single training instance. Hence, using a quadratically convergent method with a line search is far faster.
4 Inverse classification as optimization: logistic regression
Logistic regression corresponds to the case K = 2 of the softmax classifier. All the previous results apply, but in this case we can find x* in closed forn as given in theorem 4.2 Let us take k = 1 as the target class w.l.o.g. and define w = ag a1 and wy = b2 by given the softmax parameters {A, b}, or we can just think of {w, w as the weight vector and bias of the logistic regression model, where w points towards class 1. Then we have
(x( + x-up E 10,1)
(7a)
P2(x) = - (x)((x)
(7b)
(x) = llog (1 + c x=*++200
(7c)
V Ex; A) A(x x) + (1 P1 (x))
(7d)
V xx El x 2) = =AI+ pi (x) - -pi (x) wwT.
(7e)
Define the function o(a, 3): R4 x + (0, 1) as the unique root of the equation t = 1/(1 + exp (at + 8)) for a > 0 and B E TR. The next theorem shows @ is well defined
Theorem 4.1. Let > 0, B E IR and h(t) - 1/(1 + exp (at + B)) for E R. Then h has unique root 0* h,(h(()= 0, and 1x E 10,
Proof. This holds because 11(l)= 0 A3 E R, so h is strictly monotonically increasing, and h(0) < 0 and A(1) >0 0.
Theorem 4.2. The unique minimizee of E(x; (from eq. 2 2 is x* -1 ---iiw where pi (a. 3), a = == / 0 and B = w x + wo - a E R.
Proof. Since E' is strongly convex and continuously differentiable, x E DR is the unique solution of the
nonlincar system of D equations E((x*) = X(x* x + (1 (x w = 0 + x" = x - +1 )x*)) Hence W + wp w X + Wi- - (1 - pi (x || Since, from eq. 7, pr (x) = 1/(1 + exp (w" x + wn)).
'By "closed form" we in terms of the scalar function d(a, 8) (even though computing the latter requires iterative algorithm).
Thee function o(a,8) for was studied in Carreira-Perriidae & Williams, 2003 pp. 6), where arises in the context of finding the maximum of Gaussian mixture with components. that case there be one, two three roots depending on and B, so ø can be multivalued, unlike our case, where it univalued.
7

---

Published in Transactions on Machine Learning Research (03/2026)
substituting in it the previous expression yields pi 1/(1 + exp pi E (0,1) whose solution, from theorem is pi <( .).
+ 8)). This is scalar equation for exp (api
Theorem 4.2 shows that the problem of minimizing E in D dimensions is really problem in one dimension, and the solution x" lies along the ray emanating from X along w. Hence, to find the minimizer of eq. (2, we
compute a, 3, pi and x" using theorem [22 To compute pi = = 3). we have to solve a scalar equation. This can be done using a robustified version of Newton's 's method one variable (e.g. by falling back to a biscction step if the Newton step jumps out of the current root bracket, as in Vlllllyyorr & Marreira-Perpiiii
(2013) 3)).
Convergence to machine precision occurs in few iterations, in (1). The overall computational complexity is O(D), dominated by reading the data (x, w) and doing two vector-vector products (w"xx x and w w).
For D ranging from 10 to 10', the runtime ranges from microscconds to milliscconds. As shown in our experiments, this is far faster than running Newton's method in the D-dimensional space.
5 Experiments
Our experiments are very straightforward and agree well with the theory. In short, Newton's method consistently achieves the fastest runtime of any algorithm, by far, while reaching the highest precision possible. For logistic regression, the closed-form solution is even better. The appendix gives gives more details.
5.1 K-class softmax
We solve problems of the form 2 on datasots of different charactoristics: MNIST (D 784, K 10), of
handwritten digit images with grayscale pixel features (LeCun el. all 1998); RCVI (D 47236, K 51), of documents with TFIDF features (Lewis et all 2004); VGGFeat64 (D 8 192. K = 16). of neural net features from the last convolutional layer of a pre-trained VGG16 deop net (Simonvan & Zisserman, 2015) on a subset of 16 classes of the ImageNet dataset (Deng et all, 2009), where each image has been resized to 64x64 pixels; and Feat226 (D = 131 072, K = 16), like VGGFeat64 but using images of 256 256 to create the features. For each dataset we trained softmax classifier using scikit-learn (Pedregosa et al 2011).
We evaluated several well-known optimization methods, and for each we use the line search that we found worked best. For Newton's method, BFGS and L-BFGS use backtracking line search with initial step and backtracking factor p 0.8. For gradient descent (GD) and Polak-Ribière conjugate gradient (CG), we use more sophisticated line search that allows steps longer than and ensures the Wolfe conditions hold (algorithm 3.5 in Nocodal & Wright (2006)). All mothods were implemented by us in Matlab except for CG, which uses Carl Rasmussen's minimize... m very elficient implementation. For L-BFGS, we tried several values of its queue size and found m worked best in our datasets. Each method iterates until [| 10-8, up a maximum of 000 iterations (which only GD reaches, occasionally). The initial iterate was always the source instance Xy- = X.
For each dataset, we generated 50 instances of problem 2 each given by a source instance X, target class k and a value of A (see details in the appendix). Fig. shows a scatterplot of objective function value E(x*), number of iterations and runtime in seconds for each method on each problem instance. It is clear that Newton's method works better than any other method, by far (note the plots are in log scale). It takes around 10 itcrations converge and between and 100 ms runtime- a remarkable feat given that the problems are nonlinear and reach over 10a variables. Next best are CG and L-BFGS, which take about 10 times longer; and finally, GD, which is far slower. BFGS is only applicable in small- to medium-size problems because it stores a Hessian matrix approximation explicitly; in our problems this makes it very slow even if it does not require many iterations.
Fig, 2 shows the learning curves for one specific problem instance per dataset. Most informative are those for Exxx) - E(x') ) and [[x)(, which clearly show the asymptotic convergence rate of each method (note that while E must decrease monotonically at each iteration, the gradient norm need not). For lincarly convergent methods (all except Newton's) the iterates in a log-log plot should trace straight line of negative
8

---

Published in Transactions on Machine Learning Research (03/2026)
VGGFeat256
VGGFeat64
RCV1
MNIST
-1.2
-0.5
-14
-02
-0.4
-1
-1.6
Newton
Gradien
-0.2
0.6
-1.5
L-BFGS
-0.8
0
-2
CG
BFGS
-0.4
-1
-25
-2.2
1.5
1.5
3
1.5
log10 # #iterations)
1og10 (# #iterations)
1og (# (Hiterations)
10g10 (# (Hiteratios)
0.2
-1.2
0.5
-1.4
0.2
Newton
-0.
Gradient
-0.2
-0.6
-1.5
-1.8
L-BFGS
-0.8
-2
-2
CG
BFGS
-0.4
-1
2.5
1
-3
2
1og1a (time (s))
(time (s))
log10 (time (s))
log (time (s))
Figure 1: Performance of different optimization methods on a collection of 50 problem instances per dataset, in number of iterations (top) and runtime in seconds (below).
slope equal to the logarithm of the rate; for quadratically convergent methods (Newton's), they trace an exponential curve instead. This is clearly visible the ends of the curves. The last few iterates of Newton's 's method double the number of correct docimal digits at each itcration, and quickly reach the precision limit of the machine.
Figures 3 4 further investigate Newton's method. The histogram in fig. shows that the initial step (equal to 1) is accepted most times, and rarely are more than 5 trials needed. This confirms that a better line search that ensures the Wolfe conditions hold is unlikely to help much. Figure (left plot) uses the number of iterations as a proxy for "difficulty" the problem, by solving each problem for 100 values of As predicted by theorem 35 problems with X >> are easiest, followed by problems with < Figure A (right table) compares, when solving problem over a range of decreasing À values, whether to warm-start (i.e., initialize the next problem from the solution of the previous one) not (i.e., initialize always from x). Warm-start is about 5x faster and very few iterations are required for each À value. This makes it attractive to solve for a range of As and present the user an array of solutions of increasing target class probability (x(x* (A)).
5.2 Logistic regression
We created binary classification versions of the datasets used for the softmax (same training and test in- stances) by partitioning the classes into two groups and training a logistic regression to learn that. As expected, the closed-form form solution was far faster (about 100x) than Newton's method.
6 Conclusion
Inverse classification problems such counterfactual explanations and adversarial examples can be formu- lated optimization problems. We have theoretically characterized particular formulation (using the squared Euclidean distance) for two fundamental classificrs: logistic regression and softmax classifiers. The former admits a closed-form solution, while the latter can be solved extremely elficiently with Newton's method using a suitably reformulated Hessian. The fact that we can solve this so efficiently is due to the special form of the logistic regression and softmax classifiers, and to the formulation we use of the opti- mization problem. While other formulations are possible, their solution would not be as efficient as here. In our formulation, what is D-dimensional optimization problem (where D is the number of features)
9

---

Published in Transactions on Machine Learning Research (03/2026)
VGGFeat256
VGGFeat64
RCV1
MNIST
À = 0.015
0.01
0.01
0.01
(ps. po)
= (0.999, 1.28 . 10 *)) (0.141, 0.827)
[ps.po) = (0.999.1.22 10
(pio. pao)
(0.964, 1.55 10 12)
(pr.po) po)
(0.999, 6.49 10 10-9)
(3.15 1003000000000 0.963)
(2.31 10-3, 0.899)
(1.22 -1 0.999)
Newton
10'
Newton
10
Newton Gradient
Newton
Gradient L.BFGS
Gradient
Gradient
L-BFGS
L-BFGS CG
10
L-BFGS
kq 10!
CG
BFGS
BFGS
CG
CG
10
10
10
0.5
1.5
2
0
0.5
1.5
2
0.5
1,5
10 #iterations)
1og10 #iterations)
log1o # #iterations)
1og10 # #iterations)
Newton Gradieut L-BFGS
10'
Newton
10
Newton Gradient L-BFGS CG
Newton
Gradient
Gradient
L-BFGS
10
L-BPGS
10
CG
BFGS
BFGS
CG
CG
10
100
10
-0.5
0.5
-2
0
2
2.5
-1.5
log ttime (s))
log 10 (time (s))
log (time (s))
log (time (s))
100
10
10
100.
10.3
10
Newton
10
Newton
Newton
Gradlent
10.5
Newto
Gradient
10
Gradient
L-BGGS
Gradient
L-BFGS
L-BFGS
10" 10
BFGS
L-BFGS
107
BFGS
CG
CG
10 10
CG
CG
0.5
1.5
0.5
1.5
3
0.5
1.5
logio (iterations)
logıo # #itcrations)
logao #itcrations)
log #itcrations)
10
10
109
10
10
10.5
Newton
10
Newton
Newton Gradient L-BFGS
Gradient
10 5
Newton
Gradient
L-BFGS
Gradient
L-BFGS
10
BFGS
L-BFGS
10
BFGS
10:10
CG
CG
10
CG
CG
-0.5
1og (time (s))
0.5
-2
logi0 (time (s))
log (lime (s))
2.5
log (time (s))
2
-1.5
10
10
10
100
10'5
10-5
Newton
10.5%
10-5
Newton
Newton
Gradient
Newton
Gradient
10-10
L-FGSS
Gradient
10.10
BFGS
BPGS
10:10
L-FGS
Gradient
10-10
L-BFGS
BFGS
CG
10
CG
CG
CG
10
0.5
1.5
2
0.5
1.5
3
0.5
1.5
logio #iterations)
login ( #iterations)
log # #iterations)
log #iiteration)
10
Newton Gradient L-BEGS
10
10
Newton Gradient LFBGS
10
=
CG
1
Newton
1
C
1
Newzon
Gradien
Gradient
10
L.BGGS
10
L-BFOR
10
BFGS
10
BFGS
10
CG
15
-0.5
0.5 log (time (s))
0
0
2
2.5
-2 -1.5
log (time (s))
log (time (s))
log (time (s))
Figure 2: Learning curves for one problem instance per dataset (columns), indicated by its À value and class probabilities, encoded as (Pε)P)) = (at x) - (at x*). Rows 1 2, 3 4 and show E(xx), [|VE(xx)]] and Exxx) F(x*), respectively (where x* is estimated by the last iterate of Newton's method). Within each pair of rows, we show number of iterations (above) and runtime in seconds (below). All plots log-log.
10

---

Published in Transactions on Machine Learning Research (03/2026)
0.7
RCV1
0.6
VGG
VGGFeat64
Proportion
0.4
MNIST
0.3
0.2
0.1
5
7 8 9101112331411111711818
backtracking steps
Figure Histogram of the number of steps tried in the backtracking line scarch for Newton's method, for instances of different datasets.
14
12
M
login #iterations)
10
runtime (seconds)
Dataset
warm start
no warm start
ROVI
MNIST
0.021#0.003
0.093:10.015
4
VGGFeat256
VGGFeat264
1.460=00002
6.147=0.791
VGGFea164
VGGFeat64
0.079
0.296::0.014
MNIST
RCV1
1.351#00003
6.749+11.782
log1o
Figure 4: Left: number of iterations for Newton's method a function of İ (averaged, for each X, over the 50 problem instances of fig. [.. Right: total runtime (seconds) over the 100 values of X in the top plot with and without warm-start (average + stdev over the 50 problems).
can essentially be reduced to a K-dimensional optimization problem (where K the number of classes) for the softmax classifier, and to scalar problem for logistic regression. This important because K < D in most applications of interest. For both classifiers, can solve the optimization to practically machine precision and scale to feature vectors of over 10 dimensions and tens of classes with runtime under one second. This makes it suitable for real-time or interactive applications. Future work includes handling very large number of classes; constraints on the desired instance; and investigating other classifiers, distances and problem settings.
Code implementing the algorithms is available from the authors.
Acknowledgments
Work partially supported by NSF award IIS 2007147.
11

---

Published in Transactions on Machine Learning Research (03/2026)
References
Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani Srivastava, and Kai-Wei Chang, Generating natural language adversarial examples. In Proc. Conf. Empirical Methods in Natural Language Processing (EMNLP 2018), pp. 2890 2896, Brussels, Belgium, 2018.
L. Behera, M. Gopal, and S. Chaudhury. Inversion of RBF networks and applications to adaptive control of nonlinear systems. IEE Proc. Control Theory & Applications, 142(6):617 624, 1995.
Antonio Bella, Cèsar Ferri, José Hernández-Oralle and María José Ramírez- Quinttaa. Using negotiable features for prescription problems. Computing, 91:135-168, February 2011.
Stephen Boyd and Lieven Vandenberghe. Convez Optimization. Cambridge University Press, Cambridge, U.K., 2004.
Nicholas Carlini and David Wagner. Audio adversarial examples: Targeted attacks on speech-to-text. In IEEE Symposium on Security and Privacy (SP) Workshops, pp. 1 7, 2018.
Miguel Á. Parreira-Perpiñán and Suryabhan Singh Hada. Counterfactual explanations for oblique decision trees: Exact, efficient algorithms. In Proc. of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 1903-6911, Online, February 2-9 2021a.
Miguel Á. Parreira-Perpiiánn and Suryabhan Singh Hada. Counterfactual explanations for oblique decision trees: Exact, efficient algorithms. arXiv:2103. 01099, March 1 2021b.
Miguel Á. Perpiinn and Suryabhan Singh Hada. Very fast, approximale counterfactual explanations for decision forests. In Proc. of the 37th AAAI Conference on Artificial Intelligence (AAAT 2023), pp- 6935 6943, Washington, DC, February 14 2023a.
Miguel Á. Carreira-Perpiiáán and Suryabhan Singh Hada. Very fast, approximate counterfactual explanations for decision forests. EXXiv:2303.02885 March 2023b.
Miguel Á. Parriina and Weiran Wang. Distributed optimization of deeply nested systems. arXiv:1212.5921, December 24 2012.
Miguel Á. Carrefra-Perpiáan and Weiran Wang. Distributed optimization of deeply nested systems. In Samuel Kaski and Jukka Corander (eds.), Proc. of the 17th Inl. Conj. Artificial Intelligence and Stalistics (AISTATS 2014), pp. 10-19, Reykjavik, Tceland, April 22-25 2014.
Miguel A. Carreira- Carreira-Perpiiánn and Christopher K. I. Williams. On the number of modes of a Gaussian mixture. Tochnical Report EDI-INF-RE RR-0159, School of Informaties, University of Edinburgh, February 2003.
Hongge Chen, Huan Zhang, Si Si, Yang Li, Duane Boning, and Cho-Jui Hsieh. Robustness verification of troe-based models. In H. Wallach, H. Larochelle, A. Beygelzimer, F. A'Alc Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Syslems (NeurIPS), volume 32, pp. 12317 12328. MIT Press, Cambridge, MA, 2019.
Zhicheng Cui, Wenlin Chen, Yujie He, and Yixin Chen. Optimal action extraction for random forests and boosted trees. In Proc. of the 21st ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (SIGKDD 2015), pp. 179 188, Sydney, Australia, August 10 13 2015.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A largo-scale hicrarchi- cal image database. In Proc. of the 2009 IEEE Computer Sociely Conf. Computer Vision and Pattern Recognition (CVPR (0)) pp. 248 255, Miami, FL, June 20-26 2009.
Amit Dhurandhar, Pin-Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Garnett (eds.), Advances in Neurol Information Processing Systems (NeurIPS), volume 31, pp. $92-603 MIT Press, Cambridge, MA, 2018.
12

---

Published in Transactions on Machine Learning Research (03/2026)
Alexey Dosovitskiy and Thomas Brox. Inverting visual representations with convolutional networks. In Proc. of the 2016 IEEE Computer Sociely Conf. Computer Vision and Pallern. Recognilion (CVPR'16), Las Vegas, NV, June 26- -July 2016.
Samuel G. Finlayson, John D. Bowers, Joichi Ito, Jonathan L. Zittrain, Andrew L. Beam, and Isaac S. Kohane. Adversarial attacks on medical machine learning. Science, 363(64333:1188--2255 March 22 2019.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples.
In Proc. of the 3rd Int. Conf. Learning Representations (ICLR 2015), San Diego, CA, May 7-9 2015.
Tan J. Goodfellow, Patrick McDaniel, and Nicolas Papernot. Making machine learning robust against ad- versarial inputs. Comm. ACM, (1()):56 66, July 2018.
Suryabhan Singh Hada and Miguel Á. Carreira-Perpitáán Sampling the "inverse set" of neuron. In TEEE Int. Conf. Image Processing (ICIP 2021), pp. 3712-3716, Online, September 19-22 2021a.
Suryabhan Singh Hada and Miguel Á. Parreira-Perpiián. Exploring counterfactual explanations for classi- fication and regression trees. In ECML PKDD 3rd Int. Workshop and Tutorial on eXplainable Knowledge Discovery in Data Mining (XKDD 2021), pp. 489-504, 2021b.
D. A. Hoskins, J. N. Hwang, and J. Vagners. Iterative inversion of neural networks and its application to adaptive control. IEEE Trans. Neural Networks, 3(2):292-300 -012, March 1992.
Craig A. Jensen, Russell D. Rood, Robert J. Marks II, Mohamed A. El-Sharkawi, Jac- Mac-Byung Jung, Robert T. Miyamolo, Gregory M. Anderson, and Christian J. Eggen. Inversion of feedforward neural networks: Algorithms and applications. Proc. IEEE, 87(9):1536 1549, September 1999.
Alex Kantchelian, J. D. Tygar, and Anthony D. Joseph. Evasion and hardening of tree ensemble classifiers. Tn Maria-Florinn Balcan and Kilian Q. Weinberger (eds.), Proc. of the 39rd Int. Conf. Machine Learning (ICML 2016), pp. 2387 2396, New York, NY, June 19 24 2016.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual expla- nations for conscquential decisions. In Proc. of the 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS 2020), pp. 895 905, Online, August 26 28 2020.
J. Kindermann and A. Linden. Inversion of neural networks by gradient descent. Parallel Computing, 14(3): 277-286, August 1990.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to docu- ment recognition. Proc. IEEE, 86(11):2278-25 November 1998.
David D. Lewis, Yiming Yang, Tony G. Rose, and Fan Li. RCV1: A new benchmark collection for text categorization research. J. Machine Learning Research, 5:361-380 -37, April 2004.
Aravindh Mahendran and Andrea Vedaldi. Visualizing deep convolutional neural networks using natural pre-images. Inl. J. Compuler Vision, 120(3):233 2222,,3553,1111 December 2016.
David Martens and Foster Provost. Explaining data-driven document classifications. MIS Quarterly, 38(1): 73 73-99, March 2014.
Seyed-Mohsen Srosavi--ezzfolit Alhussein Fawzi, and Pascal Frossard. DeepFool: A simple and accurate method to fool deep neural networks. In Proc. of the 2016 IEFE Computer Sociely Conf. Computer Vision and Pattern Recognition (CVPR'16) pp. 2574 2582, Las Vegas, NV, June 26 July 1 2016.
Y. Nesterov. Introductory Leclures on Conver Optimization. A Basic Course. Number 87 in Applied Optimization. Springer-Verlag, 2004.
Anh Nguyen, Alexey Dosovitskiy, Jason Yosinski, Thomas Brox, and Jeff Clune. Synthesizing the preferred inputs for neurons in neural networks via deep generator networks. In D. D. Loo, M. Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems (NIPS), volume 29, pp. 3387-3395 MIT Press, Cambridge, MA, 2016.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Anh Nguyen, Jeff Chune, Yoshua Bengio, Alexey Dosovitskiy, and Jason Yosinski. Plug & play generative networks: Conditional iterative generation of images in latent space. In Proc. of the 2017 IEFE Com- puter Society Conf. Computer Vision and Pattern Recognition (CVPR 17), pp. 3510 3520, Honolulu, H1, July 21-26 2017.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series Operations Research and Financial Engineering. Springer-Verlage New York, second edition, 2006.
Axel Parmentier and Thibaut Vidal. Optimal counterfactual explanations in tree ensembles. In Marina Meila and Tong Zhang (eds.), Proc. of the 38th Int. Conf. Machine Learning (ICML 2021), pp. 8422 8431, Online, July 18 24 2021.
Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent. Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay. Scikit-learn: Machine learning in Python. J. Machine Learning Research, 12:2825 2830, October 2011. Available online at https://scikke http:://scikittleeen..oo learn.org
Chris Russell. Efficient search for diverse coherent explanations. In Proc. ACM Conf. Fairness, Accountabil- iby, and Transporency (FAT 2019), pp. 20-28, Atlanta, GA, January 29-31 2019.
Shubham Sharma, Jette Henderson, and Joydeep Ghosh. CERTIFAL: A common framework to provide explanations and analyse the fairness and robustness of black-box models. In Proc. AAAI/ACM Conference on AI, Ethics, and Society (AIES 2020), pp. 166-172, New York, NY, February 7-8 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proc. of the 3rd Tnt. Conf. Learning Representations (ICLR 2015), San Diego, CA, May 7-9 2015.
Karen Simonyan, Andrea. Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In Proc. of the 2nd Int. Conf. Learning Representations (ICLR 2014), BansI, Canada, April 14 14-166666 2014.
Christian Szegedy, Wojeiech Zaremba, Πya Sutskever, Joan Bruna, Dumitru Erhan, Tan Goodfellow and Rob Fergus. Intriguing properties of neural networks. In Proc. of the 2nd Int. Conf. Learning Representations (ICLR 2014), Banff, Canada, April 14-16 2014.
Bork Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proc. ACM Conf. Fairness, Accounlabilily, and Transpurency (FAT 2019), pp. 10-19 Atlanta, GA, January 29 99-31 2019.
Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by prototypes. In Nuria Oliver, Fernando Pérez-Crus Cruz, Stefan Kramer, Jesse Read, and José A. Lozano (eds.), Proc. of the 32nd Europeon Conf. Machine Learning (ECML 21), Bilbao, Spain, September 13 17 2021.
Max Vladymyrov and Miguel Á. Carreira-Perpinal Entropic alfinities: Properties and efficient numerical computation. In Sanjoy Dasgupta and David McAllester (eds.). Proc. of the 30th Int. Conf. Machine Learning (ICML 2013), pp. 477 485, Atlanta, GA, June 16 21 2013.
Sandra Wachter, Brent Mittclstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard J. Law & Technology, 31 31(2):8418877 Spring 2018.
James Wexler, Mahima. Pushkarna, Tolga Bolukbasi, Martin Wattenberg, Fernanda Viégas, and Jimbo Wilson. The What-lf Tool: Interactive probing of machine learning models. IEEE Trans. Visualization and Computer Graphics, 26(1):56-68 65, Jamuary 2020.
R. J. Williams. Inverting connectionist network mapping by backpropagation error. In Proc. 8th Annual Conf. Cognitive Science Sociely, pp. 859 880, Hillsdale, NJ, 1986. Lawrence Frlbaum.
14

---

Published in Transactions on Machine Learning Research (03/2026)
Qiang Yang. Jie Yin, Charles X. Ling, and Rong Pan. Extracting actionable knowledge from decision trees. IEFE Trons. Knowledge and Dala Engineering, 18(1):43 56, January 2006.
Matthew D. Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In Proc. 18th European Conf. Computer Vision (ECCV114), pp. 818- 18-833, Zürich, Switzerland, September 6-12 2014.
15

---

Published in Transactions on Machine Learning Research (03/2026)
A Datasets and experimental setup
We use the following 4 datasets (summarized in table D]:
MNIST
(LeCun et ale 1998) It consists of 28x28 grayscale images of handwritten digits of classes 0 to represented as feature veclor of pixel values in [0,1] of dimension D 784. There are 60000 training instances and 10000 test instances.
RCVI [ewis el. al, 2004) consists of newswire stories manually calegorized into K = 51 classes and made available by Reuters, Ltd. for research purposes. Each document is represented as vector of TFIDF features of dimension 47 236. There 15 564 training instances and 518 571 test instances.
VGGFeat64 Each instance corresponds to an image of 64 x64 pixels, categorized into K 16 object classes, a subset of man-made and natural objects from the ImageNet dataset (Deng et al., (200g). Each image is represented by a feature vector of dimension features from the last convolutional layer of a pre-trained VGG16 deep net (Simonvan & Zisserman, 2015) (on the subset of 16 classes). There are 16000 training instances and 3 200 lest instances.
192, corresponding to the neural net
VGGFeat256 Like VGGFeat64, but using images of 256 create a vector of D 131 072 features.
We created binary classification versions of the MNIST, RCVI and VGGFea1256 datasets for use with logistic regression. They have the same training and test instances and feature vectors and only differ in the class labels, which are regrouped from K into 2. For MNIST, we use even vs odd digits. For RCVI, we use classes 0-25 vs 26-51 51. For VGGFeat256, we use man-made objects (7 classes) vs natural objects (9 classes).
For each dataset we trained softmax classifier using scikit-learn (Pedregosa al 201 1). The training and test error are in table [I
In some experiments (e.g- in fig. I we use a collection of 50 inverse classification problem instances per dataset, each consisting of a triplet (x, A) in eq. (2). We generated them at random with the goal of having some diversity in the problem difficulty, as follows. For 40 of the problems, we picked X uniformly at random from the training set; we picked & as the class having lowest softmax probability for X (i.e., the 0.01 (which makes the minimizer achieve a
"farthest" class, having near-zero probability); and we softmax probability for class i above 0.95 so). For the remaining 10 problems, picked x uniformly random from the training set; we picked ht the class having the second largest softmax probability for x (i.e., the "closest" class); and we set A = 0.1 (which again makes the minimizer achieve a softmax probability for class i above 0.95 or so). For VGGFeat256 we set instead À = 0.006 and 0.08, respectively. In fig. ! we
used the 50 problems for each dataset but for each we kept the (x, k) part and varied À [10-4,10*
All our experiments were ran using Matlab in PC with an Intel Core i7 processor (8 cores) and 16 GB RAM.
Table Datasets and softmax classifiers.
Training set
Test set
Dataset
D
K
N
error (%)
N
error (%)
MNIST
784
10
60.000
6.14
10000
7.35
RCVI
47 236
51
15 15564
7.03
518571
14.52
VGGFeat64
192
16
16000
0.00
3000
6.54
VGGFeat256
131 072
16
160000
0.00
3200
3.07
MNIST (K -K=22
784
2
600000
15.60
10000
15.83
RCV1 (K = 2)
47 236
2
15564
4.23
518571
5.16
VGGFea1256 (K 2)
131 072
16000
0.00
30000
0.44
16

---

Published in Transactions on Machine Learning Research (03/2026)
B Looking at the digits of accuracy in the solution
As discussed in the main text, Newton's method converges quadratically while all other methods converge linearly (or superlinearly for BFGS). This is evident in fig. 2 where the E, E (or || curve is an exponential curve for Newton's method but a straight line for linearly convergent. methods. Table 2 shows this more dramatically by printing explicitly the value of Es - E so we can see the decimals accuracy achieved. It clear that, once near the minimizer, Newton's 's method enters an asymptotic regime where it converges quadratically, and the number of correct digits roughly doubles at each iteration, so reach machine precision in just few iterations. Linearly convergent methods require far many iterations to achieve the same accuracy.
Table 2: Numerical values of E(xx) - E(x") for the iterates h: = 1,2... for the RCV1 dataset example of fig. 2 Note that not all values of are shown. Blank elements mean the method already reached the stopping criterion.
k
Newton
Gradient descent
L-BFGS
Conjugate gradient
1118619041837028210
11.8610041337025210
837722201
9.9872386648974036
9.4302539222109605
1L.57995733313440477
7.8983750132222000
9.0806667584076000
8.7110587612082770
10.7583369748493361
7.66573935333552222
4
8.83059412589710611
8.38813301 1333666688
9.93496688191421208
7.16571554746015588
5
6.04174786259925387
8.16622166366068226
8.42167840421662258
2.6591874389232228
7.99322275666377588
188988728977689721
1.922728122070522
1.28906800693334155
7.9712244558801926
3.8149863066661977
6,4034389566166801
0.68532179558 7955710699
7867888933877772281
222632288220335566
6.0762833180276770
0.54247196111221
7.5005660590871734
8. ..0888003708399339
5.88144116331701109
10
0.0760466660933638
7.3211346697355822
7.886071 4868005122
5.6633127311508114
11
7.241078135565111
7.48509160490605888
5.310553660699951668
12
0.0031375 92229656
0.00311355192229666
7.09779115521472728
7. 7.24308447633004373
4.99458115433849001
13
0.0003850423026792
7.0388485056588061
6.72456775626555566
L.8097803381394512
14
6.863100006695466777
6.61275804066887594
A.6306326737056199
15
0.0000000340853227
6. 1.7097697379199944
6. 8.40908471622466229
4.22683464156846688
16
0.00000000000002218
6.5381 468877747777
6. 6.08365757962181224
4. 4.0361704289760222
17
0.00000000000000000
6.4878228440302725
5.5272241498443381
2. 2.3805364944786669
5.36366368444224331
11898091938913999
0.06297010042266668
100
0.00034440036460872
0.000000001 2869300
0.000000000096600888
145
0.00004327822561998
0.000000000000003225
0.00000000000110827
160
0.00002470039692411
0.000000000000016633
165
0.00002071291196613
500
0.00000002311446667
1000
0.0000000000000591133
1174
0.00000000000003599
17

---

Published in Transactions on Machine Learning Research (03/2026)
C
Type of line search
We consider 3 types of line search (l.s.) to determine the step size given search direction Sy IR
Wolfe This is a L.s. that finds step size that satisfies the strong Wolfe conditions:
Exx: + agsk) - Exxx) + cr (E(x)) "ss ("sufficient decrease in objective function"
VE(x + a Sk I 02 (x(x)) ("flatter gradient")
where 0 < c < 02 < 1. The l.s. based on algorithm 3.5 of Nocedal Wright (2006) (using C1 10 and c2 = 0.9). This is sophisticated L.s. requiring several evaluations of E to approximate it via cubic interpolant and procedure to zoom in and out of the scarch interval.
Backtracking This satisfies only that the step decreases E. It is much simpler and faster than the previous 1s., since all does is, starting with og =1, 1, multiply on by a constant factor p E (0,1) until step size found such that E(x; (gsa)) E(xx). We used p 0.8.
Constant We use a constant step size og = 1/L. where I. is the Lipschitz constant for E. This is the simplest and fastest Lss,, since no step sizes are searched. With gradient descent, it ensures that E decreases at each iteration and that we converge linearly to x In the example of fig. 5 4.511 so ag 0.221. We use it only with gradient descent, since for other methods it is difficult find a constant step size that is guaranteed to decrease E.
Fig. 5 compares the line searches for gradient descent (sk = - Exxx)). Clearly, gradient descent is best with a L.s. that ensures the Wolfe conditions hold; convergod within 200 itcrations while the other two did not reach the desired accuracy in 000 iterations. The extra time spent in the L.s. compensates by reducing drastically the number of iterations. One reason why this happens is that the value of the step size ag vary significantly across iterations.
Fig. d 7 compare the line searches for Newton's method (sx = - In terms of the number of iterations required to reach the desired accuracy, the Wolfe I.s. is consistently better than backtracking but by a minimal margin, it just saves a few iterations (1 to typically). Note that, from fig, G (see also the main text), Newton's method takes usually less than 10 converge, rarely reaching 14, so there very little room to improve that. In runtime, the Wolfe I.s. is around twice slower than backtracking (1.5-5x slower depending on the case), and never faster than backtracking. This is consequence of the Wolfe l.s. taking more time per ileration, particularly given that each backtracking l.s. tries very few steps before succeeding (see fig. B). very often just one. Although the precise runtimes will depend on the implementation of the Wolfe I.s. (we used Matlab), it is clear that backtracking is likely faster and certainly simpler. Also, a good 1.s. for Newton's method must ensure that slep sizes of are used once near enough the minimizer to ensure quadratic convergence.
18

---

Published in Transactions on Machine Learning Research (03/2026)
Exxx)
E(xx) E(xx)
10
Wolfe cond.
Wolfe cond. backtracking
10
backtracking
100
1
constant
constant
1
104
10
Wolfe cond
10.6
backtracking
10.4
constant
0
3
2
2
3
logio (#iteration))
log (iiteration)
log (Hiteration))
10
10
100
10
10
10
10
Wolfe cond.
Wolfe cond.
Wolfe cond.
backttacking
backtracking
10
backtracking
10
constant
constant
constant
-2
-2
2
-2
-1
(time (s))
log10 (time (s))
log10 (time (s))
Figure 5: Types of line search in gradient descent: satisfying the Wolfe conditions, backtracking and using constant step size 1/L (where L is the Lipschitz constant of the objective function E). The problem uses source instance from the VGGFeat256 dataset with À 10-3, In each column we plot E(xx), | [Vx((x)] and F(xx)~ - Exx*) (where x" was estimated using Newton's method), for each iterate k = 1,2, Row 1 shows the number iterations in the X axis and row the runtime (s). Gradient ceecent was run with each line search until either [Exx)) < 10 or 000 iterations were reached.
number of iterations
runtime (s), log plot
15
-0.5
RCV1
RCV1
-1
VGGFeat256
x
VGGFcat256
Wolfe l.s.
VGGFcat64
Wolfe L.s.
-1.5
VGGFea164
10
MNIST
MNIST
-2
x
X
-2.5
g
-3
5+
5
10
15
-3
-2
-1
backtracking I.s.
backtracking l.s.
Figure 6: Types of line search in Newton's method: satislying the Wolle conditions and backtracking. We plot the number of iterations and runtime (s) over collection of 50 problem instances for each of 4 datasets (these are the same problems in fig. D.
19

---

Published in Transactions on Machine Learning Research (03/2026)
VGGFeat256
VGGFeat64
RCV1
MNIST
À = 0.015
0.01
0.01
0.01
(ps.po) pu) = (0.999, 1.28 10 *))
(ps. ) = (0.999. 1.22 10 9)
(p1a. pro)
(0.964, 98.4984111.. 1.55 10 12)
(pr,po) )
(0.999, 6.49 10 10-9) 9)
(0.141, 0.827)
(3.15 10-8,00000000 0.963)
(2.31 10 0.899)
(1.22 10 0.999)
Backtracking Wolfe
10'
Backtracking Wolfe
10
Backtracking Wolfe
Backtracking
Wolfe
10
1o
100
10
10
0.4
0.8
0.5 logio (# #iterations)
1o #iterations)
log10 #iterations)
log1o # #iterations)
- Backtracking Wolfe
Backtracking Wolfe
Backtracking Wolfe
Backtracking Wolfe
10
10'
109
10
10
-0.6
1o (time (s))
log (time
(s)
log (time (s))
log (time (time (s))
10
10
100
10
|| E|]
10
10.5
5
10
Racktracking Wolfe
10"10
Racktracking Wolfe
Backtracking Wolfe
Backtracking Wolfe
10
10
10:10
10-10
0,5
0.2
0.4
0.6
0.8
0,5
0.5
logio #itcrations)
logno #itcraaiios)
logao #iterations)
log Dgiittitteattons
0
10
10
10
[VE]
10.5
10.5
1
1
Backtracking Wolfe
10
Backtracking Wolfe
Backtracking Wolfe
Backtracking Wolfe
10:10
10
10
.088
-0.7
-.6
2.3 -22 21
2 -1.9
0,7
-.6
0055
-04
2.7
2.6
225
-44
2.3
login (time (s))
log (time (s))
log (time (s))
log (time (s))
100
10
10
100
10.5
1
10.5
10.5
10
Backtracking
Backtracking Wolfe
10-10
Backtracking Wolfe
Backtracking Wolfe
10-10
Wolfe
15
10
0.2
0.4
0.8
0.5
0.5
logio #iterations)
1og # itteaaioos)
logio #iterations)
logio (P8io(#tenm (#iteration)
109
10
109
10
1
1
10.5
1
10
Backtracking Wolfe
Backtracking
10
Backtracking Wolfe
Backtracking
10
10
10
Wolfe
Wolfe
-0.8
-0.7 -0.6
2.7
-2.6
-2.5
-244
-2.3
-07
-066
-0.5
-0.4
-2.5 log (time (s))
.266
-24
-2.3
log (Line (s))
log
(Lime (8))
log (time (s))
Figure 7: Types of line search in Newton's method: satisfying the Wolfe conditions and backtracking, learning curves for one problem instance per dataset (columns), as in fig. 2
20

---

Published in Transactions on Machine Learning Research (03/2026)
D MNIST with 100 classes
We show another experiment using a large number of classes based on MNIST. In the original MNIST dataset, we have 10 digit classes (0 to 9) and each image is of 28. We can create a "double-digit" image by concatenating (side by side) two MNIST images, of classes i and j, to generate an image of 28x56 of class ij (say, a digit of class 6 and digit of class 4 generate a digit of class 64). Thus we generate an "MNIST-100" dataset where the instance dimensionality D 1 568 and the number of classes K 100 (00 to 99). We constructed training set of N 60k double-digit. images by creating 600 images for each class, each image being the concatenation of two random training set images of the corresponding class: likewise, created test set of 10k double-digit images. We trained a softmax classifier on the training set, which achieved 1.92% and 22.12% training and test error, respectively (this is likely overfitting, but it is fine for our purposes setting up an inverse classification problem).
This way, we create a harder inverse classification problem, because we have more feature dimensions, many more classes and hence many more parameters, which increases the computation for each method. But it also makes the Hessian more ill-conditioned (less round), since from theorem 33 the Hessian has eigenvalues greater equal than À and the rest (D K + 1) equal to A.
Fig. S shows the learning curves for a source instance of each dataset. Note that Newton's method barely needs more iterations to solve the MNIST-100 problem than to solve the MNIST one (around 10 in both cases) while all the other methods take twice as many iterations as before or more. The only exception is BFGS, which now takes fewer iterations than before; this makes sense, since after Newton's method is the method that most uses second-order information. In terms of runtime, Newton's method again the fastest by far, with bigger gain than in MNIST. BFGS becomes the slowest method because of its costly matrix-vector multiplications with D D matrix.
21

---

Published in Transactions on Machine Learning Research (03/2026)
MNIST: X 0.01, (Pr.po) (0.999, 6.49
10 10-9) (4.22
10 ..0.99)
Exxs)
[
E(x:) E(xx)
100
Newton
100
Gradient
100
L-BFGS
10.3
Newton
10
Newton
BFGS
Gradient
Gradient
CG
L-BFGS
10
L-BFGS
10-
BFGS
BFGS
1
CG
10
15
0.5
1.5
0.5
1.5
0.5
1.5
log (ol (#iteration))
logio (ootteeatiions
logio (iterations)
10
Newton
10
Gradient
10
L-BEGS
10.5
10.3
Nevton
Newton
BFGS
Gradiont
Gradient
CG
T-BFGS
10
L-BFGS
-
BPGS
BPGS
2
DG
10
CG
-2.5
-1.5 log10 (Lime (s))
-2
-2.5
-2
-1.5
-1
-2.5
-2
-1.5
-1
log (time (s))
log10 (time (s))
MNIST-100: À 0.215, (P07. P11) = (0.999, 9.98 x 10 10-14) + (0.014 x 10-4, .0.903)
E(x))
V E (xx) II
E(x;) E(x*)
Newton
100
10
Gradient
L-BFGS
10-3
Newton
10
Newton
BFGS
Gradient
Gradient
CG
1
L-BFGS
10-10 10
L-BFGS
-
BEGS
BFGS
CG
CG
10 10-15
0
0.5
1.5
2
0.5
1.5
0.5
1.5
2
log ( #iterations)
logio #iterations)
logio ( (#iterations)
Newton
100
00
Gradient
L-BFGS
3
10-5
Newton
Newton
BFGS
Gradient
Gradicut
CG
10'
BFGS
10-10
L-BRGS
-0
BFGS
BFGS
CG
Ca
10-15
-2
-1.5
-1
0.5
-2
-1.5
-1
-0.5
-2
-1.5
-1
-0.5
l (s))
logio (time (s))
log (time (s))
Figure 8: Learning curves in problem instance from the MNIST (top) and MNIST-100 (bottom) datasets. In each column we plot E(xx), ||VE(xx)) and E(x+) E(x") (where x" was estimated using Newton's method), for each iterate & = 1, 2,... For each dataset, row 1 shows the number of iterations in the X axis and row 2 the runtime (s).
22


Reviews:
[{"review_id": "JO6Z7x1ZLP", "reviewer": "Reviewer_CzjD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper the authors propose inverse classification as an optimization problem. The authors propose an objective for the inverse classification problem. The authors show theoretically 1. the convergence for a softmax classifier, 2. the close form solution for the logistic regression. Experimentally, the authors show on multiple datasets that the runtime is low.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper is well supported by theoretical evidence.", "audience_yn": "Yes", "audience_explanation": "The concept of inverse classification itself is interesting.", "requested_changes": "- The name inverse classification is a bit confusing. In fact, the optimization problem is not finding x given y and f right. It's finding other x given an initial x, y, and f. \n- The current formulation (2) itself lacks practical motivation. It is unclear to me what is the motivation of putting a L2 distance bound between the target input and the source input in real world scenarios within an optimization objective. Note that even for traditional adversarial example, the L_infty ball is more commonly used compared to the L_2 ball. Therefore, the authors should add examples on why such input space L_2 similarity is important for practical use cases.\n- Similar problem has been studied in adversarial robustness community and people have been using optimization methods such as BFGS, GD, Newton's Method to perform targeted adversarial attack. Convergence on such attacks has also been studied in a lot of prior works, on more generalized classifier. Therefore, the contribution seems a bit limited.\n- The scope of experiments is also limited. It's hard to tell the practical motivation of using these TFIDF features of images. While I think the general idea of inverse classification is a good one, it needs real world data and use cases to justify its motivation of being practical.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Uotag11pPG", "reviewer": "Reviewer_ySbN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies inverse classification for fixed logistic and softmax models. For softmax classifiers, the paper demonstrates that the Hessian has a structure that enables extremely efficient Newton steps via a K × K system. For logistic regression, the problem reduces to solving a single scalar equation, yielding fast solutions. Experiments on various datasets (MNIST, RCV1, VGG) demonstrate speed advantages over gradient-based and Newton methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical claims are supported by mathematical derivations that appear to be correct and justify the method. The experiments are extensive and consistent with the theoretical insights. The claims focus on optimization efficiency, and the experimental evidence supports these claims.", "audience_yn": "Yes", "audience_explanation": "The work will be of interest to researchers in optimization for explainability, adversarial examples, and counterfactuals, as well as those developing efficient proximal or Newton-type solvers. The scope is quite narrow, but the paper is well crafted, and its contributions are highly relevant.", "requested_changes": "* As a reader not extremely familiar with the literature on proximal operators, I am unable to directly identify which parts of the mathematical derivations are new and which ones are well-known in this literature. Therefore, I think the paper could be better anchored in the global optimization literature to highlight connections and differences.\n* I would appreciate a few discussions on the application side of the problem, what solutions the inverse optimization problem (counterfactual explanations) produces, and what their main characteristics are. This will allow the reader to better position the paper in terms of direct application use.", "broader_impact_concerns": "No major concerns. The paper touches on adversarial examples and counterfactuals. A brief note could emphasize dual-use considerations (interpretability vs. adversarial use), but no deeper ethical issues arise.", "additional_comments": "The paper is clear, rigorous, and well-organized. The contribution is valuable, and the experimentations are sound. I think this is a good paper for TMLR.", "extra_scores": {}, "extra_text": {}}, {"review_id": "EOxyjKLMqJ", "reviewer": "Reviewer_TYP4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Inspired by the growing interest in a class of optimization problems known as “inverse classification” (e.g., counterfactual explanations and adversarial examples), the authors investigated the speed of obtaining solutions for these problems in real-time or interactive scenarios.\n\nSpecifically, the authors theoretically examined how to solve these optimization problems efficiently for two commonly used classifiers: logistic regression and SoftMax classification. They show that, in the logistic regression setting, optimization for inverse classification problems can be solved in closed form. For SoftMax classification, although a closed-form solution is not available, the authors show that the problem can be solved efficiently through an iterative approach using Newton’s method combined with a suitably reformulated Hessian.\n\nThe paper concludes with experimental results across multiple datasets, providing empirical support for the theoretical findings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "To the best of the reviewer's knowledge, the claims made in the submission are accurate, convincing, and well-supported. The theoretical arguments appear credible, and the empirical results provided support the theoretical claims.", "audience_yn": "Yes", "audience_explanation": "The reviewer is convinced some individuals in the TMLR's audience would be interested in knowing the findings of this paper.", "requested_changes": "The reviewer is curious whether the problem addressed in this paper can be empirically extended to any dataset, particularly in the K-class SoftMax setting. If not, the authors are encouraged to include in the revised version more information about the datasets used and any reasons the approach may fail on others.\n\nSecondly, the authors are encouraged to extend their experiments to the CIFAR-10 and/or SVHN datasets.", "broader_impact_concerns": "The paper does not pose any broader ethical concern.", "additional_comments": "Read the requested changes above.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)